На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное DigiMania RSS
msm.ru
! Правила ЧаВО (FAQ) разделов Паскаля
В этом разделе разрешено создавать только темы, в которых описано РЕШЕНИЕ какой-либо общей проблемы, или описание какого-либо аспекта языка Паскаль.
Обсуждение уже созданных тем разрешено, но только конструктивное, например указание на ошибку или уточнение имеющегося текста.

Стоит почитать Структуры данных
Модераторы: volvo877, Romtek
  
> Линейные структуры данных, на примере динамических списков
    Линейные структуры данных на примере динамических списков

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

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

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


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

    Стек - "родная" конструкция для процедурных языков программирования. Каждый вызов процедуры или функции идет через стек (точнее, в стек записывается адрес, с которого вызвали данную функцию).
    Например:
    ExpandedWrap disabled
      procedure A;
      begin
      ...
      end;
      procedure B;
      begin
      ...
      A;
      ...
      end;
      ...
      B;
      ...

    В стек сначала запишется адрес процедуры B, тотом на вершину добавится адрес процедуры A. После выполнения процедуры A ее адрес будет удален из стека. После окончания работы процедуры B ее адрес также будет удален из стека.
    Стеком также удобно сделать проверку корректности скобочного выражения: Анализ скобочной структуры

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


    Двусвязанный список
    По идее двусвязанный список очень похож на обычный список. Единственное отличие - наличие ссылок на предыдущий элемент. Поэтому немного изменятся процедуры добаления и извлечения элементов.
    ExpandedWrap disabled
      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). Тогда такой циклический список называют кольцом с замком.
    ExpandedWrap disabled
      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. Удаляются все элементы стека
      ExpandedWrap disabled
        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 -
        Стеки

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

        Ниже показана программа для такого калькулятора.
        ExpandedWrap disabled
          {калькулятор с четырьмя операциями, иллюстрирующий работу}
           
          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 -
        Чем больше узнаешь, тем больше не знаешь, но до истины всегда можно добраться.
        0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
        0 пользователей:


        Рейтинг@Mail.ru
        [ Script Execution time: 0,1824 ]   [ 17 queries used ]   [ Generated: 21.10.19, 10:03 GMT ]