34.Создание и обработка динамических списков

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

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

При работе с односвязным списком, чтобы случайно не нарушить связность элементов, нужно запомнить и хранить, не меняя, указатель на начало списка (r).

При таком устройстве списка мы можем продвигаться по нему только слева направо. (из начала в конец)

Двусвязным списком называется структура, состоящая из записей, в которых в первом поле хранится указатель на предыдущую запись (элемент списка), во втором – переменная, а в третьем указатель на следующую запись (элемент списка).

Работать с двусвязными списками намного проще чем с односвязными, так как мы можем двигаться по списку и слева направо (из начала в конец), и справа налево (из конца в начало). Но при этом мы должны будем запомнить и хранить уже два указателя: r – на начало списка и q – на конец списка.

Описание типа для односвязного динамического списка:

type ptr=^rec;

rec=record

str:string;

next:ptr;

end;

Создание односвязного списка:

Procedure Create (var r:ptr);

var cur:ptr;

s:string;

begin

clrscr;

cur:=nil;

writeln ('Enter text');

readln (s);

if s<>’!!!!’ then

begin

new (cur);

r:=cur;

cur^.str:=s;

cur^.next:=nil;

end;

while s<>'!!!!' do {Признак конца ввода строка – “!!!”}

begin

readln (s);

if s=’!!!!’ then break;

new (cur^.next);

cur:=cur^.next;

cur^.str:=s;

cur^.next:=nil;

end;

end;

Просмотр списка:

Procedure Print (r:ptr);

var cur:ptr;

begin

if r=nil then writeln ('List not create')

else

begin

cur:=r;

repeat

writeln (cur^.str);

cur:=cur^.next;

until cur=nil;

writeln;

end;

readln;

end;

Удаление i-го элемента:

Procedure Delete (var r:ptr);

var i,j:integer;

cur,q:ptr;

begin

if r=nil then writeln ('List do not create')

else

begin

writeln ('Enter number of element to delete');

readln (i);

if (Sizeoflist (r)<i) or (i<=0) then writeln ('List haven't this element')

else

if i=1 then

begin

cur:=r;

r:=cur^.next;

dispose (cur);

end

else

begin

cur:=r;

i:=i-2;

for j:=1 to i do

cur:=cur^.next;

q:=cur^.next;

cur^.next:=q^.next;

dispose (q);

end;

end;

readln

end;

Очистка памяти (после завершения работы программы):

Procedure Clean (var r:ptr);

var cur:ptr;

q:ptr;

begin

if r<>nil then

begin

cur:=r;

repeat

if Sizeoflist (r)=1 then

begin

r:=cur^next;

dispose (cur);

break;

end;

q:=cur;

cur:=cur^.next; {Prodvizhenie po spisky}

dispose (q);

until cur =nil;

r:=nil;

end;

end;

Поиск в списке:

Procedure Search (r:ptr);

var flag:boolean;

s:string;

cur:=ptr;

begin

if r=nil then writeln ('List do not create')

else

begin

flag:=false;

writeln ('Enter string:');

readln (s);

cur:=r;

repeat

if cur^.str=s then flag:=true;

cur:=cur^.next;

until cur=nil;

if flag then writeln ('Yes')

else writeln ('Not found');

end;

readln

end;

Функция, считающая число элементов в списке (в том числе и двусвязном):

Function Sizeoflist (const r:ptr):integer;

var cur:ptr;

k:integer;

begin

if r=nil then k:=0

else

begin

cur:=r;

k:=0;

repeat

cur:=cur^.next;

k:=k+1;

until cur=nil;

end;

Sizeoflist:=k;

end;