Презентация на тему: Алгоритмы и структуры данных

Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
ТЕРМИНОЛОГИЯ
Кольцевой односвязный список
Двусвязный список
Алгоритмы и структуры данных
Кольцевой двусвязный список
Простейшие операции над односвязными списками
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Реализация стеков с помощью односвязных списков
Проверка стека на пустоту Empty(S)
Выборка элемента из стека POP(S)
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Вставка и извлечение элементов из списка
Вставка InsAfter( P, x )
InsAfter( P, X)
Алгоритм
Удаление DelAfter( P )
Алгоритмы и структуры данных
Алгоритм DelAfter( P )
Просмотр односвязного списка при вставке и удалении
Алгоритмы и структуры данных
Алгоритм просмотра односвязного списка при вставке и удалении
Примеры типичных операций над списками
Обозначим P - рабочий указатель ; в начале процедуры P = Lst. Введем также указатель Q, который отстает на один элемент от P. Когда указатель P найдет элемент,
Алгоритмы и структуры данных
Алгоритм
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритм
Элементы заголовков в списках
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Нелинейные связанные структуры
Алгоритмы и структуры данных
Пример моделирования с помощью нелинейного списка
Алгоритмы и структуры данных
Реализация графа в виде нелинейного списка
Контрольные вопросы
Рекурсивные структуры данных
Деревья
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Представление деревьев
Представление дерева в виде нелинейного списка
Бинарные деревья
Формат элемента бинарного дерева
Процедура создания элемента бинарного дерева V = MakeTree (key, rec)
Упорядоченное бинарное дерево
Алгоритмы и структуры данных
Сведение m-арного дерева к бинарному
Графическое пояснение алгоритма
Реализация полученного бинарного дерева с помощью нелинейного двусвязного списка
Основные операции с деревьями
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Операция удаления поддерева
Операция вставки поддерева
Создание дерева бинарного поиска
Алгоритмы и структуры данных
К алгоритму построения дерева
Алгоритм создания дерева бинарного поиска
Рекурсивные алгоритмы обхода (прохождения) бинарных деревьев
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Пояснение рекурсии обхода бинарного дерева на примере процедуры intrave (tree)
Пояснение рекурсии обхода
Поиск
Ключи данных
Алгоритмы и структуры данных
Последовательный поиск
К последовательному поиску
Алгоритм последовательного поиска в массиве
Алгоритмы и структуры данных
Последовательный поиск в односвязном списке
Алгоритм поиска в списке
Эффективность последовательного поиска
Алгоритмы и структуры данных
Индексно-последовательный поиск
Таблицы индексно - последовательного поиска
Алгоритмы и структуры данных
Эффективность индексно-последовательного поиска
Алгоритмы и структуры данных
Методы оптимизации поиска
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Переупорядочивание таблицы поиска путем перестановки найденного элемента в начало списка
Алгоритм перестановки в начало
Алгоритмы и структуры данных
Метод транспозиции
Алгоритмы и структуры данных
Алгоритм метода транспозиции
Алгоритмы и структуры данных
Дерево оптимального поиска
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Бинарный поиск (метод деления пополам)
Обозначим : low - индекс нижней границы интервала поиска hi - индекс верхней границы интервала поиска mid - индекс середины интервала поиска
Эффективность бинарного поиска
Поиск по бинарному дереву
Алгоритмы и структуры данных
Алгоритм поиска по бинарному дереву
Алгоритмы и структуры данных
Поиск по бинарному дереву с включением (вставкой)
Алгоритмы и структуры данных
Поиск по бинарному дереву с удалением
Удаление узлов бинарного дерева
Алгоритмы и структуры данных
Предшественником удаляемого узла ( 12 ) является самый правый узел левого поддерева (11). Преемником узла (12) - самый левый узел правого поддерева (13).
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Контрольные вопросы
Сортировка
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Сортировка методом прямого включения
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритм сортировки методом прямого включения с барьером
Эффективность алгоритма прямого включения
Алгоритмы и структуры данных
Сортировка методом прямого выбора
Алгоритм сортировки прямым выбором
Эффективность алгоритма сортировки прямым выбором
Алгоритмы и структуры данных
Сортировка с помощью прямого обмена (пузырьковая сортировка)
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритм метода прямого обмена
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Эффективность алгоритма сортировки прямым обменом
Алгоритмы и структуры данных
Улучшенные методы сортировки
Сортировка Шелла (сортировка с уменьшающимся шагом)
Иллюстрация к сортировке Шелла
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритм сортировки Шелла
Subroutine ShellSort
Быстрая сортировка ( Quick Sort )
Алгоритм быстрой сортировки
Эффективность алгоритма Quick Sort
Алгоритм сортировки с помощью бинарного дерева
Контрольные вопросы
Экзаменационные вопросы по курсу «Алгоритмы и структуры данных»
Алгоритмы и структуры данных
Алгоритмы и структуры данных
Алгоритмы и структуры данных
1/229
Средняя оценка: 4.9/5 (всего оценок: 40)
Код скопирован в буфер обмена
Скачать (1027 Кб)
1

Первый слайд презентации: Алгоритмы и структуры данных

Лектор – заведующий кафедрой компьютерных технологий и систем КубГАУ, заслуженный деятель науки РФ, доктор технических наук, профессор Лойко Валерий Иванович

Изображение слайда
2

Слайд 2

ЛИТЕРАТУРА Основная Лойко В.И. Структуры и алгоритмы обработки данных. Учебное пособие. Краснодар: Кубанский государственный аграрный университет, 2000. Лойко В.И., Лаптев С.В. Структуры и алгоритмы обработки данных. Учебное пособие. Краснодар: Кубанский государственный аграрный университет, 2013. Лойко В.И., Лаптев С.В. Алгоритмы и структуры данных: Интернет портал. Краснодар: КубГАУ, 2012. Вирт Н. Алгоритмы и структуры данных. - М.: Мир, 2001. Ленгсам Й, Огенстайн М, Тененбаум А. Структуры данных для персональных ЭВМ. - М.: Мир, 1989. Дополнительная Хусаинов Б.С. Структуры и алгоритмы обработки данных. Примеры на языке Си (+CD). Учеб. пособие. - М. : Финансы и Статистика, 2004. Райли Д. Абстракция и структуры данных. Вводный курс. М.: Мир, 1993. Ахо А.В., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы. - М. - Санкт-Петербург - Киев: Вильямс, 2001. 4. Кондратьева С.Д. Введение в структуры данных.– М. Изд. МГТУ, 2000.– 376 с.

Изображение слайда
3

Слайд 3

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

Изображение слайда
4

Слайд 4

Элемент структуры данных S:=(D,R), где S - структура данных, D – данные, R - отношения.

Изображение слайда
5

Слайд 5

Изображение слайда
6

Слайд 6

Структуры данных классифицируются: 1. По связанности данных в структуре - если данные в структуре связаны очень слабо, то такие структуры называются несвязанными (вектор, массив, строки, стеки) - если данные в структуре связаны, то такие структуры называются связанными (связанные списки) 2. По изменчивости структуры в процессе выполнения программы - статические структуры - структуры, неменяющиеся до конца выполнения программы (записи, массивы, строки, векторы) - полустатические структуры (стеки, деки, очереди) - динамические структуры - происходит полное изменение при выполнении программы 3. По упорядоченности структуры - линейные (векторы, массивы, стеки, деки, записи) - нелинейные (многосвязные списки, древовидные структуры, графы) Наиболее важной характеристикой является изменчивость структуры в процессе выполнения программы

Изображение слайда
7

Слайд 7

СТАТИЧЕСКИЕ СТРУКТУРЫ Вектор (одномерный массив) - это чисто линейная упорядоченная структура, где отношение между ее элементами есть строго выраженная последовательность элементов структуры

Изображение слайда
8

Слайд 8

Массив – структура, в которой элементами являются векторы (элементы которого тоже являются элементами массива)

Изображение слайда
9

Слайд 9

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

Изображение слайда
10

Слайд 10

Изображение слайда
11

Слайд 11

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

Изображение слайда
12

Слайд 12

Логическая структура иерархической записи 1-ый уровень Студент = запись 2-ой уровень Номер 2-ой уровень Имя = запись 3-ий уровень Фамилия 3-ий уровень Имя 3-ий уровень Отчество 2-ой уровень Анкетные данные = запись 3-ий уровень Место рождения 3-ий уровень Год рождения 3-ий уровень Родители = запись 4-ый уровень Мать 4-ый уровень Отец 2-ой уровень Факультет 2-ой уровень Группа 2-ой уровень Оценки = запись 3-ий уровень Английский 3-ий уровень Физика

