Файл: Алгоритмы сортировки данных (Структура и типы данных).pdf

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

Нелинейные разветвленные списки

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

В обработке нелинейный список определяется как любая последовательность атомов и списков (подсписков), где в качестве атома берется любой объект, который при обработке отличается от списка тем, что он структурно неделим.  ^

Графы

Граф - это сложная нелинейная многосвязная динамическая структура, отображающая свойства и связи сложного объекта. Многосвязная структура обладает следующими свойствами: на каждый элемент (узел, вершину) может быть произвольное количество ссылок; каждый элемент может иметь связь с любым количеством других элементов; каждая связка (ребро, дуга) может иметь направление и вес. 

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

Деревья

Дерево - это граф, который характеризуется следующими свойствами: 

1. Существует единственный элемент (узел или вершина), на который не ссылается никакой другой элемент - и который называется корнем. 
2. Начиная с корня и следуя по определенной цепочке указателей, содержащихся в элементах, можно осуществить доступ к любому элементу структуры. 
3. На каждый элемент, кроме корня, имеется единственная ссылка, т.е. каждый элемент адресуется единственным указателем. 

Линия связи между парой узлов дерева называется обычно ветвью. Те узлы, которые не ссылаются ни на какие другие узлы дерева, называютсялистьями или терминальными вершинами. Узел, не являющийся листом или корнем, считается промежуточным или узлом ветвления(нетерминальной или внутренней вершиной). Деревья нужны для описания любой структуры с иерархией. 

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

Глава 2. Сортировка. Списки. Метод работы.

2.1 Дек

Дек (deque — double ended queue, «двусторонняя очередь») – структура данных типа «список», функционирующая одновременно по двум принцам организации данных: FIFO и LIFO. Определить дек можно как очередь с двумя сторонами, так и стек, имеющий два конца. То есть данный подвид списка характерен двухсторонним  доступом: выполнение поэлементной операции, определенной над деком, предполагает возможность выбора одной из его сторон в качестве активной.

Рисунок 1. Дек

Двусторонняя очередь

Число основных операций, выполняемых над стеком и очередью, равнялось трем: добавление элемента, удаление элемента, чтение элемента. При этом не указывалось место структуры данных, активное в момент их выполнения, поскольку ранее оно однозначно определялось свойствами (определением) самой структуры. Теперь, ввиду дека как обобщенного случая, для приведенных операций следует указать эту область. Разделив каждую из операций на две: одну применительно к «голове» дека, другую – его «хвосту», получим набор из шести операций:

• добавление элемента в начало;
• добавление элемента в конец;
• удаление первого элемента;
• удаление последнего элемента;
• чтение первого элемента;
• чтение последнего элемента.

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

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

• Creation – обнуляет указатель на конец, так сказать создает дек;
• Full – проверяет дек на наличие элементов;
• AddL – добавляет элемент в начало;
• AddR – добавляет элемент в конец;
• DeleteL – удаляет первый элемент;
• DeleteR – удаляет последний элемент;
• OutputL – выводит первый элемент;
• OutputR – выводит последний элемент;
• Size – выводит количество элементов дека;

Помимо самого массива потребуется указатель на последний элемент, назовем его last. Указатель на первый элемент не потребуется, поскольку дек будет представлять собой смещающуюся структуру, т. е. при добавлении нового элемента в начало, каждый из старых элементов сместиться на одну позицию вправо, уступив тем самым первому элементу ячейку с индексом 0 (в C++), следовательно, адрес первого элемента – константа. (Приложение1)

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

Стандартная библиотека C++ предоставляет специальные средства работы с двусторонней очередью. Для этого в ней предусмотрен контейнер deque. Он позволяет за O(1) осуществлять вставку и удаление элементов. Методы контейнера deque:

• front – возврат значения первого элемента;
• back – возврат значения последнего элемента;
• push_front – добавление элемента в начало;
• push_back – добавление элемента в конец;
• pop_front – удаление первого элемента;
• pop_back – удаление последнего элемента;
• size – возврат числа элементов дека;
• clear – очистка дека.

