Ктн Е. В. Курапова, кф-мн Е. П. Мачикина

СТРУКТУРЫ И АЛГОРИТМЫ

ОБРАБОТКИ ДАННЫХ

Методическое пособие

Новосибирск 2006

УДК 681.3.06

ктн Е. В. Курапова, кф-мн Е. П. Мачикина

Структуры и алгоритмы обработки данных: Методическое пособие. / Сиб. гос. ун-т телекоммуникаций и информатики. – Новосибирск, 2006. – 105 с.

Методическое пособие предназначено для студентов технических специальностей, обучающихся по направлению “550400 Телекоммуникации” и изучающих дисциплину «Структуры и алгоритмы обработки данных». Пособие содержит необходимый теоретический минимум по данному предмету и варианты заданий для самостоятельного выполнения.

Рисунков ¾ 69, таблиц ¾ 13. Список лит. –5 назв.

Кафедра прикладной математики и кибернетики.

Рецензент: Зайцев М.Г., Венедиктов М.Д.

Утверждено редакционно-издательским советом СибГУТИ

в качестве методического пособия.

Ó Сибирский государственный университет

телекоммуникаций и информатики, 2006 г.

ОГЛАВЛЕНИЕ

ВВЕдение............................................................................................................ 7

1. Необходимые понятия и определения...................................... 7

1.1 Основные структуры данных.................................................................... 7

1.2 Задача сортировки массивов.................................................................... 8

1.3 Трудоемкость методов сортировки массивов........................................ 9

1.4 Задача сортировки последовательностей............................................ 10

1.5 Теорема о сложности сортировки........................................................ 10

1.6 Задача поиска элементов с заданным ключом...................................... 11

2. Методы сортировки с квадратичной трудоемкостью.... 12

2.1 Метод прямого выбора............................................................................ 12

2.2 Пузырьковая сортировка......................................................................... 13

2.3 Шейкерная сортировка........................................................................... 16

2.4 Варианты заданий................................................................................... 18

3. Метод Шелла........................................................................................... 18

3.1 Метод прямого включения...................................................................... 18

3.2 Метод Шелла............................................................................................ 19

3.3 Варианты заданий................................................................................... 21

4. Быстрые методы сортировки массивов................................. 21

4.1 Пирамидальная сортировка................................................................... 21

4.2 Метод Хоара............................................................................................. 24

4.3 Проблема глубины рекурсии.................................................................... 26

4.4 Варианты заданий................................................................................... 27

5. Работа с линейными списками................................................... 28

5.1 Указатели. Основные операции с указателями.................................... 28

5.2 Основные операции с линейными списками.......................................... 29

6. Методы сортировки последовательностей.......................... 32

6.1 Метод прямого слияния.......................................................................... 32

6.2 Цифровая сортировка............................................................................. 35

6.3 Варианты заданий................................................................................... 37

7. Двоичный поиск в упорядоченном массиве....................... 37

7.1 Алгоритм двоичного поиска................................................................... 37

7.2 Варианты заданий................................................................................... 39

8. Сортировка данных с произвольной структурой.............. 39

8.1 Сравнение данных произвольной структуры....................................... 39

8.2 Сортировка по множеству ключей. Индексация................................. 40

8.3 Индексация через массив указателей..................................................... 41

8.4 Варианты заданий................................................................................... 41

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

9.1 Основные определения и понятия.......................................................... 42

9.2 Различные обходы двоичных деревьев.................................................... 42

9.3 Вычисление основных характеристик дерева...................................... 43

9.4 Варианты заданий................................................................................... 44

10. Деревья поиска.................................................................................... 45

10.1 Поиск в дереве........................................................................................ 45

10.2 Идеально сбалансированное дерево поиска........................................ 46

10.3 Варианты заданий................................................................................ 47

11. Случайное дерево поиска............................................................. 48

11.1 Определение случайного дерева поиска............................................... 48

11.2 Добавление вершины в дерево.............................................................. 49

11.3 Удаление вершины из дерева................................................................ 50

11.4 Варианты заданий................................................................................ 52

12. сбалансированные по высоте деревья (АВЛ-ДЕРЕВЬЯ).... 52

12.1 Определение и свойства АВЛ-дерева................................................... 52

12.2 Повороты при балансировке............................................................... 54

12.3 Добавление вершины в дерево.............................................................. 56