Изображение слайда
13

Слайд 13

Основные операции над записями: Прочтение содержимого поля записи. Занесение информации в поле записи. Все операции, которые разрешаются над полем записи, соответствующего типа.

Изображение слайда
14

Слайд 14

Таблица - это конечный набор записей

Изображение слайда
15

Слайд 15

Основные операции с таблицами: Поиск записи по заданному ключу. Занесение новой записи в таблицу.

Изображение слайда
16

Слайд 16

Списки - это набор определенным образом связанных элементов данных, которые в общем случае могут быть разного типа : E 1, E 2,........, E n,... n > 1 и не зафиксировано. Количество элементов списка может меняться в процессе выполнения программы. Различают 2 вида списков: несвязные и связные (несвязанные и связанные). В несвязных списках связь между элементами данных выражена неявно (векторы, записи). В связных списках в элемент данных заносится указатель связи с последующим или предыдущим элементом списка.

Изображение слайда
17

Слайд 17

ПОЛУСТАТИЧЕСКИЕ СТРУКТУРЫ К полустатическим структурам данных относят, в принципе, динамические структуры (такие как стеки, очереди и деки ), реализованные на статических векторах (одномерных массивах).

Изображение слайда
18

Слайд 18

Структура вида LIFO ( Last Input First Output - последним пришел, первым ушел ), при которой на обработку первым выбирается тот элемент, который поступил в нее последним, называется стеком.

Изображение слайда
19

Слайд 19

Операции, производимые над стеками: 1. Занесение элемента в стек. Push ( S, x ), где S - идентификатор стека, x - заносимый элемент. 2. Выборка элемента из стека. Pop ( S ) 3. Определение пустоты стека. Empty ( S ) 4. Прочтение элемента без его выборки из стека. StackTop ( S ) 5. Определение переполнения стека (для полустатических структур) Full(S)

Изображение слайда
20

Слайд 20

i = указатель вершины Push ( S, x ) i = i+1 S(i) = x return Full(S) if i = maxS then “ переполнение ” Stop return endif Pop ( S ) x = S(i) i = i -1 return Empty ( S ) if i = 0 then “ пусто ” Stop return endif StackTop ( S ) x = S(i) return

Изображение слайда
21

Слайд 21

Push ( S, i ) if i = maxS then “ переполнение ” Stop return endif i = i+1 S(i) = x return

Изображение слайда
22

Слайд 22

Pop ( S ) if i = 0 then “ пусто ” Stop return endif x = S(i) i = i -1 return

Изображение слайда
23

Слайд 23

Empty ( S ) if i = 0 then empty = true else empty = false endif return Pop ( S ) Empty ( S ) if empty = true then “ пусто ” Stop return endif x = S(i) i = i -1 return

Изображение слайда
24

Слайд 24

Очередь – это структура вида FIFO ( First In First Out - первым пришел, первым ушел). Очередь открыта с обеих сторон, но элементы могут вставляться только в конец очереди, а удаляться только из начала очереди, т. е. удаляется первый помещаемый в очередь элемент, после чего ранее второй элемент становится первым. По этой причине очередь часто называют списком, организованным по принципу «первый размещенный первым удаляется» в противоположность принципу стековой организации — «последний размещенный первым удаляется». Для очереди вводят два указателя: один - на начало очереди ( F ), второй- на ее конец ( R ).

Изображение слайда
25

Слайд 25

Операции, производимые над очередью Операция insert ( q, x ) - помещает элемент х в конец очереди q. Операция remove ( q ) удаляет элемент из начала очереди q и присваивает его значение внешней переменной. Операция, empty (q) - вводится с целью предотвращения возможности выборки из пустой очереди. Операция full ( q ) - вводится с целью предотвращения возможности переполнения одномерного массива, на котором реализуется полустатическая очередь.

Изображение слайда
26

Слайд 26

Пример работы c очередью при использовани и стандартных процедур maxQ = 5 R = 0, F = 1 Условие пустоты очереди R < F (0 < 1) Произведем вставку элементов A, B и C в очередь : Insert (q, A); Insert (q, B); Insert (q, C);

Изображение слайда
27

Слайд 27

Убираем элементы A и B из очереди : Remove (q); Remove (q);

Изображение слайда
28

Слайд 28

Изображение слайда
29

Слайд 29

Empty (q) if R < F then empty = true else empty = false endif return Insert (q, x) Full (q) if full = true then ‘ переполнение ’ stop return endif R = R + 1 q(R) = x return Remove (q) Empty (q) if empty = true then ‘ пусто ’ stop return endif x = q(F) F = F + 1 return Full (q) if R = maxQ then full = true else full = false endif return Алгоритмы основных операций с очередью

Изображение слайда
30

Слайд 30

Убираем элементы С, D и E из очереди : Remove (q); Remove (q); Remove (q). Добавляем элементы D и E : Insert (q, D); Insert (q, E);

Изображение слайда
31

Слайд 31

Возникла абсурдная ситуация, при которой очередь является пустой ( R < F ), однако новый элемент разместить в ней нельзя, так как R = maxQ.

Изображение слайда
32

Слайд 32

Одним из решений возникшей проблемы может быть модификация операции Remove ( q ) таким образом, что при удалении очередного элемента вся очередь смещается к началу массива. Переменная F больше не требуется, поскольку первый элемент массива всегда является началом очереди. Пустая очередь представлена очередью, для которой значение R равно нулю.

Изображение слайда
33

Слайд 33

Произведем вставку элементов A, B и C в очередь : Insert (q, A); Insert (q, B); Insert (q, C);

Изображение слайда
34

Слайд 34

Убираем элемент A из очереди : Remove (q)

Изображение слайда
35

Слайд 35

Операция remove ( q ) может быть в этом случае реализована следующим образом : Remove ( q ) x = q(1) for i =1 to R-1 q(i) = q(i+1) next i R =R-1 return

Изображение слайда
36

Слайд 36

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

Изображение слайда
37

Слайд 37

Предположим, что очередь содержит три элемента - в позициях 3, 4 и 5 пятиэлементного массива. Хотя массив и не заполнен, последний элемент очереди занят.

Изображение слайда
38

Слайд 38

Если теперь делается попытка поместить в очередь элемент G, то он будет записан в первую позицию массива. Первый элемент очереди есть q (3), за которым следуют элементы q (4), q (5) и q (1). К сожалению, условие R < F больше не годится для проверки очереди на пустоту.

Изображение слайда
39

Слайд 39

Одним из способов решения этой проблемы является введение соглашения, при котором значение F есть индекс элемента массива, немедленно предшествующего (по кольцу) первому элементу очереди, а не индекс самого первого элемента. В этом случае, поскольку R содержит индекс последнего элемента очереди, условие F = R подразумевает, что очередь пуста.

Изображение слайда
40

Слайд 40

Перед началом работы с кольцевой очередью в F и R устанавливается значение последнего индекса массива maxQ, а не 1 и 0. Поскольку R = F, то очередь изначально пуста.

Изображение слайда
41

Слайд 41

Основные операции с кольцевой очередью Вставка элемента q в очередь x Insert(q,x) ; Извлечение элемента из очереди x Remove ( q ) ; Проверка очереди на пустоту Empty ( q ) ; Проверка очереди на переполнение Full(q).

Изображение слайда
42

Слайд 42

Операция Empty ( q ) if F = R then empty = true else empty = false endif return Операция Remove ( q ) empty (q) if empty = true then “ пусто ” stop endif if F = maxQ then F =1 else F = F+1 endif x = q(F) return Проверка на «пустоту» в операции Remove производится сразу же после входа в подпрограмму, до момента обновления значения F, а з начение F должно быть модифицировано до момента извлечения элемента.

Изображение слайда
43

Слайд 43

Переполнение очереди происходит в том случае, если весь массив уже занят элементами очереди, и при этом делается попытка разместить в ней еще один элемент. Исходное состояние очереди Поместим в очередь элемент G.

Изображение слайда
44

Слайд 44

Если произвести следующую вставку, то массив становится целиком заполненным, и попытка произвести еще одну вставку приводит к переполнению. Это регистрируется тем фактом, что F = R, то есть это соотношение как раз и указывает на переполнение. Очевидно, что при такой реализации нет возможности сделать различие между пустой и заполненной очередью.

Изображение слайда
45

Слайд 45

