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

[tserega]

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

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

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

Рассмотрим примеры реализации динамических линейных связанных структур данных. Прежде всего, советую ознакомиться с этой статьей: Указатели (Pointers)
Замечание: во преки расхожему мнению, список не является структурой данных. Это всего лишь идея, метод решения. На основе списка построены настоящие структуры данных - стеки (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 ее адрес также будет удален из стека.
Стеком также удобно сделать проверку корректности скобочного выражения: Анализ скобочной структуры

Очередь
Название структуры соответсвует ее смыслу. Представьте себе очередь (не толпу!) людей. Тот, кто первый пришел, первый и выйдет. Часто очередь называют струкурой 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.

[Romtek]

Пример работы со стеком.

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

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.

Сообщение отредактировано: romtek - 29.05.04, 09:51

[GazOn]

Стеки

Организация стека в определенном смысле противоположна организации очереди, поскольку здесь используется доступ по принципу "последней пошел, первый вышел" (такой метод доступа иногда называют методом LIFO ). Представим себе стопку тарелок. Нижняя тарелка из этой стопки будет использована последней, а верхняя тарелка (которая была установлена в стопку последней) будет использована первой. Стеки широко используются в системном программном обеспечении, включая компиляторы и интерпретаторы.
Исторически сложилось так, что две основные операции для стека - поместить в стек и выбрать из стека - получили название соответственно "затолкнуть" и "вытолкнуть". Поэтому для реализации стека необходимо создать две функции: "push" (затолкнуть), которая помещает элемент в вершину стека, и "pop" (вытолкнуть), которая выбирает из вершины стека значение.
Необходимо также предусмотреть определенную область в памяти, где фактически будет храниться стек. Для этого можно использовать массив или можно выделить область памяти, используя средство динамического распределения памяти, предусмотренное в языке Турбо Паскаль. Как и при работе с очередью при выборке значения из стека элемент будет потерян, если его не сохранить где-нибудь в памяти.
Ниже приводится общая форма процедур установки в стек и выборки из стека.

Const
  MAX = 100;
 
Var
  stack: array [1..100] Of integer;
  tos: integer; {помещение объекта в стек}
 
Procedure Push (i:integer);
Begin
  If tos>=MAX Then WriteLn('Стек пуст')
  Else
    Begin
      stack[tos] := i;
      tos := tos+1;
    End;
End; {конец процедуры помещения объекта в стек}
{ выборка объекта из стека }
 
Function Pop: integer;
Begin
  tos := tos-1;
  If tos<1 Then
    Begin
      WriteLn('Стек переполнен');
      tos := tos+1;
      Pop := 0;
    End
  Else Pop := stack[tos];
End;{конец функции выборки объекта из стека}

Переменная "tos" содержит значение индекса для следующего помещаемого в стек элемента. При реализации этих процедур никогда нельзя забывать о проверке ситуаций переполнения стека и выборки из пустого стека. В приведенных процедурах нулевое значение указателя "tos" означает, что стек пуст, а значение этого указателя, равное или превышающее адрес последней ячейки памяти, где содержится стек, означает заполнение стека. Рис.7 иллюстрирует работу стека.

Операция         Содержимое стека
Push (A)                 A
Push (В)                 B A
Push (С)                 C B A
Pop, выбирается С        В А
Push(F)                  F B A
Pop, выбирается F        B A
Pop, выбирается В        А
Рор, выбирается А        пусто

Рис.7. Работа стека.

Хорошим примером применения стека является калькулятор, который может выполнять четыре действия. Большинство калькуляторов используют стандартную форму выражений, которая носит название инфиксной формы. В общем виде ее можно представить в виде "операнд-оператор-операнд".
Например, для прибавления 100 к 200 вы должны ввести число 100, набрать символ сложения, ввести число 200 и нажать клавишу со знаком равенства. Однако, некоторые каль- куляторы применяют другую форму выражений, получившую название постфиксной формы. В этом случае оба операнда вводятся перед вводом оператора. Например, для добавления 100 к 200 при использовании постфиксной формы сначала вводится число 100, затем вводится число 200 и после этого нажимается клавиша со знаком плюс. Введенные операнды помещаются в стек. При вводе оператора из стека выбираются два операнда и результат помещается в стек. При использовании постфиксной формы очень сложные выражения могут легко вычисляться на калькуляторе.

Ниже показана программа для такого калькулятора.

{калькулятор с четырьмя операциями, иллюстрирующий работу}
 
Program four_function_calc;
 
Const
  MAX = 100;
 
 
Var
  stack: array [1..100] Of integer;
  tos: integer;{указатель вершины стека}
  a, b: integer;
  s: string[80];
{поместить объект в стек}
 
Procedure Push(i:integer);
Begin
  If tos >= MAX Then Writeln('Стек полон')
  Else
    Begin
      stack[tos] := 1;
      tos := tos+1;
    End;
End;{Push}
{выборка объекта из стека}
 
Function Pop: integer;
Begin
  tos := tos-1;
  If tos < 1 Then
    Begin
      Writeln('Стек переполнен');
      tos := tos+1;
      Pop := 0;
    End
  Else Pop := stack[tos];
End;{Pop}
Begin{калькулятор}
  tos := 1;
  Writeln('For Function Calculator');
  Repeat
    Write(': '); { вывод приглашения }
    Readln(s);
    Val(s, a, b); { преобразование строки символов в целое число }
{ считается, что при успешном преобразовании пользователь ввел число,
 а в противном случае пользователь ввел оператор}
 
    If (b=0) And ((Length(s)>1) Or (s[1]<>'-')) Then
      Push(a)
    Else
      Case s[1] Of
        '+':
        Begin
          a := Pop;
          b := Pop;
          Writeln(a+b);
          Push(a+b);
        End;
        '-':
        Begin
          a := Pop;
          b := Pop;
          Writeln(b+a);
          Push(b+a);
        End;
        '*':
        Begin
          a := Pop;
          b := Pop;
          Writeln(a*b);
          Push(a*b);
        End;
        '/':
        Begin
          a := Pop;
          b := Pop;
          If a=0 Then Writeln('делим на ноль')
          Else
            Begin
              Writeln(b Div a);
              Push(b Div a);
            End;
        End;
        '.':
        Begin
          a := Pop;
          Writeln(a);
          Push(a);
        End;
      End;
  Until UpCase(s[1])='G';
End.

Для того, чтобы посмотреть, что находится в вершине стека, достаточно ввести точку. Хотя данная программа выполняет арифметические действия только с целыми числами, ее легко можно приспособить для чисел с плавающей запятой, изменяя тип данных стека и преобразуя оператор "div" в оператор деления для чисел с плавающей запятой (наклонная черта).

Сообщение отредактировано: Romtek - 07.04.05, 07:25