Сложные структуры данных

I. Массивы

Совокупность однородных элементов данных, хранящихся в ОЗУ в смежных ячейках памяти, обращение к элементам которой производится по имени всей структуры с указанием индекса.

Характеристики:

1) Имя

2) Тип компоненты

3) Начальное и конечное значение индекса.

Свойства:

1) Каждая компонента может быть явно обозначена.

Для любого языка имя массива – адрес первого элемента.

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

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

Первым(статическим) способом невозможно создать массив переменных размеров.

Хранение в памяти:

- хранение по строкам

- хранение по столбцам

II. Последовательность

Совокупность неименованных элементов данных, обращение к которой происходит по имени всей структуры.

Пример: файл.

III. Стеки

Стек – это линейная однородная структура данных, определенного ограниченного размера, организованная по принципу: «пришедший последним – обслуживается первым».

Рис.13

Рассмотрим два типа организации стека:

· Сплошное – заранее отводится массив определенного размера. Запись в стек (проталкивание) и считывание (выталкивание) производится из одного и того же места – верхушки стека.

Рис.14

Недостаток сплошного хранения элементов стека: заранее надо знать размер массива.

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

Рис.15

IV. Очереди

Очередь – линейная структура однородных данных переменных размеров, организованная по принципу: «пришедший последним – обслуживается последним».

Рис.16

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

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

V. Деки

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

Рис.17

Бывают деки с ограниченным входом:

Рис.18

и ограниченным выходом:

Рис.19

VI. Деревья

Деревья – нелинейная структура данных. отображающая иерархичность в алгоритме.

Дерево (корневое дерево) – непустое конечное множество элементов таких, что существует один узел. называемый корнем, а остальные разбиты на m поддеревьев.

Корень является предком всех потомков. Узлы, не имеющие потомков, называются листьями.

Рис.20

Бинарное дерево – это частный случай дерева, когда у каждого предка не более одного потомка. В памяти ЭВМ дерево представляется так:

Рис.21

Если дерево бинарное, то каждый узел хранит содержимое и два адреса соседей. Если в дереве хотя бы где-нибудь три связи, то любой узел должен состоять из 4 частей (содержимое и еще три адреса).

VII. Графы

Граф – конечное непустое множество вершин и множество упорядоченных ребер, соединяющих эти вершины.

Рис. 22

1) S: (1, 2) – инцидентно первой вершине.

2) Вершины 1 и 2 – смежные.

3) Ребра, инцидентные одной и той же вершине – смежные.

4. Степень вершины – число ребер, выходящих из этой вершины

5. - граф с петлей.

6. Путь, соединяющий вершины V1 и Vn – последовательность вершин такая, в которой V1 и Vn соединены ребрами.

Например: V_1-2 = {1, 3, 4, 2} = 3

7. Путь замкнут, если V1 = Vn

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

9. Простой цикл – замкнутый путь, все вершинны которого, кроме V1 и Vn – попарно различны.

10. Гамильтоновый граф – граф, в котором существует простой цикл, содержащий все вершины в графе, но необязательно все ребра.

11. Расстояние между вершинами – длина кратчайшего пути, соединяющего эти вершины.

12. Если все вершины соединены ребрами, то граф называется полным.

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

Хранение в памяти:

Информация о графе хранится в матрице смежности.

Пример матрицы для рис. 22:

VIII. Орграфы

Орграф вместо ребер имеет дуги.

Вершина W достижима из вершины U, если существует путь, идущий из U в W.

Деревом называется связанный граф без циклов.

Корневое дерево – связанный орграф без циклов, если:

1) Имеется одна вершина, именуемая корнем, в которую не идет ни одной дуги.

2) К каждой вершине, отличной от корня, идет ровно одна дуга.

3) Потомки всякой вершины упорядочены.

Все понятия определяются так же, как и у графа, только с учетом ориентации дуг.

IX. Взвешенный граф

Если у ребра указан вес, то такой граф называется взвешенным.

Таблица смежности взвешенного графа называется таблицей стоимости:

Такой граф – модель для задачи коммивояжера:

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

Дата добавления: 2015-11-30