Программирование на языке Турбо Паскаль (стр. 9 из 11)

Сравнение. Два указателя можно сравнивать только на равенство (или неравенство). Можно сравнивать указатель с nil, с адресами переменных.

С динамическими переменными можно выполнять все действия, разрешённые для статических переменных, например:

if p^ >= q^ then p^ := q^;

Рассмотрим теперь несколько искусственный пример использования динамических переменных: пусть требуется сложить два числа, не используя статических переменных:

var pa,pb: ^real;

begin

new(pa); new(pb);

write('Введите a: '); readln(pa^);

write('Введите b: '); readln(pb^);

writeln('a+b=',pa^+pb^);

dispose(pa); dispose(pb);

readln;

end.

Кроме описанных указателей существуют ещё так называемые нетипизированные указатели (тип pointer), которые могут служить указателями на переменные любых типов, однако необходимость в них возникает редко, поэтому рассматривать их подробно мы не будем.

Äèíàìè÷åñêèå ñòðóêòóðû äàííûõ

Вернёмся теперь к вопросу об экономии памяти при хранении табличных данных. С использованием указателей можно отказаться от массива и использовать динамические структуры. Самой простой из них является список, который схематично изображается так:

Прямоугольники на этой схеме – динамические переменные типа запись, Data – поле (или поля), содержащие полезную информацию (например фамилии и номера телефонов), поле, которое изображено ниже Data – это указатель на следующую запись. Переменная List также является указателем на запись. Жирная точка в поле «следующий элемент» в самой последней записи означает, что там лежит значение nil, чтобы показать, что эта запись – последняя в списке.

Для описания списка на Паскале достаточно описать тип указателя на запись и тип самой записи. Выглядит всё это так:

type tItemPtr = ^tItem; {указатель на элемент}

tItem = record

Data: tData; {полезные данные}

Next: tItemPtr; {указатель на следующий элемент списка}

end;

В первой строке этого объявления бросается в глаза использование неопределённого типа tItem. Такое исключение из правил в Турбо Паскале сделано умышленно, в противном случае не было бы возможности строить списки и другие связанные структуры из динамических переменных.

Объявить сам список можно как указатель на элемент: var List : tItemPtr; пока наш список пуст, в List следует положить значение nil. При создании первого элемента будем выполнять действия New(List); List^.Next:=nil.

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

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

unit Lists;

interface

type tData = record

Name: string[50];

Phone: longint;

end;

tItemPtr = ^tItem;

tItem = record

Data: tData;

Next: tItemPtr;

end;

procedure InitList(var l: tItemPtr);

procedure AddItemToHead(var l: tItemPtr; d: tData);

function DeleteItemAfter(var l: tItemPtr; num: word): boolean;

function Count(l: tItemPtr): word;

function GetItem(l: tItemPtr; num: word; var d: tData): boolean;

procedure ClearList(var l: tItemPtr);

{---------------------------------------------------------------}

implementation

procedure InitList(var l: tItemPtr);

begin l:=nil end;

procedure AddItemToHead(var l: tItemPtr; d: tData);

var p: tItemPtr;

begin

new(p);

p^.data:=d;

p^.next:=l;

l:=p;

end;

function DeleteItemAfter(var l: tItemPtr; num: word): boolean;

var p,q: tItemPtr;

i: word;

begin

i:=1;

p:=l;

while (i<>num)and(p<>nil) do begin

i:=i+1;

p:=p^.next;

end;

if p<>nil then begin

if p^.next<>nil then begin

q:=p^.next^.next;

dispose(p^.next);

p^.next:=q;

DeleteItemAfter:=true;

end

else DeleteItemAfter:=false; {не удалён}

end

else DeleteItemAfter:=false;

end;

function Count(l: tItemPtr): word;

var p: tItemPtr;

i: word;

begin

i:=0;

p:=l;

while p<>nil do begin

i:=i+1;

p:=p^.next;

end;

count:=i;

end;

function GetItem(l: tItemPtr; num: word; var d: tData): boolean;