12.4 Удаление вершины из дерева................................................................ 58

12.5 Варианты заданий................................................................................ 63

13. Б-ДЕРЕВЬЯ.................................................................................................. 63

13.1 Определение Б-дерева порядка m......................................................... 63

13.2 Поиск в Б-дереве..................................................................................... 64

13.3 Построение Б-дерева............................................................................. 66

13.4 Определение двоичного Б-дерева.......................................................... 68

13.5 Добавление вершины в дерево.............................................................. 69

13.6 Варианты заданий................................................................................ 73

14. Деревья оптимального поиска (ДОП)....................................... 73

14.1 Определение дерева оптимального поиска......................................... 73

14.2 Точный алгоритм построения ДОП................................................... 75

14.3 Приближенные алгоритмы построения ДОП.................................. 78

14.4 Варианты заданий................................................................................ 81

15. Хэширование и поиск..................................................................... 81

15.1 Понятие хэш-функции......................................................................... 81

15.2 Метод прямого связывания.................................................................. 83

15.3 Метод открытой адресации............................................................... 85

15.4 Варианты заданий................................................................................ 87

16. Элементы теории кодирования информации.................... 88

16.1 Необходимые понятия......................................................................... 88

16.2 Кодирование целых чисел..................................................................... 90

16.3 Алфавитное кодирование.................................................................... 93

16.4 Оптимальное алфавитное кодирование............................................ 96

16.5 Почти оптимальное алфавитное кодирование............................... 99

16.6 Варианты заданий.............................................................................. 103

РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА............................................................... 105

Приложение А............................................................................................. 106

Список рисунков

Рисунок 1 Дерево решений для 6 элементов.................................................................................... 10

Рисунок 2 Метод прямого выбора..................................................................................................... 12

Рисунок 3 Пузырьковая сортировка.................................................................................................. 15

Рисунок 4 Шейкерная сортировка..................................................................................................... 17

Рисунок 5 Метод прямого включения.............................................................................................. 19

Рисунок 6 Метод Шелла..................................................................................................................... 20

Рисунок 7 Добавление в пирамиду нового элемента...................................................................... 22

Рисунок 8 Пирамидальная сортировка............................................................................................. 23

Рисунок 9 Метод Хоара...................................................................................................................... 25

Рисунок 10 Схема вызовов при вычислении 4!............................................................................... 27

Рисунок 11 Структура фрейма........................................................................................................... 27

Рисунок 12 Равенство указателей...................................................................................................... 28

Рисунок 13 Указатель на элемент списка......................................................................................... 29

Рисунок 14 Добавление в стек........................................................................................................... 30

Рисунок 15 Удаление из стека........................................................................................................... 30

Рисунок 16 Добавление в очередь..................................................................................................... 30

Рисунок 17 Структура очереди.......................................................................................................... 31

Рисунок 18 Добавление в очередь..................................................................................................... 31

Рисунок 19 Перемещение элемента.................................................................................................. 31

Рисунок 20 Слияние серий................................................................................................................. 32

Рисунок 21 Метод прямого слияния................................................................................................. 33

Рисунок 22 Начальное расщепление................................................................................................. 34

Рисунок 23 Цифровая сортировка..................................................................................................... 36

Рисунок 24 Первая версия поиска..................................................................................................... 38

Рисунок 25 Вторая версия поиска..................................................................................................... 39

Рисунок 26 Список абонентов........................................................................................................... 40

Рисунок 27 Пример двоичного дерева.............................................................................................. 42

Рисунок 28............................................................................................................................................ 43

Рисунок 29 Дерево поиска................................................................................................................. 45

Рисунок 30 Примеры ИСД и неИСД................................................................................................ 46

Рисунок 31 Построение ИСДП.......................................................................................................... 47

Рисунок 32 Случайное дерево поиска.............................................................................................. 48

Рисунок 33 Плохие СДП.................................................................................................................... 49

Рисунок 34 Добавление вершины В................................................................................................. 50

Рисунок 35 Добавление вершины 9.................................................................................................. 50

Рисунок 36 Варианты удаления вершин.......................................................................................... 50

Рисунок 37 Удаляемая вершина с двумя поддеревьями.................................................................. 51

Рисунок 38 Порядок изменения указателей при удалении вершины........................................... 51

Рисунок 39 Пример АВЛ-дерева и не АВЛ-дерева......................................................................... 53

