Web-Pascal Site | PASCAL::TUTORIAL

#18 Практикум II. Связанный список.

Вступление
Новости сайта
Теория
Послесловие

Вступление

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

Новости сайта

[17.01.03] В разделе Компиляторы появился компилятор Pro Pascal.
[16.01.03] Еще одна новая статья в разделе "Статьи": А какие они, Паскали?
[16.01.03] В разделе Документация добавлен новый курс лекций по языку Паскаль
[16.01.03] Новая небольшая статья: Динамические структуры данных

Теория

Итак сегодня мы займёмся рассмотрением классического примера: связанный список. Для начала самый простой вариант - односвязный.

Что же такое связаный список ? Давайте представим, что у нас есть запись.... для простоты введём только одно поле :)

tlist = record
   data : integer;
end;


И пускай нам нужно создать массив из N  таких записей, причём N задаётся пользователем и может изменяться во время работы программы, как в сторону увеличения, так и в сторону уменьшения.  Конечно можно создать массив таким образом:
list : array [1 .. N] of tlist;
где N будет максимально возможное число для того, что бы массив поместился в сегменте данных. Однако это не есть гуд.  Гораздо проще такая задача решается с использованием указателей. Чем мы сейчас и займёмся.  Идея связанного списка проста как бит: в каждом элементе содержится указатель на следующий. Т.е. запись выглядит так:
type
  plist = ^tlist;
  tlist = record
            data : integer;
            next : plist
  end;
Давайте рассмотрим организацию такого списка. Проще всего это дело нарисовать, к сожалению к рассылке нельзя приаттачить картинку, поэтому я нарисую её тут с использованием текстовых символов (не судите за убогость):
+------+      |---->+------+      |---->+------+
| data |      |     | data |      |     | data |
+------+      |     +------+      |     +------+
| next |      |     | next |      |     | next |
|  -----------      |  -----------      |  -------------> nil
+------+            +------+            +------+
итак как мы видим в указателе next находится адрес следующего элемента в памяти.  Последний же указатель указывает в никуда (т.е. в nil). Поэтому для организации списка нам потребуются 2 указателя на tlist. Один из них будет постоянно хранить адрес начала (т.е. первого элемента) списка, второй будет "суетится" по списку, т.е. бегать по нему из начала в конец. Можно было бы ввести ещё и указатель на последний элемент (т.е. 3-й указатель на tlist) , но в нём нет надобности, т.к. узнать кончился ли список мы можем, сравнив next с nil. Т.е. у нас будет 2 глобальных переменных:
var
  list, start : plist;
Start - будет указывать на начало списка, а list будет нашей рабочей лошадкой. Как видите наш список занимает в памяти всего  8 байт (под один указатель отводится 4).
Для начала напишем процедуру, которая добавляет элемент в список. Замечу, что добавляем мы всегда в конец списка!  Параметр d - это то, что нам нужно добавить. list у нас указывает на последний элемент списка. 
procedure Add (d : integer);
var
 l : plist;
begin
  New (l); { выделяем память под структуру }

  l^.data := d;  { инициализируем данные }
  l^.next := nil; { т.к. добавляем в конец, то указатель на следующий равен nil }

{ если start не равен nil, значит список не пуст}
  if start <> nil then
  begin
     list := start;

      { "перематываем" список, что бы list стал последним элементом }
      while list^.next <> nil do
         list := list^.next;

     list^.next := l { устанавливаем указатель  на следующий элемент, а это у нас l }
  end
  else
     start := l; { если список был пуст, тогда делаем l первым элементом }
  list := l { теперь меняем текущий элемент, присваивая ему значение l }
end;
Обратите внимание, что мы не освобождаем память, которую занимает l. Почему мы так делаем ?  Опять "нарисую" картинку:
+------+      |---->...->+------+            +------+
| data |      |     ...  | data |            | data |
+------+      |     ...  +------+            +------+
| next |      |     ...  | next |            | next |
|  -----------      ...  |  -------->nil     |  -------------> nil
+------+            ...  +------+            +------+
^                        ^                   ^ 
| - это start            | -  это list       | - это l

