Занятие 6. Удаление элемента из списка.
В результате решения задач предыдущих занятий, Вы научились создавать различными способами список, анализировать его информационную часть, формировать на базе данного списка другой список и т. д.
Поэтому для решения поставленной перед нами задачи удаления некоторого элемента из списка, нам нужно найти по какому-либо признаку этот элемент, что, надеюсь не составит для Вас труда.
Уточним поставленную перед нами задачу: удалить из списка элемент с заданной информационной частью.
Обозначим 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;
Задание. Напишите полный текст программы, решающей рассматриваемую задачу. Протестируйте программу, дополните комментарием покажите учителю для оценки.
Выберите с учителем задачи для самостоятельного решения.
1. Написать программу, содержащую процедуру, которая удаляет из списка М второй элемент, если такой есть.
2. Написать программу, содержащую процедуру, которая удаляет из списка М N-ый элемент, если такой есть. N задает пользователь.
3. Написать программу, содержащую процедуру удаления из заданного списка все вхождения элемента с заданным значением информационной части.
4. Написать программу, содержащую процедуру, которая удаляет из списка М за каждым вхождением элемента Е один элемент, если такой есть и он отличен от Е.
5. Написать программу, содержащую процедуру, которая удаляет из списка М первый отрицательный элемент, если такой есть.
6. Написать программу, содержащую процедуру, которая удаляет из списка М все отрицательные элементы.
7. Написать программу, содержащую процедуру, которая формирует список М, включив в него по одному разу элементы, которые входят хотя бы в один из списков М1 и М2.
8. Написать программу, содержащую процедуру, которая формирует список М, включив в него по одному разу элементы, которые входят одновременно в оба списка М1 и М2.
9. Написать программу, содержащую процедуру, которая формирует список М, включив в него по одному разу элементы, которые входят в список М1, но не входят в список М2.
10. Познакомившись с текстами предыдущих задач, придумайте свою задачу и решите ее.