Рисунок 40 Деревья Фибоначчи........................................................................................................ 53

Рисунок 41 LL - поворот.................................................................................................................... 54

Рисунок 42 LR – поворот................................................................................................................... 55

Рисунок 43 RR – поворот................................................................................................................... 56

Рисунок 44 RL – поворот................................................................................................................... 56

Рисунок 45 Построение АВЛ-дерева................................................................................................ 58

Рисунок 46 Три случая при удалении вершины из левого (для BL) поддерева.......................... 59

Рисунок 47 Три случая при удалении вершины правого (для BR) поддерева............................. 60

Рисунок 48 Удаление из АВЛ-дерева............................................................................................... 62

Рисунок 49 Страница Б-дерева.......................................................................................................... 64

Рисунок 50 Пример Б-дерева............................................................................................................. 64

Рисунок 51 Структура страницы Б-дерева....................................................................................... 65

Рисунок 52 Построение Б-дерева...................................................................................................... 67

Рисунок 53 Виды вершин ДБД.......................................................................................................... 69

Рисунок 54 Вершины двоичного Б-дерева....................................................................................... 69

Рисунок 55 Четыре ситуации, возникающих при росте левых или правых поддеревьев.......... 70

Рисунок 56 Построение двоичного Б-дерева................................................................................... 73

Рисунок 57 Различные деревья поиска с вершинами V₁ =1, V₂ =2, V₃ =3......................................... 74

Рисунок 58 ДОП для w₁ =60, w₂ =30, w₃ =10....................................................................................... 77

Рисунок 59 Дерево, построенное приближенным алгоритмом А1............................................... 79

Рисунок 60 Дерево, построенное приближенным алгоритмом А2............................................... 81

Рисунок 61 Отображение H: K→A................................................................................................. 82

Рисунок 62 Хеш-таблица, построенная методом прямого связывания......................................... 84

Рисунок 63 Использование квадратичных проб.............................................................................. 87

Рисунок 64 Модель системы передачи сигналов............................................................................. 88

Рисунок 65 Полное двоичное дерево с помеченными вершинами............................................... 94

Рисунок 66 Построение префиксного кода с заданными длинами............................................... 95

Рисунок 67 Процесс построения кода Хаффмена............................................................................ 98

Рисунок 68 Кодовое дерево для кода Хаффмена............................................................................. 98

Рисунок 69 Кодовое дерево для кода Фано.................................................................................... 101

СПИСОК ТАБЛИЦ

Таблица 1 Различные типы данных.................................................................................................... 7

Таблица 2 Основные операции с указателями................................................................................. 29

Таблица 3 Частоты вхождения символов в строку.......................................................................... 79

Таблица 4 Упорядоченный набор вершин........................................................................................ 80

Таблица 5 Номера символов строки.................................................................................................. 86

Таблица 6 Код класса Fixed + Variable.............................................................................................. 90

Таблица 7 Код класса Variable + Variable......................................................................................... 91

Таблица 8 γ-код Элиаса....................................................................................................................... 91

Таблица 9 ω-код Элиаса...................................................................................................................... 92

Таблица 10 Код Хаффмена................................................................................................................. 98

Таблица 11 Код Шеннона................................................................................................................. 100

Таблица 12 Код Фано........................................................................................................................ 101

Таблица 13 Код Гилберта-Мура...................................................................................................... 103

ВВЕдение

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

Данное пособие содержит необходимый теоретический материал по четырем основным разделам курса «Структуры и алгоритмы обработки данных»: методы сортировки данных, древовидные структуры данных, хэширование и кодирование информации. Все рассмотренные методы проиллюстрированы наглядными примерами. Также для каждого метода приведен конкретный алгоритм, позволяющий легко программировать данный метод. Кроме того, в каждой главе даны варианты заданий, выполнив которые, можно окончательно уяснить все особенности изучаемых методов.

1. Необходимые понятия и определения

1.1 Основные структуры данных

Любая программа в процессе работы обрабатывает некоторые данные. По способу представления в памяти компьютера данные можно разделить на две группы: статические и динамические. Статические данные имеют фиксированную структуру, поэтому размер выделенной для них памяти постоянен. Динамические данные изменяют свою структуру в процессе работы программы, при этом объём памяти изменяется. Основные структуры данных представлены в следующей таблице.

Таблица 1 Различные типы данных

