Линейные и нелинейные структуры данных

Линейные и нелинейные структуры данных
При создании тех или иных изделий и механизмов, так же как и при проведении многих научных экспериментов, весь процесс от возникновения идеи до ее реализации можно грубо разбить на следующие этапы. Сначала каким-то способом разрабатывают общий проект и готовят технологическую документацию. Затем строят опытный образец или его макет. И, наконец, проводят испытание. По его результатам в опытный образец вносят изменения и снова проводят испытание. Цикл образец — испытание — образец повторяют до тех пор, пока опытный образец не станет действующим, удовлетворяя всем заложенным в проект требованиям. Проведение каждого испытания и внесение очередных изменений в опытный образец почти всегда требует много денег и много времени. Поэтому одна из общих задач состоит в том, чтобы на пути превращения опытного образца в действующий сократить до минимума как число испытаний, так и их стоимость и время проведения.
Структуры данных — это отношения, заданные на множествах данных. Пусть X — множество данных, Y — множество значений данных:
и при этом: 
Если на множестве μ(х) задано отношение ^(х) < μ (х), то будем называть это отношение структурой данных, а μ (х) — областью определения СД. Структура данных называется простой, если между значениями данных связи отсутствуют, т.е. 5(х) = 0 и μ (х) ф 0.
Рассмотрим различные классификации СД, чтобы определить вид СД, наиболее адекватно представляющих информацию, а также место, которое они занимают в общей системе классификации СД.
Важный признак СД — характер упорядоченности ее элементов. По этому признаку СД можно делить на линейно-упорядоченные, или линейные, и нелинейные структуры (рис. 1.3).

Рис. 1.3. Линейные и нелинейные структуры данных
В зависимости от характера взаимного расположения элементов в памяти линейные СД можно разделить на СД с последовательным распределением их элементов в памяти (векторы, строки, массивы, стеки, очереди) и СД с произвольным связанным распределением элементов в памяти (односвязные, двусвязные и прочие списки).
Линейные структуры данных. Линейные СД — это такие, в которых связи между элементами не зависят от выполнения какого-либо условия. Линейные СД подразделяют на три типа: картезианские, строчные и списковые.
Основные определения: контейнер управляет набором объектов в памяти; итератор обеспечивает для алгоритма средство доступа к содержимому контейнера; функциональный объект инкапсулирует функцию в объекте для использования другими компонентами; адаптер приспосабливает компонент для обеспечения различного интерфейса.
Картезианские, или прямоугольные, структуры названы так по способу записи данных в виде прямоугольных таблиц. Например:

Строчные структуры — это одномерные, динамически изменяемые СД, различающиеся способами включения и исключения элементов (рис. 1.4).

Рис. 1.4. Строчные структуры данных
Стек — это линейный список, в котором все включения и исключения делаются в одном конце списка. Стек называют (push — down) списком, реверсивной памятью, гнездовой памятью, магазином, списком типа LIFO (last-in-first-out — «последним пришел — первым обслуживается»). Стек есть часть памяти ОЗУ компьютера, которая предназначена для временного хранения байтов, используемых микропроцессором. Действия со стеком реализуются при помощи регистра указателя стека. Логическая структура стека представлена на рис. 1.5.

Рис. 1.5. Структура стека
Важнейшие операции доступа к стеку — включение (X) элементов и исключение элементов (У) — осуществляются с вершины стека, причем в каждый момент для исключения или включения доступен один элемент, находящийся на вершине стека. Вершина стека адресуется с помощью специального указателя. Для включения нового элемента в стек указатель сначала перемещается «вверх» на длину слота, или ячейки, а затем по значению указателя (индекса) в стек помещается информация о новом элементе. При исключении элемента из стека сначала прочитывается информация об исключаемом элементе по значению указателя (индекса), а затем указатель смещается «вниз» на один слот. Стек считается пустым, если указатель смещен «вниз» на длину одной ячейки относительно нижней границы стека. Стек считается полным, если вершина стека (указатель стека) совмещается с верхней границей стека.
Пусть, например, дано множество элементов {2, 5, 7, 1, 9, 3} и задан алгоритм работы стека (X, X, X, Y, X, У, У). Тогда после работы алгоритма в стеке останется число (2).
Известные примеры стека — винтовочный патронный магазин, железнодорожный тупик для маневров с вагонами (рис. 1.6).

Рис. 1.6. Стек на железных дорогах
Очередь — это последовательность, в которую включают элементы с одной стороны, а исключают — с другой (рис. 1.7). Очередь — это такой тип данных, при котором новые данные располагаются следом за существующими в порядке поступления; поступившие первыми данные при этом обрабатываются первыми. Очередь иногда называют циклической памятью, или списком типа FIFO (first-in-first-out — «первым пришел — первым обслуживается»),
В очереди новый элемент добавляется только с одного конца, а удаление элемента происходит на другом конце (рис. 1.7).

Рис. 1.7. Структура очереди
Очередь, по сути, — однонаправленный список, только добавление и исключение элементов происходит на концах списка. Пусть, например, дано множество элементов {4, 1, 5, 9, 6, 3} и задан алгоритм работы очереди (X, Y, X, Y, X). Тогда, после работы алгоритма, в очереди останется число (5).
Дек (стек с двумя концами) представляет собой линейный список, в котором все включения и исключения делаются на обоих концах списка (рис. 1.8). Дек — это линейная структура (последовательность), в которой операции включения и исключения элементов могут выполняться как с одного, так и с другого конца последовательности. Еще один термин — «архив» — применяется к декам с ограниченным выходом, а деки с ограниченным входом называются перечнями, или реестрами.

Рис. 1.8. Схема доступа к элементам дека
Пусть, например, дано множество элементов {3, 9, 7, 4, 6, 1} и задан алгоритм работы дека (X_v У₂, Х₂, X_v Y₂, X_v Y_VX₂). Тогда после работы алгоритма в деке останутся числа (7, 6).
В списковых структурах логический порядок данных определяется указателями. Любая списковая структура представляет собой набор элементов, каждый из которых состоит из двух полей: в одном из них размещен элемент данных или указатель на него, а в другом — указатель на следующий элемент списка.
Нелинейные структуры данных. Это такие СД, у которых связи между элементами зависят от выполнения определенного условия. Примеры нелинейных структур — деревья, графы, многосвязные списки.
Древовидные структуры — это такие иерархические структуры, которые состоят из набора вершин и ребер, причем каждая вершина содержит определенную информацию и ссылку на вершину нижнего уровня. Дерево — это совокупность элементов, называемых узлами (один из которых определен как корень), и отношений, образующих иерархическую структуру узлов (рис. 1.9).
Вершина, располагающаяся в нулевом уровне, называется корнем дерева (нумерация уровней может начинаться с 1). В корень не входит ни одно ребро. Вершины, из которых не выходит ни одного ребра, называются листьями, или терминальными вершинами (вершины 8, 9, 5, 6, 7). Дерево, из каждой вершины которого выходит только по два ребра, называется бинарным (рис. 1.10).

Рис. 1.9. Древовидная структура (дерево)

Рис. 1.10. Бинарное дерево

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

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

Рис. 1.12. Многосвязный список (сплетение)