• Списки



• Стеки



• Очереди



• Деревья

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

В языках программирования существует и другой способ выделения памяти под данные, который называется динамическим. В этом случае память под величины отводится во время выполнения программы. Такие величины будем называть динамическими. Раздел оперативной памяти, распределяемый статически, называется статической памятью; динамически распределяемый раздел памяти называется динамической памятью (динамически распределяемой памятью).

Использование динамических величин предоставляет программисту ряд дополнительных возможностей. Во-первых, подключение динамической памяти позволяет увеличить объем обрабатываемых данных. Во-вторых, если потребность в каких-то данных отпала до окончания программы, то занятую ими память можно освободить для другой информации. В-третьих, использование динамической памяти позволяет создавать структуры данных переменного размера.

Работа с динамическими величинами связана с использованием еще одного типа данных — ссылочного типа. Величины, имеющие ссылочный тип, называют указателями.

Указатель содержит адрес поля в динамической памяти, хранящего величину определенного типа. Сам указатель располагается в статической памяти.

Адрес величины — это номер первого байта поля памяти, в котором располагается величина. Размер поля однозначно определяется типом.

Величина ссылочного типа (указатель) описывается следующим образом:

		имя_типа *<идентификатор>;

Вот примеры описания указателей:

	
  int *P1;
  char *P2;  

Здесь P1 — указатель на динамическую величину целого типа; P2 — указатель на динамическую величину символьного типа.

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

Каким же образом происходит выделение памяти под динамическую величину? Память под динамическую величину, связанную с указателем, выделяется в результате выполнения стандартной процедуры malloc. Формат обращения к этой процедуре:

		
	идентификатор = (тип_идентификатора*) malloc (sizeof(тип_идентификатора))

Считается, что после выполнения этого оператора создана динамическая величина, имя которой имеет следующий вид:

		<имя динамической величины> = *<указатель>

Пусть в программе, в которой имеется приведенное выше описание, присутствуют следующие операторы:

	P1 = (int*) malloc (sizeof(int));
	P2 = (char*) malloc (sizeof(char));

После их выполнения в динамической памяти оказывается выделенным место под три величины (две скалярные и один массив), которые имеют идентификаторы:

	*P1, *P2

Например, обозначение *P1 можно расшифровать так: динамическая переменная, на которую ссылается указатель P1.

Дальнейшая работа с динамическими переменными происходит точно так же, как со статическими переменными соответствующих типов. Им можно присваивать значения, их можно использовать в качестве операндов в выражениях, параметров подпрограмм и пр. Например, если переменной *P1 нужно присвоить число 25, переменной *P2 присвоить значение символа "A", то это делается так:

		*P1 = 25;
		*P2 = 'A';		

Кроме процедуры malloc значение указателя может определяться оператором присваивания:

			<указатель> = <ссылочное выражение>;

В качестве ссылочного выражения можно использовать

• указатель;
• ссылочную функцию (т.е. функцию, значением которой является указатель);
• константу NULL.

NULL — это зарезервированная константа, обозначающая пустую ссылку, т.е. ссылку, которая ни на что не указывает. При присваивании базовые типы указателя и ссылочного выражения должны быть одинаковы. Константу NULL можно присваивать указателю с любым базовым типом.

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

Рассмотрим пример. Пусть в программе описаны следующие указатели:

		int *D, *P;		

Тогда допустимыми являются операторы присваивания

		D = P; K = NULL;

Если динамическая величина теряет свой указатель, то она становится "мусором". В программировании под этим словом понимают информацию, которая занимает память, но уже не нужна.

Представьте себе, что в программе, в которой присутствуют описанные выше указатели, в разделе операторов записано следующее:

  D = (int*) malloc (sizeof(int));
  P = (int*) malloc (sizeof(int));  
{Выделено место в динамической памяти под две целые переменные. 
 Указатели получили соответствующие значения}
  *D = 3; *P = 5;
{Динамическим переменным присвоены значения}
  P = D;
{Указатели P и D стали ссылаться на одну и ту же величину, равную 3}
  cout << *P << *D; {Дважды напечатается число 3}

Таким образом, динамическая величина, равная 5, потеряла свой указатель и стала недоступной. Однако место в памяти она занимает. Это и есть пример возникновения "мусора". На схеме показано, что произошло в результате выполнения оператора P = D.

В Паскале имеется стандартная процедура, позволяющая освобождать память от данных, потребность в которых отпала. Ее формат:

		free(<указатель>);

Например, если динамическая переменная *P больше не нужна, то оператор

		free(P);

удалит ее из памяти. После этого значение указателя P становится неопределенным. Особенно существенным становится эффект экономии памяти при удалении больших массивов.

В версиях Турбо-C++, работающих под операционной системой MS DOS, под данные одной программы выделяется 64 килобайта памяти (или, если быть точнее, 65520 байт). Это и есть статическая область памяти. При необходимости работать с большими массивами информации этого может оказаться мало. Размер динамической памяти — много больше (сотни килобайт). Поэтому использование динамической памяти позволяет существенно увеличить объем обрабатываемой информации.

Следует отчетливо понимать, что работа с динамическими данными замедляет выполнение программы, поскольку доступ к величине происходит в два шага: сначала ищется указатель, затем по нему — величина. Как это часто бывает, действует "закон сохранения неприятностей": выигрыш в памяти компенсируется проигрышем во времени.

Пример. Дан текстовый файл размером не более 64 Кб, содержащий действительные числа, по одному в каждой строке. Переписать содержимое файла в массив, разместив его в динамически распределяемой памяти. Вычислить среднее значение элементов массива. Очистить динамическую память. Создать целый массив размером 10000, заполнить его случайными целыми числами в диапазоне от –100 до 100 и вычислить его среднее значение.

// Язык C++
#include < stdio.h >
#include < time.h >
#include < stdlib.h >
#include < iostream.h >
#define NMax 10000
typedef int MasInt;
typedef float MasReal;
MasInt *PInt; MasReal *PReal;
int I, n, MidInt; float MidReal; char S[255];
FILE *t; char *endptr;
void main()
{     cout << "Введите имя файла: "; cin >> S;
      t=fopen(S, "r");
      MidReal = 0; MidInt = 0;
      randomize(); I=0;
      /*Выделение памяти под вещественный массив*/
      PReal = (MasReal*) malloc (sizeof(MasReal));
      /*Ввод и суммирование вещественного массива*/
      while (!feof(t))
       {fgets(S, 255, t); // вводим из файла строку
        PReal[I] = strtod(S, &endptr); // преобразуем введенную строку в вещественное число
	MidReal += PReal[I]; I++;}
      n=I+1;
      free (PReal); /*Удаление вещественного массива*/
      PInt = (MasInt*) malloc(sizeof(MasInt)); /*Выделение памяти под целый массив*/
      /* Вычисление и суммирование целого массива */
      for (I=0; I < NMax; I++)
       { PInt[I] = -100 + random(201);
	 MidInt += PInt[I];}
      /*Вывод средних значений*/
      cout << "\nсреднее целое равно " << MidInt / double(NMax) << "\n";
      cout << "среднее вещественное равно: " << MidReal / n << "\n";
      fclose(t);
}