Выполняя присваивание list^.next := l мы переходим к такому виду:
+------+      |---->...->+------+      |---->+------+
| data |      |     ...  | data |      |     | data |
+------+      |     ...  +------+      |     +------+
| next |      |     ...  | next |      |     | next |
|  -----------      ...  |  ------------     |  -------------> nil
+------+            ...  +------+            +------+
^                        ^                   ^ 
| - это start            | -  это list       | - это l
и  после   list := l мы получаем такую картину:
+------+      |---->...->+------+      |---->+------+
| data |      |     ...  | data |      |     | data |
+------+      |     ...  +------+      |     +------+
| next |      |     ...  | next |      |     | next |
|  -----------      ...  |  ------------     |  -------------> nil
+------+            ...  +------+            +------+
^                                            ^ 
| - это start                                | - это list и l
Если же мы добавляем первай элемнт, то в начале start = nil.  В конце и list и start и l будут указывать на одно и тоже. Если же освободить память, которую занимает l, то последний (или первый) элемент списка отрежется и мы ничего не добавим.
Теперь напишем процедуру, которая выводит результаты нашей деятельности, т.е. список на экран:
procedure Display;
begin
  if start = nil then
  begin
    writeLn ('Список пуст.');
    exit
  end;

  list := start;

  while list <> nil do
  begin
   write (#32, list^.data);
   list := list^.next
  end
end;
Итак тут мы устанавливам указтель list на начало списка (list := start), а потом "прокручиваем" его, пока он не равен nil (т.е. пока он существует). Обратите внимание, что мы переходим к следующему элементу таким образом: list := list^.next
После выполнения программы было бы неплохо (я сказал даже очень замечательно) освободить память, которую занимает список. Это кстати может понадобится и в процессе выполнения самой программы. Процедура осовобождения очень похожа на  процедуру вывода - мы так же последовательно перебираем список, только вместо вывода на экран мы  освобождаем память.
procedure Clean;
var
  l : plist;
begin
  if start = nil then
    exit; { список пуст, удалять нечего }

  list := start; { переходим на начала списка }

  while list <> nil do
  begin
     l := list; { теперь l - это текущий элемент }
     list := list^.next; { list переходит на следующий }
     Dispose (l) { освобождаем память }
  end;
  start := nil { обнуляем указатель начала }
end;
Естественно, что нам может понадобится найти чего-то в списке. Для этого предназаначена следующая процедура.  Мы ищем элемент с data = d. Указатель на него останется в list после завершения работы процедуры, если же элемент не найден, то list = nil. Сама  она не представляет из себя что-то сверх выдающееся. Тот же перебор от начала до конца (или же до той поры пока не найдём). 
procedure Search (d : integer);
var
  flag : boolean;
begin
  list := start;
  flag := false;

  while (list <> nil) and (not flag) do
  begin
     if d = list^.data then
       flag := true
     else
      list := list^.next
  end
end;
Ну и напоследок напишем процедуру для удаления произвольного элемента из списка. Тут сразу же возникает 3 случая: удаляется первый, удалется последний и удаляется средний (т.е. не первый и не последний) элемент. Для начала рассмотрим  третий случай. Список  в данный момент представляет из себя что-то такое:
...->+------+      |---->+------+      |---->+------+
     | data |      |     | data |      |     | data |
     +------+      |     +------+      |     +------+
     | next |      |     | next |      |     | next |
     |  -----------      |  ------------     |  ------------...
     +------+            +------+            +------+
       prev                cur                 nxt
Я назвал условными именами элементы: cur - элемент, который удаляем; prev - элемент, который идёт перед удаляемым; nxt - элемент, идущий за удаляемым. Что бы удалить cur мы должны сделать следующие действия: prev.next = nxt (т.е. предыдущий должен указать на последующий за удаляемым):
...->+------+         +------+    |--|---->+------+
     | data |         | data |    |  |     | data |
     +------+         +------+    |  |     +------+
     | next |         | next |    |  |     | next |
     |  -----------|  |  ---------+---     |  ------------...
     +------+      |  +------+    |        +------+
       prev        |    cur       |          nxt
                   |              |
                   |--------------|
Таким образом мы исключили из списка элемент cur, теперь просто освободим память и список преобразуется в такой:
...->+------+             |------>+------+
     | data |             |       | data |
     +------+             |       +------+
     | next |             |       | next |
     |  -----------|      |       |  ------------...
     +------+      |      |       +------+
       prev        |      |          nxt
                   |      |
                   |------|
Случай удаления последнего элемента, является частным от удаления среднего, если предположить, что nxt = nil. А случай для удаления первого, если prev = nil.
Процедура, которая выполняет всё описанное выше написана ниже :)  При этом обратите внимание, что в момент входа в процедуру list указывает на элемент, который предшествует удаляемому (т.е. условно list = prev)
procedure Delete;
var
  l : plist;
