Линейные структуры данных на примере динамических списков

Все структуры данных можно классифицировать по нескольким категориям:

• линейность (линейные - стеки, очереди; нелинейные - графы, деревья)
• связанность (нужно ли физически хранить ссылки на следующий элемент(ы))
• по количеству элементов:
  • статические - количество элементов строго фиксировано
  • частично динамические - количество элементов может меняться, но не превосходит некоторого максимума
  • динамические - количество элементов может быть произвольным

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

Замечание: вопреки расхожему мнению, список не является структурой данных. Это всего лишь идея, метод решения. На основе списка построены настоящие структуры данных - стеки (stack), очереди (queue), дэки (double-ended queue), кольца (ring).

Во всех примерах для реализации списка будет использована такая структура:

Type PElement = ^TElement;
     TElement = Record
      Data : Longint; {данные - целое число}
      Next : PElement; {указатель на следующий элемент}
     End;

Самый простой представитель динамических структур. Представьте себе большую стопку книг. Понятно, что мы не можем достать книгу из самого низа. Для этого требуется снять все книги, которые лежат выше. Такую структуру называют LIFO (Last In - First Out).

Type PElement = ^TElement;
     TElement = Record
      Data : Longint;
      Next : PElement;
     End;
 
Procedure Push(X : Longint; Var S : PElement); {добавление элемента на вершину стека}
Var P : PElement;
Begin
 P:=New(PElement); {создаем временный элемент}
 P^.Data:=X; {присваиваем ему необходимое значение}
 P^.Next:=S; {следующий элемент будет уже готовый стек}
 S:=P; {а вершина стека - только что созданный элемент}
End;
 
Function Pop(Var X : Longint; Var S : PElement) : Boolean; {взятие элемента с вершины стека}
Var P : PElement;
Begin
 If (S = Nil) Then {если стек путой, то возвращать нечего}
  Begin
   X:=0;
   Pop:=False;
  End Else
  Begin
   X:=S^.Data; {запомним значение на вершине стека}
   P:=S;
   S:=S^.Next; {переместим вершину стека на следующий элемент}
   Dispose(P); {уничтожим вытащенный элемент}
  End;
End;
 
{Пример реализации}
Var Stack : PElement;
    X : Longint;
 
Begin
 Stack:=Nil;
 Push(5, Stack);
 Push(13, Stack);
 Push(2, Stack);
 Push(6, Stack);
 Push(20, Stack);
 While (True) Do
  If Pop(X, Stack) Then Writeln(X) Else Break;
End.

Стек - «родная» конструкция для процедурных языков программирования. Каждый вызов процедуры или функции идет через стек (точнее, в стек записывается адрес, с которого вызвали данную функцию). Например:

procedure A;
begin
...
end;
procedure B;
begin
...
A;
...
end;
...
B;
...

В стек сначала запишется адрес процедуры B, потом на вершину добавится адрес процедуры A. После выполнения процедуры A ее адрес будет удален из стека. После окончания работы процедуры B ее адрес также будет удален из стека. Стеком также удобно сделать проверку корректности скобочного выражения: http://forum.sources.ru/index.php?showtopic=42035

Название структуры соответствует ее смыслу. Представьте себе очередь (не толпу!) людей. Тот, кто первый пришел, первый и выйдет. Часто очередь называют структурой FIFO (First In - First Out). В отличии от стека, где добавление и извлечение элементов происходит с одного конца, здесь добавление и удаление происходит с разных концов. Поэтому будем хранить указатели на первый и последний элементы.

Type PElement = ^TElement;
     TElement = Record
      Data : Longint;
      Next : PElement;
     End;
 
     TQueue = Record {сама очередь}
      First, Last : PElement;
     End;
 
Procedure Add(X : Longint; Var Q: TQueue); {добавление элемента в очередь}
Var P : PElement;
Begin
 If (Q.Last = Nil) Then {если очерель пуста, то добавленный элемент будет одновременно первым и последним}
  Begin
   Q.Last:=New(PElement); {создаем элемент}
   Q.First:=Q.Last; {он же первый и последний одновременно}
   Q.Last^.Data:=X;
   Q.Last^.Next:=Nil; {следующего элемента пока нет}
  End Else
  Begin {в очереди уже есть элементы}
   P:=New(PElement); {создаем элемент}
   P^.Data:=X;
   P^.Next:=Nil;
   Q.Last^.Next:=P;
   Q.Last:=P; {добавляем его в конец очереди}
  End;
End;
 
Function Get(Var X : Longint; Var Q : TQueue) : Boolean; {извлечение элемента}
Var P : PElement;
Begin
 If (Q.First = Nil) Then {если очередь пустая, то извлекать нечего}
  Begin
   X:=0;
   Get:=False;
  End Else
  Begin {иначе будем брать первый элемент}
   X:=Q.First^.Data; {запомним его значение}
   P:=Q.First;
   Q.First:=Q.First^.Next; {перейдем на следующий}
   Dispose(P); {уничтожим запомненный}
   Get:=True;
  End;
End;
 
{Пример реализации}
Var Q : TQueue;
    X : Longint;
 
Begin
 Add(5, Q);
 Add(6, Q);
 Add(7, Q);
 Add(8, Q);
 While (True) Do
  If Get(X, Q) Then Writeln(X) Else Break;
