Энциклопедия Turbo Pascal. Главы 1-4
Страница 25. Связанные списки с одиночной связью


 

Связанные списки с одиночной связью

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

       ------¬     ------¬      ------¬
       ¦1info¦     ¦1info¦      ¦1info¦
       +-----+     +-----+      +-----+
       ¦2link¦     ¦2link¦      ¦3 nil¦
       L------     L------      L------
     Рис.8. Расположение списка с одиночной связью в памяти:
1 - информация; 2 - указатель связи; 3 - нуль.
     Имеется два способа построения списка с одиночной  связью. В
первом случае каждый новый элемент добавляется в начало или в ко-
нец списка.  Во втором случае каждый элемент добавляется  в  свое
место в списке /например,  так, чтобы обеспечить упорядочность по
возрастанию/.
     Способ построения  списка определяется процедурой постановки
нового элемента в список. Ниже дается такая процедура для просто-
го случая,  когда элементы добавляются в конец списка. Необходимо
определить запись, которая будет содержать информацию и указатели
связи.  В  этом примере запись содержит адрес почтовой корреспон-
денции.  Тип записи для каждого элемента в списке адресов опреде-
ляется ниже:
     AddrPointer = ^address;
     address = record
       name:   string[30];
       street: string[40];
       city:   string[20];
          state: string[2];
          zip:   string[9];
          next:  AddrPointer;  { указатель на следующую запись  }
       end;
       DataItem = address;
     var
       start.last: AddrPointer;
     Ниже представлена   функция  добавления  в  список  с  одной
связью,  когда каждый новый элемент помещается  в  конец  списка.
Указатель  записи  типа  "address" должен передаваться в качестве
аргумента функции:
     { добавление  в  список с одной связью }
     procedure SL_Store(i: AddrPointer);
     Legin
       if last=nil then  { первый элемент списка } 2
       begin
         last := i;
         start := i;
         i^.next := nil;
       end else
       begin
         last^.next := i;
         i^.next := nil;
         last := i;

       end;
     end;  { конец процедуры добавления элементов в список с
                        одной связью }

     Следует помнить, что до первого обращения к этой функции пе-
ременные  "start"  и  "last"  должны быть установлены на значение
"nil".
     Можно предусмотреть отдельную операцию по сортировке списка,
созданного с помощью указанной  функции  добавления  элементов  в
список с одной связью. Однако упорядочения легче добиться во вре-
мя вставки путем установки каждого нового элемента в соответству-
ющее место списка.  Кроме того, если список уже является отсорти-
рованным,  то имеет смысл сохранить его упорядоченность, вставляя
каждый  новый  элемент в соответствующее место списка.  Для этого
делается последовательный просмотр списка до тех пор, пока не бу-
дет  найдено нужное место.  В это место вставляется новый адрес и
делается соответствующее изменение связей.
     При вставке элемента в список с одной связью может воникнуть
одна из трех ситуаций.  Во-первых,  новый элемент может оказаться
первым в списке.  Во-вторых,  он может встать между другими двумя
элементами и в-третьих,  он может оказаться последним элементом в
списке.  На рис.9 показано, как для каждого из этих случаев изме-
няются связи.
     Если изменяется первый элемент списка,  то везде в программе
должна быть изменена точка входа в список.  Для того, чтобы избе-
жать  этого,  в качестве первого элемента нужно использовать фик-
тивный элемент.  Этот фиктивный элемент должен иметь такое значе-
ние,  которое  обеспечивает  ему  первое  место в списке.  В этом
случае точка входа в список не будет меняться.  Однако, недостат-
ком  такого  метода является необходимость расхода дополнительной
памяти для фиктивного элемента и  поэтому  в  показанном  примере
этот метод не используется.

      1 Новый первый элемент
            ------¬                         ------¬
            ¦2 new¦                         ¦2 new¦
            +-----+                         +-----+
            ¦     ¦                         ¦     ¦
            L------                         L------
                            4becomes
   ------¬  ------¬  ------¬       ------¬  ------¬  ------¬
   ¦3info¦  ¦3info¦  ¦3info¦       ¦3info¦  ¦3info¦  ¦3info¦
   +-----+  +-----+  +-----+       +-----+  +-----+  +-----+
   ¦     ¦  ¦     ¦  ¦5 nil¦       ¦     ¦  ¦     ¦  ¦5 nil¦
   L------  L------  L------       L------  L------  L------

     6 New Middle Item
            ------¬                         ------¬
            ¦2 new¦                         ¦2 new¦
            +-----+                         +-----+
            ¦     ¦                         ¦     ¦
            L------                         L------
                            4becomes
   ------¬  ------¬  ------¬       ------¬  ------¬  ------¬
   ¦3info¦  ¦3info¦  ¦3info¦       ¦3info¦  ¦3info¦  ¦3info¦
   +-----+  +-----+  +-----+       +-----+  +-----+  +-----+
   ¦     ¦  ¦     ¦  ¦5 nil¦       ¦     ¦  ¦     ¦  ¦5 nil¦
   L------  L------  L------       L------  L------  L------

      7 New Last Item
            ------¬                         ------¬
            ¦2 new¦                         ¦2 new¦
            +-----+                         +-----+
            ¦     ¦                         ¦5 nil¦
            L------                         L------
                            4becomes
   ------¬  ------¬  ------¬       ------¬  ------¬  ------¬
   ¦3info¦  ¦3info¦  ¦3info¦       ¦3info¦  ¦3info¦  ¦3info¦
   +-----+  +-----+  +-----+       +-----+  +-----+  +-----+
   ¦     ¦  ¦     ¦  ¦5 nil¦       ¦     ¦  ¦     ¦  ¦     ¦
   L------  L------  L------       L------  L------  L------

     Рис.9. Вставка элемента в список с одной связью:

     1 - новый первый элемент;
     2 - новый элемент;
     3 - информационные поля;
     4 - справа дается преобразованный список;
     5 - нулевой указатель связи;
     6 - новый средний элемент;
     7 - новый последний элемент.

     Приводимая ниже функция  используется  для  вставки  адресов