Статические	Простые	Перечислимые
Целые
Вещественные
Логические
Символьные
Структурированные	Массивы
Записи
Объединения
Динамические	Списки	Стек
Очередь
Деревья	АВЛ-деревья
Б-деревья

Основной характеристикой данных в программировании является тип данных. Любая константа, переменная, выражение, функция всегда относятся к определенному типу. Тип характеризует множество значений, которые может принимать переменная. К простым типам языка программирования относятся целые, вещественные, логические, символьные. Целые типы в языках программирования различаются количеством байт, отведённых в памяти (диапазоном значений) и наличием знака. Вещественные типы характеризуются точностью представления числа. Перечислимые типы образуются в процессе перечисления всех возможных значений. Логический тип является частным случаем перечислимого типа с двумя возможными значениями ИСТИНА и ЛОЖЬ.

Структурированные (составные) типы отличаются от простых тем, что состоят из набора компонент одинакового или разного типа. К структурированным типам относят массивы, записи (структуры), объединения (записи с вариантами).

Массивы – это наиболее известная и распространённая структура данных. Массив представляет собой фиксированное количество элементов одного типа. Всем элементам присваивается одно имя, а к отдельному элементу обращаются по его номеру (индексу). Тип элементов массива может быть любым, но тип индексов должен быть скалярным. Массив – структура данных со случайным (прямым) доступом, т.е. в любой момент времени доступен любой элемент массива, при этом индекс элемента можно вычислять. Обычный способ работы с массивом – выбор определённых элементов и их изменение. Также часто используется перебор элементов в цикле. В памяти элементы массива располагаются последовательно, без разрывов, по возрастанию адресов памяти.

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

Объединения или (записи с вариантами) используются для размещения в одной и той же области памяти данных различного типа. В один и тот же момент времени в памяти находятся данные только одного типа.

Динамические структуры данных позволяют работать с большими объемами данных. Наиболее используемые динамические структуры данных – списки и деревья.

1.2 Задача сортировки массивов

Пусть дан массив А=(а₁, а₂, …, а_n) и для всех его элементов определены операции отношения: меньше, больше, равно (<, >, =). Необходимо отсортировать массив, т.е. переставить элементы массива А таким образом, что выполняется одно из следующих неравенств:

a₁ ≤ а₂ ≤ а₃ ≤ … ≤ а_n

a₁ ≥ a₂ ≥ a₃ ≥... ≥ a_n

Если выполняется первое неравенство, то массив сортируется по возрастанию и такой порядок элементов будем называть прямым. Если выполняется второе неравенство, то массив отсортирован по убыванию и такой порядок элементов будем называть обратным. В дальнейшем, если не оговорено особо, используется прямой порядок сортировки.

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

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

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

1.3 Трудоемкость методов сортировки массивов

Существует много способов или методов сортировки массивов. Для того, чтобы оценить насколько один метод сортировки лучше другого необходимо каким-то образом оценивать эффективность метода сортировки. Естественно отличать методы сортировки по времени, затрачиваемому на реализацию сортировки. Для сортировок основными считаются две операции: операция сравнения элементов и операция пересылки элемента. Будем считать, что в единицу времени выполняется одна операция сравнения или пересылки. Таким образом, время или трудоемкость метода имеет две составляющие М и С, где

M – количество операций пересылки.

C– количество операций сравнения.

Нетрудно видеть, что M и C – зависят от количества элементов в массиве, т.е. являются функциями от длины массива. Часто бывает трудно определить точное выражение для трудоемкости алгоритма. В этом случае пользуются асимптотической оценкой времени работы.

Будем говорить, что функция g(x) асимптотически доминирует на f( x) или g(x)=O(f(x)), если | g(x)|≤const|f(x)| при x→ ∞. В дальнейшем будем рассматривать асимптотическое поведение величин М и С в зависимости от числа элементов в массиве n, при n → ∞.

Для функций f, f_1, f₂ и константы k справедливы свойства:

1. f = O(f)

2. O(k*f) = O(f)

3. O(f₁+f₂) = O(f₁) +O(f₂)

Пример. T = 10 n + 20

T = O(10 n +20) = O(10 n) + O(20) = O(n) +O(1) = O(n), при n → ∞.

Приведем ряд доминирования основных функций

O(1)<O(log n)<O(n)<O(n log n)<O(n^a)<O(aⁿ)<O(n!)<O(nⁿ), при n → ∞, a >1

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

