Работа с данными динамической структуры.

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

Под абстракцией данных понимают такой способ программирования, когда при работе с объектом учитываются только его существенные свойства. В качестве примеров абстрактных типов данных могут служить динамические структуры. Их поведение задается набором операций: открыть структуру данных, закрыть структуру данных, включить объект в структуру данных, извлечь объект из структуры данных и т.д. Набор операций и логика их выполнения не зависят от типов объектов.

Абстрактный тип данных «дек». Дек – это множество, состоящее из n > 0 узлов х[1], х[2],.., х[n]. Структурные свойства множества ограничиваются лишь относительным положением узлов, т.е. теми условиями, что если n > 0, то x[1] – первый узел; если 1<R<n, то R-ому узлу x[R] предшествует X[R-1] и за ним следует X[R+1]; x[n] является последним узлом. С деком можно выполнить следующие операции:

o поместить элемент (узел) в начало дека;

o взять элемент из начала дека;

o поместить элемент (узел) в конец дека;

o взять элемент из конца дека.

Абстрактный тип данных «стек». Стек – это структура типа «дек», с которым определены только две операции:

o поместить элемент (узел) в конец дека;

o взять элемент из конца дека.

В стеке реализована дисциплина доступа «последний вошел – первый вышел», т.е. данные помещаются в вершину стека и извлекаются только из неё. Стеки широко применяются при обработке различных иерархических структур, при построении компиляторов.

Абстрактный тип данных «очередь». Очередь – это дек, с которым определены операции:

o поместить элемент в начало дека;

o взять элемент из конца дека.

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

Абстрактный тип данных «список». Список – дек, с которым определены следующие основные операции:

o поместить элемент в начало дека;

o поместить элемент в конец дека;

o поместить элемент после заданного (R-того) элемента;

o взять элемент из начала дека;

o взять элемент из конца дека;

o взять элемент после заданного (R-го) элемента;

o взять заданный элемент.

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

может быть использован вновь (в этом состоит основное отличие списка от других динамических структур данных). Поэтому вводятся дополнительные операции над списками:

3.3.7 удалить элемент из начала списка;

3.3.8 удалить элемент из конца списка;

3.3.9 удалить элемент после заданного элемента;

3.3.10 удалить заданный элемент.

Все расположенные ранее динамические структуры данных могут быть представлены в виде списка с ограниченным набором операций.

Таким образом, написав один раз все процедуры работы со списком, можно обращаться к нему как к деку, стеку, очереди.

В зависимости от структуры элементов и организации связи между ними списки подразделяются на следующие виды:

3.3.11 линейные однонаправленные без головного элемента;

3.3.12 линейные однонаправленные с головным элементом;

3.3.13 линейные двунаправленные без головного элемента;

3.3.14 линейные двунаправленные с головным элементом;

3.3.15 циклические однонаправленные без головного элемента;

3.3.16 циклические однонаправленные с головным элементом;

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

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

Абстрактный тип данных «дерево». Дерево – конечное множество узлов с одним выделенным узлом, называемым корнем, другие узлы разделены на m ³ 0 множеств B_1,B₂,…,B_m, которые не пересекаются и каждое из которых представляет дерево (поддерево).

«Упорядоченное двоичное дерево – конечное множество элементов (вершин), которое либо пусто, либо состоит из корня (вершины) с двумя отдельными двоичными деревьями, которые называются левым и правым поддеревом этого корня» (Н. Вирт).

Упорядоченное дерево – это дерево, у которого ребра (ветви), исходящие из каждой вершины, упорядочены.

Считается, что корень дерева находится на уровне 0.

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

Вершина Y, находящаяся непосредственно ниже вершины X, называется потомком X, и наоборот, вершину X называют предком Y. Если X находится на уровне I, то говорят, что Y лежит на уровне i+1.

Если элемент не имеет потомков, то его называют терминальной вершиной, или истоком, а нетерминальную вершину – внутренней вершиной.

Число непосредственных потомков внутренней вершины называют её степенью.

Максимальная степень всех вершин есть степень дерева. Число ветвей (или ребер), которое нужно пройти от корня к вершине X, называется длиной пути к X. Корень имеет длину пути 0, его прямые потомки имеют путь длиной 1 и т.д.