Если заранее не известно, данные какого типа надо будет хранить в динамической памяти, придется использовать Нетипизированные указатели типа POINTER. В переменной типа POINTER запоминается только адрес куска памяти и его размер, но не тип хранимых в этом куске данных. При этом тип POINTER совместим с любым другим указателем. Например, возможны следующие действия:
VAR p1:^BYTE;
p2: ^WORD;
pp:POINTER;
…
pp:=p1; pp:=p2
Зачем же могут понадобиться такие неполноценные указатели? Дело в том, что в ряде случаев нужно просто зарезервировать место в памяти, не заботясь о типе хранимых там данных. Для этого предназначены следующие процедуры:
GetMem(p,size) – захватить size байт и записать адрес первого из них в указатель p;
FreeMem(p,size) – освободить size байт и записать в р значение NIL.
Как и при любой работе с динамической памятью, необходимо строго соблюдать простое правило: сколько памяти взял, столько и вернул. Невозвращение памяти приводит к так называемой утечке памяти – при каждом запуске программы все большие участки оперативной памяти оказываются занятыми, что, в конце концов, приводит к зависанию компьютера.
Яркий пример использования нетипизированных указателей – создание анимации. Для организации движения участка картинки этот участок надо где-то запомнить. Поскольку заранее требуемый размер памяти для хранения картинки неизвестен (а он зависит от размеров в картинки и числа цветов на экране), будем сохранять информацию в динамической памяти. Тип данных в данном случае не важен – программа просто скопирует заданное количество байт из видеопамяти в динамическую и обратно.
s:=ImageSize(10,10,50,50);
GetMem(p,s);
GetImage(10,10,50,50,p^);
FOR i:=0 TO 600 DO
BEGIN
PutImage(i,240,p^,XORPut);
DELAY(100);
PutImage(i,240,p^,XORPut)
END;
CloseGraph;
FreeMem(p,s)
END.
А что, если в программе нужно завести очень большой массив? Динамической памяти у нас много. Давайте заведем массив на 1000000 вещественных чисел. Оценим размер такого массива. Одна переменная типа REAL занимает 4 байта. Тогда весь массив займет 1000000 x 4 / 1024 = 3906Кб = 3,8 Мб. Казалось бы, не так много. Попробуем описать такой массив в программе:
TYPE TA=ARRAY[1..1000000] OF REAL;
VAR a:^TA;
Увы, ничего не выйдет. Паскаль выдаст сообщение об ошибке "Structure too large" – слишком большая структура данных. Ведь старого ограничения на размер массива в 64Кб никто не отменял! Как же быть? Какой смысл в сотнях мегабайт оперативной памяти, если в ней можно разместить только жалкие 64Кб? В следующем разделе мы узнаем ответ на этот вопрос.
14. Линейные списки: основные виды и способы реализации
Итак, как мы узнали на предыдущей лекции, создать большой (больше, чем 64Кб) массив в динамической памяти все равно не удается. Как же тогда работают программы, обрабатывающие десятки и сотни мегабайт данных? Оказывается, есть оригинальный способ создания больших массивов, состоящий в размещении в памяти "гибкого" массива с произвольным числом элементов (Рис. 10.1).
Рис. 14.1. Большой массив в динамической памяти.
Каждый элемент такого массива состоит из двух частей: в одной записаны хранимые в этом элементе данные и некий идентификатор элемента (скажем, порядковый номер), а в другой – адрес следующего элемента массива. Получается своеобразная цепочка. При этом для работы с таким массивов достаточно иметь лишь одну статическую переменную, в которой будет храниться адрес первого элемента массива ("головы"). У последнего же элемента массива ("хвоста") адрес следующего элемента будет равен пустому значению – NIL.
Очевидно, каждый элемент такого массива надо представить в виде записи, поскольку он должен объединять данные разного типа. Попробуем это сделать, создав массив для хранения текстовых строк (типа STRING):
TYPE Tnode=RECORD
number:WORD;
data: STRING;
next: ^???
END;
Поле number будет содержать порядковый номер элемента массива, поле data – собственно текстовую строку, а вот поле next должно быть указателем. С указателем связан конкретный тип данных. В рассматриваемом случае указатель должен указывать на следующий элемент массива, который тоже будет типа Tnode. Казалось бы, надо написать next:^Tnode. Но Паскаль этого не позволяет! Описание типа Tnode еще не окончено, а мы внутри этого описания ссылаемся на еще неописанный тип. Это явное нарушение краеугольного принципа Паскаля, гласящего: «Все упоминаемые в программе объекты (переменные, типы, константы, процедуры, функции) должны быть предварительно описаны».
Получили тупиковую ситуацию: правила Паскаля не позволяют создавать массивы в памяти указанным выше способом. Но ведь программы-то как-то работают! Специально для случая создания таких массивов в строгости Паскаля было внесено исключение: при описании указателя можно создать указатель на тип данных, описанный ниже по тексту программы. Проще говоря, можно сделать так:
TYPE Ptr = ^Tnode; { указатель на еще не описанный тип }
TYPE Tnode=RECORD
number: WORD;
data: STRING;
next: Ptr
END;
За счет некоторого отступления от жестких правил Паскаля удалось создать необходимый тип данных. Что дальше? Прежде всего, нужна статическая переменная, через которую из программы можно будет работать с массивом. Объявим ее:
VAR p:Ptr;
Теперь все готово для добавления в массив новых элементов. В начальный момент массив пуст, p=NIL. Для добавления элемента в "голову" массива нужно выполнить следующие действия:
1. Выделить память под новый элемент массива и запомнить указатель на него..
2. Присвоить полю next нового элемента значение p.
3. Присвоить p значение указателя на новый элемент.
Все происходящее показано на Рис. 10.2 (Адрес1 – адрес первого элемента массива).
Рис. 14.2. Добавление элемента в "голову" массива.
Программируется это так:
VAR q:Ptr;
BEGIN
{ выделили память и запомнили указатель на нее в вспомогательной переменной q}
New(q);
{ старая ссылка на голову (р) идет в хвост }
q^.Ptr:=p;
{ теперь голова указывает на новый первый элемент }
p:=q
Важен порядок выполнения этих операторов – если их поменять местами, ничего не получится.