Следующая программа полностью повторяет функционал предыдущей, но для обработки дека она использует не пользовательские подпрограммы, а методы контейнера deque. (Приложение2)

2.2 Очередь

Очередь – структура данных типа «список», позволяющая добавлять элементы лишь в конец списка, и извлекать их из его начала. Она функционирует по принципу FIFO (First In, First Out — «первым пришёл — первым вышел»), для которого характерно, что все элементы a₁, a₂, …, a_n-1, a_n, добавленные раньше элемента a_n+1, должны быть удалены прежде, чем будет удален элемент a_n+1. Также очередь может быть определена как частный случай односвязного списка, который обслуживает элементы в порядке их поступления. Как и в «живой» очереди, здесь первым будет обслужен тот, кто пришел первым.

 Рисунок 2. Очередь

Очередь

Стандартный набор операций (часто у разных авторов он не идентичен), выполняемых над очередями, совпадает с тем, что используется при обработке стеков:

• добавление элемента;
• удаление элемента;
• чтение первого элемента.

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

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

Реализация очереди с помощью массива

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

• Creation(Q) – создание очереди Q;
• Full(Q) – проверка очереди Q на пустоту;
• Add(Q) – добавление элемента в очередь Q (его значение задается из функции);
• Delete(Q) – удаление элемента из очереди Q;
• Top(Q) – вывод начального элемента очереди Q;
• Size(Q) – размер очереди Q.

В программе каждая из этих операций предстанет в виде отдельной подпрограммы. Помимо того, потребуется описать массив данных data[N], по сути, являющийся хранилищем данных вместимостью N, а также указатель на конец очереди (на ту позицию, в которую будет добавлен очередной элемент) – last. Изначально last равен 0. (Приложение3)

 В функции main, сразу после запуска программы, создается переменная Q структурного типа Queue, адрес которой будет посылаться в функцию (в зависимости от выбора операции) как фактический параметр. Функция Creation создает очередь, обнуляя указатель на последний элемент. Далее выполняется оператор цикла do..while (цикл с постусловием), выход из которого осуществляется только в том случае, если пользователь ввел 0 в качестве номера команды. В остальных случаях вызывается подпрограмма соответствующая команде, либо выводиться сообщение о том, что команда не определена.

Из всех подпрограмм особого внимания заслуживает функция Delete. Удаление элемента из очереди осуществляется путем сдвига всех элементов в начало, т. е. значения элементов переписываются: в data[0] записывается значение элемента data[1], в data[1] – data[2] и т. д.; указатель конца смещается на позицию назад. Получается, что эта операция требует линейного времени O(n), где n – размер очереди, в то время как остальные операции выполняются за константное время. Данная проблема поддается решению. Вместо «мигрирующей» очереди, наиболее приемлемо реализовать очередь на базе циклического массива. Здесь напрашивается аналогия с «живой» очередью: если в первом случае покупатели подходили к продавцу, то теперь продавец будет подходить к покупателям (конечно, такая тактика оказалась бы бесполезной, например, в супермаркетах и т. п.). В приведенной реализации очередь считалась заполненной тогда, когда указатель last находился над последней ячейкой, т. е. на расстоянии N элементов от начала. В циклическом варианте расширяется интерпретация определения позиции last относительно начала очереди. Пусть на начало указывает переменная first. Представим массив в виде круга – замкнутой структуры. После последнего элемента идет первый, и поэтому можно говорить, что очередь заполнила весь массив, тогда когда ячейки с указателями last и first находятся радом, а именно за last следует first. Теперь, удаление элемента из очереди осуществляется простым смещением указателя first на одну позицию вправо (по часовой); чтобы добавить элемент нужно записать его значение в ячейку last массива data и сместить указатель last на одну позицию правее. Чтобы не выйти за границы массива воспользуемся следующей формулой:

(A mod N) + 1

Здесь A – один из указателей, N – размер массива, а mod – операция взятия остатка от деления.

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