Begin repeat with start^ do

begin writeln(name); writeln(adr); writeln(tel);

end; start:=start^.pred

until start= nil

end {write_stack};

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

window(10,5,40,20);TextBackground(green); ClrScr;head:= nil;

repeat new(p); with p^ do {заполнение полей записи}

begin write('Ф.И.О.:'); readln(name); write('Адрес:'); readln(adr);

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

end; head:=p;readln(s)

until (s=' '); writeln('Стек телефонов создан');

write_list(head); writeln('Конец вывода стека');

END {list_tel}.

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

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

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

program RING_METRO; {Кольцевая линия Московского метро}

type link=^nest;nest= record forw,back:link;inf: string end;

var r,r1,start:link;f:text;c,c1,c2: string;dir:Boolean;L:byte;

procedure insert(el1,el2:link);{вставка el2 после el1}

begin el2^.forw:=el1^.forw;el2^.back:=el1;el1^.forw^.back:=el2;el1^.forw:=el2;

end {insert};

procedure dir_path(var d:Boolean;s1,s2:string);{направление}

var g:link;j1,j2:byte;er1,er2:Boolean;

begin j1:=0;j2:=0;g:=start;er1:=false;er2:=false;

repeat g:=g^.forw; if g^.inf=s1 then

repeat g:=g^.forw;j1:=j1+1;er1:=(g^.inf=s1);d:=(2*j1<L);

until (g^.inf=s2) or (g^.inf=s1) else if g^.inf=s2 then

repeat g:=g^.forw;j2:=j2+1;er2:=(g^.inf=s2);d:=(2*j2>L);

until (g^.inf=s1) or (g^.inf=s2);

until (g=start) or (g^.inf=s1) or (g^.inf=s2); if er1 or er2 then

begin write('Ошибка в названии ');

if er1 then write('конечной') else write('начальной');writeln(' станции');halt

end; if j1+j2=0 then begin writeln('Ошибка в названиях станций');halt end

end {dir_path};

procedure write_path(d:Boolean;s1,s2: string);{кратчайший путь}

var p:link;

begin p:=start; while not (p^.inf=s1) do p:=p^.forw;

repeat writeln(p^.inf); if d then p:=p^.forw else p:=p^.back;

until (p^.inf=s2); writeln(p^.inf);

end {write_path};

BEGIN writeln('КОЛЬЦЕВАЯ ЛИНИЯ МОСКОВСКОГО МЕТРО');

new(start);r:=start;r^.forw:=r;r^.back:=r;assign(f,'names_st');{$I-}reset(f);{$I+};

if IOResult<>0 then begin writeln('Не найден файл names_st');halt end;

L:=1;readln(f,r^.inf); while not eof(f) do {создание кольца }

begin readln(f,c);new(r1);insert(r,r1);r1^.inf:=c;r:=r1;L:=L+1 end;

writeln('Задайте начальную и конечную станции:'); readln(c1);readln(c2); dir_path(dir,c1,c2); writeln('Кратчайший путь:');write_path(dir,c1,c2);

END {ring_metro}.

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

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

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

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

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

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

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

type link =^node; node = record c:char;count:word;left,right:link end;

Программа имеет следующий вид:

program frequency_letters; {Частота вхождения латинских букв в строку}

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

node= record c:char;count:word;left,right:link end;

var root:link; {Корень дерева поиска} symb:char;j:word;

L: set of char; {множество символов}

s: string; { вводимая строка }

procedure insert_tree(var r:link;ch:char);{Вставка ch в дерево}

begin if r= nil then

begin new(r); with r^ do begin c:=ch;count:=1;left:= nil;right:= nil end end

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