Pascaler
О проекте Теоретический материал Тестирование Архив задач
Войти в личный кабинет



О проекте


Преподавателям


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

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

Поэтому для решения поставленной перед нами задачи удаления некоторого элемента из списка, нам нужно найти по какому-либо признаку этот элемент, что, надеюсь не составит для Вас труда.

Уточним поставленную перед нами задачу: удалить из списка элемент с заданной информационной частью.

Обозначим 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. Познакомившись с текстами предыдущих задач, придумайте свою задачу и решите ее.
Вернуться назад
2003—2012 © Группа «Vimedia»
Проект «Pascaler» — лучший на ХI Всероссийской конференции молодых исследователей с международным участием «Шаг в будущее», Россия, Москва, 12 – 16 апреля 2004г.