Удаление элемента из списка

Пусть имеется связный список из трех чисел: 5, -3, -12.

Список сформирован, и значениями переменныхheadиqявляется ссылка на первый элемент списка:

Необходимо удалитьиз списка элемент -3.

Для удаления(исключения) существующего элемента из списка выполняются следующие действия:

1.указателиq(поисковый) иr (отстает от поискового на шаг) ставим в голову списка:

q := head^.Next; на первый элемент списка

r := head; на указатель на голову списка

2.в списке отыскивается удаляемый элемент, для этого используем поисковый указательq:

While (q <> Nil) Do пока не дошли до конца списка

If (q^.Inf = -3) если нашли нужный элемент,

Then Break то выходим из цикла поиска,

Else

Begin

r := q; иначе подтягиваем r к q

q := q^.Next; и делаем шаг по списку указателем q

End;

сейчас ссылка qуказывает на элемент-3 , то естьq^.Inf = -3, а полеq^.Nextсодержит адрес элемента-12. Ссылкаrуказывает на предыдущий элемент списка, то есть на5, а в r^.Next содержится адрес удаляемого элемента- r^.Next = q:

3.в ссылочное поле r^.Next помещается адрес, хранящийся вq^.Next,то есть адрес элемента-12:

r^.Next := q^.Next;

Сейчас оба элемента (5 и-3) будут соединены с элементом-12,

а связь между элементами 5и-3разрывается.

4.освобождаем память от удаленного элемента-3 и возвращаем указателиq иr в голову списка:

Dispose(q); удаляем из памяти элемент -3

q := head^.Next; на первый элемент списка

r := head; на указатель на голову списка

Пример: сформировать список из элементов5, -3, 17, -12и вывести его на экран. Удалить из списка несколько элементов (конец удаления – число0), каждый раз выводя новый список на экран.

Интерфейс:

Создание списка

Первое число: -12

Следующее число: 17

Следующее число: -3

Следующее число: 5

Следующее число: 0

Введено чисел: 4

Введенные числа:

5 -3 17 -12

Удаление элементов из списка

Удаляемый элемент: 17

Новый список:

5 -3 -2 -12

Удаляемый элемент: 5

Новый список:

-3 -2 -12

Удаляемый элемент: 10

Такого элемента в списке нет

Список:

-3 -2 -12

Удаляемый элемент: 0

Список:

-3 -2 -12

Программа:

Program Spisok;

Uses CRT;

Type TPoint = ^TElement;

TElement = Record

Inf: Integer;

Next: TPoint;

End;

Var head, q, r : tPoint;

poisk: Integer;

flag: 0..1; флаг поиска (0 – элемент не найден)

Procedure Formir_spisok;

Begin

New(head); head - указатель на голову списка

head^.Inf := 0; количество элементов в списке

head^.Next := Nil; списка еще нет

New(q); формируем первый элемент

Write(‘Первое число: ’);

ReadLn(q^.Inf); вводим его информационную часть

If (q^.Inf=0) если ввели 0,

Then Exit; то выходим из процедуры

head^.Inf := 1; в списке один элемент

q^.Next := head^.Next; вставляем его в голову списка

head^.Next := q; в head^.Next адрес головы списка

Repeat

New(q); формируем очередной элемент

Write(‘Очередное число: ’);

ReadLn(q^.Inf); вводим его информационную часть

If (q^.Inf=0) если ввели 0,

Then Break; то выходим из цикла ввода

head^.Inf := head^.Inf + 1; увеличиваем счетчик элементов на 1

q^.Next := head^.Next; вставляем элемент в голову списка

head^.Next := q; в head^.Next адрес головы списка

Until (q^.Inf = 0);

End;

Procedure Vyvod_spisok; процедура вывода списка

Begin

q := head^.Next; текущую ссылку – на первый элемент

While (q <> Nil) Do пока не конец списка

Begin

Write(q^.Inf:5); выводим очередной элемент

q := q^.Next; ссылку – на следующий элемент

End;

WriteLn;

End;

Begin головная программа

ClrScr;

WriteLn(‘Создание списка’);

WriteLn;

Formir_spisok; обращение к процедуре создания списка

WriteLn(‘Введено чисел: ’, head^.Inf);

WriteLn(‘Введенные числа:’);

Vyvod_spisok; обращение к процедуре вывода списка

WriteLn;

WriteLn(‘Удаление элементов из списка’);

WriteLn;

New(r);

Repeat

WriteLn;

Write(‘Удаляемый элемент: ’);

ReadLn(poisk);

If (poisk = 0) если он равен нулю,

Then Break; то выходим из цикла удаления

flag := 0; флаг поиска равен нулю – удаляемый элемент пока не найден

q := head^.Next; поисковый указатель q – на первый элемент списка,

r := head; тормозной r - на голову списка

While (q <> Nil) Do пока не конец списка

If (q^.Inf = poisk) ищем нужный элемент

Then

Begin

flag := 1; если элемент найден:

Break; выходим из цикла поиска

End

Else

Begin

r := q; иначе подтягиваем r к q

q := q^.Next; и делаем шаг по списку

End;

If (flag = 0) Then если элемент не найден:

Begin

WriteLn(‘Такого элемента в списке нет’);

WriteLn(‘Список:’);

Vyvod_spisok; выводим список

Continue; и продолжаем цикл удаления

End;

r^.Next := q^.Next; если элемент найден,

Dispose(q); то удаляем его из списка и освобождаем память

head^.Inf := head^.Inf - 1; уменьшаем счетчик элементов на единицу

q := head^.Next; возвращаем указатели в голову списка

r := head;

If (head^.Inf = 0) Then если в списке не осталось элементов

Begin

WriteLn(‘Список пуст’);

Break;

End;

WriteLn;

WriteLn(‘Новый список:’);

Vyvod_spisok; выводим новый список

Until (poisk = 0); окончание цикла удаления элементов

WriteLn(‘Список:’);

Vyvod_spisok; выводим окончательный список

ReadLn;

End.

Таким образом, операции вставки и удаления элементов из списка представляют собой изменение значений ссылочных полей определенных элементов списка.