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

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

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

type

звено = record тело: char; следующий:связь end;

связь = Iзвено;

var тело:char;

стек:связь;

procedure загрузить (тело:char;var стек:связь);

var элемент:связь;

begin new(элемент); элементI.тело:=тело;элементI.следующий:=стек;

стек:=элемент

end{загрузить}

procedure выгрузить (var тело:char;var стек:связь);

var использованный:связь;

begin ifnot(стек = nil) then

begin тело := стекI.тело; использованный:= стек;

стек:=стекI.следующий; dispose(использованный) end

else write ('стек пуст')

end{загрузить}

Обратите внимание на значение оператора dispose.

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

Структуры данных

АСД (абстрактные структуры данных) - математическая структура, с помощью которой мы представляем прикладные данные программы.

АЛГОРИТМ ------> ЯЗЫК ПРОГРАММИРОВАНИЯ

В каждом языке программирования существует своя концепция данных.

Назовем структуры данных конкретного ЯП структурой данных хранения (СДХ).

ПРОБЛЕМА: как отобразить АСД алгоритма на СДХ ЯП ?

Над "АСД определены некоторые операции (удалить, заменить элемент и т.д.)

Критерием выбора СДХ является сложность. Следует выбирать как можно более простые СДХ.

ЗАДАЧА. Дано: АСД и набор СДХ.

Требуется: построить АСД -----> СДХ так, чтобы сложность пераций с СДХ (аналогичных операциям с АСД) была минимальной.

Определение: Отношением порядка R на множестве M называют множество пар, обладающих следующими свойствами:

 1) рефлексивность: (a,a) Î R {a £ a}

 2) транзитивность: a £ b, b £ c Þ a £ c

 3) антисимметричность: a £ b, b £ a Þ a = b

если отношение не обладает свойством 3), то R - предпорядок

Отношение строгого порядка, если в п. 3) (a,b) Î R Þ (b,a) Ï R

R - линейный порядок, если R определено для "a и b и R является строгим порядком.

Некоторое множество частично упорядочено, если на нем зафиксирован некоторый порядок, т.е. на множестве существуют несравнимые величины.

Структура G на множестве M - пара (R,M), где R отношение порядка на множестве M.

Примеры: множество натуральных чисел - структура,

множество слов - структура

Индексация I - отображение M на отрезок [ 1..½M½].

Абстрактные структуры данных

 Строка Граф Дерево Стек Очередь Таблица

Строка

Строка - конечное множество символов с отношением линейного порядка. Значит для каждого символа мы знаем предшествующий и последующий символы.

Примеры строк: текст, формулы без индексов и др.

Свойства строк:

- переменная длина,

- обращение к элементам строки идет в соответствии с отношением линейного порядка, а не в соответствии с индексацией на этом множестве.

(L,M) I: M Þ [1..ôMô]

- часто строка имеет дополнительную структуру - синтаксис.

Операции:

- поиск символа,

- вставка символа,

- удаление символа,

- замена символа.

Граф

Графом гамма называются пары (X,U), где X - множество, U- отношение порядка на X (X - частично упорядоченное множество).

Если U - просто порядок, то граф - ориентирован, в силу свойства антисимметричности.

Если U - предпорядок, то граф неориентированный.

Пару (a,b) соединяют дугой, если пара (a,b) Î множеству U.

Граф гамма называется взвешанным, если каждой дуге мы сопоставляем некоторое вещественное число, называемое весом данной дуги.

m: UÞR

 

Граф гамма - размеченный, если задано некоторое отображение

h: X Þ A, где A - множество меток.

ПРИМЕРЫ: 1) сеть дорог (вес - расстояние, метка - название населенного пункта). Найти кратчайший путь из п.A в п.B.

2) Найти электрические характеристики в различных участках электрической цепи.

Способы задания графа:

 - графический,

 - применение матрицы смежности

 ½x½ = n; X...X

.

X

ì 1, (X, X) Î U

S = í

î 0, (X, X) Ï U

 - применение матрицы инцедентности

U...U (дуги)

X

.

X

(Вершины)

ì 1, если X инцендентно U и Xявляется концом дуги U

s = í -1, если X инцендентно U и Xявляется началом дуги U

î 0, в противном случае.

 

Степень вершины - число дуг входящих (в) и выходящих (из) данной вершины (инцендентных данной вершине).

Степень захода (исхода) - число дуг входящих (выходящих) в (из) данную вершину.

Граф называется регулярным, если степень его вершин постоянна.

Последовательность вершин графа X...Xназывается цепью, если для

" (X, X) Î U, т.е. существуют дуги по которым можно перейти от X к X, от X к X и т.д.

Последовательность вершин графа называется путем, если для

" (X, X) Î U или (X, X) Î U.

Всякая цепь - путь, но не всякий путь - цепь.

Если в цепи X=X, то такая цепь называется цикл.

Граф называется слабосвязанным, если для " его двух вершин существует путь их соединяющий, без относительно их ориентации.

Граф называется сильносвязанным, если для " его двух вершин существует путь их соединяющий, с учетом их ориентации.

Вес пути X ... X - сумма весов дуг этого пути.

 m (X ... X) =m (x, x)

Операции:

 - вставить вершину,

 - удалить вершину,

 - вставить дугу,

 - удалить дугу и т.д.

С точки зрения графа строка это цепь.

Дерево

Дерево - связный ациклический граф.

Одна вершина в дереве обязательно имеет степень захода 0. Эта вершина - корень дерева. Листья дерева - вершины, имеющие степень исхода равную 0.

Для любой вершины дерева (кроме корня) степень захода равна 1.

 

Деревья могут быть ориентированные и неориентированные.

Высота дерева (H) - самый длинный путь из корня к листу.

Рекурсивное определение: Множество из одной вершины - дерево.

Если T ... T - деревья, то

Дерево называется k-ичным, если все вершины имеют степень исхода k.

Дерево называется линейным, степень исхода равна 1.

ЗАДАЧА. Подсчитать количество деревьев, имеющих n вершин.

РЕШЕНИЕ. B - число деревьев из i вершин. Следуя рекурсивному определению дерева:

 

Þ

 

 

Дерево совершенное, если любой путь от корня к листу отличается не более чем на 1 от самого длинного пути.

Совершенное дерево из n вершин имеет минимальную высоту.

Свойства совершенных деревьев:

 - составляют минимальную часть всех деревьев,

 - все пути от корня к листу равноправны.

Список литературы

Для подготовки данной работы были использованы материалы с сайта http://www.ergeal.ru/