Оч _ередь

2.5 Оч _ередь

Очередь - упорядоченный, одномерный, динамически изменяемый

набор компонент, в котором включение новых компонент произво-

дится с одного конца очереди, а доступ и исключение с другого.

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

ляется динамическим объектом и длинна ее не фиксируется. Так

как в Pascal нет структурного типа очередь, его можно отобра-

зить на уже имеющиеся структуры: файл и массив. Отображение

очереди из целых чисел на массив можно реализовать так:

const N=10;

type Qel:integer;

Queue: record

 first,last:integer;

body: array [1..N] of Qel;

end;

где first и last - указатели на первый и последний элемент

очереди соответственно, а N - максимальное число компонент оче-

реди. Отображение на массив накладывает ограничение на длину

очереди, кроме того программист сам запрещает себе прямой дос-

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

дующие процедуры:

Init(Q) - процедура создания очереди Q.

Empty(Q) - логическая функция, если очередь пуста Empty вы-

дает значение true, если нет - false.

Pop(Q) - процедура, выталкивающая первый элемент очереди Q.

Top(Q) - функция, выдающая значение первого элемента очереди.

Push(Q,v) - процедура, добавляющая новый элемент v типа Qel

в конец очереди Q.

Print(Q) - процедура, распечатывающая содержимое очереди.

Size(Q) - функция, выдающая число компонент (длину) очереди.

Отображение очереди на файл выглядит так:

type T = Qel;

Queue = file of T;

Операции над очередью определяются также как и при отображе-

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

буферной переменной. При таком отображении время на операции

тратится больше, так как файл приходится все время "перематы-

вать".

На Pascal очередь может быть организована и как двунаправ-

ленный список:

type T = Qel;

pointer = ^T;

Queue = record

info:T;

pred,sled:pointer;

end;

где pred и sled - указатели на предыдущий и следующий эле-

мент очереди. Операции над очередью при такой организации опре-

деляются аналогично.

2.6  _Стек

Стек - структура данных, в которой можно добавлять и уда-

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

последний добавленный элемент. Как и очередь стек в Pascal мож-

но организовать в виде линейного списка:

type pointer = ^elem;

elem = record

info:TValue;

sled:pointer;

end;

Stask = pointer;

или отображения на массив:

const N=10;

type Stask = record

tp:integer;

body:array [1..N] of TValue;

end;

Для работы со стеком реализуются процедуры:

Init(S) - процедура создания стека S.

Empty(S) - логическая функция, выдающая true если стек пуст

и false если в нем есть элементы.

Push(S,v) - процедура вставляющая новый элемент v в стек.

Pop(S) - процедура выталкивающая верхний элемент из стека.

Top(S) - функция, возвращающая значение верхнего элемента

стека.

Size(S) - функция,возвращающая число элементов стека.

Display(S) - процедура, распечатывающая содержимое стека.

Имея эти базовые процедуры довольно просто реализовать про-

цедуры: вставки элемента в стек под каким-то номером

(Insert(S,v,n)) и удаления элемента из стека по значению

(Remove(S)). Надо заметить, что стек - одна из наиболее исполь-

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

решении различных задач.

2.7  _Дек

Deque (double-ended queue) - двухсторонняя очередь, структу-

ра данных, где элементы могут добавляться и удаляться с обоих

концов. Дек является и стеком и очередью одновременно. При реа-

лизации должны быть определены операции: вставка нового элемен-

та в начало дека, вставка нового элемента в конец дека, удале-

ние (или просмотр) элемента из начала дека, удаление элемента

из конца дека.

2.8  _Графы

Множество объектов соединенных произвольным образом, но не

более чем одной линией связи между двумя объектами - называется

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

ориентированный граф - в котором линии связи имеют определенное

направление.При использовании графов часто возникает проблема

поиска пути между двумя вершинами.

В Pascal удобно для этой цели представлять граф в виде мат-

рицы смежности, в которой хранится информация о связях между

вершинами графа.Если граф содержит N вершин, то матрица смеж-

ности - квадратная булевская матрица N*N, в которой

М(i,j)=true, если есть связь между i-ой и j-ой вершинами и

М(i,j)=false в противном случае. Для неориентированных графов

матрица смежности симметрична.

Граф с К вершинами можно также представить в виде К списков,

соответствующих вершинам и содержащих номера вершин с которыми

у данной есть связь.Если граф меняется в процессе обработки,

т.е. добавляются и удаляются вершины и линии связи, то удобнее

использовать списки.

Графы применяются в задачах машинного проектирования и в

создании систем искусственного интеллекта.

2.9  _Деревья

Дерево - частный случай графа.Структура определяется рекур-

сивно,образованная данным элементом, называемым корнем дерева,

и конечным списком с переменным числом элементов - деревьев то-

го же типа, называемых поддеревьями. Двоичным или бинарным де-

ревом называется дерево состоящее из корня, правого и левого

поддеревьев.

В Pascal двоичное дерево можно определить так:

