Структуры и алгоритмы обработки данных

       

Линейные списки


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

Рис. 1.1. Линейный список (связанный список)

В языке Turbo Pascal предусмотрены два типа указателей v типизированные и не типизированные указатели. В случае линейного списка описание данных может выглядеть следующим образом.

type

element = record

                   data:string;

                   next: pointer;

       end;

var

       head: pointer;

       current, last : ^element;



В данном примере элемент списка описан как запись, содержащая два поля. Поле data строкового типа служит для размещения данных в элементе списка. Другое поле next представляет собой не типизированный указатель, который служит для организации списковой структуры.

В описании переменных описаны три указателя head, last и current. Head является не типизированным указателем. Указатель current является типизированным указателем, что позволяет через него организовать доступ к полям внутри элемента, имеющего тип element. Для объявления типизированного указателя обычно используется символ ^, размещаемый непосредственно перед соответствующим типом данных. Однако описание типизированного указателя еще не означает создание элемента списка. Рассмотрим, как можно осуществить создание элементов и их объединение в список.

В системе программирования Turbo Pascal для размещения динамических переменных используется специальная область памяти heap-область¦.
Heap-область размещается в памяти компьютера следом за областью памяти, которую занимает программа и статические данные, и может рассматриваться как сплошной массив, состоящий из байтов.

Попробуем создать первый элемент списка. Это можно осуществить при помощи процедуры New

New(Current);

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

Current^.data:= -данные в первом элементе списка - ;

Сurrent^.next:=nil;

Значение указателя nil означает пустой указатель. Обратим внимание на разницу между присвоением значения указателю и данным, на которые он указывает. Для указателей допустимы только операции присваивания и сравнения. Указателю можно присваивать значение указателя того же типа или константу nil. Данным можно присвоить значения, соответствующие декларируемым типам данных. Для того чтобы присвоить значение данным, после указателя используется символ ^. Поле Сurrent^.next само является указателем, доступ к его содержимому осуществляется через указатель Current.

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

Head:=Current;

New(last);

Last^.data:= -данные во втором элементе списка - ;

Last^.next:=nil;

Сurrent^.next:=nil;

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

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


Самым простым способом удаления элемента из списка является переопределение указателей, связанных с данным элементом (указывающих на него). Однако сам элемент данных при этом продолжает занимать память, хотя доступ к нему будет навсегда утерян. Для корректной работы с динамическими структурами следует освобождать память при удалении элемента структуры. В языке TurboPascal для этого можно использовать функцию Dispose. Покажем, как следует корректно удалить первый элемент нашего списка.

Head:=last;

Dispose(current);

Рассмотрим пример более сложной организации списка. Линейный список неудобен тем, что при попытке вставить некоторый элемент перед текущим элементом требуется обойти почти весь список, начиная с заголовка, чтобы изменить значение указателя в предыдущем элементе списка. Чтобы устранить данный недостаток введем второй указатель в каждом элементе списка. Первый указатель связывает данный элемент со следующим, а второй v с предыдущим. Такая организация динамической структуры данных получила название линейного двунаправленного списка (двусвязанного списка).



Рис.1.2. Двунаправленный список

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

Приведем пример программы, которая выполняет следующие операции с двунаправленным линейным списком:

добавление (справа и слева от текущего);

удаление (справа и слева от текущего);

поиск;

вывод списка.

program;

           type   element = record

                   data:string;

                   last, next: pointer;



          end;

var

        i,n: integer;

       head: pointer;

       current, pnt, pnt2: ^element;

       s:string;

begin

new(current);

head:=current;

current^.data:=head;

current^.next:=nil;

current^.last:=nil;

repeat

        writeln(-1 v сделать текущим-);

        writeln(-2 v список элементов-);

        writeln(-3 v добавить справа-);

        writeln(-4 v добавить слева-);

        writeln(-5 v удалить текущий-);

        writeln(-6 v удалить справа от текущего-);

        writeln(-7 v удалить слева от текущего-);

        writeln(-0 v выход-);

        writeln(-текущий элемент: -, current^.data);

        readln(n);

       if n=1 then

{Выбор нового текущего элемента}

       begin

             writeln(--); readln(s);

             pnt:=head;

            repeat

                     if pnt^.data=s then current:=pnt;

                    pnt:=pnt^.next;

           until pnt=nil;

      end;

      if n=2 then

     {Вывод всех элементов}



      begin

            pnt:=head; i:=1

            repeat

                      writeln(i, - v -, pnt^.data);

                       pnt:=pnt^.next;

                       i:=i+1;

           until pnt=nil;

      end;

      if n=3 then

{ Добавление нового элемента справа от текущего}

      begin

              writeln(-элемент-); readln(s);

              new(pnt);

              pnt^.data:=s;

              pnt^.last:=current;

              pnt^.next:=current^.next;

              pnt2:=current^.next;

              if not(pnt2=nil) then pnt2^.last:=pnt;

      end;

      if n=4 then

{Добавление нового элемента слева от текущего}

       begin

             writeln(-элемент-); readln(s);

             new(pnt);

             pnt^.data:=s;



             pnt^.last:=current^.last;

             pnt^.next:=current;

             pnt2:=current^.last;

             if not(pnt2=nil) then pnt2^.next:=pnt;

       end;

       if n=5 and not(current=head) then

  {Удаление текущего элемента}

       begin

              pnt:=current^.last;

              pnt^.next:=current^next;

              pnt2:=current^.next;

              if not(pnt2=nil) then pnt2^.last:=current^.last;

              dispose(current);

       end;

       if n=6 and not(current^.next=nil) then

{ Удаление элемента справа от текущего}

       begin

               pnt:=current^.next;

               current^.next:=pnt^next;

               pnt2:=pnt^.next;

               if not(pnt2=nil) then pnt2^.last:=current;

              dispose(pnt);

       end;

       if n=7 and not(current^.last=head) and not(current^.last=nil) then



{Удаление элемента слева от текущего}

      begin

              pnt:=current^.last;

              current^.last:=pnt^.last;

              pnt2:=pnt^.last;

              if not(pnt2=nil) then pnt2^.next:=current;

              dispose(pnt);

      end;

until n=0;

end.

В данной программе реализован алгоритм поиска элемента в списке (сделать текущим). В процессе поиска происходит обход с начала списка. Наличие указателя на заголовок списка ускоряет процесс поиска, так как не требуется сначала найти первый элемент, а затем - сделать обход списка.




Содержание раздела