Во второй главе рассмотрены некоторые нелинейные списковые структуры: деревья, в том числе двоичные деревья поиска, операции над деревьями, способы представления деревьев в памяти ЭВМ. <...> Рекурсивный алгоритм - это алгоритм, который при вычислениях обращается сам к себе. <...> Записать рекурсивный алгоритм на языке программирования можно при помощи рекурсивной функции. <...> Рекурсивные вызовы функций Следует иметь в виду, что в рекурсивной функции обязательно должна быть предусмотрена возможность прекратить дальнейший самовызов и начать обратный процесс. <...> Рекурсивное вычисление факториала. #include "stdafx.h" #include <iostream> using namespace std; unsigned long int factorial(unsigned long int f) // рекурсивная функция { if (f == 1 || f == 0) // базовое или частное решение return 1; 10 return = f * factorial(f - 1); // рекурсивный вызов } int main(int argc, char* argv[]) { int n; cout << "Enter n!: "; cin >> n; cout << n << "!" << "=" << factorial(n) << endl; // вызов рекурсивной функции system("pause"); return 0; } Процесс вычисления факториала вызывается factorial(5); будет выглядеть так (рис. <...> 2). завершается factorial(5); значение функции равно 120 вызывается factorial(4); завершается factorial(4); значение функции равно 24 вызывается factorial(3); завершается factorial(3); значение функции равно 6 вызывается factorial(2); завершается factorial(2); значение функции равно 2 вызывается factorial(1); завершается factorial(1); значение функции равно 1 Рис. <...> Если рекурсивная функция имеет локальные переменные, то они сохраняют свои значения для каждого вызова функцией самой себя. <...> Нелинейные списковые структуры Нелинейные структуры данных позволяют выражать более сложные отношения между элементами, чем линейные отношения соседства как в линейных списках. <...> К нелинейным структурам данных, в первую очередь, относят различного рода графы, в том числе деревья и сети, списки. <...> Узлы n1, n2, ., nk называются дочерними узлами узла n. <...> Путем из узла n1 в узел nm называется последовательность узлов n1, n2, ., nm, где для всех <...>
Структуры_и_алгоритмы_обработки_данных._Часть_2.pdf
УДК 004.4(07)
Б282
Рецензенты:
доц., канд. техн. наук Скуднев Д.М.;
кафедра энергетических и информационных систем
НОУ ВПО «Международный институт компьютерных технологий»
Батищев, Р.В.
Б282 Структуры и алгоритмы обработки данных. Часть 2 [Текст]: учеб._пос. /
Р.В. Батищев. - Липецк: Изд-во Липецкого государственного технического
университета, 2015. – 82 с.
ISBN
ISBN 41
Учебное пособие предназначено для студентов, изучающих курс "Структуры
и алгоритмы обработки данных" и представляет собой вторую часть практического
руководства к проведению лабораторных работ по дисциплине
"Структуры и алгоритмы обработки данных". В учебном пособии рассматриваются
вопросы внутримашинного представления таких структур, как деревья и
графы. Приводятся основные алгоритмы на этих структурах, алгоритмы организации
эффективного поиска и сжатия данных.
Пособие содержит теоретический материал с иллюстрациями алгоритмов
и примерами программ на языке программирования высокого уровня "Си".
Ил. 71. Библиогр. 10 назв.
Печатается по решению Редакционно-издательского совета ЛГТУ.
ISBN
ISBN 41
© ФГБОУ ВПО "Липецкий
государственный технический
университет", 2015
© Батищев Р.В., 2015
5
Стр.3
СОДЕРЖАНИЕ
ВВЕДЕНИЕ...................................................................................................
1. Рекурсия ....................................................................................................
2. Нелинейные списковые структуры ...........................................................
2.1. Деревья. Основные понятия ...............................................................
2.2. Операции, выполняемые над деревьями ............................................
2.3. Способы представления деревьев в памяти компьютера ...................
2.3.1. Представление деревьев с помощью массивов................................
2.3.2. Представление деревьев с помощью указателей .............................
2.4. Двоичные деревья поиска ...................................................................
2.5. Сбалансированные деревья. АВЛ-дерево ...........................................
2.5.1. Алгоритм добавления вершины.......................................................
2.5.2. Алгоритм удаления вершины ..........................................................
2.6. Сбалансированные деревья. В-деревья ..............................................
2.6.1. Структура вершины В-дерева ..........................................................
2.6.2. Операция вставки ............................................................................
2.6.3. Удаление элемента...........................................................................
3. Анализ эффективности некоторых алгоритмов поиска
с помощью деревьев. Динамическое программирование .............................
3.1. Алгоритм поиска с возвращением ......................................................
3.2. Метод ветвей и границ .......................................................................
3.3. Динамическое программирование......................................................
4. Элементы теории графов...........................................................................
4.1. Способы формализованного задания графа .......................................
4.2. Алгоритмы на графах .........................................................................
4.2.1. Алгоритмы обхода графа .................................................................
4.2.2. Алгоритмы поиска кратчайшего пути .............................................
4.2.3. Остовные деревья минимальной стоимости ....................................
6
5
7
10
10
12
14
14
17
18
23
24
39
40
41
42
46
48
50
51
52
55
57
60
60
61
63
Стр.4
4.2.4. Раскраска графа ...............................................................................
5. Обработка прямоугольных таблиц. Информационный поиск ..................
5.1. Поиск в информационном массиве во внутренней памяти ................
5.2. Поиск в информационном массиве на устройстве внешней памяти ..
5.3. Поиск в бинарном дереве ...................................................................
5.4. Поиск в В-дереве ................................................................................
5.5. Деревья цифрового поиска .................................................................
5.6. Хеширование для организации эффективного поиска .......................
6. Кодирование информации. Сжатие данных ..............................................
БИБЛИОГРАФИЧЕСКИЙ СПИСОК ...........................................................
64
65
66
67
69
69
70
73
77
81
7
Стр.5
ВВЕДЕНИЕ
Как самые первые ЭВМ, так и современные компьютеры своей основной
задачей имеют обработку данных. Работа любой программы, в конечном итоге,
сводится к различного рода манипуляциям над числами, символами, информационными
массивами и т.д. Они, в свою очередь, представляют собой некоторые
структуры, хранимые в памяти ЭВМ.
Если рассматривать самый нижний уровень представления - физический,
то как программы, так и данные являются лишь множеством двоичных цифр.
Однако на более высоком уровне представления, используемом разработчиками
программного обеспечения, данные являют собой абстракции, уже далекие
от двоичного представления. Они принадлежат одному из определенных подмножеств
- типов данных, могут образовывать различного рода структуры, в
которых элементы способны иметь связи между собой. Понятия "тип данных" и
"структура данных" являются средствами, позволяющими повысить эффективность
разработки программного обеспечения, давая возможность оперировать
более близкими человеку понятиями.
Любая программа, записанная на любом языке программирования, использующая
и изменяющая данные и структуры данных, представляет собой
один из способов записи алгоритма - последовательности действий, которую
нужно выполнить для получения результата. К настоящему времени разработано
огромное количество разнообразных алгоритмов для всех областей человеческой
деятельности, связанных с обработкой данных. Их знание и понимание
позволяет существенно облегчить и повысить эффективность решения задач
различного рода, связанных с организацией вычислений, управлением, планированием,
прогнозированием и т.п.
Первая глава учебного пособия посвящена описанию такого важного понятия
как «рекурсия» применительно к алгоритмизации и программированию.
Организация рекурсивного вычислительного процесса в часто позволяет суще8
Стр.6