Основы программирования в паскале

     Часто требуется, чтобы структуры данных меняли свои размеры в ходе решения  задачи. Такие структуры данных называются динамическими, к ним относятся стеки, очереди, списки, деревья и другие. Описание динамических структур с помощью массивов, записей и файлов приводит к неэкономному использованию памяти ЭВМ и увеличивает время решения задач.

     Каждая  компонента любой  динамической структуры  представляет собой  запись, содержащую по крайней мере два  поля: одно поле типа указатель, а второе - для размещения данных.

     В общем случае запись может содержать  не один, а несколько укзателей  и несколько полей данных. Поле данных может быть переменной, массивом, множеством или записью.

     Для дальнейшего рассмотрения представим отдельную компоненту в виде: 

     

     где поле p - указатель; поле D - данные.  

     Описание  этой компоненты дадим следующим  образом:

     (на доске)

     //

       type

         Pointer = ^Comp;

         Comp = record

                 D:T;

                 pNext:Pointer

              end;

     здесь T - тип данных. Рассмотрим основные правила работы с динамическими  структурами данных типа стек, очередь  и список, базируясь на приведенное  описание компоненты.

     //

     1.5 СТЕКИ

     Стеком  называется динамическая структура  данных, добавление компоненты в которую  и исключение компоненты из которой  производится из одного конца, называемого  вершиной стека.

     Стек  работает по принципу LIFO (Last-In, First-Out) - поступивший последним, обслуживается первым. 

     Обычно  над стеками выполняется  три операции:

1. начальное формирование стека (запись первой компоненты);
2. добавление компоненты в стек;
3. выборка компоненты (удаление).

 

     Для формирования стека  и работы с ним необходимо иметь две переменные типа указатель, первая из которых определяет вершину стека, а вторая - вспомогательная.  

     Пусть описание этих переменных имеет вид:

       var pTop, pAux: Pointer;

     где pTop - указатель вершины стека;

     pAux - вспомогательный указатель. 

     Начальное формирование стека выполняется следующими операторами:

      

       

     Последний оператор или группа операторов записывает содержимое поля данных первой компоненты. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     Добавление  компоненты в стек призводится с  использованием вспомогательного указателя:

     (на доске) 

                           

     

     

                                                                    
 
 
 
 
 
 
 
 
 

     (на  доске)

     Добавление  последующих компонент производится аналогично.

     Рассмотрим  процесс выборки компонент из стека. Пусть к моменту начала выборки стек содержит три компоненты:

                         

     

     Первый  оператор или группа операторов осуществляет чтение данных из компоненты - вершины  стека. Второй оператор изменяет значение указателя вершины стека:

                             

     

     Как видно из рисунка, при чтении компонента удаляется из стека. 

     Пример. Составить программу, которая формирует  стек, добавляет в него произвольное количество компонент, а затем читает все компоненты и выводит их на экран дисплея, В качестве данных взять строку символов. Ввод данных - с клавиатуры дисплея, признак конца ввода - строка символов END.

     Program STACK;

       uses Crt;

       type

        Alfa= String[10];

        PComp= ^Comp;

        Comp= Record

                sD: Alfa;

                pNext: PComp

               end;

       var

        pTop: PComp;

        sC: Alfa;

       Procedure CreateStack(var pTop: PComp; var sC: Alfa);

        begin

         New(pTop);

         pTop^.pNext:=NIL;

         pTop^.sD:=sC

        end;

       Procedure AddComp(var pTop: PComp; var sC: Alfa);

        var pAux: PComp;

        begin

         NEW(pAux);

         pAux^.pNext:=pTop;

         pTop:=pAux;

         pTop^.sD:=sC

        end;

       Procedure DelComp(var pTop: PComp; var sC:ALFA);

        begin

         sC:=pTop^.sD;

         pTop:=pTop^.pNext

        end;

       begin

        Clrscr;

        writeln('  ВВЕДИ СТРОКУ ');

        readln(sC);

        CreateStack(pTop,sC);

        repeat

         writeln('  ВВЕДИ СТРОКУ ');

         readln(sC);

         AddComp(pTop,sC)

        until sC='END';

        writeln('****** ВЫВОД РЕЗУЛЬТАТОВ ******');

        repeat

         DelComp(pTop,sC);

         writeln(sC);

        until pTop = NIL

       end.