Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=54278&view=findpost&p=380027 Sun, 13 Jun 2004 19:26:02 +0000 Линейные структуры данных https://forum.sources.ru/index.php?showtopic=54278&view=findpost&p=380027 Стеки

Организация стека в определенном смысле противоположна организации очереди, поскольку здесь используется доступ по принципу "последней пошел, первый вышел" (такой метод доступа иногда называют методом 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" в оператор деления для чисел с плавающей запятой (наклонная черта).]]> Gazon Pascal: Структуры данных https://forum.sources.ru/index.php?showtopic=54278&view=findpost&p=368554 Sat, 29 May 2004 09:37:43 +0000 Линейные структуры данных https://forum.sources.ru/index.php?showtopic=54278&view=findpost&p=368554 Пример работы со стеком.

Вводятся положительные числа. Введение отрицательного числа означает конец ввода данных.
  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 Pascal: Структуры данных https://forum.sources.ru/index.php?showtopic=54278&view=findpost&p=358916 Sat, 15 May 2004 13:44:52 +0000 Линейные структуры данных https://forum.sources.ru/index.php?showtopic=54278&view=findpost&p=358916 Линейные структуры данных на примере динамических списков

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

Рассмотрим примеры реализации динамических линейных связанных структур данных. Прежде всего, советую ознакомиться с этой статьей: Указатели (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.
]]> tserega Pascal: Структуры данных