Динамические массивы
Выбери формат для чтения
Загружаем конспект в формате doc
Это займет всего пару минут! А пока ты можешь прочитать работу в формате Word 👇
Лекция 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;
}