Печатать книгуПечатать книгу

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

Сайт: Информатикс
Курс: Структуры данных
Книга: Теоретический материал: списки (Паскаль)
Напечатано:: Гость
Дата: Пятница, 27 Июнь 2025, 22:23

Оглавление

Список. Создание списка путем добавления элементов в конец списка. Просмотр списка

Определение. Списком называется структура данных, каждый элемент которой посредством указателя связывается со следующим элементом.

Из определения следует, что каждый элемент списка содержит поле данных (Data) (оно может иметь сложную структуру) и поле ссылки на следующий элемент (Next). Поле ссылки последнего элемента должно содержать пустой указатель (Nil).

Схематически это выглядит так:

Попробуем вместе сформировать небольшой список путем добавления элементов в конец списка.

Задача. Сформировать список, содержащий целые числа 3, 5, 1, 9.

Для этого сначала определим запись типа S с двумя полями. В одном поле будут содержаться некоторые данные (в нашем случае числа 3, 5 , 1 и 9), а в другом поле будет находиться адрес следующего за ним элемента.

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

Type
  Ukazatel = ^S;
  S = Record
       Data : integer;
       Next : Ukazatel ;
  End;

Таким образом, мы описали типы, с помощью которых можно создать наш связанный однонаправленный список.

Заметим, что все элементы списка взаимосвязаны, т. е. о том, где находится следующий элемент, "знает" только предыдущий. Поэтому самое главное в программе - это не потерять начало списка. Для этого на начало списка установим указатель с именем Head и будем следить за тем, чтобы на протяжении выполнения программы значение этого указателя не менялось.

А теперь опишем переменные для решения нашей задачи:

Var
  Head, {указатель на начало списка}
  x {вспомогательный указатель для создания очередного элемента списка}
  : Ukazatel;

Создадим первый элемент:

New(x); {выделим место в памяти для переменной типа S}
  x^.Data := 3; {заполним поле Data первого элемента}
  x^.Next := Nil; {заполним поле Next первого элемента: указатель в Nil}
  Head := x; {установим указатель головы списка на первый элемент}

Таким образом, к выделенной области памяти можно обратиться через два указателя.

Продолжим формирование списка, для этого добавим элемент в конец списка. Вспомогательная переменная указательного типа х будет хранить адрес последнего элемента списка. Сейчас последний элемент списка совпадает с его началом, поэтому справедливы равенства:

Head^.Next = x^.Next;
Head^.Data = x^.Data;
Head = x;

Выделим область памяти для следующего элемента списка.

New(x^.Next);

Присвоим переменной х значение адреса выделенной области памяти, то есть, переставим указатель на вновь выделенную область памяти:

x := x^.Next;

Определим значение этого элемента списка, то есть, заполним поля:

x^.Data := 5;
x^.Next := Nil;

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

Задание. Ответьте на вопросы:

  1. Какие операции требуется выполнить для вставки в список его элемента?

  2. Можно ли для построения списка обойтись одной переменной?

  3. Сколько элементов может содержать список?

  4. Когда прекращать ввод элементов списка?

  5. Запишите операторы, создающие третий и четвертый элементы списка (1, 9).

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

Procedure Init(Var u : Ukazatel);
Var
  x : Ukazatel;
  Digit : integer; {Значение информационной части элемента списка}
Begin
  Writeln('Введите список ');
  u := Nil; {Список пуст}
  Writeln ('Введите элементы списка. Конец ввода 0');
  Read (Digit);
  if Digit <> 0
    then {Формируем и вставляем первый элемент списка}
      Begin
        New(x);
        x^.Next := Nil;
        x^.Data := Digit;
        u := x;
        Read (Digit);
        while Digit<>0 do
          Begin
            New(x^.Next); {Формируем и вставляем элемент в конец списка}
            x := x^.Next;
            x^.Next := Nil;
            x^.Data := Digit;
            Read(Digit);
          End;
      End;
  Writeln;
End;

Рассмотрите формирование списка несколько другим способом.

Procedure Init(Var u : Ukazatel);
Var
  x, y : Ukazatel;
  Digit : integer;