Одно из решений состоит в том, чтобы пожертвовать одним элементом массива и позволить очереди расти до объема, на единицу меньшего максимального. Предыдущий рисунок иллюстрирует именно это соглашение. Попытка разместить в очереди еще один элемент приведет к переполнению. Проверка на переполнение в подпрограмме insert производится после установления нового значения для R, в то время как проверка на «пустоту» в подпрограмме remove производится сразу же после входа в подпрограмму, до момента обновления значения F.

Изображение слайда
46

Слайд 46

Подпрограмма Insert ( q,x ) может быть записана следующим образом: if R = maxQ then R = 1 else R = R+1 endif ‘ проверка на переполнение ’ if R = F then print «переполнение очереди» stop endif q (R) = x return Проверка на переполнение в подпрограмме производится после установления нового значения для R.

Изображение слайда
47

Слайд 47

Дек Происходит от английского DEQ - Double Ended Queue (очередь с двумя концами). Дек можно рассматривать как два стека, соединенных нижними границами. Операции над деками: Insert ( d, x ) - вставка элемента. Remove(d) - извлечение элемента из дека. Empty(d) - проверка на пустоту. Full(d) - проверка на переполнение.

Изображение слайда
48

Слайд 48

Контрольные вопросы 1. К каким структурам данных относятся очереди и стеки ? 2. Каково правило выборки элемента из стека ? 3. Какая операция читает верхний элемент стека без его удаления ? 4. Какую дисциплину обслуживания принято называть FIFO, а какую - LIFO ? 5. Признак переполнения кольцевой очереди ? 6. Признак пустой очереди ? 7. Что называется списком? 8. Перечислите виды списков. 9. Назовите элементы и указатели очереди. 10. Как организуется кольцевая очередь? 11. Какова особенность деков?

Изображение слайда
49

Слайд 49

Динамические структуры данных

Изображение слайда
50

Слайд 50

Динамические структуры данных имеют две особенности: Заранее не определено количество элементов в структуре. Элементы динамических структур физически не имеют жесткой линейной упорядоченности. Они могут быть разбросаны по памяти.

Изображение слайда
51

Слайд 51

P 1 и P 2 это указатели, содержащие адреса элементов, с которыми связаны соответствующие элементы структуры.

Изображение слайда
52

Слайд 52

Связные списки С точки зрения логического представления различают линейные и нелинейные списки. К линейным спискам относятся односвязные и двусвязные списки. К нелинейным - многосвязные. Элемент списка в общем случае представляет собой информационное поле и одно или несколько полей указателей.

Изображение слайда
53

Слайд 53

Односвязные списки Элемент односвязного списка содержит, как минимум, два поля: информационное поле ( info ) и поле указателя ( ptr ).

Изображение слайда
54

Слайд 54

Особенностью указателя является то, что он дает только адрес последующего элемента списка. Поле указателя последнего элемента в списке является пустым ( NIL ). LST - указатель на начало списка. Список может быть пустым, тогда LST будет равен NIL. Доступ к элементу списка осуществляется только от его начала, то есть обратной связи в этом списке нет.

Изображение слайда
55

Слайд 55: ТЕРМИНОЛОГИЯ

p - указатель node(p) – узел, на который ссылается указатель p [ при этом неважно в какое место изображения элемента (узла) списка он направлен на рисунке ] ptr(p) – ссылка на последующий элемент узла node(p) ptr(ptr(p)) – ссылка последующего для node(p) узла на последующий для него элемент

Изображение слайда
56

Слайд 56: Кольцевой односвязный список

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

Изображение слайда
57

Слайд 57: Двусвязный список

Двусвязный список характеризуется тем, что у любого элемента есть два указателя. Один указывает на предыдущий (левый) элемент ( L ), другой указывает на последующий (правый) элемент ( R ).

Изображение слайда
58

Слайд 58

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

Изображение слайда
59

Слайд 59: Кольцевой двусвязный список

Двусвязные списки получают следующим образом: в качестве значения поля R последнего элемента принимают ссылку на первый элемент, а в качестве значения поля L первого элемента - ссылку на последний элемент.

Изображение слайда
60

Слайд 60: Простейшие операции над односвязными списками

Вставка элемента в начало односвязного списка Удаление элемента из начала односвязного списка

Изображение слайда
61

Слайд 61

Вставка в начало списка P=GetNode Info(P)= x Ptr(P) = Lst Lst = P return

Изображение слайда
62

Слайд 62

Удаление из начала списка P = Lst x =Info(P) Lst = Ptr(P) FreeNode(P ) return

Изображение слайда
63

Слайд 63: Реализация стеков с помощью односвязных списков

Стековые операции, применимые к спискам 1. Чтобы добавить элемент в стек, надо в алгоритме вставки в начало списка заменить указатель Lst на указатель S (операция Push(S, x ) ). P = GetNode Info(P) = x Ptr(P) = S S = P return

Изображение слайда
64

Слайд 64: Проверка стека на пустоту Empty(S)

if S = Nil then print “ Стек пуст ” Stop endif return

Изображение слайда
65

Слайд 65: Выборка элемента из стека POP(S)

Empty(S) P = S X = Info(P) S = Ptr(P) FreeNode(P) return

Изображение слайда
66

Слайд 66

Операции с очередью, реализованной на односвязном списке Указатель начала списка принимаем за указатель начала очереди F, а указатель R, указывающий на последний элемент списка - за указатель конца очереди.

Изображение слайда
67

Слайд 67

Проверка очереди на пустоту Empty(Q) If F = nil then print “ Очередь пуста ” S top endif return

Изображение слайда
68

Слайд 68

Операция удаления из очереди Remove(Q) Операция удаления из очереди должна происходить из ее начала. If F = nil then print “ Очередь пуста ” S top endif P = F F = Ptr(P) X = Info(P) FreeNode(P) return

Изображение слайда
69

Слайд 69

Операция вставки в очередь Insert(Q, x) Операция вставки в очередь должна осуществляться к ее концу. P = GetNode Info(P) = x Ptr(P) = Nil Ptr(R)= P R = P return

Изображение слайда
70

Слайд 70

Контрольные вопросы 1.Какие динамические структуры Вам известны? 2.В чем отличительная особенность динамических объектов? 3.Какой тип данных представлен для работы с динамическими объектами? 4.Как связаны элементы в динамической структуре ? 5.Назовите основные особенности односвязного списка. 6.В чем отличие линейных списков от кольцевых ? 7.Зачем были введены двусвязные списки ? 8.В чем разница в операциях, производимых над односвязными и двусвязными списками ? 9.Какой список является более удобным в обращении, односвязный или двусвязный ? 10.Что такое указатель? 11.Какие стековые операции можно производить над списками? 12.Какие операции, производимые над очередью, можно производить над списками ?

Изображение слайда
71

Слайд 71

Организация операций Getnode, Freenode и утилизация освободившихся элементов Для более эффективного использования памяти компьютера при работе его со списками, создается свободный список, имеющий тот же формат полей, что и у функциональных списков. Как правило, свободный список создается в памяти машины как стек. Создание нового элемента (операция GetNode ) эквивалентно выборке элемента из свободного стека, а операция FreeNode - добавлению в свободный стек освободившегося элемента.

Изображение слайда
72

Слайд 72

Пустой список по типу стека с указателем начала списка - Avail Операция P = GetNode Для реализации операции GetNode необходимо указателю сгенерированного элемента присвоить значение указателя начала свободного списка, а указатель начала свободного списка перенести к следующему элементу. Перед этим надо проверить, есть ли элементы в списке. Пустота свободного списка ( Avail = n il ), эквивалентна переполнению функционального списка.

Изображение слайда
73

Слайд 73

If Avail = Nil then Print “ Переполнение ” Stop else P = Avail Avail = Ptr(Avail) e ndif return

Изображение слайда
74

Слайд 74

Операция FreeNode (P) При освобождении элемента из функционального списка, он заносится в свободный список. Ptr(P) = Avail Avail = P return

Изображение слайда
75

Слайд 75

Метод счетчиков В каждый элемент многосвязного списка вставляется поле счетчика, который считает количество ссылок на данный элемент. Когда счетчик элемента оказывается в нулевом состоянии, а поля указателей элемента находятся в состоянии nil, этот элемент может быть возвращен в пул свободных элементов. Утилизация освободившихся элементов в многосвязных списках

Изображение слайда
76

Слайд 76

Метод маркера (сборки мусора, то есть неиспользуемых элементов) Если с каким-то элементом установлена связь, то однобитовое поле элемента (маркер) устанавливается в “1”, иначе - в “0”. По сигналу переполнения отыскиваются элементы, у которых маркер установлен в ноль, т. е. включается программа сборки мусора, которая просматривает всю отведенную память и возвращает в список свободных элементов все элементы, не помеченные маркером.