почтовых  корреспонденций  в  порядке  возрастания  фамилий /поле
"name"/.  В качестве результата функции выдается  первый  элемент
списка.  Входными  аргументами этой функции являются указатели на
начало и конец списка.

  { добавление элементов в список с одной связью с сохранением
                упорядоченности }
      function SLS_Store(info, start: AddrPointer;
                        var last: AddrPointer): AddrPointer;
     var
       old, top: AddrPointer;
       done: boolean;
     begin
       top := start;
       old := nil;
       done := FALSE;

       if start=nil then
       begin { первый элемент списка }
         info^.next:=nil;
         last:=info;
         SLS_Store:=info;
       end else
       begin
         while (start<>nil) and (not done) do
       begin
         if start^.name < info^.name then
         begin
           old:=start;
           start:=start^.next;
         end else
         begin { вставка в середину }
           if old<>nil then

          begin
            old^.next:=info;
            info^.next:=start;
            SLS_Store:=top; { сохранить начало  }
            done:=TRUE;
          end else
          begin
            info^.next:=start; { новый первый элемент }
            SLS_Store:=info;
            done:=TRUE;
          end;
        end;
       end; {while}
       if not done then
       begin
         last^.next:=info; { вставка в конец }
         info^.next:=nil;
         last:=info;
         SLS_Store:=top;
       end;
      end;
     end;
{ конец процедуры упорядоченной вставки в список с одной связью}

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

     procedure Display(start: AddrPointer);
     begin
       while start<>nil do begin
         WriteLn(start^.name);
         start:=start^.next;
       end;
     end;  { конец процедуры вывода}

     Здесь переменная  "start"  является указателем на первую за-
пись в списке.
     Поиск элемента в списке представляет собой простую процедуру
прохода по цепочке.  Процедуру поиска адресов по  фамилиям  можно
составить следующим образом:

    function Search(start:AddrPointer;name:str80):AddrPointer;
    var
      done:boolean;
    begin
      done := FALSE;
      while (start<>nil) and (not done) do
    begin
      if name=start^.name then
      begin
        Search:=start;
        done:=TRUE;
      end else
        start:=start^.next;
      end;
      if start=nil then Search := nil; { нет в списке }
    end; { конец процедуры поиска элемента }

     Поскольку эта процедура поиска в результате выдает указатель
на тот элемент списка, который соответствует искомой фамилии, пе-
ременная  "Search"  должна  объявляться как указатель записи типа
"address".  Если требуемый элемент отсутствует в списке, то в ре-
зультате выдается нулевой указатель.
     Процедура удаления элемента из списка с одной  связью  прог-
раммируется  просто.  Как при вставке элемента здесь может встре-
титься один из трех случаев:  удаляется первый элемент, удаляется
средний элемент и удаляется последний элемент.  На рис.10 иллюст-
рируется каждая ситуация.

     1 Deleting the First Item   2becomes
       ------¬  ------¬  ------¬     ------¬  ------¬  ------¬
       ¦3info¦  ¦3info¦  ¦3info¦     ¦3info¦  ¦3info¦  ¦3info¦
       +-----+  +-----+  +-----+     +-----+  +-----+  +-----+
       ¦     ¦  ¦     ¦  ¦5 nil¦     ¦5 nil¦  ¦     ¦  ¦5 nil¦
       L------  L------  L------     L------  L------  L------

     6 Deleting a Middle Item    2becomes
       ------¬  ------¬  ------¬     ------¬  ------¬  ------¬
       ¦3info¦  ¦3info¦  ¦3info¦     ¦3info¦  ¦     ¦  ¦3info¦
       +-----+  +-----+  +-----+     +-----+  +-----+  +-----+
       ¦     ¦  ¦     ¦  ¦5nil ¦     ¦     ¦  ¦5 nil¦  ¦5 nil¦
       L------  L------  L------     L------  L------  L------

     7 Deleting the Last Item    2becomes
       ------¬  ------¬  ------¬     ------¬  ------¬  ------¬
       ¦3info¦  ¦3info¦  ¦3info¦     ¦3info¦  ¦3info¦  ¦     ¦
       +-----+  +-----+  +-----+     +-----+  +-----+  +-----+
       ¦     ¦  ¦     ¦  ¦5 nil¦     ¦     ¦  ¦5 nil¦  ¦5 nil¦
       L------  L------  L------     L------  L------  L------

     Рис.10. Удаление элемента из списка с одной связью:

1 - удаление первого элемента;
2 - левый список преобразуется в правый;
3 - информационные поля;
4 - удаленный элемент;
5 - связь с нулевым значением;
6 - удаление среднего элемента;
7 - удаление последнего элемента.

     Приводимая ниже функция выполняет удаление заданного элемен-
та из списка записей адресов:

     function SL_Delete(start, item, prior_item: AddrPointer)
                        :AddrPointer;
     begin
       if prior_item<>nil then
         prior_item^.next:=item^.next
       else start:= item^.next;
       SL_Delete:=start;
     end;  { конец функции удаления элемента из списка с одной
                           связью }

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

 
« Предыдущая статья