Begin
  Writeln('Введите список ');
  u := Nil;
  Writeln ('Введите элементы списка. Конец ввода 0');
  Read (Digit);
  while Digit<>0 do
    Begin
      New(y);
      y^.Next := Nil;
      y^.Data := Digit;
      if u=Nil
        then
          u := y
        else
          x^.Next := y;
      x := y;
      Read(Digit);
    End;
  Writeln;
End;

Задание. Разберитесь, как работает данная процедура.

Просмотр списка

Просмотр элементов списка осуществляется последовательно, начиная с его начала. Указатель р поочередно устанавливается на первый, второй, и т.д. элементы списка до тех пор, пока весь список не будет пройден. При этом с каждым элементом списка выполняется операция вывода поля данных на экран. Начальное значение р – адрес первого элемента списка p^. Если р указывает на конец списка, то его значение равно Nil, то есть

while p<>Nil do
Begin
  Write(p^.Data, ' ');
  p := p^.Next;
End

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

Создание списка путем вставки элементов в начало

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

Эту задачу Вы решите сами немного позже, а сейчас рассмотрим, как добавить в этот список некоторый элемент, например, 2:

Выполним следующие действия:

New(x); {Выделяем память для нового элемента}


x^.Data := 2; {Заполняем информационное поле созданного элемента}

x^.Next := Head; {Присоединим элементы списка к созданному элементу}

Head := x; {Изменим значение указателя начала списка}

Итак, нужный элемент вставлен. Теперь Вы можете сформировать весь данный список полностью.

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

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

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

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

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

Для того чтобы вставить в список элемент со значением 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;

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

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

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

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

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

Обозначим 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(Digit : integer; Var u : Ukazatel );
Var
  x, dx : UKAZATEL ;
Begin
  x := u;
  while x<>Nil do
    if x^.Data=Digit
      then
        Begin
          if x=u
            then
              Begin
                u := u^.Next;
                Dispose(x);
                x := u;
              End
            else
              Begin
                dx^.Next := x^.Next;
                Dispose(x);
                x := dx^.Next;
              End;
        End 
      else
        Begin
          dx := x;
          x := x^.Next;
        End;
End;

Задание. Напишите полный текст программы, решающей рассматриваемую задачу. Протестируйте программу, дополните комментарием.

Пример задачи, решаемой с помощью списка

Задание. Ознакомьтесь с предложенной программой и объясните алгоритм решения задачи. Если необходимо, наберите программу на компьютере и просмотрите, как она работает.

Задача 1. Проверить встречается ли (и сколько раз)  непустой список М1 в непустом списке М2.

Program BaranovA;
Uses
  Crt;
Type
  EXS = ^S;
  S = Record
       Data : integer;
       Next : EXS;
  End;
Var
  m1, m2 : EXS;
  Kol : integer;
Procedure Poisk(Var x1, x2 : EXS);
Var
  m3, m4 : EXS;
Begin
  Kol := 0;
  m3 := x1;
  m4 := x2;
  while m4 <> Nil do
    Begin
      if m4^.Data = m3^.Data
        then
          Begin
            m3 := m3^.Next;
            m4 := m4^.Next;
            if m3 = Nil
              then
                Begin
                  Kol := Kol+1;
                  m3 := x1;
                End;
          End
        else
          Begin
            m3 := x1;
            m4 := m4^.Next;
          End;
      End;
End;
Procedure Init (Var u : EXS);
Var
  x, y : EXS;
  Digit : integer;
Begin
  Writeln('Введите список. Конец ввода – 0');
  u := Nil;
  Read(Digit);
  while Digit <> 0 do
    Begin
      New(y);
      y^.Next := Nil;
      y^.Data := Digit;
      if u = Nil
        then
          u := y
        else
          x^.Next := y;
      x := y;
      Read(Digit);
    End;
  Writeln;
End;
Procedure Print(X : EXS);
Begin
  while X <> Nil do
    Begin
      Write(X^.Data : 5);
      X := X^.Next;
    End;
  Readln;
  Writeln;
End;
Begin
  ClrScr;
  Init(m1);
  Init(m2);
  Writeln('***Список 1***');
  Print(m1);
  Writeln('***Список 2***');
  Print(m2);
  Poisk(m1, m2);
  Writeln('Список 1 встречается в списке 2 ', Kol, ' раз(а)');
  Readln;
End.