Изображение слайда
77

Слайд 77

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

Изображение слайда
78

Слайд 78

Пример Необходимо вставить элемент X в существующий массив между 5-м и 6-м элементами.

Изображение слайда
79

Слайд 79

Для проведения данной операции в массиве нужно сместить “вниз” все элементы, начиная с X6 - увеличить их индексы на единицу. В результате вставки получаем следующий массив :

Изображение слайда
80

Слайд 80

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

Изображение слайда
81

Слайд 81: Вставка и извлечение элементов из списка

Сначала определяем элемент, после которого необходимо провести операцию вставки или удаления. Вставка производится с помощью процедуры InsAfter( P, x ), а удаление - DelAfter( P ). При этом рабочий указатель P должен указывать на элемент, после которого необходимо произвести вставку или удаление.

Изображение слайда
82

Слайд 82: Вставка InsAfter( P, x )

Пусть необходимо вставить новый элемент с информационным полем x после элемента, на который указывает рабочий указатель P.

Изображение слайда
83

Слайд 83: InsAfter( P, X)

Q X Lst P Lst P Lst P Lst P Lst P Lst P nil

Изображение слайда
84

Слайд 84: Алгоритм

Q = GetNode i nfo(Q) = x ptr(Q) = ptr(P) p tr(P) = Q return

Изображение слайда
85

Слайд 85: Удаление DelAfter( P )

Пусть необходимо удалить элемент списка, который следует после элемента, на который указывает рабочий указатель P.

Изображение слайда
86

Слайд 86

DelAfter( P ) Lst Lst Lst Lst Lst nil P Q

Изображение слайда
87

Слайд 87: Алгоритм DelAfter( P )

Q = ptr(P) X = info(Q) ptr(P) = ptr(Q) FreeNode(Q) return

Изображение слайда
88

Слайд 88: Просмотр односвязного списка при вставке и удалении

Обозначим через P - рабочий указатель ; в начале процедуры P = Lst. Введем также указатель Q, который отстает на один элемент от P ; в начале процедуры Q = nil. Когда указатель P получит значение nil, цикл просмотра заканчивается.

Изображение слайда
89

Слайд 89

Анимация просмотра односвязного списка при вставке и удалении Lst nil P Q Q P Q P

Изображение слайда
90

Слайд 90: Алгоритм просмотра односвязного списка при вставке и удалении

Q =Nil P = Lst while (P <> nil) do Q = P P = ptr(P) endwhile return

Изображение слайда
91

Слайд 91: Примеры типичных операций над списками

Задача 1 Требуется просмотреть список и удалить элементы, у которых информационные поля равны 4.

Изображение слайда
92

Слайд 92: Обозначим P - рабочий указатель ; в начале процедуры P = Lst. Введем также указатель Q, который отстает на один элемент от P. Когда указатель P найдет элемент, последний будет удален относительно указателя Q как последующий элемент

Изображение слайда
93

Слайд 93

Анимация решения задачи 1 Lst nil P Q 4 4 8 21 P Q P

Изображение слайда
94

Слайд 94: Алгоритм

x = 4 Q = nil P = Lst while P <> nil do if info(P) = x then if Q = nil then Pop(Lst) P = Lst else DelAfter(Q) endif else Q = P P = Ptr(P) endif endwhile return

Изображение слайда
95

Слайд 95

Задача 2 Дан упорядоченный по возрастанию i nfo - полей список. Необходимо вставить в этот список элемент со значением X, не нарушив упорядоченности списка. Пусть X = 16 Начальные условия: Q = Nil, P = Lst

Изображение слайда
96

Слайд 96

Анимация решения задачи 2 Lst nil P Q 4 9 8 21 X > info(P) = ? Да ! Q P Q P Нет ! 16 S Q

Изображение слайда
97

Слайд 97: Алгоритм

X = 16 Q =Nil P = Lst while (P <> nil) and (X > info(P)) do Q = P P = Ptr(P) endwhile if Q = nil then Push(Lst, X) endif InsAfter(Q, X) return

Изображение слайда
98

Слайд 98: Элементы заголовков в списках

Для создания списка с заголовком в начало списка вводится дополнительный элемент, который может содержать информацию о списке.

Изображение слайда
99

Слайд 99

В заголовок списка часто помещают динамическую переменную, содержащую количество элементов в списке (не считая самого заголовка).

Изображение слайда
100

Слайд 100

Если список пуст, то остается только заголовок списка. Удобно занести в информационное поле заголовка значение указателя конца списка. Тогда, если список используется как очередь, то F = Lst, а R = Info(Lst ). Информационное поле заголовка можно использовать для хранения рабочего указателя при просмотре списка P = Info(Lst). Другими словами, заголовок - это дескриптор (описатель) структуры данных.

Изображение слайда
101

Слайд 101: Нелинейные связанные структуры

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

Изображение слайда
102

Слайд 102

Можно выделить три отличительных признака нелинейной структуры: 1) Любой элемент структуры может ссылаться на любое число других элементов структуры, то есть может иметь любое число полей -указателей. 2) На данный элемент структуры может ссылаться любое число других элементов этой структуры. 3) Ссылки могут иметь вес, то есть подразумевается иерархия ссылок.

Изображение слайда
103

Слайд 103: Пример моделирования с помощью нелинейного списка

Пусть имеется дискретная система, в графе состояния которой узлы - это номера состояний, а ребра – направления переходов из состояния в состояние

Изображение слайда
104

Слайд 104

Входной сигнал в систему это X. Реакцией на входной сигнал является выработка выходного сигнала Y и переход в соответствующее состояние. Граф состояния дискретной системы можно представит в виде комбинации одного двусвязного и трех односвязных списков, которые вместе составляют нелинейный двусвязный список. При этом в информационных полях должна записываться информация о состояниях системы и ребрах. Указатели элементов должны формировать логические ребра системы.

Изображение слайда
105

Слайд 105: Реализация графа в виде нелинейного списка

Изображение слайда
106

Слайд 106: Контрольные вопросы

1. Для чего предназначены операции Getnode и Freenode? 2. Какие методы утилизации вы знаете ? 3. Перечислите элементы заголовков в списках. 4.Зависит ли время, затраченное на вставку элемента в односвязный список, от количества элементов в списке ? 5. Где процесс вставки и удаления эффективнее, в списке или в массиве ? 6. Как можно производить просмотр односвязного списка? 7. Что означает AVAIL? 8. Какой недостаток односвязных списков по сравнению с массивом? 9. Какие структуры являются нелинейными ? 10. Каковы признаки отличия нелинейных структур? 11. Как можно создать нелинейную связную структуру? 12. Что такое граф состояния ?

Изображение слайда
107

Слайд 107: Рекурсивные структуры данных

Рекурсивная структуры данных - структура данных, элементы которой являются такими же структурами данных

Изображение слайда
108

Слайд 108: Деревья

Дерево - нелинейная связанная структура данных. Дерево характеризуется следующими признаками: - дерево имеет один элемент, на который нет ссылок от других элементов. Этот элемент называется корнем дерева; - в дереве можно обратиться к любому элементу путем прохождения конечного числа ссылок (указателей); - каждый элемент дерева связан только с одним предыдущим элементом.

Изображение слайда
109

Слайд 109

Любой узел дерева может быть промежуточным либо терминальным ( листом ). На рисунке промежуточными являются элементы M1, M2 ; листьями - A, B, C, D, E. Характерной особенностью терминального узла является отсутствие ветвей. Высота дерева - это количество уровней дерева. У дерева на рисунке высота равна двум.

Изображение слайда
110

Слайд 110

Количество ветвей, растущих из узла дерева, называется степенью исхода узла (на рисунке для M1 степень исхода 2, для М2 - 3). Для описание связей между узлами дерева применяют также следующую терминологию: М1 - “ отец ” для элементов А и В. А и В - “ сыновья ” узла М1.

Изображение слайда
111

Слайд 111

Деревья могут классифицироваться по степени исхода : 1) если максимальная степень исхода равна m, то это - m-арное дерево; 2) если степень исхода равна либо 0, либо m, то это - полное m-арное дерево; 3) если максимальная степень исхода равна 2, то это - бинарное дерево; 4) если степень исхода равна либо 0, либо 2, то это - полное бинарное дерево.

Изображение слайда
112

Слайд 112: Представление деревьев

Наиболее удобно деревья представлять в памяти ЭВМ в виде связанных списков. Элемент списка должен содержать информационные поля, в которых могут содержаться значение ключа узла и другая хранимая информация, а также поля-указатели, число которых равно степени исхода.

Изображение слайда
113

