Лекция 1. Динамические массивы

1. Понятие динамических данных

В лекции 2 прошлого семестра мы рассматривали понятие времени жизни (существования) данных. Время жизни данного — это промежуток времени, в течение которого данное распределено в памяти.

По времени жизни имена делятся на статические (существуют все время выполнения программы), автоматические (существуют во время выполнения функции, в которой описаны), динамические (получают место в памяти с помощью операторов динамического распределения памяти).

К статическим данным относятся:

• глобальные данные, т.е. данные, описанные вне функций;

• данные, объявленные внутри функции с помощью, ключевого слова static; эти данные доступны только функции, в которой описаны, но существуют (занимают память) во время выполнения всей программы.

Статические локальные данные часто используются программами управления ресурсами - например, для подсчета числа обращений к программе, пример приведен в лекции 2 прошлого семестра.

Статические данные распределяются в памяти на этапе компиляции, это распределение не меняется все время выполнения программы. Они хранятся в специальной области памяти, которая называется статической памятью или статическим сегментом памяти.

Глобальные данные доступны в любой точке файла, в котором они объявлены, от места объявления до конца файла. Для расширения области действия глобальных переменных (на часть файла от начала до места объявления или на другой файл) используется инструкция extern.

К автоматическим данным относятся:

• локальные данные (т. е. данные функций), не объявленные static;

• данные типа register, которые мы не будем рассматривать в нашем курсе.

Автоматические данные распределяются в памяти на этапе выполнения программы (при каждом вызове функции, в которой они описаны) и освобождают память при завершении работы функции.

Автоматические данные располагаются в специальной области памяти — стеке функций, за исключением данных, описанных как register; которые хранятся во внутренних регистрах процессора.

Автоматические данные могут использоваться только внутри функции, в которой они описаны.

Динамические данные распределяются и уничтожаются в памяти на этапе выполнения программы с помощью специальных команд.

При работе с динамическими данными объявляются не сами данные, а начальные адреса — указатели — области памяти, где они хранятся. Время жизни и область действия указателей определяется как для обычных (статических или автоматических) данных.

Динамические данные хранятся в специальной области памяти, которая называется динамической памятью или кучей (англ. heap).

Динамическое распределение памяти используется, когда статической памяти и стека подпрограмм не хватает для решения задачи; когда объем требуемой памяти (например, число элементов массива) неизвестен до выполнения программы (вводится или вычисляется); когда характер задачи требует динамического распределения (данные поступают порциями в процессе выполнения программы, например, в режиме реального времени).

Так как работа с динамическими данными невозможна бех использования указателей, далее рассмотрим указатели в Си. Этот материал частично рассматривался в лекции 1 прошлого семестра.

2. Указатели в Си

Указатель - это специальная переменная, которая содержит адрес другой переменной.

Основные операции для работы с указателями (см., также лекцию 1 прошлого семестра):
* — взятие содержимого по адресу (*i - содержимое данного с адресом i)
& — взятие адреса (&a - адрес данного а).

При описании указателя задается тип значения, на которое он указывает. Описание имеет вид:

тип *имя_указателя;

Можно интерпретировать смысл этой конструкции так:: объявляется переменная, содержимое которой имеет данный тип.

Пример: int *i, j, *pointj;

j -переменная целого типа; i, pointj - указатели на значения целого типа.

При описании указателей возможна их инициализация. Пример:

int v1, *pointv1=&v1, *p=(int*)200;

Здесь указателю pointv1 задается начальное значение, равное адресу переменной v1, а указателю р - значение константы 200, приведенное к типу int*, т. е. адрес двухсотой от начала рассматриваемой области памяти ячейки типа int.

Как данные любого типа, указатели могут быть переменными или константами. Указателями-константами, например, являются адреса переменных, имена массивов, явные константы (например, (int*)200), а также константа NULL (нулевой или несуществующий адрес).

При работе с указателями-константами надо помнить следующее:

1. нельзя брать содержимое от константы без приведения типа; запись *200 является некорректной в отличие от *(int*)200

2. нельзя брать адрес константы (например, некорректна запись &200), в Си адрес константы считается недоступным;

3. нельзя определять адрес выражения.

Размер памяти, отводимой под указатель, зависит от используемого компьютера и модели памяти.

