4.2. Реализация стека на базе массива

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

type stack = record

buf: array [1..max_size] { Массив элементов. }

of integer;

count: integer; { Количество элементов. }

end;

Инициализация стека осуществляется путем присваивания переменной count значения 0:

{ Операция инициализации стека. }

{ Входные параметры: }

{ s - стек; }

procedure init(var s: stack);

begin

s.count := 0;

end;

При добавлении элемента в стек следует следить за текущим количеством элементов в стеке (оно должно быть больше максимального количества элементов). Сложность операции O(1):

{ Операция добавления нового элемента. }

{ Входные параметры: }

{ s - стек; }

{ item - новый элемент; }

procedure push(var s: stack; item: integer);

begin

{ Если текущее количество элементов меньше }

{ максимального, выполняем добавление элемента. }

if (s.count < max_size) then

begin

s.buf[s.count + 1] := item;

{ Увеличиваем число элементов на 1. }

inc(s.count);

end;

end;

При просмотре верхнего элемента стека отдельно обрабатывается случай, когда число элементов равно 0. В данном случае возвращается некое фиксированное значение или код ошибки. Если стек содержит хотябы один элемент, то возвращается верхушка стека. Сложность операции O(1):

{ Операция просмотра вершины стека. }

{ Входные параметры: }

{ s - стек; }

function peek(s: stack): integer;

begin

{ Если нет ни одного элемента, возвращаем 0. }

if (s.count <= 0) then

peek := 0

{ В противном случае возвращаем элемент из вершины. }

else

peek := s.buf[1];

end;

Операция удаления элемента из стека производит выемку элемента из вершины с его возвратом. При этом, если стек пуст, возвращается код ошибки. Сложность операции O(n):

{ Операция удаления элемента из вершины стека. }

{ Входные параметры: }

{ s - стек; }

function pop(var s: stack): integer;

var

i: integer;

begin

{ Если в стеке нет элементов, возвращаем 0. }

if (s.count <= 0) then

pop := 0

else

begin

{ Удаляем элемент из вершины. Все остальные }

{ сдвигаем влево на одну позицию. }

pop := s.buf[1];

i := 1;

while (i < s.count) do

begin

s.buf[i] := s.buf[i + 1];

inc(i);

end;

{ Уменьшаем количество элементов на 1. }

dec(s.count);

end;

end;

4.3. Реализация стека на базе связного списка

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

type pnode = ^node; { Тип: указатель на узел стека. }

node = record { Объявление узла стека. }

data: integer; { Полезная информация. }

next: pnode; { Ссылка на следующий элемент. }

end;

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

type stack = record

first: pnode; { Указатель на первый элемент. }

count: integer; { Количество элементов. }

end;

Инициализация стека производится обнулением количества элементов в стеке и присваиванием пустой ссылки указателю на первый элемент:

{ Операция инициализации стека. }

{ Входные параметры: }

{ s - стек; }

procedure init(var s: stack);

begin

s.first := nil;

s.count := 0;

end;

Добавление элемента производится в начало стека. При этом ссылка на первый элемент должна указывать на новый элемент. Если стек пустой, то необходимо произвести инициализацию указателя на первый элемент. Сложнойсть операции O(1):

{ Операция добавления нового элемента. }

{ Входные параметры: }

{ s - стек; }

{ item - новый элемент; }

procedure push(var s: stack; item: integer);

var

i: pnode;

begin

{ Если ссылка на первый элемент пуста, значит }

{ в стеке нет ни одного элемента. Добавляемый }

{ элемент будет первым. }

if (s.first = nil) then

begin

new(s.first);

s.first^.data := item;

s.first^.next := nil;

end

{ В противном случае добавляем элемент в начало стека. }

else

begin

i := s.first;

new(s.first);

s.first^.data := item;

s.first^.next := i;

end;

{ После добавления увеличиваем количество элементов }

{ в стеке на единицу. }

inc(s.count);

end;

Операция просмотра первого элемента в стеке возвращает 0, если он пуст. В противном случае, возвращает элемент в вершине стека. Сложность операции O(1):

{ Операция просмотра вершины стека. }

{ Входные параметры: }

{ s - стек; }

function peek(s: stack): integer;

begin

{ Если нет ни одного элемента, возвращаем 0. }

if (s.count <= 0) then

peek := 0

{ В противном случае возвращаем элемент из вершины. }

else

peek := s.first^.data;

end;

Операция удаления элемента очищает память, занимаемую первым элементов стека и переставляет указатель на вершину. Функция возвращает данные, хранимые в удаленном элементе. Следует обрабатывать ситуации, когда стек пуст. В данном случае функция возвращает 0 в качестве кода ошибки. Сложность операции O(1):

{ Операция удаления элемента из вершины стека. }

{ Входные параметры: }

{ s - стек; }

function pop(var s: stack): integer;

var

i: pnode;

begin

{ Если в стеке нет элементов, возвращаем 0. }

if (s.count <= 0) then

pop := 0

else

