Динамические массивы

Лекция 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 (нулевой или несуществующий адрес). При работе с указателями-константами надо помнить следующее: *0 нельзя брать содержимое от константы без приведения типа; запись *200 является некорректной в отличие от *(int*)200 *1 нельзя брать адрес константы (например, некорректна запись &200), в Си адрес константы считается недоступным; *2 нельзя определять адрес выражения. Размер памяти, отводимой под указатель, зависит от используемого компьютера и модели памяти. Кроме операции *, к указателям применимы операции сравнения (<, <=, >, >=, ==, !=), присваивания, арифметические операции сложения, вычитания, инкремента и декремента. Справа от операции присваивания должен стоять указатель того же типа, что и слева (от операции присваивания), или указатель 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 b[0] b[0][0] b[0][1] . . . b[0][7] b[1] b[1][0] b[1][1] . . . b[1][7] b[2] b[2][0] b[2][1] . . . b[2][7] b[3] b[3][0] b[3][1] . . . b[3][7] b[4] b[4][0] b[4][1] . . . b[4][7] Элемент массива b[i][j] можно также обозначить *(b[i]+j) или *(*(b+i)+j); это все равноправные обозначения. &b[i][j], b[i]+j, *(b+i)+j - также равноправные обозначения адреса элемента массива b[i][j]. Для любого из трех обозначений элемента двумерного массива программа в кодах получается практически одинаковой по производительности, хотя при использовании арифметики указателей вместо квадратных скобок несколько более короткой [3]. Хороший стиль программирования предполагает употребление в пределах одной программы одного (из трех) обозначений. 4. Функции Си для распределения и освобождения памяти Прототипы рассматриваемых функций находятся в заголовочном файле . Функция malloc1 имеет прототип: void *malloc(size_t2 size); Функция malloc возвращает указатель на первый байт области памяти размером size (в байтах), которая была выделена из кучи. Если нет достаточного объема памяти, возвращается NULL. Функция calloc3 имеет прототип: void *calloc(size_t num, size_t size); Функция calloc выделяет память для хранения num значений, каждое длиной size байт. Каждое значение инициализируется нулем. Если нет достаточного объема памяти, возвращается NULL. Функция realloc4 имеет прототип: void *realloc(void *ptr, size_t newsize) Функция realloc изменяет величину выделенной памяти, на которую указывает ptr, на новую величину, задаваемую параметром newsize. Величина newsize задается в байтах и может быть больше или меньше оригинала. Возвращается указатель на блок памяти, поскольку может возникнуть необходимость переместить блок при возрастании его размера. В таком случае содержимое старого блока копируется в новый блок и информация не теряется. Если свободной памяти недостаточно для выделения в куче блока размером newsize, то возвращается NULL. Функция free5 имеет прототип: void free( void * ptr ); Функция free возвращает в кучу блок памяти, на который указывает ptr. Этот блок ранее должен быть выделен с помощью вызова malloc, calloc или realloc. Как Вы помните, основной трудностью работы со статическими массивами является обязательность указания количества их элементов при объявлении. В любом алгоритмическом языке, требующим компиляции (в частности, в Си, Паскале, Фортране), границами индексов массива при описании могут быть только константы. Если длина массива по условию задачи не известна, то она берется с запасом, то есть рассматривается максимально возможное число элементов массива. Использование динамических массивов позволяет сначала ввести число элементов массива, а потом выделить под массив требуемое количество ячеек памяти, как показано в следующих примерах. Пример 1. Работа с динамическим одномерным массивом. #include #include #include void main() { int *a, n, i;// a – указатель на одномерный массив, //n – число элементов массива, i-счетчик элементов массива. cout<<"Input the number of elements\n";//приглашение к вводу n cin>>n; // ввод числа элементов массива n a=(int*)malloc(n*sizeof(int)); // выше - распределение памяти под динамический массив cout<<"Input elements\n"; //приглашение к вводу массива for (i=0;i>a[i];// в цикле вводится массив // далее каждый элемент массива заменяется своим квадратом for (i=0;i #include #include void main() { int **a, n,m, i,j; //a-указатель на массив указателей на строки матрицы //n-число строк, m-число столбцов; cout<<"Input n,m\n";//приглашение к вводу n и m cin>>n>>m;// ввод n и m a=(int**)malloc(n*sizeof(int*)); //распределение памяти под // массив указателей на строки матрицы cout<<"Input matrix\n";//приглашение к вводу матрицы for (i=0;i>a[i][j];//*(*(a+i)+j) }//ввод закончен for (i=0;i #include void main() {int *a, n, i; cout<<"Input the number of elements\n"; cin>>n; a=new int[n]; //распред-ие памяти под динамич. массив cout<<"Input elements\n"; for (i=0;i>a[i];//*(a+i) for (i=0;i #include void main() { int **a, n,m, i,j; cout<<"Input n,m\n"; cin>>n>>m; a=new int*[n]; cout<<"Input matrix\n"; for (i=0;i>a[i][j];//*(*(a+i)+j) } for (i=0;i #include float sum(float **a, int n, int m); void main() { float **a; int n,m, i,j; cout<<"Input n,m"<>n>>m; a=new float*[n]; for (i=0;i>a[i][j]; } cout<<"sum="<> mat[i][j]; } cout << endl; } return mat; } Вызов фунции input будет осуществляться, например, так: float **A, **B; A = input(3, 5); B = input(7, 3); Кроме того, имеет смысл написать функцию дя освобождения памяти из-под матрицы: void delMat(float** mat, int n) { for (int i = 0; i < n; i++) { delete[] mat[i]; } delete[] mat; }