begin
  if start = nil then
    exit; { список пуст - удалять нечего }

  l := list^.next; { теперь l указыват на удаляемый элемент l = cur}

  if list <> nil then
  begin{ если удаляется не первый элемент }
    list^.next := l^.next; { prev.next = nxt (или же prev.next = cur.next) }
    Dispose (l){ Освобождаем память }
  end
  else
  begin { удаляем первый элемент }
    list := start^.next; 
    Dispose (start); { освобождаем память }
    start := list { устанавляваем новое начало списка }
  end
end;
Теперь у нас есть довольно мощный арсенал для работы со списком. Мы можем заполнить список с помощью Add, очистить его Clean, найти нужный элемент Search и удалить его .... или нет удалить его сразу мы не можем. Ведь после выполнения Search list указывает на найденный элемент, а для выполнения Delete нам в list нужен  указатель на предыдущий. Надо бы  написать ещё процедуру, которая бы  находила элемент предшествующий данному. Это и будет домашним заданием.  Написать процедуру findPrior, которая ищет элемент списка, предшествующий list.... после её выполнения именно   list и должен указывать на этот элемент (что бы потом проще было вызывать Delete). Так же было бы не плохо (а вернее очень хорошо) написать процедуру для добавления элемента в начало списка.
Ниже я привёл пример работы со связанным списком.  Это просто все процедуры описанные выше + маленькая менюшка. Естественно не хватает процедуры findPrior. Поэтому не пытайтесь что-то удалять пока не напишите её.

program listexample;

uses CRT;

type
  plist = ^tlist;
  tlist = record
            data : integer;
            next : plist
  end;

var
  list, start : plist;
  i : integer;

procedure Add (d : integer);
var
 l : plist;
begin
  New (l);
  l^.data := d;
  l^.next := nil;

  if start <> nil then
  begin
     list := start;

     while list^.next <> nil do
        list := list^.next;
     list^.next := l
  end
  else
     start := l;
  list := l
end;

procedure Display;
begin
  if start = nil then
  begin
    writeLn ('‹Ёбв Їгбв');
    exit
  end;

  list := start;

  while list <> nil do
  begin
   write (#32, list^.data);
   list := list^.next
  end
end;

procedure Clean;
var
  l : plist;
begin
  if start = nil then
    exit;

  list := start;

  while list <> nil do
  begin
     l := list;
     list := list^.next;
     Dispose (l)
  end;
  start := nil
end;

procedure Delete;
var
  l : plist;
begin
  if start = nil then
    exit;

  l := list^.next;

  if list <> nil then
  begin
    list^.next := l^.next;
    Dispose (l)
  end
  else
  begin
    list := start^.next;
    Dispose (start);
    start := list
  end
end;

procedure Search (d : integer);
var
  flag : boolean;
begin
  list := start;
  flag := false;

  while (list <> nil) and (not flag) do
  begin
     if d = list^.data then
       flag := true
     else
      list := list^.next
  end
end;

procedure findPrior;
begin
  **** ERROR ****
end;


begin
  while true do
  begin
     ClrScr;
     writeLn ('Џа®Ја ¬¬  ¤«п а Ў®вл б® бўп§ л¬ бЇЁбЄ®¬');
     writeLn ('1 - ¤®Ў ўЁвм н«Ґ¬Ґв');
     writeLn ('2 -  ©вЁ Ё г¤ «Ёвм н«Ґ¬Ґв');
     writeLn ('3 - ®зЁбвЁвм бЇЁб®Є');
     writeLn ('4 - ўлўҐбвЁ бЇЁб®Є');
     writeLn ('5 - ўле®¤');
     writeLn ('>>>>>');
     Display;
     gotoxy (7, 7);
     readLn (i);
     gotoxy (1, 9);

     case i of
      1 :  begin
             write ('‚ўҐ¤ЁвҐ зЁб«®: ');
             readLn (i);
             Add (i)
           end;
      2 : begin
            write ('‚ўҐ¤ЁвҐ зЁб«®: ');
            readLn (i);
            Search (i);
            if list = nil then
            begin
             writeLn ('ЌҐ  ©¤Ґ®');
             readLn;
             continue
            end;
            findPrior;
            Delete;
           end;
       3 : Clean;
       4 : begin
            ClrScr;
            Display;
            readLn;
           end;
       5 : begin
            Clean;
            break
         end
     end
  end
end.

Послесловие

В следующий раз мы продолжим заниматься списками.
До встречи.

[Назад] [Содержание] [Дальше]