Теоретический материал: списки (Паскаль)

Упорядочивание списка. Вставка элемента в середину списка

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

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

После ввода очередного числа с клавиатуры определяем его место в списке. Заметим, что при этом элемент может быть вставлен либо в начало списка, либо в конец его, либо в середину. Первый и второй случаи мы уже рассмотрели выше. Остановимся на третьем случае.

Для того чтобы вставить в список элемент со значением Digit между двумя элементами, нужно найти эти элементы и запомнить их адреса (первый адрес – в переменной px, второй – в dх), после чего установить новые связи с элементом, в котором хранится значение Digit.

Графически это можно представить так:

Операторы, выполняющие данную задачу, будут следующими:

New(x);
x^.Data := Digit;
px^.Next := x;
x^.Next := dx;

Приведем процедуру InsInto, которая ищет место в списке и вставляет элемент, переданный ей как параметр. В результате сразу получается упорядоченный список. Адрес первого элемента списка передается параметром Head.

Procedure InsInto(Digit : integer; Var Head : Ukazatel );
Var
  dx, px, x : Ukazatel ;
Begin
  New(x);
  x^.Data := Digit;
  x^.Next := Nil;
  if Head = Nil
    then {Если список пуст, то вставляем первый элемент}
      Head := x
    else
    {Если список не пуст, то просматриваем его до тех пор, пока не отыщется подходящее место для Digit или не закончится список}
      Begin
        dx := Head;
        px := Head;
        while (dx<>Nil) and (dx^.Data<=Digit) do
          Begin
            px := dx;
            dx :=dx^.Next;
          End;
        if dx=Nil
          then {Пройден весь список}
            px^.Next := x {Элемент добавляется в конец списка}
          else {Пройден не весь список}
            Begin
              x^.Next := dx;
              if dx=Head
                then
                  Head := x {Вставляем в начало списка}
                else
                  px^.Next := x; {Вставляем внутрь списка}
            End;
      End;
End;

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