- •Структуры и алгоритмы обработки данных
- •Алгоритмы. Основные определения
- •От задачи к программе
- •Написание программы.
- •Типы данных, структуры данных и абстрактные типы данных
- •Указатели и курсоры
- •Время выполнения программ
- •Измерение времени выполнения программы
- •Степень (порядок) роста
- •Вычисление времени выполнения программ
- •Линейные абстрактные типы данных атд «Список»
- •Реализация списков посредством массивов
- •Реализация списков с помощью указателей
- •Атд «Стек»
- •Атд «Очередь»
- •Реализация очередей с помощью циклических массивов
- •Нелинейные абстрактные типы данных Деревья
- •Порядок узлов
- •Прямой, обратный и симметричный обходы дерева
- •Помеченные деревья и деревья выражений
- •Представление деревьев с помощью массивов
- •Специальные виды множеств атд “Дерево двоичного поиска”
- •Атд "Словарь", основанный
- •Представление ориентированных графов
- •Атд для ориентированных графов
- •Задача нахождения кратчайшего пути
- •Int **c, // массив стоимостей
- •Int *d) // массив кратчайших
- •Остовные деревья минимальной стоимости
- •Обход графов
- •Поиск в ширину
- •Поиск в глубину
- •Сортировка
- •Простые схемы сортировки Метод «пузырька»
- •Сортировка вставками
- •Быстрая сортировка
- •Пирамидальная сортировка
- •«Карманная» сортировка
- •Порядковые статистики
- •Методы разработки алгоритмов. Типы алгоритмов
- •Алгоритмы «разделяй и властвуй» (метод декомпозиции)
- •Баланс подзадач
- •Динамическое программирование
- •Перемножение нескольких матриц
- •Шаг 1: строение оптимальной расстановки скобок
- •Шаг 2: рекуррентное соотношение
- •Шаг 3: вычисление оптимальной стоимости
- •Void MatrixChainOrder(int n, // кол-во матриц
- •Int p[], // размеры матриц
- •Int **s) // оптимальное k
- •Шаг 4: построение оптимального решения
- •Int **s, // таблица, полученная
- •Int I, // индексы
- •Когда применимо динамическое программирование?
- •Оптимальность для подзадач
- •Перекрывающиеся подзадачи
- •«Жадные» алгоритмы
- •"Жадные" алгоритмы как эвристики
- •Когда применим жадный алгоритм?
- •Принцип жадного выбора
- •Оптимальность для подзадач
- •Поиск с возвратом
- •Функции выигрыша
- •Метод ветвей и границ
- •Структуры данных и алгоритмы для внешней памяти
- •Внешняя сортировка
- •Хранение данных в файлах
- •Простая организация данных
- •Хешированные файлы
- •Индексированные файлы
- •Содержание
- •Глава I. Линейные абстрактные типы данных 31
- •Глава II. Сортировка 108
Указатели и курсоры
Для облегчения доступа к совокупностям ячеек в языках программирования используются указатели и курсоры. Указатель – это ячейка, чье значение указывает на другую ячейку (содержит адрес другой ячейки).
В Си указатель на ячейку заданного типа определяется следующим образом:
<тип ячейки> *<имя переменн>;
Пример. Два поля в записи являются указателями на другие записи.
struct child{
char name[25]; /* Имя */
int brothers; /* Кол-во братьев */
int sisters ; /* Кол-во сестер */
struct child *mother; /* Мать */
struct child *father; /* Отец */
};
Курсор – это ячейка с целочисленным значением, используемая для указания на элемент массива. Курсоры используются в языках, которые не имеют явного типа указателя (например, Фортран, Алгол).
Схематически структуры данных изображаются следующим образом:
Одномерный массив:
-
12.1
16.7
54.56
43.45
546.1
1
2
3
4
5
Двумерный массив:
-
2
6
0
4
6
9
5
0
2
4
5
8
3
2
7
8
3
6
1
4
6
1
1
0
0
6
7
4
2
Запись:
Василий |
1 |
1 |
0х000F2123 |
0х000F3126 |
|
|
|
|
|
|
|
|
|
|
Марина |
0 |
0 |
………. |
………. |
|
|
|
|
|
|
|
|
|
|
Дмитрий |
2 |
0 |
……….. |
……….. |
Стрелками изображаются указатели.
Время выполнения программ
В процессе решения прикладных задач выбор подходящего алгоритма вызывает определенные трудности. В самом деле, на чем основывать свой выбор, если алгоритм должен удовлетворять следующим противоречащим друг другу требованиям. С одной стороны
-
Быть простым для понимания, перевода в программный код и отладки.
-
Эффективно использовать компьютерные ресурсы и выполняться по возможности быстро.
Если написанная программа должна выполняться только несколько раз, то первое требование наиболее важно. Стоимость рабочего времени программиста обычно значительно превышает стоимость машинного времени выполнения программы, поэтому стоимость программы оптимизируется по стоимости написания (а не выполнения) программы. Если мы имеем дело с задачей, решение которой требует значительных вычислительных затрат, то стоимость выполнения программы может превысить стоимость написания программы, особенно если программа должна выполняться многократно. Поэтому, с финансовой точки зрения, более предпочтительным может стать сложный комплексный алгоритм (в надежде, что результирующая программа будет выполняться существенно быстрее, чем более простая программа). Но и в этой ситуации разумнее сначала реализовать простой алгоритм, чтобы определить, как должна себя вести более сложная программа. При построении сложной программной системы желательно реализовать ее простой прототип, на котором можно провести необходимые измерения и смоделировать ее поведение в целом, прежде чем приступать к разработке окончательного варианта. Т.О. программисты должны быть осведомлены не только о методах построения быстрых программ, но и знать когда их следует применять (желательно с минимальными программистскими усилиями).