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

Begin

End

Begin

Begin

End

End

Begin

Begin

Implementation

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);

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

procedure InitList(var l: tItemPtr);

begin l:=nil end;

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

var p: tItemPtr;

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;

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;

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

else DeleteItemAfter:=false;

end;

function Count(l: tItemPtr): word;

var p: tItemPtr;

i: word;

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;

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;

else GetItem:=false;

end;

procedure ClearList(var l: tItemPtr);

var p: tItemPtr;

while (l<>nil) do begin

p:=l^.next;

dispose(l);

l:=p;

end;

end;

end.

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

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

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

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

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

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

type tItemPtr = ^tItem

tItem = record

data: tData;

next,prev: tItemPtr;

end;

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

........

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

procedure DelAfter(p: tItemPtr);

var q: tItemPtr;