Динамические структуры данных в Паскале

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

К оглавлению

Содержание:

Стеки
Очереди
Деревья
- Двоичные деревья

Стеки

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

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

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;

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

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

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

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

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

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 элемент:

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

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

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

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

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

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

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

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;

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

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;

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

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

type PNode = ^Node;
     Node = record
       data: integer;
       next: PNode;
     end;
type Queue = record
       head, tail: PNode;
     end;

Добавляем новый элемент:

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;

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

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 — предок для всех других узлов в дереве
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 — При каждом сравнении отбрасывается половина оставшихся элементов.
Число сравнений ~ log₂N

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

Создадим функцию для поиска. На вход функции из главной программы подаются два параметра: 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;

К оглавлению