Слайд 113: Представление дерева в виде нелинейного списка

Изображение слайда
114

Слайд 114: Бинарные деревья

Согласно представлению деревьев в памяти ЭВМ каждый элемент бинарного дерева является записью, содержащей четыре поля. Значения этих полей - соответственно ключ записи, текст записи, ссылка на элемент влево – вниз и ссылка на элемент вправо – вниз.

Изображение слайда
115

Слайд 115: Формат элемента бинарного дерева

Изображение слайда
116

Слайд 116: Процедура создания элемента бинарного дерева V = MakeTree (key, rec)

p = getnode r (p) = rec k (p) = key v = p left ( v ) = nil right (v) = nil return

Изображение слайда
117

Слайд 117: Упорядоченное бинарное дерево

В упорядоченном бинарном дереве левый сын имеет ключ меньший, чем у отца, а значение ключа правого сына больше значения ключа отца. Например, построим бинарное дерево из следующих элементов: 50, 46, 61, 48, 29, 55, 79.

Изображение слайда
118

Слайд 118

Получено идеально сбалансированное дерево - дерево, в котором левое и правое поддеревья имеют количество уровней, отличающихся не более чем на единицу.

Изображение слайда
119

Слайд 119: Сведение m-арного дерева к бинарному

Неформальный алгоритм: 1.В любом узле дерева отсекаются все ветви, кроме крайней левой, соответствующей старшим сыновьям. 2.Соединяются горизонтальными линиями все сыновья одного родителя. 3. Старшим (левым) сыном в любом узле полученной структуры будет узел, находящийся под данным узлом (если он есть).

Изображение слайда
120

Слайд 120: Графическое пояснение алгоритма

Изображение слайда
121

Слайд 121: Реализация полученного бинарного дерева с помощью нелинейного двусвязного списка

Изображение слайда
122

Слайд 122: Основные операции с деревьями

1. Обход дерева. 2. Удаление поддерева. 3. Вставка поддерева. Для выполнения обхода дерева необходимо выполнить три процедуры: 1.Обработка корня. 2.Обработка левой ветви. 3.Обработка правой ветви.

Изображение слайда
123

Слайд 123

В зависимости от того, в какой последовательности выполняются эти три процедуры, различают три вида обхода. 1.Обход сверху вниз. Процедуры выполняются в последовательности 1- 2 - 3. 2.Обход слева направо. Процедуры выполняются в последовательности 2 - 1- 3. 3.Обход снизу вверх. Процедуры выполняются в последовательности 2 - 3 -1.

Изображение слайда
124

Слайд 124

A B C D E F G A-B-C-E-D-F-G – сверху вниз C-B-D-E-F-A-G – слева направо C-D-F-E-B-G-A – снизу вверх Направления обхода дерева

Изображение слайда
125

Слайд 125

В зависимости от того, после какого по счету захода в узел он подвергается обработке, реализуется один из трех видов обхода. Если обработка идет после первого захода в узел, то это обход сверху вниз, если после второго - то слева направо, если после третьего - то снизу вверх.

Изображение слайда
126

Слайд 126: Операция удаления поддерева

Необходимо указать узел, к которому подсоединяется удаляемое поддерево и указатель корня этого поддерева. Исключение поддерева состоит в том, что разрывается связь с удаляемым поддеревом, т. е. указатель элемента, связанного с узлом-корнем удаляемого поддерева, устанавливается в nil.

Изображение слайда
127

Слайд 127: Операция вставки поддерева

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

Изображение слайда
128

Слайд 128: Создание дерева бинарного поиска

Пусть заданы элементы с ключами: 14, 18, 6, 21, 1, 13, 15. Построим упорядоченное бинарное дерево по этим ключам.

Изображение слайда
129

Слайд 129

14 18 tree q p v p 14, 18 К алгоритму построения дерева

Изображение слайда
130

Слайд 130: К алгоритму построения дерева

Изображение слайда
131

Слайд 131: Алгоритм создания дерева бинарного поиска

read (key, rec) tree = maketree(key, rec) while not eof do p = tree q = tree read (key, rec) v = maketree(key, rec) while p <> nil do q = p if key < k(p) then p = left(p) else p = right(p) endif endwhile if key < k(q) then left(q) = v else right(q) = v endif endwhile return

Изображение слайда
132

Слайд 132: Рекурсивные алгоритмы обхода (прохождения) бинарных деревьев

1. Сверху вниз А, В, С. 2. Слева направо или симметричное прохождение В, А, С. 3. Снизу вверх В, С, А. Наиболее часто применяется второй способ.

Изображение слайда
133

Слайд 133

“ сверху вниз ” subroutine pretrave (tree) if tree <> nil then print info(tree) pretrave(left(tree)) pretrave(right(tree)) endif return

Изображение слайда
134

Слайд 134

“ симметричный ” subroutine intrave (tree) if tree <> nil then intrave(left(tree)) print info(tree) intrave(right(tree)) endif return

Изображение слайда
135

Слайд 135: Пояснение рекурсии обхода бинарного дерева на примере процедуры intrave (tree)

Пронумеруем строки алгоритма процедуры if tree <> nil then intrave (left(tree)) print info (tree) intrave (right (tree)) endif return Обозначим указатели : t → tree; l → left; r → right.

Изображение слайда
136

Слайд 136: Пояснение рекурсии обхода

Изображение слайда
137

Слайд 137: Поиск

Поиск является одной из основных операций при обработке информации в ЭВМ. Ее назначение - по заданному аргументу найти среди массива данных те данные, которые этому аргументу соответствуют.

Изображение слайда
138

Слайд 138: Ключи данных

Набор данных (любых) будем называть таблицей или файлом. Любое данное (или элемент структуры) отличается каким-то признаком от других данных. Этот признак называется ключом. Ключ может быть первичным ( уникальным ), т. е. в таблице существует только одна запись с этим ключом. Такой уникальный ключ называется первичным. Вторичный ключ в одной таблице может повторяться, но по нему тоже можно организовать поиск. Ключи данных могут быть собраны в одном месте (в другой таблице). Ключи, которые выделены из таблицы данных и организованы в свой файл, называются внешними ключами. Если ключ находится в записи, которую определяет, то он называется внутренним.

Изображение слайда
139

Слайд 139

Поиском называется алгоритм, определяющий соответствие ключа заданному аргументу. Результатом работы алгоритма поиска может быть нахождение этого ключа или отсутствие его в таблице. В случае нахождения ключа (и информации ему соответствующей) возможны две операции: обработка найденной информации ; удаление найденной информации. В случае отсутствия ключа возможны тоже две операции: индикация того, что ключа нет ; вставка ключа (и информации) в таблицу.

Изображение слайда
140

Слайд 140: Последовательный поиск

Последовательный поиск применяется в том случае, если неизвестна организация данных или данные неупорядочены. Тогда производится последовательный просмотр по всей таблице начиная от младшего адреса в оперативной памяти и кончая самым старшим. Пусть k - массив ключей. Для каждого k(i) существует r(i) – запись информации. Key - аргумент поиска. Ему соответствует информационная запись rec.

Изображение слайда
141

Слайд 141: К последовательному поиску

Изображение слайда
142

Слайд 142: Алгоритм последовательного поиска в массиве

Переменная search хранит индекс найденного элемента. for i = 1 to n if k(i) = key then search = i return endif next i search = 0 return

Изображение слайда
143

Слайд 143

Если элемент в таблице не найден и необходимо произвести вставку, то последние два оператора заменяются на n = n + 1 k(n) = key r(n) = rec search = n return

Изображение слайда
144

Слайд 144: Последовательный поиск в односвязном списке

Если таблица данных задана в виде списка, то производится последовательный поиск в списке

Изображение слайда
145

Слайд 145: Алгоритм поиска в списке

q = nil p = table while (p <> nil) do if k(p) = key then search = p return endif q = p p = nxt(p) endwhile s = getnode k(s) = key r(s) = rec nxt(s) = nil if q = nil then table = s else nxt(q) = s endif search = s return

Изображение слайда
146

Слайд 146: Эффективность последовательного поиска

Эффективность любого поиска может оцениваться по количеству сравнений С аргумента поиска с ключами таблицы данных. Чем меньше количество сравнений, тем эффективнее алгоритм поиска. Эффективность последовательного поиска в массиве C min = 1, C max = n. Если данные расположены равновероятно во всех ячейках массива, то C ср ≈ ( n + 1)/2. Эффективность последовательного поиска в списке - то же самое. Порядок эффективности последовательного поиска O ( n )

Изображение слайда
147

Слайд 147

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

Изображение слайда
148

Слайд 148: Индексно-последовательный поиск

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

Изображение слайда
149

Слайд 149: Таблицы индексно - последовательного поиска

Изображение слайда
150

Слайд 150

Алгоритм индексно - последовательного поиска i = 1 while (i <= m) and (kind(i) <= key) do i=i+1 endwhile if i = 1 then low = 1 else low = pind(i-1) endif if i = m+1 then hi = n else hi = pind(i)-1 endif for j = low to hi if key = k(j) then search = j return endif next j search = 0 return

Изображение слайда
151

Слайд 151: Эффективность индексно-последовательного поиска

Ecли считать равновероятным появление всех значений аргумента поиска, то эффективность индексно-последовательного поиска можно рассчитать следующим образом. Введем обозначения: n - размер основной таблицы; m - размер индексной таблицы; p - размер шага; m = n / p

Изображение слайда
152

Слайд 152

Тогда C = (m+ 1 )/ 2 + ( n + 1 )/ 2 = (n/p+ 1 )/ 2 + ( n + 1 )/ 2 = = n/ 2 p + n / 2 + 1 Продифференцируем C по p и приравняем производную нулю : d C /dp = (d/dp) (n/ 2 p + n / 2 +1 ) = - n / 2 p 2 + 1 / 2 = 0 Отсюда p 2 = n ; p опт = Подставив р опт в выражение для C, получим следующее количество сравнений: C = + 1 Порядок эффективности индексно-последовательного поиска O ( )

Изображение слайда
153

Слайд 153: Методы оптимизации поиска

Будем считать, что искомый элемент в таблице существует. Можно говорить о некотором значении вероятности поиска того или иного элемента в таблице. Тогда вся таблица поиска может быть представлена как система с дискретными состояниями, а вероятность поиска i - го элемента - это вероятность p(i) i - го состояния системы.

Изображение слайда
154

Слайд 154

Количество сравнений при поиске в таблице, представленной как дискретная система, представляет собой значение дискретной случайной величины, определяемой вероятностями состояний и номерами состояний системы. Z = C = 1 p( 1 ) + 2 p( 2 ) + 3 p( 3 ) +…+ np(n)

Изображение слайда
155

Слайд 155

Желательно, чтобы p (1) ≥ p (2) ≥ p (3) ≥ … ≥ p ( n ). Это минимизирует количество сравнений, то есть увеличивает эффективность. Так как последовательный поиск начинается с первого элемента, то на это место надо поставить элемент, к которому чаще всего обращаются (с наибольшей вероятностью поиска).

Изображение слайда
156

Слайд 156: Переупорядочивание таблицы поиска путем перестановки найденного элемента в начало списка

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

Изображение слайда
157

Слайд 157: Алгоритм перестановки в начало

q= nil p = table while (p <> nil) do if key = k(p) then search = p if q = nil then 'перестановка не нужна' return endif nxt(q) = nxt(p) nxt(p) = table table = p return endif q = p p = nxt(p) endwhile search = 0 return

Изображение слайда
158

Слайд 158

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

Изображение слайда
159

Слайд 159: Метод транспозиции

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

Изображение слайда
160

Слайд 160

р - рабочий указатель q - вспомогательный указатель, отстает на один шаг от р s - вспомогательный указатель, отстает на два шага от р

Изображение слайда
161

Слайд 161: Алгоритм метода транспозиции

s = nil q = nil p = table while (p <> nil) do if key = k(p) then ‘ нашли, транспонируем if q = nil then ‘ переставлять не надо return endif nxt(q) = nxt(p) nxt(p) = q if s = nil then table = p else nxt(s) = p search = p endif return endif s =q q = p p = nxt(p) endwhile search = nil return

Изображение слайда
162

Слайд 162

Этот метод удобен при поиске не только в списках, но и в массивах (так как меняются только два стоящих рядом элемента ).

Изображение слайда
163

Слайд 163: Дерево оптимального поиска

Число сравнений, необходимых для поиска по дереву бинарного поиска ( бинарному дереву ), C = О (log n). Рассмотрим деревья бинарного поиска, приведенные на рисунках a и б. Оба дерева содержат три элемента - К 1, К 2, К 3, где К 1 <К 2 <К 3.

Изображение слайда
164

Слайд 164

Число сравнений ключей, которые необходимо сделать для извлечения некоторой записи, равно номеру уровня этой записи в дереве бинарного поиска плюс 1. Предположим, что: p 1 - вероятность поиска первого элемента р2 - вероятность поиска второго элемента р3 - вероятность поиска третьего элемента q 0 - вероятность того, что ключ меньше k 1 q 1 - вероятность того, что ключ больше k 1 q 2 - вероятность того, что ключ больше k 2 q 3 - вероятность того, что ключ больше k 3 С а - число сравнений в дереве « а » С б - число сравнений в дереве « б »

Изображение слайда
165

Слайд 165

Ожидаемое число сравнений в некотором поиске есть сумма произведений вероятности того, что данный аргумент имеет некоторое заданное значение, на число сравнений, необходимых для извлечения этого значения, где сумма берется по всем возможным значениям аргумента поиска. Поэтому С а = 2р1+1р2+2р3+2q0+2q1+1q2+2q3 С б = 2р1+3р2+1р3+2q0+2q1+3q2+1q3

Изображение слайда
166

Слайд 166

Пусть заданы следующие вероятности значений ключей P1 = 0.1 P1 = 0.1 P2 = 0.3 P2 = 0.1 P3 = 0.1 P3 = 0.3 q0 = 0.1 q0 = 0.1 q1 = 0.2 q1 = 0.1 q2 = 0.1 q2 = 0.1 q3 = 0.1 q3 = 0.2 Тогда С а = 1. 6 С а = 1. 8 С б = 2.2 С б = 1.7

Изображение слайда
167

Слайд 167

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

Изображение слайда
168

Слайд 168: Бинарный поиск (метод деления пополам)

Метод используется только для отсортированных массивов. Допустим необходимо найти элемент с ключом key = 52.

Изображение слайда
169

Слайд 169: Обозначим : low - индекс нижней границы интервала поиска hi - индекс верхней границы интервала поиска mid - индекс середины интервала поиска

low = 1 hi = n while (low <= hi) do mid = (low + hi) div 2 if key = k(mid) then search = mid return endif Алгоритм бинарного поиска if key < k(mid) then hi = mid - 1 else low = mid + 1 endif endwhile search = 0 return

Изображение слайда
170

Слайд 170: Эффективность бинарного поиска

Количество сравнений при бинарном поиске (эффективность) имеет порядок О( log 2 N )

Изображение слайда
171

Слайд 171: Поиск по бинарному дереву

Длительность операции поиска зависит от структуры дерева.

Изображение слайда
172

Слайд 172

Наибольший эффект использования дерева достигается в том случае, когда дерево сбалансировано. Поиск элемента в сбалансированном дереве называется бинарным поиском по дереву. При бинарном поиске по дереву перебирается не больше log 2 N элементов. Другими словами, эффективность бинарного поиска по дереву имеет порядок O ( log 2 N )

Изображение слайда
173

Слайд 173: Алгоритм поиска по бинарному дереву

p = tree whlie p <> nil do if key = k(p) then search = p return endif if key < k(p) then p = left(p) else p = right(p) endif endwhile search = nil return tree

Изображение слайда
174

Слайд 174

Очень часто следствием поиска являются ситуации: если узел с заданным ключом не найден, то его надо вставить ; если узел с заданным ключом найден, то его надо удалить.

Изображение слайда
175

Слайд 175: Поиск по бинарному дереву с включением (вставкой)

Для включения новой записи в дерево, прежде всего нужно найти тот узел, к которому можно присоединить новый элемент, не нарушив упорядоченности дерева. Модифицируем процедуру поиска по бинарному дереву так, чтобы фиксировалась ссылка на узел, после обработки которого поиск прекращается. С этой целью введем вспомогательный указатель q, отстающий от рабочего p на один шаг.

Изображение слайда
176

Слайд 176

p = tree q = nil while p <> nil do q = p if key = k(p) then search = p return endif if key < k(p) then p = left(p) else p = right(p) endif endwhile v = maketree(key, rec) if q = nil then tree = v else if key < k(q) then left(q) = v else right(q) = v endif endif search = v return Алгоритм поиска по бинарному дереву с включением (вставкой)

Изображение слайда
177

Слайд 177: Поиск по бинарному дереву с удалением

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

Изображение слайда
178

Слайд 178: Удаление узлов бинарного дерева

Изображение слайда
179

Слайд 179

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

Изображение слайда
180

Слайд 180: Предшественником удаляемого узла ( 12 ) является самый правый узел левого поддерева (11). Преемником узла (12) - самый левый узел правого поддерева (13)

Изображение слайда
181

Слайд 181

Будем разрабатывать алгоритм для преемника (узел 13 ), который будет поставлен на место удаляемого узла 12. Введем указатели : p - рабочий указатель; q - отстает от р на один шаг; v - указывает на преемника удаляемого узла; t - отстает от v на один шаг; s - на один шаг впереди v (указывает на левого сына или пустое место). В результате поиска преемника на узел 13 должен указывать указатель v, а указатель s - на пустое место (как показано на рисунке).

Изображение слайда
182

Слайд 182

q = nil p = tree while (p <> nil) and (k(p) <> key) do q = p if key < k(p) then p = left(p) else p = right(p) endif endwhile if p = nil then ‘ Ключ не найден ’ return endif if left(p) = nil then v = right(p) else if right(p) = nil then v = left(p) else ‘ У nod(p) - два сына ’ ‘ Введем два указателя (t отстает от v на 1 шаг, s - опережает )’ t = p v = right(p) s = left(v) Алгоритм поиска по бинарному дереву с удалением

Изображение слайда
183

Слайд 183

while s <> nil do t = v v = s s = left(v) endwhile if t <> p then ‘v не является сыном p’ left(t) = right(v) right(v) = right(p) endif left(v) = left(p) endif endif if q = nil then ‘p - корень ’ tree = v else if p = left(q) then left(q) = v else right(q) = v endif endif freenode(p) return Алгоритм поиска по бинарному дереву с удалением ( продолжение )

Изображение слайда
184

Слайд 184: Контрольные вопросы

1.В чем состоит назначение поиска? 2.Что такое уникальный ключ? 3.Какая операция производится в случае отсутствия заданного ключа в списке? 4.В чем различие между последовательным и индексно-последовательным поиском? 5.Какой из них более эффективный и почему? 6.Какие способы переупорядочивания таблицы поиска Вы знаете? 7.Основные отличия метода перестановки в начало от метода транспозиции. 8.Где они будут работать быстрее, в массиве или списке? 9.В чем суть бинарного поиска? 10.Как можно обойти бинарное дерево? 11.Можно ли применять бинарный поиск к массивам? 12.Если удалить корень в непустом бинарном дереве, какой элемент станет на его место?

Изображение слайда
185

Слайд 185: Сортировка

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

Изображение слайда
186

Слайд 186

Если сортируемые записи занимают большой объем памяти, то их перемещение требует больших затрат. Для того, чтобы их уменьшить, сортировку производят в таблице адресов ключей, то есть делают перестановку указателей, а сам массив не перемещается. Это - метод сортировки таблицы адресов.

Изображение слайда
187

Слайд 187

При сортировке могут встретиться одинаковые ключи. В этом случае желательно после сортировки расположить одинаковые ключи в том же порядке, что и в исходном файле. Это - устойчивая сортировка. Мы будем рассматривать только сортировки, не использующие дополнительную оперативную память. Такие сортировки называются « на том же месте ».

Изображение слайда
188

Слайд 188

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

Изображение слайда
189

Слайд 189

Выделяем первый критерий. Эквивалентом затраченного на сортировку времени можно считать количество сравнений и количество перемещений при выполнении сортировки. Порядок числа сравнений и перемещений при сортировке лежит в пределах от О ( n log n ) до О ( n 2 ); О ( n ) - идеальный и недостижимый случай.

Изображение слайда
190

Слайд 190

Различают следующие методы сортировки: строгие (прямые) методы; улучшенные методы. Строгие методы: метод прямого включения; метод прямого выбора; метод прямого обмена. Эффективность строгих методов примерно одинакова.

Изображение слайда
191

Слайд 191: Сортировка методом прямого включения

Элементы мысленно делятся на уже готовую последовательность a 1,...,a i -1 и исходную последовательность. При каждом шаге, начиная с i = 2 и увеличивая i каждый раз на единицу, из исходной последовательности извлекается i -й элемент и перекладывается в готовую последовательность, при этом он вставляется на нужное место.

Изображение слайда
192

Слайд 192

Алгоритм этой сортировки таков: for i = 2 to n x = a(i) находим место среди а (1)… а ( i ) для включения х next i

Изображение слайда
193

Слайд 193

Алгоритм сортировки методом прямого включения без барьера for i = 2 to n x = a(i) for j = i - 1 downto 1 if x < a(j) then a( j + 1 ) = a(j) else go to L endif next j L: a( j + 1 ) = x n ext i r eturn

Изображение слайда
194

Слайд 194

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

Изображение слайда
195

Слайд 195: Алгоритм сортировки методом прямого включения с барьером

for i = 2 to n x = a(i) a (0) = x { a (0) - барьер } j = i - 1 while x < a(j ) do a( j + 1 ) = a(j ) j = j - 1 endwhile a( j + 1 ) = x next i return

Изображение слайда
196

Слайд 196: Эффективность алгоритма прямого включения

Минимальные оценки числа сравнений C min и перемещений M min встречаются в случае уже упорядоченной исходной последовательности элементов, наихудшие же оценки С max и M max - когда они первоначально расположены в обратном порядке.

Изображение слайда
197

Слайд 197

Количество сравнений в худшем случае, когда массив отсортирован противоположным образом, С max = n (n - 1)/2, то есть порядок О ( n 2 ). Количество перестановок M max = C max + 3( n -1), то есть порядок О ( n 2 ). Если же массив уже отсортирован, то число сравнений и перестановок минимально: C min = n -1; M min = 3( n -1).

Изображение слайда
198

Слайд 198: Сортировка методом прямого выбора

Этот метод основан на следующих принципах. 1. Выбирается элемент с наименьшим ключом. 2. Он меняется местами с первым элементом a 1. 3. Затем этот процесс повторяется с оставшимися n -1 элементами, n -2 элементами и т.д. до тех пор, пока не останется один, самый "большой" элемент.

Изображение слайда
199

Слайд 199: Алгоритм сортировки прямым выбором

for i = 1 to n - 1 x = a(i) k = i for j = i + 1 to n if a(j) < x then k = j x = a(k) endif next j a(k) = a(i) a(i) = x next i return

Изображение слайда
200

Слайд 200: Эффективность алгоритма сортировки прямым выбором

Число сравнений ключей C, очевидно, не зависит от начального порядка ключей. Можно сказать, что в этом смысле поведение этого метода менее естественно, чем поведение прямого включения. Для C при любом расположении ключей имеем: C = n ( n -1)/2 Порядок числа сравнений, таким образом, О( n 2 )

Изображение слайда
201

Слайд 201

Число перестановок минимально М min = 3( n - 1) в случае изначально упорядоченных ключей и максимально, М max = 3( n - 1) + С, т.е. порядок О( n 2 ), если первоначально ключи располагались в обратном порядке. В худшем случае сортировка прямым выбором дает порядок n 2, как для числа сравнений, так и для числа перемещений.

Изображение слайда
202

Слайд 202: Сортировка с помощью прямого обмена (пузырьковая сортировка)

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

Изображение слайда
203

Слайд 203

Как и в упоминавшемся методе прямого выбора, мы повторяем проходы по массиву, сдвигая каждый раз наименьший элемент оставшейся последовательности к левому концу массива. Если мы будем рассматривать массивы как вертикальные, а не горизонтальные построения, то элементы можно интерпретировать как пузырьки в чане с водой, причем вес каждого соответствует его ключу. В этом случае при каждом проходе один пузырек как бы поднимается до уровня, соответствующего его весу (см. иллюстрацию на следующем слайде). Такой метод широко известен под именем "пузырьковая сортировка".

Изображение слайда
204

Слайд 204

Иллюстрация к обменной сортировке

Изображение слайда
205

Слайд 205: Алгоритм метода прямого обмена

for i = 2 to n for j = n to i step - 1 if a(j) < a(j - 1 ) then x = a(j - 1 ) a(j - 1 ) = a(j) a(j) = x endif next j next i return

Изображение слайда
206

Слайд 206

В нашем случае получился один проход “вхолостую”. Чтобы лишний раз не просматривать элементы, а значит проводить сравнения, затрачивая на это время, можно ввести флажок (переменную) fl, который остается в значении false, если при очередном проходе не будет произведено ни одного обмена. На нижеприведенном алгоритме добавления отмечены красным цветом.

Изображение слайда
207

Слайд 207

fl = true for i = 2 to n if fl = false then return endif fl = false for j = n to i step - 1 if a(j) < a(j - 1 ) then fl = true x = a(j - 1 ) a(j - 1 ) = a(j) a(j) = x endif next j next i return

Изображение слайда
208

Слайд 208

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

Изображение слайда
209

Слайд 209: Эффективность алгоритма сортировки прямым обменом

Число сравнений C max = n ( n -1)/2, порядок О( n 2 ). Число перемещений М max = 3 C max = 3 n ( n -1)/2, порядок О( n 2 ). Если массив уже отсортирован и применяется алгоритм с флажком, то достаточно всего одного прохода по массиву, и тогда получаем минимальное число сравнений C min = n - 1, порядок О( n ), а перемещения вообще отсутствуют

Изображение слайда
210

Слайд 210

Сравнительный анализ прямых методов сортировок показывает, что обменная "сортировка" в классическом виде представляет собой нечто среднее между сортировками с помощью включений и с помощью выбора. Если же в нее внесены приведенные выше усовершенствования, то для достаточно упорядоченных массивов пузырьковая сортировка даже имеет преимущество.

Изображение слайда
211

Слайд 211: Улучшенные методы сортировки

Сортировка Шелла (сортировка с уменьшающимся шагом) Быстрая сортировка ( Quick Sort )

Изображение слайда
212

Слайд 212: Сортировка Шелла (сортировка с уменьшающимся шагом)

В 1959 году Д. Шеллом было предложено усовершенствование сортировки с помощью метода прямого включения. Иллюстрация его сортировки с начальным шагом, равным 4, представлена на нижеследующем рисунке.

Изображение слайда
213

Слайд 213: Иллюстрация к сортировке Шелла

Изображение слайда
214

Слайд 214

Сначала отдельно группируются и в группах сортируются элементы, отстоящие друг от друга на расстоянии 4. Такой процесс называется четверной сортировкой. В нашем примере 8 элементов, и каждая группа состоит из двух элементов, то есть 1-й и 5-й элементы, 2-й и 6-й, 3-й и 7-й и, наконец, 4-й и 8-й элементы. После четверной сортировки элементы перегруппировываются - теперь каждый элемент группы отстоит от другого на 2 позиции - и вновь сортируются. Это называется двойной сортировкой. И наконец, на третьем проходе идет обычная или одинарная сортировка.

Изображение слайда
215

Слайд 215

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

Изображение слайда
216

Слайд 216

Ясно, что такой метод в результате дает упорядоченный массив, и, конечно, сразу же видно, что каждый проход от предыдущих только выигрывает; также очевидно, что расстояния в группах можно уменьшать по разному, лишь бы последнее было единичным, ведь в самом плохом случае последний проход и сделает всю работу.

Изображение слайда
217

Слайд 217

Приводимый ниже алгоритм не ориентирован на некую определенную последовательность расстояний и использует метод прямой вставки с безусловным переходом. При использовании метода барьера каждая из сортировок нуждается в постановке своего собственного барьера, поэтому приходится расширять массив с [0.. N ] до [- h 1.. N ].

Изображение слайда
218

Слайд 218

Не доказано, какие расстояния дают наилучший результат, но они не должны быть множителями один другого. Д. Кнут предлагает такую последовательность шагов h (в обратном порядке): 1, 3, 7, 15, 31, … То есть: h m = 2 h m -1 + 1, а количество шагов t = ( log 2 n ) - 1. При такой организации алгоритма его эффективность имеет порядок O ( n 1,2 )

Изображение слайда
219

Слайд 219: Алгоритм сортировки Шелла

Обозначим h [1.. t ] - массив размеров шагов ; t – количество шагов ; a [1.. n ] - сортируемый массив ; k – переменная, в которую записывается размер шага сортировки ; x - значение вставляемого элемента.

Изображение слайда
220

Слайд 220: Subroutine ShellSort

const t = 3 h(1) = 7 h(2) = 3 h(3) = 1 for m = 1 to t k = h(m) for i = 1 + k to n x = a(i) for j = i - k to 1 step -k if x < a(j) then a( j+k) = a(j) else goto L endif next j L: a(j+k) = x next i next m return

Изображение слайда
221

Слайд 221: Быстрая сортировка ( Quick Sort )

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

Изображение слайда
222

Слайд 222: Алгоритм быстрой сортировки

if i <= j then y = a(i) a(i) = a(j) a(j) = y i = i + 1 j = j - 1 endif until i > j if L < j then sort (L, j) endif if i < R then sort (i, R) endif return Sub Sort (L, R) i = L j = R x = a((L + R) div 2) repeat while a(i) < x do i = i + 1 endwhile while a(j) > x do j = j - 1 endwhile Sub QuickSort Sort (1, n) return

Изображение слайда
223

Слайд 223: Эффективность алгоритма Quick Sort

Из всех существующих методов сортировки Quick Sort самый эффективный. Его эффективность имеет порядок О (n log 2 n)

Изображение слайда
224

Слайд 224: Алгоритм сортировки с помощью бинарного дерева

if key < k(q) then left(q) = v else right(q) = v endif endwhile if tree <> nil then intrave(left(tree)) print info(tree) intrave(right(tree)) endif return read (key, rec) tree = maketree(key, rec) while not eof do p = tree q = tree read (key, rec) v = maketree(key, rec) while p <> nil do q = p if key < k(p) then p = left(p) else p = right(p) endif endwhile

Изображение слайда
225

Слайд 225: Контрольные вопросы

Что такое сортировка? Назовите основные методы сортировки. Какие методы сортировки относятся к строгим? Какие методы сортировки относятся к улучшенным? Какая сортировка называется устойчивой? В чем состоит суть метода прямого включения? В чем состоит суть метода прямого выбора? В чем состоит суть метода прямого обмена? Назовите разницу между этими тремя методами. Какой метод сортировки является самым эффективным? К какому из основных методов относится метод Шелла?

Изображение слайда
226

Слайд 226: Экзаменационные вопросы по курсу «Алгоритмы и структуры данных»

Понятие типов и структур данных. Оперативные и внешние структуры. Стандартные и пользовательские типы данных. Определение и представление структур данных. Классификация структур данных. Векторы и массивы как статистические структуры. Записи и таблицы как статические структуры. Понятие списковой структуры. Стек как полустатическая структура. Операция над стеками Очередь как полустатическая структура. Операции над очередью. Недостатки полустатической очереди, методы их исправления. Очередь со сдвигом. Кольцевая полустатическая очередь. Операции над кольцевой очередью. Деки, операции над ними. Понятие динамических структур данных. Организация односвязных и двусвязных списков. Простейшие операции над односвязными списками.

Изображение слайда
227

Слайд 227

Продолжение экзаменационных вопросов Реализация стеков с помощью списков. Смысл и организация операций создания и удаления элемента динамической структуры. Понятие свободного списка и пула свободных элементов. Утилизация освободившихся элементов. Очередь и операции над ней при реализации связными списками Операции вставки и извлечения элементов из списка. Сравнение этих операций с аналогичными в массивах. Недостаток связного списка по сравнению с массивом. Пример алгоритма решения задачи извлечения элементов из списка по заданному признаку. Пример алгоритма решения задачи вставки заданного элемента в упорядоченный список. Элементы заголовков в списках; нелинейные связные структуры. Понятие рекурсивных структур данных. Деревья, их признаки и представления. Алгоритм сведения m-арного дерева к бинарному; основные операции над деревьями; виды обхода. Понятие поиска и ключей; назначение и структуры алгоритмов поиска.

Изображение слайда
228

Слайд 228

Продолжение экзаменационных вопросов Последовательный поиск и его эффективность. Индексно-последовательный поиск. Оптимизация поиска. Переупорядочивание таблицы с учетом вероятности поиска элемента. Дерево оптимального поиска. Метод оптимизации поиска путем перестановки в начало списка. Метод транспозиции при оптимизации поиска. Бинарный поиск Алгоритм создания упорядоченного бинарного дерева. Поиск по бинарному дереву. Эффективность поиска по бинарному дереву. Поиск по бинарному дереву с включением. Поиск по бинарному дереву с удалением.

Изображение слайда
229

Последний слайд презентации: Алгоритмы и структуры данных

Продолжение экзаменационных вопросов Алгоритмы прохождения бинарных деревьев. Понятие сортировки, ее эффективность; классификация методов сортировки. Сортировка методом прямого выбора. Сортировка методом прямого включения. Сортировка методом прямого обмена. Быстрая сортировка. Сортировка Шелла. Сортировка с помощью бинарного дерева. Сравнительный анализ эффективности методов сортировки. Нерекурсивный алгоритм обхода бинарного дерева.

Изображение слайда