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

Т. е. элементы из стека можно доставать только в порядке, обратном порядку добавления их в стек.

Примерами стеков могут служить:

А) обыкновенная детская пирамидка: большое колечко, которое было надето раньше, нельзя снять, не сняв маленькое, которое было надето позже;

Б) железнодорожный тупик: вагон нельзя выгнать из тупика, не выгнав предварительно вагон, который был загнан позже;

В) труба с одним запаянным концом, куда помещают разноцветные бочонки;

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

Элемент стека, который в данный момент можно взять, т.е. верхний,

Называется вершиной стека. Если число элементов в стеке не может превышать некоторой величины, то стек называют ограниченным, а максимальное число элементов в нем – глубиной стека.

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

1). Создание;

2). Разрушение;

3). Проверка пустоты;

4). Вставка (добавление);

5). Извлечение;

когда стек имеет ограниченную глубины:

6). Проверка заполнености;

Дополнительные операции:

7). Доступ к вершине для чтения;

8). Доступ к вершине для изменения;

9). Удаление вершины;

10). Очистка;

11). Конструктор копирования;

и другие.

Реализация стека ограниченной глубины на базе массива.

Unit Astack;

Interface

Type Telem = char;

Ar = array[1..1] of Telem;

{Вынося это описание в интерфейсную часть можно не делать преобразование типов, но пользователь получает информацию о реализации стека}

Par = ^Ar;

Type Pstack = ^Cstack;

Cstack = object

Public

Constructor Init (n:word);{n-максимальная глубина стека}

Destructor Done; Virtual;

Function IsEmpty:boolean;{проверка на пустоту}

Function IsFull:boolean;{проверка на полную заполненность; для стека неограниченной глубины этой функции быть не должно}

Procedure Push (x:Telem);{вставка, x размещается в качестве новой вершины стека}

Procedure Pop (var x:Telem);{извлечение}

Private

Procedure Failure (n:word);{n – номер ошибки}

Private

Nmax: word;{максимальная глубина стека}

Itop: word; {текущая глубина}

P: Par;

End;

Implementation

Uses crt;

{$Q+,R-}

procedure Cstack. Failure;

begin

clrscr;

writeln (‘Ошибка стека № ‘,n);

case n of

1: writeln (‘Не хватает памяти’);

2: writeln (‘Добавление в полный стек’);

3: writeln (‘Выборка из пустого стека’);

end;

halt (1);

end;

constructor Cstack.Init;

var k:longint;

begin

nmax:= n;

k:= longint(n)*sizeof(Telem);

if (k>65520) or (k>maxavail) then failure(1);

getmem (p, k);

itop:= 0;

end;

destructor Cstack.Done;

begin

freemem (p, nmax*sizeof(Telem));

{далее следует необязательная часть}

nmax:= 0;

itop:= 0;

p:= nil;

end;

function Cstack.IsEmpty;

begin

IsEmpty:= (itop = 0);

End;

Function Cstack.IsFull;

Begin

IsFull:= (itop = nmax);

End;

Procedure Cstack.Push;

Begin

If itop = nmax then failure(2);

Inc(itop);{itop:= itop +1}

P^[itop]:= x;

End;

Procedure Cstack.Pop;

Begin

If itop = 0 then failure(3);

x:= p^[itop];

dec(itop);{itop:= itop –1}

end;

begin { не обязателен }

end.

Некоторые замечания:

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

Можно создать парный стек. С одного конца массива заполняется один стек, а с другого другой.

Иногда выгоднее хранить не вершину стека, а индекс первого свободного места. В этом случае лучше начинать нумерацию с 0.

Работа стека организована по принципу LIFO (от анг. Last In - First Out последний вошел первый вышел), а очереди по принципу FIFO (First In - First Out первый вошел первый вышел).

Кроме уже рассмотренных способов построения в памяти стеков и очередей существует еще много способов сделать это. Рассмотрим их:

1) Построение очереди на основе массива

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

переменная:= (переменная + 1) mod длина_массива

Но эта формула работает только если индексы в массиве начинаются с 0. Если

нумерация начинается не с 0, то формула примет вид:

переменная:= (переменная + 1) mod длина_массива + начальный_индекс

Кроме этого понятно, что надо еще и уметь проверять очередь на заполненность.

Есть два решения этой проблемы:

а) ввести переменную в которой хранить текущую длину очереди. При добавлении элемента

длина увеличивается, а при удалении, естественно, уменьшается. Если при очередном добавлении длина массива совпадет со значением в этой переменной, то значит очередь заполнена полностью.

б) ввести буферный элемент. Теперь после каждого нового прибавления единицы к переменной,

содержащей индекс конца очереди, нужно проверить не совпадают ли значения начала и конца

очереди. Если они совпадают, то надо сгенерировать ошибку - очередь переполнена. При

взятии элемента проверяем на совпадение первую и вторую переменную. Если они совпали, то

очередь пуста (генерируем ошибку). Т.е. теперь переменные, указывающие на начало и конец

