Занятие №15. Часть 2: Динамические структуры данных: стеки и очереди

На занятии происходит с понятием динамические структуры данных; будут рассмотрены стеки, очереди, деки и деревья в паскале

Стеки

Стек — динамическая структура данных, в которой добавление и удаление элементов доступно только с одного конца (с верхнего (последнего) элемента).

Существуют такие сокращения:

  • LIFO = Last In -> First Out — с английского языка «Кто последним вошел, тот первым вышел»
  • FILO = First In -> Last Out — «первым вошел, последним вышел»
  • Последовательные этапы засылки в стек чисел 1, 2, 3.

    Последовательные этапы засылки в стек чисел 1, 2, 3

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

    • добавление в стек нового элемента;
    • add(<нач_стека>,<новый_элемент>):<нач_стека>
    • определение пуст ли стек;
    • empty(<нач_стека>):boolean
    • доступ к последнему включенному элементу, вершине стека;
    • take(<нач_стека>):<тип_элементов_стека>
    • исключение из стека последнего включенного элемента.
    • del(<нач_стека>):<нач_стека>

    Создание структуры узла:

    type PNode = ^Node; { указатель на узел }
         Node = record
           data: char;  { полезная }
           next: PNode; { указатель на след. элемент }
         end;

    Добавление элемента в стек:

    procedure Push( var Head: PNode; x: char);
    var NewNode: PNode;
    begin
      New(NewNode);          { выделение памяти }
      NewNode^.data := x;    { запись символа }
      NewNode^.next := Head; { сделать первым узлом }
      Head := NewNode;
    end;

    Забор элемента с вершины:

    function Pop ( var Head: PNode ): char;
    var q: PNode;
    begin
      if Head = nil then begin { если стек пустой } 
        Result := char(255); { неиспользуемый символ, т.е. ошибка }
        Exit;
      end;
      Result := Head^.data;  { берем верхний символ }
      q := Head;             { запоминаем вершину } 
      Head := Head^.next; { удаляем вершину }
      Dispose(q);            { удаление из памяти }
    end;

    Проверка, пустой ли стек:

    function isEmptyStack ( S: Stack ): Boolean;
    begin
      Result := (S = nil);
    end;

    Объявления в основной программе:

    var S: PNode;
    ...
    S := nil;

    Рассмотрим подробную работу со стеком на примере:

    Пример: вводится символьная строка, в которой записаны теги в угловых скобках (<>). Определить, верно ли расставлены скобки (не обращая внимания на остальные символы).
    пример работы со стеком

    Алгоритм выполнения задания:

    1. изначально стек пустой;
    2. в цикле просматриваем каждый символ строки;
    3. если текущий символ – открывающая угловая скобка, то вставляем ее на вершину стека;
    4. если текущий символ – закрывающая угловая скобка, то проверяем верхний элемент стека: там должна находиться открывающая угловая скобка (иначе — ошибка);
    5. в конце стек должен стать пустым, иначе — ошибка.

    Создаем структуру стека:

    const MAXSIZE = 50;
    type Stack = record  { стек рассчитан на 50 символов }
          tags: array[1..MAXSIZE] of char;
          size: integer; { число элементов }
         end;

    Процедура добавления элемента в стек:

    procedure Push( var S: Stack; x: char);
    begin
      if S.size = MAXSIZE then Exit;  // выход, если произошло переполнение стека
      S.size := S.size + 1;
      S.tags[S.size] := x; // добавляем элемент
    end;

    Функция взятия элемента с вершины:

    function Pop ( var S:Stack ): char;
    begin
      if S.size = 0 then begin
        Result := char(255); // 255 - пустой символ, ошибка - стек пуст
        Exit;
      end;
      Result := S.tags[S.size];
      S.size := S.size - 1;
    end;

    Создаем функцию для проверки, пустой ли стек:

    function isEmptyStack ( S: Stack ): Boolean;
    begin
      Result := (S.size = 0);
    end;

    Основная программа:

    var  expr: string;
        br1, br2: char;  { угловые скобки }
        i, k: integer;
        upper: char;    { верхний символ, снятый со стека }
        error: Boolean; { признак ошибки }
        S: Stack;
    begin
      br1 := '<'; br2 := '>';
      S.size := 0;
      error := False;
      writeln('Введите html-текст');
      readln(expr);
      ...  { здесь вставляется цикл с обработкой строки } 
      if not error  and  isEmptyStack(S) then
           writeln('Текст верный.')
      else writeln('Текст составлен неверно.')
    end.

    Обработка строки в цикле:

    for i:=1 to length(expr) { проходимся по всем символам строки expr }
     do begin
     
          if expr[i] = br1 then begin { открывающая скобка < }
            Push(S, expr[i]); { втолкнуть в стек }
            break;
          end;
          if expr[i] = br2  then begin { закрывающая скобка < }
            upper := Pop(S); { снять символ со стека }
            error := upper <> br1; { ошибка: стек пуст или не та скобка }
            break;
          end;
     
        if error then break; // была ошибка, значит, прерываем цикл
      end;

    Очереди

    Очередь — динамическая структура данных, у которой в каждый момент времени доступны только два элемента: первый и последний. Добавление элементов возможно только с одного конца (конца очереди), а удаление элементов – только с другого конца (начала очереди).

    Существует сокращение для очереди: FIFO = First In – First Out, с английского — «Кто первым вошел, тот первым вышел».

    Для очереди доступны следующие операции:

    • добавить элемент в конец очереди (PushTail);
    • удалить элемент с начала очереди (Pop).

    Работа с очередью обычным массивом:
    Это достаточно простой способ, который подразумевает два неблагоприятных момента: заблаговременное выделение массива, сдвиг элементов при удалении из очереди.
    очередь

    Работа с очередью с помощью кольцевого массива:

    очередь через кольцевой массив

    Если в очереди 1 элемент:
    1

    Если очередь пуста:
    2

    Если очередь заполнена:

    Определение размера массива (при пустой и заполненной очереди):
    3

    Очередь в Паскале (использование кольцевого массива)

    Создание структуры:
    структура очереди

    type Queue = record
           data: array[1..MAXSIZE] of integer;
           head, tail: integer;
         end;

    Как добавить в очередь:
    2

    procedure PushTail( var Q: Queue; x: integer);
    begin
      if Q.head = (Q.tail+1) mod MAXSIZE + 1 
        then Exit; { очередь уже полна }
      Q.tail := Q.tail mod MAXSIZE + 1;
      Q.data[Q.tail] := x;
    end;

    Как выбрать из очереди:
    3

    function Pop ( var S: Queue ): integer;
    begin
      if Q.head = Q.tail mod MAXSIZE + 1 then begin
        Result := MaxInt;
        Exit;
      end;
      Result := Q.data[Q.head];
      Q.head := Q.head mod MAXSIZE + 1;
    end;

    Создание очереди посредством списка

    Объявление узла:
    Объявление узла
    2

    1
    2
    3
    4
    5
    6
    7
    8
    
    type PNode = ^Node;
         Node = record
           data: integer;
           next: PNode;
         end;
    type Queue = record
           head, tail: PNode;
         end;

    Добавляем новый элемент:
    добавление элемента в очередь

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    
    procedure PushTail( var Q: Queue; x: integer );
    var NewNode: PNode;
    begin
      New(NewNode);
      NewNode^.data := x;
      NewNode^.next := nil;
      if Q.tail <> nil then
        Q.tail^.next := NewNode;
      Q.tail := NewNode; 
      if Q.head = nil then Q.head := Q.tail;
    end;

    Выбираем элемент из списка:
    Без имени

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    
    function Pop ( var S: Queue ): integer;
    var top: PNode;
    begin
      if Q.head = nil then begin
        Result := MaxInt;
        Exit;
      end;
      top := Q.head;
      Result := top^.data;
      Q.head := top^.next;
      if Q.head = nil then Q.tail := nil;
      Dispose(top);
    end;

    Деки

    Дек — англ. double ended queue, т.е. очередь с двумя концами – это динамическая структура данных, добавлять и удалять элементы в которой можно с обоих концов.

    Задание: В файле записан список чисел. Необходимо переписать его в другой файл в обратном порядке.

    Деревья

    Дерево – это структура данных, которая состоит из узлов и соединяющих их направленных ребер или дуг; в каждый узел за исключением корневого ведет только одна дуга.

    • Корнем называется главный или начальный узел дерева.
    • Листом называется узел, из которого не выходят дуги.
    • 1

    • Перечислим некоторые иерархические отношения в дереве:
    • 1 — предок для всех других узлов в дереве
      6 — потомок для узлов 5, 3 и 1
      3 — родитель узлов 4 и 5
      5 — сын узла 3
      5 — брат узла 4

    • Высота дерева определяется как наибольшее расстояние от корня до листа (количество дуг).

    Двоичные деревья

    В двоичном (бинарном) дереве каждый узел имеет не более двух дочерних узлов (сыновей).
    Объявление:
    структура дерева

    type PNode = ^Node;        { указатель на узел } 
         Node = record
           data: integer;      { данные }
           left, right: PNode; 
         end;

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

    Пример: Найти в дереве ключ, равный k.

    Алгоритм решения:

    • если дерево пустое, значит, ключ не найден;
    • если ключ узла равен k, то остановка;
    • если ключ узла меньше k, то искать k в левом поддереве;
    • если ключ узла больше k, то искать k в правом поддереве.

    Сравним поиск в массиве c n элементами с поиском в бинарном дереве:

    Поиск в массиве: каждое сравнение - отбрасываем 1 элемент. Число сравнений – N.

    Поиск в массиве: каждое сравнение — отбрасываем 1 элемент.
    Число сравнений – N.

    При каждом сравнении отбрасывается половина оставшихся элементов. Число сравнений ~ log2N

    При каждом сравнении отбрасывается половина оставшихся элементов.
    Число сравнений ~ log2N

    Поиск в бинарном дереве на Паскале:

    Создадим функцию для поиска. На вход функции из главной программы подаются два параметра: tree — адрес корня дерева и x — искомое число. Функция возвращает адрес узла с искомым значением или nil, если ничего не найдено.

    поиск в бинарном дереве

    function SearchInTree(Tree: PNode; x: integer): PNode;
    begin
      if Tree = nil then begin
        Result := nil;
        Exit;
      end;
      if x = Tree^.data then
         Result := Tree
      else
      if x < Tree^.data then
           Result := SearchInTree(Tree^.left, x)
      else Result := SearchInTree(Tree^.right, x);
    end;

    Создание дерева поиска:

    Для создания дерева воспользуемся процедурой с двумя параметрами: tree — адрес корня дерева, x — добавляемый элемент.
    создание дерева поиска на паскале

    procedure AddToTree( var Tree: PNode; x: integer );
    begin
      if Tree = nil then begin
        New(Tree);
        Tree^.data := x;
        Tree^.left := nil;
        Tree^.right := nil;
        Exit;
      end;
      if x < Tree^.data then
           AddToTree(Tree^.left, x)
      else AddToTree(Tree^.right, x);
    end;

    Обход дерева:
    Данное действие необходимо для перечисления всех узлов в определенном порядке.

    Рассмотрим варианты обхода:
    ключи в дереве

  • обход ЛКП или левый – корень – правый: 16, 30, 45, 59, 76, 98, 125;
  • обход ПКЛ или правый – корень – левый: 125, 98, 76, 59, 45, 30, 16;
  • обход КЛП или корень – левый – правый: 59, 30, 16, 45, 98, 76, 125;
  • обход ЛПК или левый – правый – корень: 16, 45, 30, 76, 125, 98, 59.
  • Создадим процедуру для обхода ЛКП дерева. Процедура имеет один параметр — tree — адрес корня.
    обход дерева на паскале

    procedure LKPObhod(Tree: PNode);
    begin
      if Tree = nil then Exit;
      LKPObhod(Tree^.left);
      write(' ', Tree^.data);
      LKPObhod(Tree^.right);
    end;
    Поделитесь уроком с коллегами и друзьями:

    Добавить комментарий

    Ваш e-mail не будет опубликован. Обязательные поля помечены *

    *
    *

    Вставить формулу как
    Блок
    Строка
    Дополнительные настройки
    Цвет формулы
    Цвет текста
    #333333
    Используйте LaTeX для набора формулы
    Предпросмотр
    \({}\)
    Формула не набрана
    Вставить