Лекция 3. Динамические массивы (Электронные лекции)

Лекция 3. Динамические массивы1. Понятие динамических данныхВ лекции 2 мы рассматривали понятие времени жизни (существования) данных. Время жизни данного — это промежуток времени,в течение которого данное распределено в памяти.По времени жизни имена делятся на статические (существуютвсе время выполнения программы), автоматические (существуют вовремя выполнения функции, в которой описаны), динамические (получают место в памяти с помощью операторов динамического распределения памяти).К статическим данным относятся:глобальные данные, т.е. данные, описанные вне функций;данные, объявленные внутри функции с помощью, ключевого словаstatic; эти данные доступны только функции, в которой описаны, носуществуют (занимают память) во время выполнения всей программы.Статические локальные данные часто используются программами управления ресурсами - например, для подсчета числа обращенийк программе, пример приведен в лекции 2.Статические данные распределяются в памяти на этапе компиляции, это распределение не меняется все время выполнения программы.

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

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

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

Этот материал частично рассматривался ранее в лекции 1.2. Указатели в СиУказатель - это специальная переменная, которая содержит адрес другой переменной.Основные операции для работы с указателями (см., также лекцию 1 прошлого семестра):* — взятие содержимого по адресу (*i - содержимое данного с адресом i)& — взятие адреса (&a - адрес данного а).2При описании указателя задается тип значения, на которое онуказывает.

Описание имеет вид:тип *имя_указателя;Можно интерпретировать смысл этой конструкции так:: объявляется переменная, содержимое которой имеет данный тип.Пример: int *i, j, *pointj;j -переменная целого типа; i, pointj - указатели на значения целого типа.При описании указателей возможна их инициализация.

Пример:int v1, *pointv1=&v1, *p=(int*)200;Здесь указателю pointv1 задается начальное значение, равноеадресу переменной v1, а указателю р - значение константы 200, приведенное к типу int*, т. е. адрес двухсотой от начала рассматриваемойобласти памяти ячейки типа int.Как данные любого типа, указатели могут быть переменными иликонстантами. Указателями-константами, например, являются адресапеременных, имена массивов, явные константы (например, (int*)200), атакже константа NULL (нулевой или несуществующий адрес).При работе с указателями-константами надо помнить следующее:* нельзя брать содержимое от константы без приведения типа;запись *200 является некорректной в отличие от *(int*)200* нельзя брать адрес константы (например, некорректна запись&200), в Си адрес константы считается недоступным;* нельзя определять адрес выражения.Размер памяти, отводимой под указатель, зависит от используемого компьютера и модели памяти.Кроме операции *, к указателям применимы операции сравнения(<, <=, >, >=, ==, !=), присваивания, арифметические операции сложения, вычитания, инкремента и декремента.

Справа от операцииприсваивания должен стоять указатель того же типа, что и слева (отоперации присваивания), или указатель NULL. Сравнивать можно указатели одного типа (или указатель произвольного типа с NULL).Нельзя суммировать (вычитать) указатели, можно только прибавлять к ним (вычитать из них) целую величину. При этом результат3операции зависит не только от значения операндов, но и от типа, с которым связан указатель. Если объявление указателя р имеет вид тип*р, то в результате оператора р=р+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; вышесказанное поясняется схемой:bb[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].Для любого из трех обозначений элемента двумерного массивапрограмма в кодах получается практически одинаковой по производи4тельности, хотя при использовании арифметики указателей вместоквадратных скобок несколько более короткой [3].

Хороший стиль программирования предполагает употребление в пределах одной программы одного (из трех) обозначений.4. Функции Си для распределения и освобождения памятиПрототипы рассматриваемых функций находятся в заголовочномфайле <stdlib.h>.Функция 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.1англ. memory allocation, выделение памяти.Под типом size_t в MS Visual Studio 2008 подразумевается unsigned int.3англ.

clear allocation, чистое выделение памяти.4англ. reallocation, перераспределение памяти.25Функция free5 имеет прототип:void free( void * ptr );Функция free возвращает в кучу блок памяти, на который указывает ptr. Этот блок ранее должен быть выделен с помощью вызова malloc, calloc или realloc.Как Вы помните, основной трудностью работы со статическими массивами является обязательность указания количества ихэлементов при объявлении.

В любом алгоритмическом языке, требующим компиляции (в частности, в Си, Паскале, Фортране), границами индексов массива при описании могут быть только константы.Если длина массива по условию задачи не известна, то она беретсяс запасом, то есть рассматривается максимально возможное числоэлементов массива. Использование динамических массивов позволяет сначала ввести число элементов массива, а потом выделитьпод массив требуемое количество ячеек памяти, как показано вследующих примерах.Пример 1. Работа с динамическим одномерным массивом.#include <iostream.h>#include <conio.h>#include <stdlib.h>void main(){ int *a, n, i;// a – указатель на одномерный массив,//n – число элементов массива, i-счетчик элементов массива.cout<<"Input the number of elements\n";//приглашение к вводу ncin>>n; // ввод числа элементов массива na=(int*)malloc(n*sizeof(int));// выше - распределение памяти под динамический массивcout<<"Input elements\n"; //приглашение к вводу массиваfor (i=0;i<n;i=i+1)cin>>a[i];// в цикле вводится массив// далее каждый элемент массива заменяется своим квадратомfor (i=0;i<n;i=i+1)5англ.

free, освободить6a[i]=a[i]*a[i];cout<<"Squares of elements:\n";//пояснение выводимых значений//далее в цикле выводится массивfor (i=0;i<n;i=i+1)cout<<a[i]<<" ";cout<<endl;_getch();//задержка экрана для просмотра результатовfree(a);//освобождение памяти из-под массива}Пример 2. Работа с динамической матрицей.#include <iostream.h>#include <conio.h>#include <stdlib.h>void main(){ int **a, n,m, i,j;//a-указатель на массив указателей на строки матрицы//n-число строк, m-число столбцов;cout<<"Input n,m\n";//приглашение к вводу n и mcin>>n>>m;// ввод n и ma=(int**)malloc(n*sizeof(int*)); //распределение памяти под// массив указателей на строки матрицыcout<<"Input matrix\n";//приглашение к вводу матрицыfor (i=0;i<n;i=i+1)//цикл ввода по строкам{a[i]=(int*)malloc(m*sizeof(int));// распределение памяти//под i-ую строкуfor (j=0;j<m;j=j+1) // в цикле вводятся элементы i-й строкиcin>>a[i][j];//*(*(a+i)+j)}//ввод законченfor (i=0;i<n;i=i+1)//в цикле каждый элемент матрицы удваиваетсяfor (j=0;j<m;j=j+1)a[i][j]=2*a[i][j];cout<<"The changed matrix:\n";//пояснение выводимых значений//далее в цикле выводится матрица и овсобождается память7for (i=0;i<n;i=i+1){for(j=0;j<m;j=j+1)cout<<a[i][j]<<" ";cout<<endl;free (a[i]);}_getch();free(a);}5.