очереди при пустой очереди не совпадают. Первая переменная указывает на один из элементов

массива, а другая - на следующий за ним элемент. При этом изменяется порядок взятия

элемента из массива: сначала к переменной прибавляется единица, а только потом берется

элемент на который он указывает.

2) построение очереди на основе одно-связанного списка

Прежде всего, необходимо разобраться что хранить. Возможны варианты:

а) указатели на начало и конец очереди

При добавлении элемента в очередь выделяется память для нового элемента и в нее

записывается значение. Указатель на конец очереди принимает новое значение. При

удалении элемента из очереди удаляется память на которую указывает указатель начала и

значение этого указателя должно указывать на следующий за ним элемент списка. При

работе с такой реализацией очереди проверка на пустоту выполняется очень просто.

Сравниваем указатель начала на nil. Если равны - то очередь пуста, иначе - нет. При

работе с данным типом очереди следует обратить внимание на то, что добавление самого

первого элемента происходить достаточно специфически. В связи с этим более

распространен второй путь реализации.

б) указатель на начало и первый свободный элемент

Пустая очередь состоит из одного блока цепочки на который указывают два указателя. При

добавлении элемента блок заполняется данными и выделяется память для следующего

элемента. После этого меняем значение указателя на конец очереди (оно должно стать

равно адресу выделенного блока). При удалении элемента освобождаем блок на который

указывает указатель начала и меняем его значение так, чтобы он указывал на следующий

блок. При данном методе реализации сравнивание на конец очереди происходит немного

громоздко. Если следующий блок, который следует за блоком, на который указывает

указатель на начало оказался nil, то значит очередь пуста.

ДЕК

Дек является симбиозом стека и очереди - это та же структура, но на этот раз с ней можно работать с обеих концов. Таким образом, если мы будем работать с деком только с левого края, то фактически получается стек. Аналогично мы получим стек, если будем работать только с правого края (конца дека). Пользуясь предписаниями "добавить в конец" и "взять из начала", мы сможем получить очередь, элементы которой будут продвигаться справа налево.

Название дека произошло от сокращения английских слов Double Ended Queue - очередь с двумя концами.

Дек можно реализовать на основе статической памяти и на основе списка.

На основе динамической памяти это реализовывается почти так же как и

для очередей и стеков. Реализовать дек возможно только в виде двух связанного

списка.

ЯЗЫКИ И ГРАММАТИКИ

Пусть А - алфавит (это обычное множество каких-либо элементов), элементы называются символами алфавита. В данном случае алфавит это немножко не то что мы под ним понимаем, - это произвольное непустое множество элементов призвольного типа (например, алфавит Z -алфавит целых чисел).

Подмножество множества конечных цепочек символов называется языком над алфавитом. Естественно, что над заданным алфавитом можно построить бесконечное множество языков. Рассмотрим пример алфавита построения алфавита арифметических выражений:

А = {a,b,+,-,(,)} - алфавит из 6 символов (сразу заметим, что символ "," не является сиволом алфавита А). Соответственно, нашему языку принадлежат выражения вида: a, a+b, (a)+b-a, но не принадлежат, например, такие (a, (), -a+b. Последнее не принадлежит языку потому, что перед a стоит унарный минус, что недопустимо (чтобы это выражение было в языке необходимо ввести в алфавит унарный плюс и унарный минус.

Грамматика:

Метаалфавит - это какой либо другой алфавит, не пересекающийся с А, состоящий из метасимволов. При этом один из метасимволов выделяется отдельно и называется главным. Существует множество методов задания грамматики. Мы рассмотрим только один способ задания грамматики. В этой грамматике используются предложения вида:

метасимвол::= цепочка символов и метасимволов

Символ::= означает "по определению есть", и не является символом ни

алфавита, ни метаалфавита. Зададим метаалфавит: М = {c,d,e} (считаем, что c - главный)

Зададим грамматику для нашего примера:

e::=+

e::=-

d::=a

d::=b

c::=d

c::=(c)

c::=cec

Один и тот же язык можно описать с помощью разных грамматик. Если заменить символ c на c::=cecec - язык не измениться, а грамматика измениться. Однако, как можно заметить, что этот способ задания грамматики является рекурсивным и может зациклится. Чтобы избежать этой ситуацию введем грамматику без зацикливаний - так называемую нотацию Бэкуса-Наура. В ней дополнительно нужны следующие символы:

1) | - или, благодаря этому оператору можно намного проще и короче

задавать нотации. Например, символ e задается e::=+|-

2) <название метасимвола> - для более естественной записи. В нашем

случае нам необходим метаалфавит М = {<знак>,<переменная>,

<формула>}, считаем, что <формула> - главный метасимвол.

Перепишем нотацию:

<знак>::=+|-

<переменная>::=a|b

<формула>::=<переменная> | (<формула>) | <формула><знак><формула>

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

Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычис­лить, когда этот...

ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...

ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...

Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: