ГоловнаЗворотній зв'язок

Алгоритмы структуры данных

«АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ

--- ТЕМА1

--- Построение и анализ алгоритмов

--- 1.1. От задачи к программе

Алгоритмы

Листинг 1.1. Первое приближение программы greedy

Листинг 1. 2.

Листинг 1. 3.Измененная программа greedy

1.2. Абстрактные типы данных

1.3. Типы данных, структуры данных и абстрактные типы данных

1.4. Время выполнения программ

Асимптотические соотношения

1.5. Вычисление времени выполнения программ

Вызовы процедур.

Программы с операторами безусловного перехода

1.6. Практика программирования

1.7. Расширение языка Pascal

ТЕМА 2

--- Основные абстрактные типы данных

--- 2.1. Абстрактный тип данных „Список"

2.2. Реализация списков

Реализация списков с помощью указателей

Листинг 2.4. Реализация некоторых операторов при представлении 'списков' с помощью указателей

Листинг 2.6. Реализация некоторых операторов списка при использовании курсоров

Листинг 2.7. Удаление элемента из дважды связного списка

Реализация стеков с помощью массивов

Реализация очередей с помощью указателей

Реализация очередей с помощью циклических массивов

Листинг 2.1.1. Реализация очередей с помощью циклических массивов

Листинг 2.12. Реализация операторов отображений посредством массива

Листинг 2.13. Реализация отображения посредством списков

2.6. Стеки и рекурсивные процедуры

Полное исключение рекурсий

ТЕМА 3

Прямой, обратный и симметричный обходы дерева

Листинг 3.1. Рекурсивные процедуры обхода деревьев

Помеченные деревья и деревья выражений

3.2. Абстрактный тип данных TREE

3.3. Реализация деревьев

Представление деревьев с использованием списков сыновей

Листинг 3.6. Функции, использующие представление деревьев посредством связанных списков 

Листинг 3.7. Функция CREATE2      

3.4. Двоичные деревья

Листинг 3.9. Две процедуры

ТЕМА 4

Операторы АТД, основанные на множествах

Листинг 4.1. Программа вычисления областей действий операторов определения переменных

4.3. Реализация множеств посредством двоичных векторов

4.4. Реализация множеств посредством связанных списков

Листинг 4.3. Процедура INTERSECTION, использующая связанные списки

Листинг 4.4. Процедура вставки элемента

4.5. Словари

Листинг 4.6. Объявления типов и процедуры реализации словаря посредством  массива

4.7. Структуры данных, основанные на хеш-таблицах

Листинг 4.8. Реализация словарей посредством открытой хеш-таблицы

Закрытое хеширование

Листинг 4.9. Реализация словаря посредством закрытого хеширования

4.8. Оценка эффективности хеш-функций

Анализ закрытого хеширования

„Случайные" методики разрешения коллизий

Реструктуризация хеш-таблиц

4.10. Очереди с приоритетами

Листинг 4.11. Выделение процессам машинного времени

Реализация очереди с приоритетами посредством частично упорядоченных деревьев

Реализация частично упорядоченных деревьев посредством массивов

4.12. Некоторые структуры сложных множеств

Структуры мультисписков

Листинг 4.14. Реализация поиска в мультисписке

Эффективность двойных структур данных

ТЕМА 5

Листинг 5.2. Вставка нового элемента в дерево двоичного поиска

5.2. Анализ времени выполнения операторов

5.3. Нагруженные деревья

Листинг 5.7. Процедура INSERT

Эффективность структуры данных нагруженных деревьев

5.4. Реализация множеств посредством сбалансированных деревьев

Типы данных для 2-3 деревьев

Листинг 5.9. Процедура вставки в 2-3 дерево

Реализация оператора DELETE

5.5. Множества с операторами MERGE и FIND

Простая реализация АТД MFSET

Быстрая реализация АТД MFSET

Листинг5.14.Операторы АТД МFSET

Сжатие путей

5.6. АТД с операторами MERGE и SPLIT

Листинг 5.15. Программа нахождения НОП

 

1