Лекция: Алгоритмы работы со списками
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