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

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

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

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

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

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

Описанные ранее строки (называемые строками ASCII), как указывалось, могут иметь максимальную длину только 255 символов. В то же время API-функции Windows, а также язык С используют другой тип строк - "строки, заканчивающиеся нулём" (называемые ASCIIZ-строками). Это - строки, которые ꗬÁIЙለ¿ကЀሢ橢橢뎲뎲Й鈰
��ጕ Ɠ￿ [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);

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

Дата добавления: 2014-01-07