Динамические структуры данных, указатели, страница 3

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

Процедура writeln (s) выводит значения полей данных узлов списка. Узлы перебираются последовательно до тех пор, пока не встретится последний, нулевой указатель.

Следующая процедура — Insert — предназначена для добавления в начало списка нового узла, поле данных которого содержит значение 11. Для этого вначале отводится намять для добавляемого узла (процедура new), затем инициализируется его поле данных.

Процедура delete удаляет узел. Эта операция заключается в удалении ссылки на узел и последующем освобождении памяти, которую занимал удаленный узел (процедура dispose).

Последняя процедура — list_killer — удаляет весь список и последовательно освобождает память, занимаемую каждым узлом.

Пример. Программа, демонстрирующая работу со связными списками.

program  Linked_lisi;

uses crt;

type

nodeptr = ^nodetype;

          nodetype = record

number : Integer:

nextnode : nodeptr;

end;

var

list :  nodeptr;

procedure list_Init( var list : nodeptr);

var

p : notleptr;

1 : integer;

begin

New(list);

List^.number := 1;

p := list;

for i = 2 to 10 do

begin

New( p^.nextnode);

P^.nextnode.number := i;

p := p^.nextnode;

end;

p^.nextnode : = nil;

end;

procedure write_List( list : nodeptr);

var

p : nodeptr;

begin

p := list;

while p nil do

begin

Write(p^.nuinber:3);

p := p^.nextnode;

end;

end;

procedure insert( var list : nodeptr);

var

p : nodeptr;

begin

New(p);

P^.number := 11;

P^.nextnode := list;

if p^.nextnode = nil then

p^.nextnode^.nextnode := nil;

list := p;

end;

procedure delete( var list : nodeptr);

var

          p, t : nodeptr;

begin

p := list;

t := p^.nextnode^.nextnode;

Dispose(p^.nextnode);

Р^.nextnode := t;

end;

procedure list_killer(var list : nodeptr);

var

p, t :  nodeptr;

begin

p := list;

while p  nil do begin

t := p^.nextnode;

Dispose(p);

 p :=t;

end;

end;

begin

ClrScr;

WriteLn('Объем памяти до размещения списка : ', memavail, ' байт');

list_init(list);

WriteLn('Объем памяти после размещения списка  :  ', memavail, ' байт'); Write('Список :   ');

Write_List(list);

WriteLn;

 Insert(list):

Write('Список после добавления узла :  ');

Write_List(list);

          WriteLn;

WriteLn('Объем памяти пocлe добавления узла :  '. memavail, ' байт');

WriteLn;

Delete(List);

Write( 'Список после удаления узла     :  ');

Write_List(list);

WriteLn;

WriteLn('Объем памяти после удаления узла :  '. memavail. ' байт');

WriteLn;

WriteLn('Удаление списка из памяти');

list_killer(list);

WriteLn('Объем доступной памяти :  '. memavail, ' байт');

WriteLn( 'После завершения нажмите <Enter>');

ReadLn;

end.

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

1.3  Стеки

Стек представляет собой частный случай списка, доступ к которому возможен только в корневой точке. Добавление или удаление нового элемента производится в начале списка. Иногда стек обозначают английской аббревиатурой L1FO — Last In First Out, что можно перевести как «последний вошел — первый вышел». Это сокращение правильно передает механизм работы стека.