var p: tItemPtr;

i: word;

begin

i:=1;

p:=l;

while (i<>num)and(p<>nil) do begin

i:=i+1;

p:=p^.next;

end;

if p<>nil then begin

d:=p^.data;

GetItem:=true;

end

else GetItem:=false;

end;

procedure ClearList(var l: tItemPtr);

var p: tItemPtr;

begin

while (l<>nil) do begin

p:=l^.next;

dispose(l);

l:=p;

end;

end;

end.

Лекция 16. Динамические переменные: другие виды списков, стек и очередь.

1. Другие виды списков

Кроме рассмотренных списков возможны более сложные варианты, связанные с наличием двух дополнительных свойств:

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

Замкнутость списка. Поле next в последнем элементе указывает на первый элемент. Иначе такие списки называются кольцевыми. Этот вид позволяет упростить процедуру удаления элемента списка и другие операции.

С учётом этих свойств возможны четыре различных типа списков.

Для примера рассмотрим описание и реализацию кольцевого двунаправленного списка:

type tItemPtr = ^tItem

tItem = record

data: tData;

next,prev: tItemPtr;

end;

var List: tItemPtr; {список - указатель на один из элементов}

........

{Удалить после указанного:}

procedure DelAfter(p: tItemPtr);

var q: tItemPtr;

begin

if (p<>nil)and(p^.next<>p) then begin

q:=p^.next^.next;

dispose(p^.next);

p^.next:=q;

q^.prev:=p;

end;

end;

{Вставить перед указанным:}

procedure InsertBefore(p: tItemPtr; d: tData);

var q: tItemPtr;

begin

if p<>nil then begin

new(q);

q^.data:=d;

q^.next:=p;

q^.prev:=p^.prev;

p^.prev:=q;

q^.prev^.next:=q;

end;

end;

2. Стек и очередь

Стеком называется такой способ хранения данных, при котором элемент, записанный в хранилище данных, последним всегда извлекается первым (дисциплина LIFO – «last in - first out»). При извлечении элемента происходит его удаление со стека.

Рассмотрим простейший пример использования стека. Предположим, что имеется строка, состоящая из одних лишь открывающих и закрывающих скобок. Требуется определить, является ли она правильным скобочным выражением (то есть для каждой открывающей скобки должна найтись закрывающая). Заведём массив и переменную для хранения номера последнего значимого элемента в массиве (то есть вершины стека), в который при проходе по строке будем складывать все открывающиеся скобки (с увеличением номера вершины на 1), а при встрече с закрывающей будем удалять соответствующую открывающую (попросту уменьшать номер вершины стека). Если окажется, что «пришла» закрывающая скобка, а стек пуст (то есть номер вершины равен 0), то выражение ошибочно. Это же можно сказать и в случае, когда строка закончилась, а стек не пуст.

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

Для данных более сложного вида стек можно организовать с помощью однонаправленного некольцевого списка. Чтобы положить элемент в стек, нужно добавить его в начало списка, чтобы извлечь со стека – получить данные первого элемента, после чего удалить его из списка.

Любая реализация стека должна содержать следующие процедуры и функции:

procedure InitStack – инициализация стека;

procedure Push(d: tData) – положить элемент в стек;

procedure Pop(var d: tData) – извлечь элемент с вершины стека;

function NotEmpty: boolean – проверка стека на пустоту;

Очередь отличается от стека тем, что последний пришедший в неё элемент будет извлечён последним, а первый – первым («FIFO»). С помощью списков её можно организовать следующим образом: будем хранить не только указатель на «голову» списка, но и на «хвост»; добавлять будем в «хвост», а извлекать – из «головы».

Любая реализация очереди (не обязательно с помощью списков) должна «уметь» выполнять такие действия:

procedure InitQueue – инициализация очереди;

procedure AddQueue(d: tData) – поставить элемент в очередь;

procedure SubQueue(var d: tData) – извлечь элемент из очереди;

function NotEmpty: boolean – проверка очереди на пустоту;

Лекция 17. Деревья и поиск в деревьях