Лекции 24-25: Использование указателей для представления динамически структур данных

Begin repeat with start^ do

begin writeln(name);

writeln(adr);

writeln(tel);

end; start:=start^.next

until start= nil;

end {write_list};

BEGIN TextBackground(cyan);TextColor(white);ClrScr;

window(10,5,40,20);TextBackground(green); ClrScr;

new(first);p:=first;pp:= nil;

repeat if pp<> nil then {образование очередного элемента}

begin new(p);pp^.next:=p end;

with p^ do { заполнение элемента списка}

begin write('Ф.И.О.:'); readln(name);

write('Адрес:'); readln(adr);

write('Телефон:');readln(tel);

next:= nil

end; pp:=p;readln(s)

until (s=' ');

writeln('Список телефонов создан');

write_list(first);writeln('Вывод списка завершен');

END {list_tel}.

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

Для возврата освободившегося участка хип-памяти используется процедура dispose (p), где p – типизированный указатель, и процедура freemem(p,k), где к – размер в байтах освобождаемого участка для нетипизированного указателя p.

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

Процедура mark(ptr) - запоминает в ptr текущее значение указателя HeapPtr.

Процедура release(ptr) - освобождение участка хип-памяти от текущего указателя, сохраненного процедурой mark(ptr), до конца хип-памяти.

Функции maxavail и memavail - возвращают размер (в байтах) наибольшего непрерывного участка или общего свободного пространства хип-памяти соответственно.

Функция addr(x) - возвращает указатель, содержащий адрес аргумента x (имя переменной, процедуры, функции). Эту же функцию выполняет операция @x.

1. Тип Pchar и "строки, заканчивающиеся нулем".

2. Линейные списки и очереди.

3. Кольцевые списки.

4. Использование указателей для обработки деревьев.

1. Тип Pchar и "строки, заканчивающиеся нулём".

Описанные ранее строки (называемые строками ASCII), как указывалось, могут иметь максимальную длину только 255 символов. В то же время API-функции Windows, а также язык С используют другой тип строк - "строки, заканчивающиеся нулём" (называемые ASCIIZ-строками). Это - строки, которые ꗬÁIЙለ¿ကЀሢ
橢橢뎲뎲Й鈰
��ጕ Ɠ￿￿￿]۸۸۸۸ૌૌૌૠૠૠૠ8ଘʹຌΌૠꀴìᓤŬᙐᙦᙦᙦ嚑ଈ憙̴操Ɯ锜[1]锞锞锞5镓Ô阧Ô電ꄠǴꌔf電हૌ晩嘕|嚑晩晩電изован в версии Borland Pascal 7.0 специальным модулем Strings, в котором содержатся функции обработки таких строк и преобразований между строками ASCII и строками ASCIIZ.

Тип PChar является указателем на область памяти, где размещена строка, заканчивающаяся символом #0. Сама строка представляет собой массив вида:

array [0..K] of Char; где: K - количество символов строки.

В отличие от строки string в "строке, заканчивающейся нулем" первый символ имеет индекс 0, а последний - K-1. Символ-терминатор #0 размещен в позиции K и недоступен для прикладной программы.

Замечание

Все стандартные процедуры и функции, рассмотренные для типа string, также применимы и для строк типа PChar. Для определения длины такой строки s можно использовать функцию Length(s), но не ord(s[0]).

Функции над ASCIIZ-строками (все они имеют префикс Str) можно разделить на три группы: аналоги функций для ASCII-строк, оригинальные функции (не имеющие аналога среди функций ASCII-строк) и функции преобразования.

Функции - аналоги: StrCopy, StrPos, StrLen, StrCat.

Оригинальные функции для ASCIIZ-строк включают функции сравнения строк (с учётом или без учёта регистра символа), инициализации строки, стирания строки, определения вхождения символа в строку (первого или последнего вхождения), специальные функции копирования и некоторые другие. Работа с этими функциями требует некоторых знаний механизма указателей.

Функции преобразования: преобразование из ASCIIZ к ASCII (StrPas), из ASCII к ASCIIZ (StrPCopy).

Чтение и запись ASCIIZ-строк поддерживается обычными стандартными процедурами: read, readln, write, writeln.

2. Линейные списки и очереди.

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

Линейный список - линейная последовательность произвольного числа компонент (элементов списка), каждый из которых непосредственно связан со следующим или/и предшествующим элементом. Список однонаправленный, если в нём имеется только связь с предшествующим или только со следующим элементом. Список двунаправленный, если в нем имеется связь, как с предшествующим, так и со следующим элементом.

Построение списков с помощью указателей позволяет размещать элементы списка в динамической памяти независимо друг от друга (т.е. необязательно сплошным массивом адресов), что придает спискам бóльшую гибкость по сравнению с обычными массивами. Над такими списками легко выполнять операции включения элемента в любое место списка или удаления произвольного элемента из списка (без перемещения остальных элементов в памяти), однако, доступ к любому элементу только последовательный (через голову списка). Переменная-указатель выполняет в списке роль связи между соседними элементами.

Линейные списки часто используются для представления и обслуживания очередей. Характерным для очередей является её естественный порядок: каждый новый элемент помещается в "хвост" очереди. Различают две дисциплины обслуживания очередей:

FIFO (first input first output) - первым пришёл, первым обслуживается.

LIFO (last input first output) - последним пришёл, первым обслуживается.

Дисциплина FIFO соответствует классической очереди, однако, в ряде случаев используются очереди с дисциплиной LIFO (такие очереди распространены в приложениях информатики, например при анализе иерархически вложенных языковых конструкций, а также в некоторых технических системах - обоймы патронов в автоматическом оружии).

Очередь с дисциплиной обслуживания LIFO называется стеком, а с классической дисциплиной FIFO - магазином.

Пример программы создания очереди - FIFO был приведен выше (список телефонов). Аналогичная программа для стека телефонов (имеющая смысл для определения, кто звонил последним) приведена ниже.

program stack_tel;{создание стека телефонов}

uses CRT;

type ref=^inf; {тип - Указатель на запись }

inf= record name,adr,tel: string;

pred:ref

end;

var head,p:ref; {указатель на начало стека и текущий}

s: string;

procedure write_stack(start:ref);

{вывод всех элементов стека}