Информатика и информационные технологии: конспект лекций. А. В. Цветкова

списка на два и более списков;

      6) объединение двух и более списков в один;

      7) другие операции.

      Однако, как правило, необходимости во всех операциях при решении различных задач не возникает. Поэтому в зависимости от основных операций, которые необходимо применить, существуют различные виды списков. Наиболее популярные из них – это стек и очередь.

      2. Стеки

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

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

      1) начальное формирование стека (запись первой компоненты);

      2) добавление компоненты в стек;

      3) выборка компоненты (удаление).

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

      Пример. Составить программу, которая формирует стек, добавляет в него произвольное количество компонент, а затем читает все компоненты и выводит их на экран дисплея. В качестве данных взять строку символов. Ввод данных – с клавиатуры, признак конца ввода – строка символов 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('****** ВЫВОД РЕЗУЛbТАТОВ ******');

      repeat

      DelComp(pTop, sC);

      writeln(sC);

      until pTop = NIL;

      end.

      3. Очереди

      Очередью называется динамическая структура данных, добавление компоненты в которую производится в один конец, а выборка осуществляется с другого конца. Очередь работает по принципу FIFO (First-In, First-Out) – «Поступивший первым, обслуживается первым».