Методы программирования

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

1 ТЕОРЕТИЧЕСКАЯ ЧАСТЬ. СТРУКТУРЫ ДАННЫХ

1.1 СПОСОБЫ ЗАДАНИЯ ЭЛЕМЕНТОВ ОПРЕДЕЛЕННОГО ТИПА

1.2 СТЕК ЭЛЕМЕНТОВ ТИПА Е

1.3 ОЧЕРЕДЬ ЭЛЕМЕНТОВ ТИПА Е

1.4 ДЕК ЭЛЕМЕНТОВ ТИПА Е

1.5 МНОЖЕСТВО ЭЛЕМЕНТОВ ТИПА Е

1.6 НАГРУЖЕННОЕ МНОЖЕСТВО

1.7 ПОСЛЕДОВАТЕЛЬНОСТЬ ЭЛЕМЕНТОВ ТИПА Е

1.8 Л2-СПИСОК ЭЛЕМЕНТОВ ТИПА Е

1.9 Л1-СПИСОК ЭЛЕМЕНТОВ ТИПА Е

1.10 ВЕКТОР ЭЛЕМЕНТОВ ТИПА Е С ПРОИЗВОЛЬНЫМ ДОСТУПОМ

1.11 МАТРИЦА ЭЛЕМЕНТОВ ТИПА Е С ИНДЕКСАМИ ТИПА И1, И2.

1.12 ДИНАМИЧЕСКИЙ ВЕКТОР ЭЛЕМЕНТОВ ТИПА Е

1.13 ГРАФЫ

1.14 ДЕРЕВЬЯ

2 ПРАКТИЧЕСКАЯ ЧАСТЬ. СТРУКТУРЫ ДАННЫХ

2.1 ОБЩИЕ СВЕДЕНИЯ. 20

2.2 АССЕМБЛЕР (ASSEMBLER)

Директивы определения данных

Директива DB (db)

Директива DW (dw)

Директива DD (dd)

Директивы эквивалентности и присваивания

2.3 СИ/СИ++ (C/C++)

Константы

Символьная константа

Константное выражение

Строчная константа

Описания

Преобразование типов

Инициализация

Макроподстановка

Указатели и массивы

Указатели и адреса

Указатели и массивы

Многомерные массивы

Массивы указателей; указатели указателей

Указатели и многомерные массивы

Структуры

Поля

Объединения

2.4 ПАСКАЛЬ (PASCAL)

Идентификаторы

Типы

Записи

Порядковые типы

Вещественные типы

Строковые типы

Символьный тип

Булевы типы

Массив

Указательные типы

Файлы

Целочисленные типы

Переменные

Постоянные выражения

Константы

Типизированные константы

Стандартная директива Absolute

2.5 БЕЙСИК (BASIC)

2.6 ПРОЛОГ (PROLOG)

Объекты данных

Атомы и числа

Переменные

Структуры

Списки

3. ДЕРЕВЬЯ. ПРИКЛАДНЫЕ АЛГОРИТМЫ

3.1. ОСНОВНАЯ ТЕРМИНОЛОГИЯ

Порядок узлов

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

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

Вычисление "наследственных" данных

3.2. АБСТРАКТНЫЙ ТИП ДАННЫХ TREE

3.3. РЕАЛИЗАЦИЯ ДЕРЕВЬЕВ

Представление деревьев с помощью массивов

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

Представление левых сыновей и правых братьев

3.4. ДВОИЧНЫЕ ДЕРЕВЬЯ

Представление двоичных деревьев

Пример: коды Хаффмана

3.5. РЕАЛИЗАЦИЯ ДВОИЧНЫХ ДЕРЕВЬЕВ С ПОМОЩЬЮ УКАЗАТЕЛЕЙ

4. ОРИЕНТИРОВАННЫЕ ГРАФЫ. ПРИКЛАДНЫЕ АЛГОРИТМЫ

4.1. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ

4.2. ПРЕДСТАВЛЕНИЯ ОРИЕНТИРОВАННЫХ ГРАФОВ

АТД для ориентированных графов

4.3. ЗАДАЧА НАХОЖДЕНИЯ КРАТЧАЙШЕГО ПУТИ

Обоснование алгоритма Дейкстры

Время выполнения алгоритма Дейкстры