1.4 Задача сортировки последовательностей

Пусть дана последовательность S=S₁S₂ …S_n , т.е. совокупность данных с последовательным доступом к элементам. Примерами такой последовательности могут служить файл на магнитной ленте, линейный список:

Необходимо переставить элементы последовательности так, чтобы выполнялись неравенства:S₁≤ S₂ ≤ … ≤ S_n Последовательный доступ означает, что любой элемент списка может быть получен только путём просмотра предыдущих элементов, причём просмотр возможен только в одном направлении. Это является существенным ограничением по сравнению с массивом, где можно было обратиться к любому элементу массиву, используя индекс. Поэтому методы сортировки, разработанные специально для массивов, не годятся для последовательностей, в то время как методы сортировки последовательностей используются и для сортировки массивов. Трудоемкость методов сортировки последовательностей измеряется количеством операций, затрачиваемых на сортировку. Характерными операциями при сортировке последовательностей являются операция сравнения элементов и операция пересылки элемента одной последовательности в другую. Как и прежде будем обозначать количества операций сравнения и пересылки С и М соответственно.

1.5 Теорема о сложности сортировки

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

Теорема. Если все перестановки из n элементов равновероятны, то любое дерево решений, сортирующее последовательность из n элементов имеет среднюю высоту не менее log(n!).

Приведем нестрогое доказательство. Рассмотрим дерево решений для трех элементов a, b, c.

Рисунок 1 Дерево решений для 6 элементов

Все возможные перестановки – это листья дерева (6 вариантов). Чтобы получить конкретную перестановку нужно сделать два или три сравнения. Оценим среднее количество сравнений, необходимых для упорядочивания массива или срденюю длину пути от корня дерева до листьев. Для этого посчитаем сумму длин всевозможных путей от корня до листьев (длина внешнего пути двоичного дерева) и поделим ее на количество листьев С_ср= (2+3+3+3+3+2)/6=2,6.

Из теории графов известно, что длина внешнего пути двоичного дерева с m листьями D(m)≥ m log m. Поскольку в общем случае на дереве имеется n! листьев. Тогда С_ср≥ n! log(n!)/ n!=lоg n! > n log n–n log e. Последнее неравенство является известной нижней оценкой для значения факториала. Таким образом, не существует алгоритма сортировки n элементов, использующего в среднем меньше чем (n log n – log e) операций сравнения. Класс сложности n log n является предельно достижимым для алгоритмов сортировки с использованием операций сравнения. Что касается количества пересылок, то если мы определим требуемую перестановку, и имеем память для второй копии массива, то достаточно сделать n пересылок. На сегодняшний день алгоритм, требующий n log n сравнений и n пересылок, неизвестен.

1.6 Задача поиска элементов с заданным ключом

Пусть имеется массив A = (a₁, a₂, … a_n) и задан ключ поиска X. Необходимо найти элемент (элементы) массива с ключом X, или определить, что элемента с заданным ключом в массиве нет. Если массив не упорядочен, то единственный путь поиска – просмотр всех элементов массива (линейный поиск) до тех пор, пока не будет найден этот элемент, или просмотрен весь массив. Трудоёмкость поиска в этом случае равна O(n), n → ∞. Более эффективные алгоритмы поиска можно построить, если предполагать, что массив отсортирован, т.е. a₁≤ a₂ ≤ a₃ ≤ … ≤ a_n. Трудоемкость метода поиска будем оценивать по количеству сравнений, требуемых для поиска нужного элемента, при этом нас интересует только асимптотическая оценка трудоемкости.

2. Методы сортировки с квадратичной трудоемкостью

2.1 Метод прямого выбора

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

Пример. Упорядочим слово методом прямого выбора.

Условные обозначения

Х сравнение элемента Х с текущим максимальным элементом

текущий максимальный элемент

Перестановка элементов

•			•
К	У	Р	А	П	О	В	А
	•	•	•			•	•
А	У	Р	К	П	О	В	А
		•	•			•
А	А	Р	К	П	О	В	У
			•
А	А	В	К	П	О	Р	У
				•	•
А	А	В	К	П	О	Р	У
					•
А	А	В	К	О	П	Р	У
						•
А	А	В	К	О	П	Р	У
А	А	В	К	О	П	Р	У

Рисунок 2 Метод прямого выбора