Кроме операции *, к указателям применимы операции сравнения (<, <=, >, >=, ==, !=), присваивания, арифметические операции сложения, вычитания, инкремента и декремента. Справа от операции присваивания должен стоять указатель того же типа, что и слева (от операции присваивания), или указатель NULL. Сравнивать можно указатели одного типа (или указатель произвольного типа с NULL).

Нельзя суммировать (вычитать) указатели, можно только прибавлять к ним (вычитать из них) целую величину. При этом результат операции зависит не только от значения операндов, но и от типа, с которым связан указатель. Если объявление указателя р имеет вид тип *р, то в результате оператора р=р+k, где k - некоторое целое значение, р увеличится на k*sizeof (тип).

Пример. short *p; long int pp;...
p++; /*p увеличилось на 2*/

pp++; /*pp увеличилось на 4*/

3. Связь массивов с указателями в Си

Одномерные массивы

Имя одномерного массива является указателем-константой, равной адресу начала массива, т. е. адресу элемента с индексом 0 (первого элемента).

Рассмотрим объявление некоторого одномерного массива, для определенности int a[10]; тогда обозначение &a[0] эквивалентно a, a[0] эквивалентно *a, &a[i] эквивалентно a+i (i=0,1,...9), a[i] эквивалентно *(a+i).

Двумерные массивы

Имя двумерного массива является указателем-константой на начало (элемент с индексом 0) массива указателей-констант, i-й элемент этого массива - указатель -константа на начало (элемент с индексом 0) i-й строки двумерного массива.

Так, например, с массивом int b[5][8] связан массив указателей-констант b[0], b[1],...,b[4]; b[ i ] - указатель на начало i-й строки, т. е. на элемент b[ i ][0], i=0,1,...,4; вышесказанное поясняется схемой:

Элемент массива b[i][j] можно также обозначить *(b[i]+j) или *(*(b+i)+j); это все равноправные обозначения. &b[i][j], b[i]+j, *(b+i)+j - также равноправные обозначения адреса элемента массива b[i][j].

Для любого из трех обозначений элемента двумерного массива программа в кодах получается практически одинаковой по производительности, хотя при использовании арифметики указателей вместо квадратных скобок несколько более короткой [3]. Хороший стиль программирования предполагает употребление в пределах одной программы одного (из трех) обозначений.

4. Функции Си для распределения и освобождения памяти

Прототипы рассматриваемых функций находятся в заголовочном файле <stdlib.h>.

Функция malloc¹ имеет прототип:

void *malloc(size_t² size);

Функция malloc возвращает указатель на первый байт области памяти размером size (в байтах), которая была выделена из кучи. Если нет достаточного объема памяти, возвращается NULL.

Функция calloc³ имеет прототип:

void *calloc(size_t num, size_t size);

Функция calloc выделяет память для хранения num значений, каждое длиной size байт. Каждое значение инициализируется нулем. Если нет достаточного объема памяти, возвращается NULL.

Функция realloc⁴ имеет прототип:

void *realloc(void *ptr, size_t newsize)

Функция realloc изменяет величину выделенной памяти, на которую указывает ptr, на новую величину, задаваемую параметром newsize. Величина newsize задается в байтах и может быть больше или меньше оригинала. Возвращается указатель на блок памяти, поскольку может возникнуть необходимость переместить блок при возрастании его размера. В таком случае содержимое старого блока копируется в новый блок и информация не теряется. Если свободной памяти недостаточно для выделения в куче блока размером newsize, то возвращается NULL.

Функция free⁵ имеет прототип:

void free( void * ptr );

Функция free возвращает в кучу блок памяти, на который указывает ptr. Этот блок ранее должен быть выделен с помощью вызова malloc, calloc или realloc.

Как Вы помните, основной трудностью работы со статическими массивами является обязательность указания количества их элементов при объявлении. В любом алгоритмическом языке, требующим компиляции (в частности, в Си, Паскале, Фортране), границами индексов массива при описании могут быть только константы. Если длина массива по условию задачи не известна, то она берется с запасом, то есть рассматривается максимально возможное число элементов массива. Использование динамических массивов позволяет сначала ввести число элементов массива, а потом выделить под массив требуемое количество ячеек памяти, как показано в следующих примерах.

Пример 1. Работа с динамическим одномерным массивом.

#include <iostream.h>