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



О проекте


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


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

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

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

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

Для того чтобы вставить в список элемент со значением Digit между двумя элементами, нужно найти эти элементы и запомнить их адреса (первый адрес – в переменной dx, второй – в рх), после чего установить новые связи с переменной, в которой хранится значение 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
    {Если список не пуст, то просматриваем его до тех пор, пока не отыщется подходящее место для x^ или не закончится список}
      Begin
        dx := Head;
        px := Head;
        while (px<>Nil) and (px^.Data<=Digit) do
          Begin
            dx := px;
            px :=px^.Next;
          End;
        if px=Nil
          then {Пройден весь список}
            dx^.Next := x {Элемент добавляется в конец списка}
          else {Пройден не весь список}
            Begin
              x^.Next := px;
                if px=Head
                  then
                    Head := x {Вставляем в начало списка}
                  else
                    dx^.Next := x; {Вставляем внутрь списка}
            End;
      End;
End;

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

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