metod_15.03.04_atppp_oaip_up_2016 (Методические документы), страница 19

Так как в Паскале нетструктурного типа очередь, его можно отобразить на уже имеющиеся структуры:файл и массив. Отображение очереди из целых чисел на массив можнореализовать так:const N=10;type Qel:integer;Queue: recordfirst,last:integer;body: array [1..N] of Qel;end;где first и last - указатели на первый и последний элемент очереди соответственно,а N - максимальное число компонент очереди. Отображение на массив104накладывает ограничение на длину очереди, кроме того программист самзапрещает себе прямой доступ к элементам массива.В Паскале очередь может быть организована и как двунаправленныйсписок:type T = Qel;pointer = ^T;Queue = recordinfo:T;pred,sled:pointer;end;где pred и sled - указатели на предыдущий и следующий элемент очереди.Операции над очередью при такой организации определяются аналогично.Для работы с очередью реализуются следующие процедуры: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;Операции над очередью определяются также как и при отображении намассив, а обработка элементов ведется с использованием буферной переменной.При таком отображении время на операции тратится больше, так как файлприходится все время "перематывать".12.8.

ДекDeque (double-ended queue) - двухсторонняя очередь, структура данных, гдеэлементы могут добавляться и удаляться с обоих концов. Дек является и стеком иочередью одновременно. При реализации должны быть определены операции:вставка нового элемента в начало дека, вставка нового элемента в конец дека,удаление (или просмотр) элемента из начала дека, удаление элемента из концадека.12.9. ГрафМножество объектов соединенных произвольным образом, но не более чемодной линией связи между двумя объектами - называется графом.Связный граф когда имеется путь между двумя вершинами, ориентированный граф - в которомлинии связи имеют определенное направление.При использовании графов частовозникает проблема поиска пути между двумя вершинами.В Паскале удобно для этой цели представлять граф в виде матрицысмежности, в которой хранится информация о связях между вершинамиграфа.Если граф содержит N вершин, то матрица смежности - квадратнаябулевская матрица N*N, в которой М(i,j)=true, если есть связь между i-ой и j-ой105вершинами и М(i,j)=false в противном случае.

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

ДеревьяДеревочастныйслучайграфа.Структураопределяетсярекурсивно,образованная данным элементом, называемым корнем дерева, иконечным списком с переменным числом элементов - деревьев того же типа,называемых поддеревьями. Двоичным или бинарным деревом называется деревосостоящее из корня, правого и левого поддеревьев.В Паскале двоичное дерево можно определить так:type BTree = ^BNode;BNode = recordinfo:TValue;left,right:BTree;end;При анализе структур данных, заданных в виде дерева, применяютсяразличные способы просмотра и перебора узлов. Основная особенность каждогообхода заключается в том, что просматриваются все узлы дерева в некоторомпорядке, причем каждый узел обрабатывается ровно один раз.Для бинарного дерева определены три способа обхода: прямой илипрефиксный (корень - левое поддерево - правое поддерево),обратный илиинфиксный (левое поддерево - корень - правое поддерево) и концевой илипостфиксный (левое поддерево - правое поддерево - корень).При обходе дерева используются рекурсивные процедуры или стек.

Впрошитых деревьях используются дополнительные указатели на наличиеподдеревьев (LTAG и RTAG). Введение дополнительных указателей не приводитк большому увеличению затрат памяти, но позволяет при обходе отказаться отстека.Надо отметить,что любое дерево общего вида можно представить в видедвоичного, надо в исходном дереве у каждого узла соединить его сыновей отстаршего к младшему и убрать все связи узла с сыновьями, оставив только связьсо старшим сыном.Над деревьями удобно определить операции: чтение информационной частииз узла дерева, создание дерева, присоединение к узлу нового поддерева,удаление поддерева.Особенно полезны деревья при сортировке.

Алгоритм состоит в том, чтопри просмотре данных очередной элемент помещается в двоичное дерево. Ключнового элемента сравнивается с ключом текущего узла.Если указатель текущегоузла NIL, то указатель на новый узел добавляется в то место откуда был извлеченNIL. Если ключ нового узла меньше ключа текущего узла, то поиск места для106нового узла продолжается в левом поддереве, если больше - в правом. После тогокак все данные занесены в двоичное дерево сортировки, выполняется обратныйобход дерева с выводом.Деревья применяются также при интерпритации и вычислении какарифметических, так и логических функций.107.