1.3. Характеристики основных типовых структур

Линейные и нелинейные.

Все структуры данных можно подразделить на линейные и нелинейные. У первых все элементы структуры расположены на одном уровне, у вторых – на нескольких уровнях.

С другой стороны, структуры данных можно разделить на два больших класса по признаку физического размещения в памяти:

• физически последовательные структуры данных, или просто последовательные структуры данных (ПСД);

• структуры с произвольным размещением элементов.

Среди структур, данных с произвольным размещением элементов, прежде всего, выделяются списковые структуры данных (ССД), или просто списки.

К линейным структурам данных относятся ПСД и простые списки, называемые также строками, или строчными структурами. ПСД реализуют естественное отношение порядка на множестве данных в среде хранения. Если этот естественный порядок в ПСД совпадает с логическим отношением порядка на множестве элементов данных (чаще всего, когда у элементов данных выделяются ключевые атрибуты, он устанавливается в соответствии со значениями ключа), то такие разновидности ПСД называются упорядоченными (сортированными), в противном случае – неупорядоченными.

Служебная информация для описания ПСД обычно содержит сведения о количестве элементов множества данных, размерах (длине) элементов, о расположении ключа или ключей (если элементами являются записи) и их размерах, адресе первого элемента множества данных, и др.

В зависимости от разнообразия длин данных и способа указания длины записи ПСД подразделяются на следующие разновидности:

• ПСД с фиксированной длиной элементов;

• ПСД с элементами переменной длины;

• ПСД с элементами неопределенной длины.

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

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

• стек – последовательность, в которой доступ на чтение и запись разрешен только к последнему моменту;

• очередь – последовательность элементов, в которой разрешено добавление в конец, а удаление - только из начала;

• дек – двусторонняя очередь, структура, позволяющая добавлять и извлекать элементы как в начале, так и в конце последовательности данных.

Списковые структуры данных.

Списковые структуры данных (ССД) – это множество физически не связанных элементов, для которых отношение следования определено с помощью специальных адресов связи.

В адресе связи указывается адрес элемента, следующего в логическом порядке хранения за данным элементом.

Элементы ССД могут быть двух типов: простые, логически неделимые (их называют подсписками) или сложные – совокупность простых и сложных меньшего объема. В простые ССД (или строки, или цепи) входят только простые элементы. В сложные ССД входят и простые, и сложные элементы. Каждый элемент ССД содержит собственную информацию – значение элемента и ассоциативную информацию – адреса связи с другими элементами структуры, которые объединяются в звенья связи.

По виду взаимосвязи элементов различают однонаправленные, двунаправленные и кольцевые списковые структуры.

В однонаправленных списках реализуется взаимосвязь между элементами типа «следующий». Каждый элемент такого списка содержит указатель с адресом следующего элемента. Последний элемент имеет в указателе вместо адреса связи специальный знак – признак конца списка. Для задания однонаправленной списковой структуры требуется следующая ассоциативная информация:

• указатель списка с адресом первого элемента;

• звено связи элементов, в которых для простого элемента содержатся адрес следующего элемента списка и адрес значения элемента, а для сложного элемента – адрес следующего элемента списка и адрес первого элемента подсписка.

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

• указатель списка, содержащий адрес первого и последнего элементов;

• звенья связи элементов, для простого элемента это звено содержит адреса предыдущего и последующего элементов, а также адрес значения элемента, для сложного элемента в звене связи содержится адрес последующего и предыдущего элементов списка и адреса первого и последнего элемента подсписка.

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

• указатель строки, который содержит адрес указателя начала кольца;

• указатель начала кольца, который хранит константу N – число просмотров строки, и адрес первого элемента строки;

• звенья связи элементов, содержащие адрес последующего элемента и адрес значения элемента; звено связи последнего элемента вместо признака конца списка содержит адрес указателя начала кольца.

При каждом просмотре кольца значение N уменьшается на 1 и проверяется условие N=0. Если N≠0, просмотр продолжается; при N=0 просмотр заканчивается. Двунаправленная кольцевая строка отличается от однонаправленной тем, что вместо указателя начала кольца вводятся два указателя со своими константами – указатель начала прямого направления и указатель начала обратного направления со своими константами чисел просмотра N1 и N2. Кроме того, звенья связи содержат адреса предыдущего и последующего элементов.

Древовидные (иерархические) структуры данных

Элементы древовидных структур данных (ДСД) располагаются на различных уровнях и соединяются с помощью адресов связи. ДСД соответствует графу типа «дерево» и представляется набором элементов, распределенных по уровням иерархии следующим образом:

На первом уровне расположен только один элемент, который называется корнем дерева; к любому элементу k-го уровня ведет только один адрес связи; к любому элементу k-го уровня адрес связи идет только от элемента (k-1)-го уровня. Количество уровней в ДСД называют рангом. Элементы дерева, которые адресуются от общего элемента (k-1)-го уровня, образуют группу. Максимальное число элементов в группе называется порядком дерева. Деревья с порядком больше двух принято называть общими ДСД, а с порядком 2 – двоичными, или бинарными деревьями. Дерево порядка 1 – строчная структура. В зависимости от количества элементов в группе некоторой вершины различают три типа вершин. Если n – порядок дерева, то вершины из n элементов называются полными, вершины, не имеющие группы – концевыми (листьями), а остальные – неполными.

Для ДСД можно определить ее двунаправленный и кольцевой варианты. Если в однонаправленном варианте некоторая вершина A имеет адрес связи на вершину B, то в двунаправленном дереве дополнительно появится адрес связи от B к A. Если все концевые вершины дерева имеют адрес связи на вершину-корень, то ДСД называется кольцевой. Наиболее распространенным видом ДСД являются бинарные деревья, в которых каждая вершина k-го уровня содержит два адреса (правый и левый) связи на вершины (k+1)-го уровня и один (обратный) – на вершину (k-1)-го уровня. Множество вершин, соединенных с данной вершиной через левый адрес связи, образует левую ветвь этой вершины. Аналогично определяется правая ветвь.

В случае, когда элементы дерева являются записями, наиболее распространенным условием организации бинарных деревьев является упорядоченность. Записи снабжаются ключами с числовыми значениями. Каждый элемент в упорядоченном бинарном дереве (УБД) имеет на своей левой ветви элементы с меньшим, чем у него, значением ключа, а на правой ветви – элементы с большим или равным значением ключа.

Для общих ДСД часто используется разновидность: B-деревья (сбалансированные деревья) со специальным алгоритмом их формирования. В алгоритме формирования УБД дерево растет вниз и корень его не меняется, а в алгоритме формирования B-дерева оно растет вверх и его корень может меняться.

Табличные структуры данных

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

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

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

Сетевые структуры данных

Сетевые структуры представляют собой структуру наиболее общего вида, так как способна воспроизводить большинство связей между объектами [3].