1 БАЗЫ ДАННЫХ СТРУКТУРЫ ДАННЫХ

2 МОДЕЛИ СТРУКТУР ДАННЫХ Линейная структура (списки и кольца) Линейная структура (списки и кольца) Иерархическая структура (деревья) Иерархическая структура (деревья) Сетевая структура Сетевая структура Табличная структура (реляционная) Табличная структура (реляционная)

3 ЛИНЕЙНЫЕ СТРУКТУРЫ ДАННЫХ Список (очередь, цепь) Список (очередь, цепь) Стек Стек Дек Дек Кольцо Кольцо

4 СПИСКИ, ОЧЕРЕДИ И ЦЕПИ 1 N 3 2 … Пётр Джорж Сидор Иван … Иванов Буш Сидоров Петров k ИсаакНьютон ПОЛЯ ЗАПИСЕЙ СПИСКА ЗАПИСИ или ЭЛЕМЕНТЫ или УЗЛЫ списка ОПРЕДЕЛЕНИЕ Линейный список – это множество, состоящее из N0 узлов (записей, элементов, членов) X 1, X 2,… X k,…X N, структурные свойства которого ограниченны линейным (одномерным) относительным положением узлов, т.е. если 1

5 ОПЕРАЦИИ С ЛИНЕЙНЫМИ СПИСКАМИ Получить доступ к k- му узлу списка, что бы проанализировать и/или изменить его содержимое. Получить доступ к k- му узлу списка, что бы проанализировать и/или изменить его содержимое. Включить новый узел непосредственно перед k- м узлом. Включить новый узел непосредственно перед k- м узлом. Исключить k-й узел. Исключить k-й узел. Объединить два линейных списка в один список (в случае необходимости объединить N списков – объединяем попарно). Объединить два линейных списка в один список (в случае необходимости объединить N списков – объединяем попарно). Разбить линейный список на два (или более). Разбить линейный список на два (или более). Сделать копию линейного списка. Сделать копию линейного списка. Определить количество элементов в списке. Определить количество элементов в списке. Выполнить сортировку элементов списка (в возрастающем или убывающем порядке) по некоторым полям в элементах. Выполнить сортировку элементов списка (в возрастающем или убывающем порядке) по некоторым полям в элементах. Найти в списке элемент с заданным значением в некотором поле. Найти в списке элемент с заданным значением в некотором поле. Особо выделяются специальные случаи: k=1 и k=N, поскольку в линейном списке легче получить доступ к первому и последнему элементам, чем к произвольному элементу.

6 ДОБАВЛЕНИЕ ЭЛЕМЕНТА В СПИСОК И УДАЛЕНИЕ ЭЛЕМЕНТА ИЗ СПИСКА НАЧАЛОКОНЕЦТРЕТИЙВТОРОЙ ИСКЛЮЧИТЬ ВКЛЮЧИТЬ 2½2½ НАЧАЛОКОНЕЦТРЕТИЙВТОРОЙЧЕТВЁРТЫЙ

7 УПОРЯДОЧИВАНИЕ И СОРТИРОВКА 1A2D3W4F5Q1A2D3W4F5Q

8 ПЕРЕСЕКАЮЩИЕСЯ ЦЕПИ ЗАГОЛОВОК ЦЕПИ ЗАГОЛОВОК ЦЕПИ 2 Как удалить запись 3?

9 ПЕРЕСЕКАЮЩИЕСЯ ЦЕПИ С ДВУНАПРАВЛЕННЫМИ УКАЗАТЕЛЯМИ ЗАГОЛОВОК ЦЕПИ ЗАГОЛОВОК ЦЕПИ 2

10 ОЧЕРЕДЬ НАЧАЛОКОНЕЦТРЕТИЙВТОРОЙ ИСКЛЮЧИТЬ ВКЛЮЧИТЬ Очередь Очередь – линейный список, в котором все включения производятся на одном конце списка, а все исключения (и обычно всякий доступ) делаются на другом конце списка.

11 СТЕК И МАГАЗИН НАЧАЛО (ВЕРХ) КОНЕЦ (НИЗ) ТРЕТИЙ СВЕРХУ ВТОРОЙ СВЕРХУ ВКЛЮЧИТЬ ИЛИ ИСКЛЮЧИТЬ ЧЕТВЁРТЫЙ СВЕРХУ Стек Стек – линейный список, в котором все включения и исключения (и обычно всякий доступ) делаются в одном конце списка.

12 СТЕК N123 … IP Указатель на вершину стека 0 … 1A … 2XYD … 2AB … 3ABC … 2ABC … 3ABD … 2ABD … 1ABD … 0ABD … 1XBD … PUSH (A) PUSH (B) PUSH (X) IPOP PUSH (D) IPOP IPOP IPOP PUSH (C) PUSH (Y) A B CD X Y

13 ДЕК ЛЕВЫЙ КОНЕЦ ПРАВЫЙ КОНЕЦ ВТОРОЙ СПРАВА ВТОРОЙ СЛЕВА Включить или исключить Дек Дек – линейный список, в котором все включения и исключения (и обычно всякий доступ) делаются на обоих концах списка.