type BTree = ^BNode;

BNode = record

info:TValue;

left,right:BTree;

end;

При анализе структур данных, заданных в виде дерева, приме-

няются различные способы просмотра и перебора узлов.Основная

особенность каждого обхода заключается в том, что просматрива-

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

обрабатывается ровно один раз.

Для бинарного дерева определены три способа обхода: прямой

или префиксный (корень - левое поддерево - правое поддере-

во),обратный или инфиксный (левое поддерево - корень - правое

поддерево) и концевой или постфиксный (левое поддерево - правое

поддерево - корень).

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

стек.В прошитых деревьях используются дополнительные указатели

на наличие поддеревьев (LTAG и RTAG). Введение дополнительных

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

позволяет при обходе отказаться от стека.

Надо отметить,что любое дерево общего вида можно представить

в виде двоичного, надо в исходном дереве у каждого узла соеди-

нить его сыновей от старшего к младшему и убрать все связи узла

с сыновьями, оставив только связь со старшим сыном.

Над деревьями удобно определить операции: чтение информаци-

онной части из узла дерева, создание дерева, присоединение к

узлу нового поддерева, удаление поддерева.

Особенно полезны деревья при сортировке.Алгоритм состоит в

том, что при просмотре данных очередной элемент помещается в

двоичное дерево. Ключ нового элемента сравнивается с ключом те-

кущего узла.Если указатель текущего узла NIL, то указатель на

новый узел добавляется в то место откуда был извлечен NIL.Если

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

нового узла продолжается в левом поддереве, если больше - в

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

сортировки, выполняется обратный обход дерева с выводом.

Деревья применяются также при интерпритации и вычислении

как арифметических, так и логических.

Теперь рассмотрим области применения сложных структур дан-

ных.Одной из таких областей является процесс создания компиля-

торов, который отработан достаточно хорошо.

Исходный текст разбивается на лексемы (идентификаторы, конс-

танты, знаки операций). Лексемы заносятся в таблицы, а в тексте

лексема заменяется ссылкой на элемент таблицы, таким образом

текст программы заменяется на последовательность лексем. Для

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

один и тот же элемент таблицы, необходлимо для каждого анализи-

руемого идентификатора просматривать все встретившиеся ранее.

Для ускорения этого поиска применяются: упорядочение элементов

таблицы (сортировка) для дальнейшего бинарного поиска, хеш-ад-

ресация и некоторые другие способы.Для хранения последователь-

ности лексем используют массивы и списки.

Следующим этапом после замены текста программы на цепочку

лексем является синтаксический анализ, при котором широко ис-

пользуются стеки, таблицы и строки.

В операционных системах распространены такие сложные струк-

туры данных, как очереди. Операционная система вынуждена под-

держивать несколько очередей: очередь процессов готовых к вы-

полнению, очередь на свопинг на диск и очереди к устройствам

(например к принтеру).

Сложные структуры данных используются также в системах уп-

равления базами данных (СУБД). СУБД могут накапливать информа-

цию о большом числе объектов, описание которых содержат разные

сведения.

Свойства объектов могут выступать в роли ключей (например

фамилия служащего) и тогда по этим свойствам объекты могут быть

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

Для описания объектов обычно используют записи, которые в

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

Наконец,еще одной областью применения являются задачи с ис-

пользованием разреженных матриц (с относительно небольшим чис-

лом ненулевых элементов).Иногда при нехватке оперативной памяти

бывает выгодно хранить только ненулевые элементы, применяя раз-

личные методы упаковки (в три массива, в один массив, с помощью

связного списка и т.д.).

Язык Pascal предоставляет весьма гибкие возможности в отно-

шении используемых структур данных. Удачный выбор структуры

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

трудоемкость разработки и повышает надежность.

2.10 С П И С О К И С П О Л Ь З О В А Н Н Ы Х

И С Т О Ч Н И К О В

1. В.М.Брябрин. Программное обеспечение персональных

ЭВМ, М., "Наука", 1990.

2. Н.Вирт. Програмирование на языке Модула-2,

М., "Мир", 1987.

3. К.Кристиан. Введение в операционную систему UNIX,

М., "Финансы и статистика", 1985.

4. М.И.Беляков, Ю.И.Рабовер, А.Л.Фридман.

Мобильная операционная система,М.,"Радио и связь",

1991.

5. Ф.Л.Бауэр, Г.Гооз, Информатика, т.2, М., "Мир",

1990.

6. В.Г.Абрамов, Н.П.Трифонов, Г.Н.Трифонова,

Введение в язык паскаль,М., "Наука",1988.

7. И.З.Луговая, Л.Н.Чернышов, С.М.Юдин,

Динамические структуры данных языка паскаль, М.,

издательство МАИ, 1988.

8. Л.Н.Чернышов, С.М.Юдин, Инструментальная система

ИНФОРТ и работа с динамическими структурами данных,

М., издательство МАИ, 1984.

9. Лекции, семинары, консультации по АЯП.