begin

{ Удаляем элемент из вершины. Второй элемент }

{ становится на место первого. }

pop := s.first^.data;

i := s.first^.next;

dispose(s.first);

s.first := i;

{ Уменьшаем количество элементов на 1. }

dec(s.count);

end;

end;

10.Деревья: основные принципы построения, операции вставки, поиска и удаления элементов. Балансировка дерева.

B-деревья: принципы построения, основные операции

Идея индексированных файлов состоит в построении доп. файла, содержащего ключи записей и указатели на данные в главном файле. Индексы бывают разреженные (или первичные) и плотные (или вторичные).

Разреженные индексы ключ должен гарантировать уникальное значение. Записи индекса состоят из пар (v, b), где b – адрес блока, а v – зн-ние ключа 1ой записи блока. Записи в главном файле д.б. упорядочены. Записи в индексе также упорядочены.

Плотное индексирование не требует упорядочивать гл. файл и не требуют уникальности ключа, поэтому для нек-ого отношения можно построить мн-во плотных индексов. Запись в плотном индексе представляет собой пару (V, p), где V – зн-ние ключа записи, а p – адрес записи.

При увеличении числа блоков в разреженном индексе снижается эф-ть работы.

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

Сущ-ет 2а соглашения при построении В-деревьев:

не д.б. блоков заполненных меньше, чем наполовину;

значение ключа 1ой записи индексного блока пропускается.

Поиск в В-деревьях

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

Вставка в В-дерево

При вставке записи находим блок В, в к-ом д.б. размещена запись. Если в найденном блоке есть свободное место, то помещаем в него запись, сохраняя упорядоченность. В этом случае изменения в индекс вносится не будут, т.к. не м.б. вставлена 1ая запись блока.

Если в блоке нет свободного места, то д.б. получен пустой блок В`. Записи между В и В` распределяются поровну и инфо о В` д.б. заменена в индексе, т.е. в индексном файле д.б. выполнена операция вставка с сохранением порядка записи. Однако блок индекса также м.б. заполнен, а, следовательно, необходимо выделить новый блок индекса с перераспределением записей и добавлением инфо о новом блоке на уровень выше. В результате операция вставки может привести к увеличению числа уровней В-дерева.

Удаление из В-дерева

Находим блок, в к-ом располагается удаляемая запись. Если блок после удаления заполнен наполовину или более, то операция удаления прекращается. Если блок заполнен меньше, чем наполовину, то рассматриваются его соседи слева и справа для перераспределения записей между 2мя блоками, чтобы дерево осталось сбалансированным. Если это условие не м.б. соблюдено, то блоки объединяются. Инфо об одном из блоков в этом случае удаляется из индексного файла. Если файл индекса также оказывается заполненным меньше, чем наполовину, то с ним производится аналогичная операция. Т.о., удаление может привести к уменьшению числа уровней В-дерева. Если удаление затронуло только главный файл и при этом изменялась 1ая запись блока, то необходимо внести изменения в индексные файлы, при этом необходимо помнить, что это необязательно будет 1ый индексный уровень.

Индексированные файлы: операции вставки и удаления записей

Идея индексированных файлов состоит в построении доп. файла, содержащего ключи записей и указатели на данные в главном файле. Индексы бывают разреженные (или первичные) и плотные (или вторичные).

Разреженные индексы

В разреженном индексе ключ должен гарантировать уникальное значение. Записи индекса состоят из пар (v, b), где b – адрес блока, а v – зн-ние ключа 1ой записи блока. Записи в главном файле д.б. упорядочены. Записи в индексе также упорядочены.

Плотное индексирование

Плотные индексы не требуют упорядочивать гл. файл и не требуют уникальности ключа, поэтому для нек-ого отношения можно построить мн-во плотных индексов. Запись в плотном индексе представляет собой пару (V, p), где V – зн-ние ключа записи, а p – адрес записи.

В файле индекса в самой 1ой записи вместо значения ключа помещается -∞, чтобы упростить алгоритм поиска. Индекс также может состоять более чем из одного блока. В этом случае блоки индекса организуются как последовательный файл, либо над индексом строится еще один индекс.

Для разреженных индексов

Операция вставки

Пусть необходимо добавить запись с ключом v1. Для этого необходимо найти блок bi, в к-ом д.б. запись. Затем объясняем корректное положение записи в блоке bi. Для этого смещаем все записи с ключом большим v1 вправо. Если блок bi не содержит свободного места, то выделяется новый блок в главном файле, записи распределяются пополам между bi и новым блоком (порядок д.б. сохранен). При появлении нового блока инфо о нем д.б. записана в индексном файле. При этом также должен сохраняться порядок записей.

Операция удаления

При удалении записи с ключом v1 также производится операция поиска блока, затем производится сдвиг всех записей блока с ключом больше v1 влево. Если при этом блок остается пустым, то он возвращается файловой системе, а из индекса удаляется запись о нем. Если удаляется 1ая запись блока, то запись в индексе модифицируется.