14 КОЛЬЦЕВЫЕ СТРУКТУРЫ ИСКЛЮЧИТЬ ВКЛЮЧИТЬ

15 КОЛЬЦЕВЫЕ СТРУКТУРЫ Заголовок кольца Кольцо с однонаправленными указателями. Что произойдет если некоторая запись разрушится?

16 КОЛЬЦЕВЫЕ СТРУКТУРЫ Заголовок кольца Кольцо с указателями на заголовок. При входе в кольцо не через его начало можно быстро получить информацию из заголовка. Что произойдет если некоторая запись разрушится?

17 КОЛЬЦЕВЫЕ СТРУКТУРЫ КОЛЬЦО С ДВУНАПРАВЛЕННЫМИ УКАЗАТЕЛЯМИ Заголовок кольца Если какая-нибудь запись цепи будет разрушена, все остальные записи останутся доступными. Если будет испорчен один указатель – его можно восстановить.

18 КОЛЬЦЕВЫЕ СТРУКТУРЫ «КОРАЛЛОВОЕ» КОЛЬЦО Заголовок кольца Если разрушена запись с четным номером любая другая запись может быть найдена. Если потеряна запись с нечетным номером (за исключением 1) то некоторые записи могут стать недоступными.

19 ИЕРАРХИИ ИЛИ ДЕРЕВЬЯ A BC D F G HE I LK J O P NM Уровень 4 Уровень 2 Уровень 3 Уровень 1 КОРЕНЬ УЗЕЛ (степени 2) ЛИСТ Уровень 4 насчитывает 8 элементов Порождённый элемент

20 ИЕРАРХИИ ИЛИ ДЕРЕВЬЯ A BC D F G HE I LK J O P NM Семейство размерности 3 Диаграмма максимального пути Диаграмма пути (глубина 3)

21 ДЕРЕВЬЯ 1.Самый верхний уровень иерархии имеет один узел, называемый корнем. 2.Все узлы, кроме корня, связываются с одним и только одним узлом на более высоком уровне по сравнению с ним самим. Дерево может быть определено как иерархия узлов с попарными связями, в которой: Рекурсивное определение дерева (Д.Кнут): Конечное множество T, состоящее из одного и более узлов, таких, что 1.Имеется один, специально обозначенный узел, называемый корнем данного дерева, 2.Остальные узлы (кроме корня) содержатся в m0 попарно не пересекающихся множествах T 1,…,T m, каждое из которых в свою очередь является деревом. Деревья T1,…,Tm называются поддеревьями данного корня.

22 РЕКУРСИЯ Объект называется рекурсивным, если он содержит сам себя или определен с помощью самого себя. Если процедура р содержит явное обращение к самой себе, то она называется явно рекурсивной. Если процедура р содержит обращение к некоторой процедуре q, которая в свою очередь содержит прямое или косвенное обращение к р, то р - называется косвенно рекурсивной. Рекурсивная программа не может вызывать себя бесконечно, иначе она никогда не остановится, таким образом в программе (функции) должна присутствовать еще один важный элемент - так называемое терминальное условие, то есть условие при котором программа прекращает рекурсивный процесс. Объект называется рекурсивным, если он содержит сам себя или определен с помощью самого себя. Если процедура р содержит явное обращение к самой себе, то она называется явно рекурсивной. Если процедура р содержит обращение к некоторой процедуре q, которая в свою очередь содержит прямое или косвенное обращение к р, то р - называется косвенно рекурсивной. Рекурсивная программа не может вызывать себя бесконечно, иначе она никогда не остановится, таким образом в программе (функции) должна присутствовать еще один важный элемент - так называемое терминальное условие, то есть условие при котором программа прекращает рекурсивный процесс.

23 РЕКУРСИЯ

24 ИЕРАРХИИ ИЛИ ДЕРЕВЬЯ A BC D F G HE I LK J O P NM

25 СПОСОБЫ ПРЕДСТАВЛЕНИЯ ДРЕВОВИДНЫХ СТРУКТУР A B C J K L I D E O F P H M G N (A(B(D(I),E(J,K,L)),C(F,(O),G(M,N),H(P)))) A B C D F G H E I L J O P N M K

26 ОБХОД ДЕРЕВА ПРЯМОЙ ПОРЯДОК A BC D F G HE I LK J O P NM

27 СБАЛАНСИРОВАННЫЕ И НЕСБАЛАНСИРОВАННЫЕ ДЕРЕВЬЯ

28 ОРГАНИЗАЦИЯ БИНАРНОГО ДЕРЕВА КАК СТРУКТУРЫ ДАННЫХ ABCDEFGHJ

29 ОРГАНИЗАЦИЯ БИНАРНОГО ДЕРЕВА ABCDEFGHJ

30 ПЕТЛИ В ДЕРЕВЬЯХ ABCDEFGHJ

31 D СТЕК И ДЕРЕВЬЯ A B E IJ A B C D F G H E I L KJOPN M KL C FG OMN H P X

32 СЕТЕВАЯ СТРУКТУРА ДАННЫХ