В результате решения задач предыдущих занятий, Вы научились создавать различными способами список, анализировать его информационную часть, формировать на базе данного списка другой список и т. д.
Поэтому для решения поставленной перед нами задачи удаления некоторого элемента из списка, нам нужно найти по какому-либо признаку этот элемент, что, надеюсь не составит для Вас труда.
Уточним поставленную перед нами задачу: удалить из списка элемент с заданной информационной частью.
Обозначим Head – исходный список, Digit – значение информационной части удаляемого элемента.
При исследовании списка на наличие в нем заданного элемента может встретиться три различных случая. Рассмотрим их.
Удаление элемента из начала списка
Изобразим удаление графически:
Напишем фрагмент программы:
x:= Head; {Запомним адрес первого элемента списка}
Head:= Head^.Next; {Теперь Head указывает на второй элемент списка}
Dispose(x); {Освободим память, занятую переменной x^}
Удаление элемента из середины списка
|
|
Для этого нужно знать адреса удаляемого элемента и элемента, находящегося в списке перед ним.
Изобразим удаление графически:
x:= Head; {Переменная х для хранения адреса удаляемого элемента}
{Найдем адреса нужных элементов списка}
while (x<>Nil) and (x^.Data<>Digit) do
Begin
dx:= x;
x:= x^.Next
End;
dx^.Next:= x^.Next;
Dispose(x);
Удаление элемента из конца списка
Удаление элемента из конца списка производится, когда указатель dx показывает на предпоследний элемент списка, а х – на последний.
Изобразим удаление графически:
{Найдем предпоследний элемент}
x:= Head;
dx:=Head;
while x^.Next<>Nil do
Begin
dx:= x;
x:= x^.Next;
End;
{Удаляем элемент x^ из списка и освобождаем занимаемую им память}
dx^.Next:= Nil;
Dispose(x);
Теперь опишем процедуру удаления элементов из списка в общем случае:
Procedure Del(Gigit: integer; Var u: Ukazatel);
Var
x, dx: UKAZATEL;
Begin
x:= Head;
while x<>Nil do
if x^.Data=Digit
then
Begin
if x=y
then
Begin
Head:= Head^.Next;
Dispose(x);
x:= Head;
End;
else
Begin
dx^.Next:= x^.Next;
Dispose(x);
x:= dx^.Next;
End;
End;
else
Begin
dx:= x;
x:= x^.Next;
End;
End;
Задание. Напишите полный текст программы, решающей рассматриваемую задачу. Протестируйте программу, дополните комментарием покажите учителю для оценки.