4.4. НАХОЖДЕНИЕ КРАТЧАЙШИХ ПУТЕЙ МЕЖДУ ПАРАМИ ВЕРШИН

Сравнение алгоритмов Флойда и Дейкстры.

Вывод на печать кратчайших путей

Транзитивное замыкание

5. СОРТИРОВКА. ПРИКЛАДНЫЕ АЛГОРИТМЫ

5.1. МОДЕЛЬ ВНУТРЕННЕЙ СОРТИРОВКИ

5.2. ПРОСТЫЕ СХЕМЫ СОРТИРОВКИ

Сортировка вставками

Сортировка посредством выбора

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

Подсчет перестановок

Ограниченность простых схем сортировки

5.3. БЫСТРАЯ СОРТИРОВКА

Временная сложность быстрой сортировки

Время выполнения быстрой сортировки в среднем

Реализация алгоритма быстрой сортировки

5.4. ПИРАМИДАЛЬНАЯ СОРТИРОВКА

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

5.5. КАРМАННАЯ СОРТИРОВКА

Анализ "карманной" сортировки

5.6. СОРТИРОВКА МНОЖЕСТВ С БОЛЬШИМИ ЗНАЧЕНИЯМИ КЛЮЧЕЙ

5.7. ОБЩАЯ ПОРАЗРЯДНАЯ СОРТИРОВКА

Анализ поразрядной сортировки

5.8. ВРЕМЯ ВЫПОЛНЕНИЯ СОРТИРОВОК СРАВНЕНИЯМИ

Деревья решений

Размер дерева решений

Анализ времени выполнения в среднем

5.9. ПОРЯДКОВЫЕ СТАТИСТИКИ

5.10. ВАРИАНТ БЫСТРОЙ СОРТИРОВКИ

5.11. ЛИНЕЙНЫЙ МЕТОД НАХОЖДЕНИЯ ПОРЯДКОВЫХ СТАТИСТИК

Случай равенства некоторых значений ключей

5.12. КРАТКОЕ ОПИСАНИЕ НАИБОЛЕЕ РАСПРОСТРАННЫХ СОРТИРОВОК

Метод выбора

Метод обмена (метод «пузырька»)

Метод вставок

Метод подсчета

Метод сортировки Шелла

6. АЛГОРИТМЫ ДЛЯ ВНЕШНЕЙ ПАМЯТИ. ПРИКЛАДНЫЕ АЛГОРИТМЫ

6.1. МОДЕЛЬ ВНЕШНИХ ВЫЧИСЛЕНИЙ

Стоимость операций со вторичной памятью

6.2. ВНЕШНЯЯ СОРТИРОВКА

Сортировка слиянием

Ускорение сортировки слиянием

Минимизация полного времени выполнения

Многоканальное слияние

Многофазная сортировка

Когда скорость ввода-вывода не является „узким местом"

Схема с шестью входными буферами

Схема с четырьмя буферами

6.3. ХРАНЕНИЕ ДАННЫХ В ФАЙЛАХ

Простая организация данных

Ускорение операций с файлами

Хешированные файлы

Индексированные файлы

Несортированные файлы с плотным индексом

Вторичные индексы

6.4. ВНЕШНИЕ ДЕРЕВЬЯ ПОИСКА

Разветвленные Деревья поиска

В-деревья

Поиск записей

Вставка записей

Удаление записей

Время выполнения операций с В-деревом

Сравнение методов

7. ХЕШИРОВАНИЕ. ПРИКЛАДНЫЕ АЛГОРИТМЫ

7.1. ТЕОРИЯ

7.2. РЕАЛИЗАЦИЯ

ЛАБОРАТОРНЫЕ РАБОТЫ

КОНТРОЛЬНЫЕ РАБОТЫ

КОНТРОЛЬНАЯ 1

КОНТРОЛЬНАЯ 2

ПРИЛОЖЕНИЯ

ТАБЛИЦЫ КОДИРОВОК РУССКОГО ЯЗЫКА

ИСХОДНЫЕ ТЕКСТЫ ПРОГРАММ

Работа с матрицами

Работа с деревьями

Работа со списками

ПРИМЕР ОФОРМЛЕНИЯ КОНТРОЛЬНОЙ РАБОТЫ

ВОПРОСЫ К ЭКЗАМЕНУ

СПИСОК РЕКОМЕНДУЕМЫХ ИСТОЧНИКОВ