End.

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

Type PElement = ^TElement;
     TElement = Record
      Data : Longint;
      Next, Prev : PElement;
     End;
 
Procedure AddAfter(X : Longint; Var L : PElement); {добавление в НЕПУСТОЙ список}
Var P : PElement;
Begin
 P:=New(PElement); {создаем элемент}
 P^.Data:=X;
 If (L^.Next = Nil) Then {надо добавить элемент в конец списка}
  Begin
   L^.Next:=P;
   P^.Prev:=L;
   P^.Next:=Nil;
  End Else
  Begin {надо вставить элемент между двумя}
   P^.Next:=L^.Next;
   L^.Next^.Prev:=P;
   P^.Prev:=L;
   L^.Next:=P;
  End;
End;
 
{Пример реализации}
Var L, P : PElement;
 
Begin
 L:=Nil;
 L:=New(PElement); L^.Next:=Nil; L^.Prev:=Nil; L^.Data:=0; {создаем первый элемент}
 AddAfter(7, L);
 AddAfter(5, L);
 L:=L^.Next;
 AddAfter(3, L);
 While L^.Next <> Nil Do L:=L^.Next;
 While L <> Nil Do
  Begin
   Writeln(L^.Data);
   P:=L;
   L:=L^.Prev;
   Dispose(P);
  End;
End.

Если в списке ссылка последнего элемента указывает на первый, то такой список называют зацикленным (циклическим, или просто кольцом). Понятно, что у такого списка нет ни начала, ни конца. Чтобы определить «начальный» элемент, часто создают элемент, которому приписано специальное значение (например, если это список букв, то элому элементу можно присвоить значение #0, т.е. символ с кодом 0). Тогда такой циклический список называют кольцом с замком.

Type PElement = ^TElement;
     TElement = Record
      Data : Longint;
      Next : PElement;
     End;
 
Procedure Add(X : Longint; Var R : PElement); {добавление элемента в кольцо, эквивалентно вставки элемента между двумя}
Var P : PElement;
Begin
 P:=New(PElement);
 P^.Data:=X;
 P^.Next:=R^.Next;
 R^.Next:=P;
End;
 
{Пример реализации}
Var R, P : PElement;
    I : Longint;
 
Begin
 R:=New(PElement); R^.Data:=0; R^.Next:=R;
 For I:=1 To 4 Do
  Add(I, R);
 I:=0;
 {два раза выведем список}
 While (I < 3) Do
  Begin
   If R^.Data = 0 Then Inc(I) Else Writeln(R^.Data);
   R:=R^.Next;
  End;
 {уничнтожение списка связано с маленьким фокусом: преобразуем колько в линейный список}
 P:=R; {"разорвем" список на одном из элементов}
 R:=R^.Next;
 P^.Next:=Nil;
 {уничтожим как обычный список}
 While R <> Nil Do
  Begin
   P:=R;
   R:=R^.Next;
   Dispose(P);
  End;
End.

Вводятся положительные числа. Введение отрицательного числа означает конец ввода данных.

1. Ввод чисел
2. Выводится стек в обратном порядке введения чисел
3. Выводится отсортированный стек
4. Удаляются все элементы стека

program StackStuff;
 
type PItem = ^stack;
     stack = record
       Value: integer;
       next : PItem;
     end;
var
   top  : PItem;
   count: word;
 
function Correct(var num: integer): boolean; { To check condition }
begin
     readln(num);
     Correct := (Num>=0);
end;
 
procedure FillStack(var P: PItem);
var last: PItem;
    v: integer;
begin
     P:=Nil;
     count:=0;
     while Сorrect(v) do
     begin
          New(last);
 
          last^.next:=P;
          last^.Value:=v;
          P:=last;
 
          inc(count); { increase count of elements }
     end;
end;
 
Procedure SortStack(P: PItem);
Var
 Q    : PItem;
 T    : Integer;
 Done : Boolean;
 
Begin
     Repeat
           Done := True;
           Q := P;
           While Q^.Next <> Nil Do
           Begin
                If Q^.Value > Q^.Next^.Value Then
                Begin
                     { Change values }
                     T := Q^.Value;
                     Q^.Value := Q^.Next^.Value;
                     Q^.Next^.Value := T;
 
                     Done := False;
                End;
                Q := Q^.Next;
           End;
     Until Done;
end;
 
procedure ViewStack(P: PItem);
begin
     write('Stack values: ');
     if P = Nil then
     begin
          write('stack is empty.');
          exit;
     end
     else
     { start from last element }
     repeat
           write(P^.Value : 8);
           P := P^.next;
     until P = Nil;
end;
 
procedure Del_All (var P: PItem); { Deleting of All stack elements }
var Last: PItem;
begin
     repeat
           Last := P;
           P := P^.next;
           Dispose (Last);
     until P = Nil;
end;
 
begin
     writeln (#13#10'Enter positive number (negative to finish)');
     FillStack (Top);
 
     writeln (#13#10'The stack consist of ',count,' numbers.');
     ViewStack (Top);
     readln;
 
     writeln (#13#10'--Sorted stack--');
     SortStack (Top);
     ViewStack (Top);
     readln;
 
     writeln (#13#10'Deleting stack...');
     Del_All (Top);
     ViewStack (Top);
     readln;
end.