Введение в динамические структуры
ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. СТЕК
Лекция № 16.
Часто в программах возникает необходимость использовать такие типы данных, размер и структура которых должны меняться в процессе работы. Динамические массивы здесь не выручают, поскольку заранее нельзя сказать, сколько памяти надо выделить – это выясняется только в ходе выполнения программы.
Кроме того, хранение обычных структур (массивов, записей, множеств) в динамической памяти приводит к неэкономному использованию памяти, особенно, если размер таких структур данных достаточно велик.
Для хранения структурированных данных в динамической памяти используются специальные динамические структуры данных (ДСД) – такие структуры данных, в которых число элементов может изменяться в процессе работы.
Наибольший интерес представляют связанные ДСД, то есть ДСД, между элементами которых устанавливаются определенные связи.
Каждая связная ДСД характеризуется
|
|
1) взаимосвязью элементов;
2) набором типовых операций над этой структурой (такой набор в основном состоит из операций записи, поиска и выборки).
В зависимости от типа связей и набора типовых операций связные ДСД классифицируются:
Связные динамические структуры данных Линейные (списки) Иерархические (деревья) (частный случай: пирамида) Односвязные Двусвязные Кольцевые списки списки списки (одно- и двусвязные) (частные случаи: Стек Очередь Дек) |
Линейные списки – данные динамической структуры, представляющие собой совокупность линейно связанных однородных элементов, в которой разрешается добавлять элементы между любыми двумя другими и удалять любой элемент.
Связанные списки могут иметь одиночные или двойные связи.
Список с одной связью (односвязный или однонаправленный список) содержит элементы, каждый из которых имеет связь со следующим элементом данных.
В списке с двойной связью (двусвязный или двунаправленный список) каждый элемент имеет связь как со следующим элементом, так и с предыдущим элементом.
В зависимости от допустимых действий над элементами списка выделяют частные случаи односвязного списка:
Стек – частный случай линейного односвязного списка, для которого разрешено удалять или добавлять элементы только с одного конца списка, который называется вершиной (головой) стека.
Очередь – частный случай линейного односвязного списка, для которого разрешены только два действия: добавление элемента в конец (хвост) очереди и удаление элемента из начала (головы) очереди.
Дек – частный случай линейного односвязного списка, для которого разрешено добавление и удаление элемента с любой стороны.
|
|
Кольцевые списки (кольцо) – данные динамической структуры, аналогичные линейным спискам, но имеющие дополнительную связь между первым и последним элементами списка.
Деревья – данные динамической иерархической структуры произвольной конфигурации. Элементы дерева называются вершинами (узлами).
Частным случаем дерева является
Пирамида (упорядоченное дерево) – дерево, в котором значения узлов всегда возрастают или убывают при переходе на следующий уровень.
Виды связей в различных ДДС:
ДДС Связи | Односвязный список | Двусвязный список | Односвязное кольцо | Двусвязное кольцо | Дерево |
следующий | |||||
предыдущий | |||||
начало и конец | |||||
произвольные |
Частные случаи линейного односвязного списка:
ДДС Операции | Стек | Очередь | Дек |
Добавление элемента | в начало (вершину) | в конец (хвост) | с любой стороны |
Удаление элемента | с начала (вершины) | с начала (головы) | с любой стороны |