Алгоритмы работы со списками

1. Построение списка сводится к последовательному добавлению элементов в первоначально пустой список. На пустой список указывает (head = nil). Пусть требуется создать список слов, вводимых с клавиатуры. Последнее слово в списке – «end».

Type

psp = ^tsp;

tsp = Record

wd:string; {В нашем примере информационное по

ле имеет тип string}

next: psp

End;

Var

head,p:psp;

sl:string;

Begin

New(p);

head:=p;

p^.next:=nil;

Readln(sl);

p^.wd:=sl;

while sl<>'end'

Do begin

Readln(sl);

New(q);

q^.wd:= sl;

p^.next:= q;

q^.next:= nil;

p:= q

End;

End;

2. Просмотр и печать списка. Пусть требуется написать процедуру Print_Spisok печати элементов списка, созданного в алгоритме 1.

Procedure Print_spisok;

begin

p:= head;

while p <> nil

Do begin

writeln((p^.wd);

p:= p^.next

End

End;

3. Поиск элемента в списке. Определить, есть ли в списке (алгоритм I) слово «begin» и если есть, то сколько раз встречается. К описанию алгоритма 1 добавим: var k: integer;

…

begin

p:= head;

while p <> nil

Do begin

if p^.wd = ‘begin’

Then inc(k);

p:= p^.next

End;

if k=0

then writeln(‘Такого элемента нет’)

else writeln(‘Слово’,sl,’ встречается ‘,k,’ раз’)

End;

4. Удаление первого элемента списка. Необходимо: 1) передвинуть указатель head на следующий элемент; 2) освободить память; 3) освободить память, занятую удаляемым элементом.

Begin

p:= head;

head:= p^.next;

Dispose(p);

Print_Spisok

End;

5. Удаление последнего элемента списка. К разделу описаний алгоритма 1 добавим вспомогательную переменную q типа psp.

begin

p:= head;

q:= p^.next;

while q^.next <> nil