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

Чтение книги онлайн.

СКАЧАТЬ не один, а несколько указателей и несколько полей данных. Поле данных может быть переменной, массивом, множеством или записью.

      Если в указующей части содержится адрес одного элемента списка, то список называется однонаправленным (или односвязным). Если же он содержит две компоненты, то двусвязным. Над списками можно проводить различные операции, например:

      1) добавление элемента к списку;

      2) удаление элемента из списка с заданным ключом;

      3) поиск элемента с заданным значением ключевого поля;

      4) сортировка элементов списка;

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

      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);

СКАЧАТЬ