Упражнение

1) Описать процедуру Insert_2 вставки в список перед каждым элементом с заданным значением x нового элемента с заданным значением y, не используя "трюка" с обменом значений звена q и звена p.

Пример 5.3 Удалить из списка все элементы со значением, равным заданному значению x.

procedure Del(var start:link; x:integer);

var p,pr:link; {указатели на текущий и предыдущий элементы}

begin

p:=start;

while p<>nil do

if start^.inf=x then {удаление в начале списка}

begin

start:=start^.next;

dispose(p);

p:=start

end

else

if p^.inf=x then {удаление в списке}

begin

pr^.next:=p^.next;

dispose(p);

p:=pr^.next

end

else

begin

pr:=p; p:=p^.next

end

end;

В другом варианте удаления элементов проверка и возможное удаление первого элемента списка осуществляется после просмотра всех, кроме него, элементов.

procedure Del_1(var start:link; x:integer);

var p,pr:link; {указатели на текущий и предыдущий элементы}

begin

if start<>nil then

begin {просмотр и удаление, начиная со второго элемента}

p:=start^.next;

pr:=start;

while p<>nil do

if p^.inf=x then

begin

pr^.next:=p^.next;

dispose(p);

p:=pr^.next

end

else

begin

pr:=p;

p:=p^.next

end;

{удаление первого элемента}

if start^.inf=x then

begin

p:=start;

start:=start^.next;

dispose(p)

end

end

end;

6 Поиск элемента в списке

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

Пример 6.1 Найти элемент с заданным значением x, то есть с заданным ключём x (заданным значением информационного поля).

Поиск элемента списка с заданным значением x может быть оформлен в виде функции, которая возвращает указатель на элемент со значением x или значение nil (пустую ссылку), если среди элементов списка нет элемента со значением x.

function Search(start:link; x:integer): link;

var fl:boolean; {признак отсутствия элемента}

begin fl:=true;

while (start<>nil) and fl do {поиск элемента}

if start^.inf=x then fl:=false

else start:=start^.next;

if fl then Search:=nil

else Search:=start

end;

Другой вариант функции поиска не использует флаг fl :

function Search(start:link; x:integer): link;

begin

while (start<>nil) and (start^.inf <> x) do

start:=start^.next;

Search:=start

end;

7 Вставка и удаление элемента

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

Например, если условие поиска – элемент с заданным значением x, то после обращения к функции Search(start,x) (см. раздел 5) можно выполнить необходимые действия:

p:= Search (start, x);

if p = nil then

writeln('в списке нет элемента с заданным значением')

else

begin

{обработка найденного элемента}

end;

Однако, лучше операцию удаления элемента или вставки нового элемента реализовать в виде отдельной подпрограммы, используя поиск элемента, удовлетворяющего заданному условию, как начальную часть операции.

Пример 7.1 Вставить в список после элемента с заданным значением x новый элемент с заданным значением y.

Решение оформлено в виде функции, которая возвращает значение true, если элемент со значением x был найден и новый элемент вставлен в список, и значение false, если среди элементов списка нет элемента со значением x.

function Insert_3(start:link; x,y:integer):boolean;

var p, {текущий указатель}

q:link; {указатель на новый элемент}

fl:boolean; {признак отсутствия элемента}

begin

p:=start; fl:=true;

while (p<>nil) and fl do {поиск элемента}

if p^.inf=x then fl:=false

else p:=p^.next;

if not fl then

begin

new(q); q^.inf:=y; {вставка нового элемента}

q^.next:=p^.next;

p^.next:=q

end;

Insert_3:=not fl

end;