Структуры данных. Понятие Структуры данных. Линейные структуры данных (массив, список, очередь).

Структуры данных (сд) – совокупность эл-в данных, объединенных структурными взаимосвязями, при этом каждый эл- в данных в структуре может быть представлен как структура данных

Каждая сд хар-ся набором типовых операций, применимых к данной структуре, на которой ориентирована данная структура

Группы структур:

Линейные, циклические, нелинейные, другие (ост-е)

 

Линейные

Массив, список, очередь, стек, дек, хэш-таблица

Массив (яд, индекс. массив) – сд, эл-ты которой расположены в памяти др. за др., доступ к ним осущ-ся по индексам

Кол-во используемых индексов различно

Операции:

· Получение значения эл-та по индексу

· Установка значения эл-та по индексу

Дост.:

Легкость вычисления адреса эл-та по индексу

Одинаковое время доступа ко всем эл-там

Мин. Размер эл-в (только собственные данные)

Недост.:

Для статич. массива это отсутствие динамики (удаление и вставка эл-та, сдвигая другие)

Для динамич. более низкое быстродействие по сравнению со статич. и доп. расходы на поддержку динамич св-в

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

Список — сд, её эл-ты расположены в памяти в произв. порядке, эл-ты связаны м/д собой, образуя лин. последовательность, порядок эл-в в списке может не совпадать с порядком расположения в памяти. Каждый эл-т содержит соб. данные и 1-2 ссылки на соседние эл-ты (односвязный двусвязный) Операции:

· удалить из списка

· поместить в список

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

Операции:

· вставка в очередь

· удаление из очереди

 

 

24. Структуры данных. Понятие Структуры данных. Линейные структуры данных (стек, дек, хеш-таблица).

См в №23

Стек - сд доступ к данным по принципу LIFO

Стек м/б реализован на базе массива или списка

Операции:

· push (добавление в стек)

· pop (удаление из стека)

Дек – (двусвязная очередь) сд, в которой эл-ты добав. и удал. как в начале так и в конце

Операции:

· push Back (добав. эл-т – последний)

· pop Front (добав. эл-т – первый)

· push Front (2 эл-т с конца– последний)

· pop Back(2 эл-т с конца – первый)

Хеш-таблица — это сд, каждый эл-т которой представляет собой пару (ключ-данные), доступ к эл-там осущ-ся по знач. ключа.

Ключ – некий уник. идентификатор данных эл-та

Обычно ключ получается применением Hash функций к данным эл-та

Типы:

· таблица в которой не допускается дублирование ключей

· таблица в которой возможно хранение эл-в с одинак. ключами

Hash Table – допускается дубл.

Ассоциатив-й масс. – по опр. не допускается дубл.

Hash Table чаще всего реализуется на базе масс. в этом случае ключ – индекс

Операции:

· Добавление эл-та (в 3 этапа)

1. расчет знач. ключа

2. проверка возможности добав. эл-та в табл.

3. добав.

· Удаление эл-та (в 3 этапа)

1. расчет знач. ключа

2. проверка наличия эл-та

3. удаление

· Поиск эл-та в таблице

1. расчет знач. ключа

2. поиск (проверка есть или нет)

 

Структуры данных. Понятие Структуры данных. Циклические структуры данных (циклический список, циклическая очередь, циклический дек). Назначение циклических структур данных.

См в №23

Циклический список

· односвязный (посл. эл-т ссылается на первый)

· двусвязный (посл. на первый, первый на посл.)

Операции аналогично лин. списку

Циклическая очередь

Циклический дек

Осн. назначение

Оптимизация лин. структур под особенности работы алгоритма в первую очередь повышение скорости работы

Структуры данных. Понятие Структуры данных. Нелинейные структуры данных (граф, дерево).

См в №23

И лин. и цикл. структуры – частный случай нелинейных

Граф (Осн. структура) - многосвязная сд, эл-ты расположены в произв. порядке, имеют произв. кол-во связей. В общем случае – множество вершин (узлов) и ребер (дуг)

Узлы – данные

Ребра – связи

Свойства:

· на каждый эл-т может указывать множество ссылок

· каждый эл-т может ссылаться на множество др.

эл-в

· каждая связь может иметь направление и вес

Неориентированный граф – граф у которого все ребра не имеют направления

Ориентированный граф – граф у которого все ребра имеют заданное направление

Смешанный граф – граф у которого нек. ребра ориентированы, а нек. нет.

Дерево – частный случай графа, это ориент. или неориент. граф, хар-ся 3 св-ми:

· не содержит цикл (сущ. только 1 способ добраться от 1 вершины к др.)

· выделена 1 вершина – корень, на него не ссылается ни одна вершина

· на каждую вершину дерева кроме корня имеется одна единственная ссылка

листья, поддерево!!!

Высота – число уровней вершин

Бинарное дерево

N-нарное дерево

? дерево любого вида м/б представлено эквивалентный бинарным деревом

Типовые операции:

· поиск узла в дереве

· удаление узда или поддерева

· добавление узла

· обход дерева в зад. направлении

Дост:

Хорошо подходит для работы с отсорт. данными

По совокуп. операций эта структура обеспечивает наилучшую проив-сть

Недост.: сложность реализации алгоритмов типовых оперций