Основные операции при работе с деревьями

Содержание

Основные операции при работе с деревьями. 3

Определение глубины дерева. 4

Обход дерева на заданную глубину. 4

включение нового значения в дерево. 4

Поиск первого подходящего в дереве на основе полного обхода. 4

Поиск в дереве максимального (минимального) значения. 5

Оптимизация поиска в дереве. 5

Нумерация вершин. 6

Поиск и включение в двоичное дерево. 7

Нумерация вершин в двоичном дереве. 8

Контрольные вопросы.. 8

Задания для практической работы.. 8

Сбалансированные двоичные деревья. 13

Преобразование двоичного дерева в лозу. 13

Преобразование лозы в сбалансированное двоичное дерево. 14

Контрольные вопросы.. 16

Задания для практической работы.. 16

Графы.. 17

Основные понятия. 17

Алгоритмы представления графа. 17

Представление графа в виде массива. 18

Представление графа в виде матрицы смежности. 19

Представление графа в виде связанного списка. 21

Представление графа в виде списка дуг. 24

Преобразования структур графа. 26

Обходы в графах. 27

Определение путей и контуров Эйлера. 30

Поиск кратчайших путей. 32

Определение остовных деревьев. 36

Контрольные вопросы.. 44

Задания для практической работы.. 44

Жадные алгоритмы.. 47

Контрольные вопросы.. 49

Задания для практической работы.. 49

Алгоритмы сортировок. 50

Сортировка выбором.. 50

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

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

Быстрая сортировка. 51

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

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

Контрольные вопросы.. 58

Задания для практической работы.. 58

Алгоритмы поиска. 59

Введение. 59

Последовательный поиск. 59

Двоичный поиск. 59

Работа со словарем. Иоиск и вставка. Хеширование. 59

Поиск подстроки в строке. 66

Алгоритм прямого поиска подстроки в строке. 66

БМ-поиск (Боуера–Мура) 68

КМП-поиск (Кнута–Мориса и–Пратта) 71

Контрольные вопросы.. 77

Задания для практической работы.. 77

Основные операции при работе с деревьями

К основным операциям работы с деревьями относятся:

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

б) включение элемента в дерево. Операция заключается в добавлении листа (исключая сбалансированное дерево – включение элемента в сбалансированное дерево приводит, как правило, к его перестройке) в какое-то поддерево, если такого элемента нет в исходном дереве. При включении нового элемента в дерево поиска лист добавляется в то поддерево, в котором не нарушается отношение порядка;

в) удаление элемента из дерева. Операция заключается в изменении связей между дочерними и родительскими, по отношению к удаляемому, элементами (исключая сбалансированное дерево – удаление элемента из сбалансированного дерева приводит, как правило, к его перестройке); здесь необходимо рассматривать три случая: удаление листа (см. рис.1.а), удаление элемента с одним потомком (см. рис.1.б), удаление элемента с двумя потомками (см. рис.1.в).

Рис. 1. Случаи удаления листа дерева

 

При удалении элемента степени 2 из дерева поиска изменять связи необходимо так, чтобы не нарушалось установленное в дереве отношение порядка. Лучшим вариантом в этом случае будет перемещение на место удаляемого элемента либо самого правого листа из левого поддерева удаляемого элемента, либо самого левого листа из правого поддерева удаляемого элемента;

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

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

Далее рассмотрим операции поиска и включения элемента в дерево. Остальные операции можно выполнить на основе работы алгоритмов поиска и включения элемента в дерево.

 

 

Определение глубины дерева

При определении минимальной (максимальной) длины ветви дерева каждая вершина должна получить значения минимальных длин ветвей от потомков, выбрать из них наименьшую и передать предку результат, увеличив его на 1 - " добавить себя" .

struct tree{int val;tree *p[4];};//---- Определение ветви минимальной длиныint MinLnt(tree *q){if (q==NULL) return 0;int min= MinLnt(q->p[0]); for (int i=1; i< 4; i++){ int x=MinLnt(q->p[i]); if (x < min) min=x;}return min+1;}

Обход дерева на заданную глубину

 

Для отслеживания процесса " погружения" достаточно дополнительной переменной, которая уменьшает свое значение на 1 при очередном рекурсивном вызове.

//------Включение вершины в дерево на заданную глубинуint Insert(tree *ph, int v, int d) { // d - текущая глубина включенияif (d == 0) return 0; // Ниже не просматриватьfor ( int i=0; i< 4; i++) if (ph->p[i] == NULL){ tree *pn=new tree; pn->val=v; for (int j=0; j< 4; j++) pn ->p[j]=NULL; ph->p[i]=pn; return 1; }else if (Insert(ph->p[i], v , d-1)) return 1; // Вершина включенаreturn 0; }

Включение нового значения в дерево

Для включения простейшим способом нового значения в дерево в ближайшее в корню место достаточно соединить две указанные функции вместе.

void main(){ tree PH={ 1,{NULL,NULL,NULL,NULL} };for (int i=0; i< 100; i++) Insert( & PH, rand( 20 ), MinLnt( & PH));}

Поиск первого подходящего в дереве на основе полного обхода

 

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

//---- Поиск в дереве строки, длиной больше заданнойstruct stree{char *str;stree *p[4];};char *big_str(stree *q){if (q==NULL) return NULL;if (strlen(q->str)> 5) return q->str; // Найдена в текущей вершине for (int i=0; i< 4; i++){ char *child=big_str(q->p[i]); // Получение строки от потомка if (child!=NULL) return child; // Вернуть ее " от себя лично" }return NULL;} // Нет ни у себя, ни у потомков

Поиск в дереве максимального (минимального) значения

 

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

//---- Поиск максимального в деревеint GetMax(tree *q){if (q==NULL) return -1;int max=q->val; for (int i=0; i< 4; i++){ int x=GetMax(q->p[i]); if (x > max) max=x;}return max;}

Оптимизация поиска в дереве

Основное свойство дерева соответствует пословице " дальше в лес - больше дров" . Точнее, количество просматриваемых вершин от уровня к… Функция включения в такое дерево ради сохранения свойств должна в каждой…

Нумерация вершин

Способы обхода дерева.В деревьях обход вершин возможен только с использованием рекурсии, поэтому и их логическая нумерация производится согласно… Если каждая вершина дерева будет содержать дополнительный параметр количество… В двоичном дереве каждая вершина имеет не более двух потомков, обозначенных как левый ( left) и правый ( right). Кроме…

Поиск и включение в двоичное дерево

Нумерация вершин в двоичном дереве

 

В двоичном дереве естественная нумерация вершин соответствует обходу в порядке возрастания их значений, то есть левое поддерево текущая вершина правое поддерево.

//---- Обход двоичного дерева с нумерацией вершинvoid ScanNum ( btree *q, int &n ) {if (q==NULL) return;ScanNum(q->left,n);printf("n=%d val=%d\n",n,q->val); n++;ScanNum(q->right,n);}

Контрольные вопросы

1. Что представляет собой двоичное дерево?
2. Чем отличается двоичное дерево от двусвязного списка?
3. В чем заключается особенность дерева как структуры данных?
4. Процедуры какого характера наиболее эффективны при работе с деревьями?
5. В чем заключается вставка узла в дерево?
6. В чем заключается удаление узла из дерева?
7. Каковы особенности удаления элемента из древовидной структуры данных?
8. В чем заключается поиск в дереве?
9. Что такое «прохождение дерева»?
10. Какие возможны варианты прохождения дерева?
11. Что такое высота дерева?
12. Как сохранить сбалансированность дерева при вставке и удалении узлов?

Задания для практической работы

Создать класс операций по работе с деревом. Программа должна содержать функцию обхода дерева с выводом его содержимого, функцию добавления вершины дерева (ввод), а также указанную в варианте функцию.

1. Вершина дерева содержит указатель на строку. Строки в дереве не упорядочены. Функция включает вершину в дерево с новой строкой в ближайшее свободное к корню дерева место. ( В результате дерево будет сбалансированным). Для исключения полного обхода в каждую вершину дерева поместить длину его минимальной ветви и корректировать его в процессе включения во всех проходимых вершинах.

2. Вершина двоичного дерева содержит массив целых и два указателя на правое и левое поддерево. Массив целых в каждом элементе упорядочен, дерево в целом также упорядочено. Функция включает в дерево целую переменную с сохранением упорядоченности.

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

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

5. Вершина дерева содержит целое число и массив указателей на поддеревья. Целые в дереве не упорядочены. Функция включает вершину в дерево с новой целой переменной в ближайшее свободное к корню дерева место. (То есть дерево должно иметь ветви, отличающиеся не более чем на 1).

6. Вершина дерева содержит два целых числа и три указателя на поддеревья. Данные в дереве упорядочены. Написать функцию включения нового значения в дерево с сохранением упорядоченности.

7. Вершина дерева содержит указатель на строку и N указателей на потомков. Функция помещает строки в дерево так, что строки с меньшей длиной располагаются ближе к корню. Если новая строка " проходит" через вершину, в которой находится более длинная строка, то новая занимает место старой, а алгоритм включения продолжается для старой строки. Функция включения выбирает потомка минимальным количеством вершин в поддереве.

8. Вершина дерева содержит либо 4 целых значения, либо 2 указателя на потомков, причем концевые вершины содержат данные, а промежуточные - указатели на потомков. Естественная нумерация значений производится при обходе концевых вершин слева направо. Разработать функции получения и включения значения в дерево по логическому номеру.

9. Вершина дерева содержит N целых значений и два указателя на потомков. Запись значений производится таким образом, что меньшие значения оказываются ближе к корню дерева (то есть все значения в поддеревьях больше самого большого значения у предка). Разработать функции включения и поиска данных в таком дереве. Если новое значение " проходит" через вершину, в которой находится большее, то оно замещает большее значение, а для последнего алгоритм включения. Функция включения выбирает потомка максимальным значением в поддереве.

10. Выражение, содержащее целые константы, арифметические операции и скобки, может быть представлено в виде двоичного дерева. Концевая вершина дерева должна содержать значение константы. Промежуточная - код операции и указатели на правый и левый операнды - вершины дерева. Функция получает строку, содержащую выражение, и строит по ней дерево. Другая функция производит вычисления по полученному дереву.

11. Вершина дерева содержит указатель на строку и динамический массив указателей на потомков. Размерность динамического массива в корневой вершине - N, на каждом следующем уровне - в 2 раза больше. Функция при включении строки создает вершину, наиболее близкую к корню.

12. Вершина дерева содержит динамический массив целых значений и два указателя на потомков. Значения в дереве не упорядочены. Размерность динамического массива в корневой вершине - N, на каждом следующем уровне - в 2 раза больше. Функция включает новое значение в свободное место в массиве ближайшей к корню вершины.

13. Вершина дерева содержит массив целых и два указателя на правое и левое поддерево. Значения в дереве не упорядочены. Естественная нумерация значений производится путем обхода дерева по принципу " левое поддерево - вершина - правое поддерево" . Разработать функции включения и получения значения элемента по заданному логическому номеру.

14. Написать функцию, которая добавляет к бинарному дереву T новую вершину с элементом E (если ее не было в T).

15. Написать функцию , которая заменяет в дереве T значения всех отрицательных элементов вершин на их абсолютные величины (информационное поле вершины дерева T имеет тип Real).

16. Написать функцию , которая удаляет все вершины с одинаковыми элементами из непустого дерева T (разрешается использовать вспомогательную множественную структуру данных).

17. Написать функцию , которая удаляет из непустого бинарного дерева T вершины, содержащие максимальный и минимальный элемент (информационное поле вершины дерева имеет тип Real).

18. Написать функцию , которая удаляет из непустого дерева поиска T вершины, содержащие максимальный и минимальный элемент (информационное поле вершины дерева имеет тип Real).

19. Написать функцию , которая удаляет из непустого дерева все вершины с положительными элементами (информационное поле вершины дерева имеет тип Real).

20. Написать функцию , которая удаляет из непустого дерева поиска все вершины с отрицательными элементами (информационное поле вершины дерева имеет тип Real).

21.

22. Написать функцию, которая определяет, входит ли вершина, содержащая информационное поле E, в заданное бинарное дерево дважды.

23. Написать функцию, которая проверяет, входит ли вершина, содержащая информационное поле E, в правое или левое поддерево заданного дерева поиска.

24. Написать функцию, которая проверяет совпадают ли элемент из самого левого листа непустого поиска дерева с элементом из самого правого листа того же дерева.

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

26. Установить, можно ли попасть из одной вершины дерева поиска в другую, если двигаться по ветвям к листьям.

27. Используя линейную скобочную запись дерева поиска, описать логическую функцию, проверяющую на равенство деревья поиска T1 и T2.

28. Написать с помощью линейной скобочной записи бинарного дерева функцию, проверяющую, входит ли вершина с элементом E в правое (левое) поддерево заданного бинарного дерева.

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

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

31. Описать функцию , которая вычисляет сумму элементов всех вершин заданного непустого дерева поиска (информационное поле вершины дерева имеет тип Real).

32. Описать функцию, которая определяет максимальную глубину непустого дерева, т.е. количество ветвей в самом длинном из путей от корня дерева до листьев.

33. Определить глубину (высоту) непустого дерева поиска, используя функцию определения пути от данной вершины до корня.

34. Используя линейную скобочную запись дерева, описать функцию, которая определяет максимальную глубину непустого бинарного дерева.

35. Описать функцию, которая подсчитывает количество вершин на k-ом уровне непустого дерева поиска (корень - вершина 0-го уровня).

36. Написать функцию, которая определяет количество вхождений элемента E в информационные поля вершин левого поддерева заданного бинарного дерева.

37. Написать функцию, которая вычисляет среднее арифметическое всех элементов заданного непустого дерева (информационное поле вершины дерева имеет тип Real).

38. Написать функцию, которая находит в заданном непустом бинарном дереве длину (количество ветвей) пути от корня до 1ближайшей вершины с заданным элементом E.

39. Определить суммарный путь данного дерева поиска, используя функцию определения пути от данной вершины до корня.

40. Используя линейную скобочную запись дерева, написать функцию, которая находит содержимое информационного поля самого левого (правого) листа непустого дерева поиска.

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

42. Используя линейную скобочную запись дерева, написать функцию, которая находит в заданном непустом бинарном дереве длину (количество ветвей) пути от корня до вершины с заданным элементом E.

43. Написать функцию, которая выбирает из непустого дерева поиска все разные английские буквы (информационное поле вершины дерева имеет тип Char).

44. Написать функцию, которая определяет максимальный элемент из всех листьев непустого бинарного дерева (информационное поле вершины дерева имеет тип Integer).

45. Написать процедуру, которая выводит на экран содержимое информационных полей всех внутренних вершин бинарного дерева.

46. Выписать все вершины дерева поиска, находящиеся на заданном уровне k (k=0,1,2,...), используя функцию определения пути от данной вершины до корня.

47. Используя линейную скобочную запись дерева, описать процедуру, которая определяет элементы всех внутренних вершин дерева поиска.

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

49. Написать функцию , которая записывает в файл F элементы вершин заданного дерева поиска в порядке возрастания.

50. Множество целых чисел поместить в дерево поиска и на основе этого представления упорядочить данное множество.

 

Сбалансированные двоичные деревья

После каждой операции изменения дерева можно проводить балансировку дерева, которая позволяет минимизировать его высоту. При этом поиск по двоичному… К сожалению, пока нет способа проведения быстрой балансировки дерева до его… Алгоритм балансировки состоит из двух частей:

Преобразование двоичного дерева в лозу.

 

Мы проходим по дереву указателем p, начиная в корне дерева. Вспомогательный указатель q указывает на родителя p (поскольку мы строим левоассоциативное дерево, то p всегда является левым ребенком q). На каждом шаге возникает одна из двух возможных ситуаций:

- Если у p нет правого ребенка, то эта часть дерева уже перестроена. p и q просто спускаются по дереву (приравниваются своим левым сыновьям).

- Если у p есть правый ребенок (обозначим его r), тогда выполняется левый поворот относительно p:

Рис. 3. Выполнение левого поворот

 

На рисунке a, b и c обозначают поддеревья, которые могут быть пусты. После поворота устанавливаем указатель p на r.

 

Преобразование лозы в сбалансированное двоичное дерево.

Этот этап алгоритма более содержательный и поэтому менее очевидный. Поэтому сначала будет разобран простой пример, а потом будет дано его… Пусть есть лоза, которая состоит из 2n-1 вершин для какого-либо натурального… На первой операции пройдем по лозе сверху вниз, начиная в корне, и раскрасим каждую вершину соответственно в серый или…

Контрольные вопросы

1. Что означает термин «сбалансированное» дерево?

2. Для чего выполняется балансировка?

3. Опишите фазы балансировки.

4. Как происходит преобразование исходного дерева в лозу?

5. Как происходит преобразование лозы в сбалансированное дерево?

6. В каких случаях необходимо укорачивать лозу?

7. Как определить размер укорачивания?

 

Задания для практической работы

 

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

 

Графы

Основные понятия

 

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

Для моделирования сетей в математике служат объекты, называемые графами. Графом G называется пара множеств (V, E), где V— конечное множество элементов, называемых вершинами графа, а E— конечное множество упорядоченных пар е = (w, v), называемых дугами, где w, v— вершины.

Говорят, что дуга е выходит из вершины w и входит в вершину v. Вершины w и v называют инцидентными дуге е, а дугу е — инцидентной вершинам w и v.

В этом определении множество вершин V соответствует множеству узлов моделируемой сети, а множество дуг— связям между узлами. Определение, данное выше, отражает лишь структуру сети, но не характеристики ее отдельных узлов и связей. Если такие характеристики все же существенны, то рассматривают нагруженные графы, в которых с каждой вершиной или дугой (может быть, и с тем, и с другим) связана величина или несколько величин, называемых нагрузкой на граф. Формально говоря, нагрузку графа определяют функции:

 

f:V->W1 и g: E -> W2,

где W1 и W2 представляют собой множества значений нагрузки вершин и дуг графа соответственно. Иногда при анализе графа неважно, какая из вершин w и v в дуге е = (w, v) первая, а какая вторая, т. е. пара (w, v) не упорядочена. В этом случае дугу е называют ребром, а весь граф называют неориентированным в отличие от ориентированного графа, задаваемого исходным определением. Разумеется, в этом случае бессмысленно говорить о том, из какой вершины ребро выходит и в какую вершину входит. Формально говоря, неориентированным графом называют такой граф, у которого наряду с любой дугой e1 = (u, v) имеется и противоположная дуга е2 — (v, u). Эта пара дуг и образует ребро е = <u, v> неориентированного графа.

 

Алгоритмы представления графа

При программировании задач обработки сетевых структур требуется решить вопрос о представлении графа структурами данных языка программирования. Выбор… Говоря о представлении графа, имеют в виду прежде всего вопрос о представлении… Ниже приводится несколько способов представления графов, причем для каждого способа указано, для каких алгоритмов он…

Представление графа в виде массива

 

Первое из описываемых представлений графа основано на следующих соображениях. Структуру графа можно описать, сопоставив каждой вершине множество дуг, выходящих из нее, причем каждая дуга, выходящая из вершины u, идентифицируется своим концом— номером вершины, в которую эта дуга входит. Таким образом, граф представляется массивом, в котором каждому номеру вершины и в диапазоне от 0 до N сопоставлено множество целых чисел — номеров вершин, в которые входят дуги, исходящие из выбранной вершины u. Описанное представление графа будем называть S-графом (от set— множество). Будем считать, что множество целых чисел в диапазоне от 0 до N представлено объектом класса Set. Тогда S-граф может быть описан следующим классом:

 

Файл graph.h

class Graph

{

public:

// Функция addArc позволяет добавить к графу новую дугу,

// ведущую из вершины с номером from в вершину с номером to.

virtual void addArc (int from, int to) = 0;

// Функция has Arc проверяет, имеется ли в графе дуга, ведущая

//из вершины с номером from в вершину с номером to.

virtual bool hasArc(int from, int to) const = 0;

// Функция vertexCount выдает число вершин графа

virtual int vertexCount() const = 0;

};

 

Файл setgraph.h

#include "set.h" // Определение класса для работы с множествами class SetGraph : public Graph { Set **graph; // Массив множеств дуг

Представление графа в виде матрицы смежности

Еще один распространенный способ представления графа — это представление в виде матрицы смежности размером N * N (рис.1). B этой матрице в элементе… Представление в виде матрицы смежности будем называть М-графом. Удобно…

Файл MatrixGraph.h

#include "graph.h"

class MatrixGraph : public Graph {

bool **graph;

int vertexNumber;

 

public:

// Конструктор с параметром - количеством вершин графа.

MatrixGraph(int n);

 

// Количество вершин постоянно и содержится в поле vertexNumber

int vertexCount() const { return vertexNumber; }

 

// Остальные виртуальные функции, реализацию которых требуется

// предоставить при определении конкретного представления графа

void addArc(int from, int to);

bool hasArc(int from, int to) const;

};

 

Файл MatrixGraph.cpp

  // Реализация конструктора - заказ и инициализация памяти // под двумерный массив логических значений

Представление графа в виде связанного списка

Рис.2. Граф и его представление в виде связанных списков.  

Файл ListGraph.h

  // Описание шаблона классов для представления // простых однонаправленных списков

Файл ListGraph.cpp

  // Реализация операций над списком. // Добавление нового элемента в список

Представление графа в виде списка дуг

Иногда используются и другие представления графов, например, для случая очень разреженных графов, когда при большом количестве N вершин графа число…  

Файл ArcGraph.h

// Описание класса для представления A-графа class ArcGraph : public Graph { // Дуга представлена элементом списка, содержащим номера

Файл ArcGraph.cpp

  //Реализация операции добавления дуги void ArcGraph::addArc(int from, int to) {

Преобразования структур графа

 

приведем функции преобразования, которые могли бы использоваться для изменения представления графа. Так определенные функции должны, как правило, иметь доступ к структурам как исходного, так и результирующего графов, так что в соответствующих описаниях классов эти функции должны быть объявлены "друзьями" соответствующих классов. В листинге 1.13 описаны четыре функции для следующего преобразования структур: M-граф -> S-граф -> L-граф -А-граф -> M-граф.

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

 

Файл convert.срр

#include "MatrixGraph.h" #include "ListGraph.h" #include "ArcGraph.h"

Обходы в графах

Как и в случае обхода деревьев, для графов существуют два основных класса обходов: обходы в глубину и обходы в ширину. Обходы в глубину пытаются каждый раз после прохождения некоторой вершины А… Обходы в ширину пытаются, начав с некоторой вершины, в качестве очередных рассматривать только вершины,…

Определение путей и контуров Эйлера

Путь Эйлера проходит по каждому ребру в графе только один раз. Контур Эйлера проходит каждое ребро в графе тоже один раз, а также начинается и… Если серьезно, то поиск путей и контуров Эйлера имеет более практичное…

Поиск кратчайших путей

Путем в графе называют чередующуюся последовательность вершин и дуг v1, e1, v2, e2,... vn-1 en-1, vn, в которой каждый элемент vi— вершина графа, а… Среди характеристик пути чаще всего рассматривается его длина— количество дуг… Самая простая задача поиска кратчайшего пути в графе состоит в следующем. Пусть заданы две вершины — начальная и…

Алгоритм Э. Дейкстры.

Алгоритм поиска кратчайшего пути в этом случае несколько напоминает алгоритм обхода графа в ширину и состоит в следующем. Будем рассматривать два… В начале работы первое множество будет пустым, а второе будет содержать все… Для определения пограничной вершины во время работы алгоритма постоянно корректируется массив расстояний dist, в…

Алгоритм Флойда — Уоршалла

Gk(i,j) = min(Gk-1(i,j), Gk-1(i,k-1) + Gk-1(k -1, j)) . В этой формуле считается, что если вершины i и j не соединены дугой, то… Кроме матрицы длин кратчайших путей G надо получить еще и матрицу направлений D для того, чтобы можно было определить…

Определение остовных деревьев

Остовиым деревом (скелетом) неориентированного графа называется его подграф, не имеющий циклов и содержащий все вершины исходного графа. Так,… Рис. 9. Нагруженный неориентированный граф и его остовные поддеревья

Файл listgraph.h

class ListGraph {   // Массив списков дуг

Файл Arc.h

// происходит по их весам   struct Arc {

Файл listgraph.cpp

double ListGraph::minSkeleton( // Выходной поток для вывода результирующей информации: std::ostream & out,

Контрольные вопросы

 

1. Основные понятия теории графов
2. Перечислите алгоритмы представления графа
3. Особенности представления графа в виде массива
4. Особенности представления графа в виде матрицы смежности
5. Особенности представления графа в виде связанного списка
6. Особенности представления графа в виде списка дуг
7. Особенности преобразования структур графа
8. Реализация обходов в графах
9. Определение путей и контуров Эйлера
10. Поиск кратчайших путей методом Дейкстры
11. Поиск кратчайших путей методом Флойда-Уоршала
12. Определение остовных деревьев методом Крускала
13. Определение остовных деревьев методом Прима

 

Задания для практической работы

 

Выберите граф и выполните следующие операции:

a) представить граф в виде массива;

b) представить граф в виде матрицы смежности;

c) представить граф в виде связанного списка;

d) представить граф в виде списка дуг;

e) предусмотреть возможность преобразования структур графа;

f) реализовать обход графа в глубину и ширину;

g) определить если имеются путь и контур Эйлера;

h) реализовать поиск кратчайшего пути методом Дейкстры и методом Флойда-Уоршала. Провести сравнительные характкристики;

i) определить минимальноем остовное дерево методом Крускала и методом Прима. Провести сравнительные характкристики.

 

1. 2.

3. 4.

5. 6.

7. 8.

9. 10.

11. 12.

13. 14.

16.

15.

 

Жадные алгоритмы

Жадный алгоритм (англ. Greedy algorithm) — алгоритм, заключающийся в принятии локально оптимальных решений на каждом этапе, допуская что конечное решение также окажется оптимальным.

Общего критерия оценки применимости жадного алгоритма для решения конкретной задачи не существует, однако, для задач, решаемых жадными алгоритмами характерны две особенности:

во-первых, к ним применим Принцип жадного выбора ;

во-вторых, они обладают свойством Оптимальности для подзадач.

Принцип жадного выбора

Говорят, что к оптимизационной задаче применим принцип жадного выбора, если последовательность локально оптимальных выборов даёт глобально оптимальное решение. В типичном случае доказательство оптимальности следует такой схеме: Сначала доказывается, что жадный выбор на первом шаге не закрывает пути к оптимальному решению: для всякого решения есть другое, согласованное с жадный выбором и не худшее первого. Затем показывается, что подзадача, возникающая после жадного выбора на первом шаге, аналогична исходной, и рассуждение завершается по индукции.

Свойство оптимальности для подзадач

Говорят, что задача обладает свойством оптимальности для подзадач, если оптимальное решение задачи содержит в себе оптимальные решения для всех её подзадач. Например, в задаче о выборе заявок можно заметить, что если A — оптимальный набор заявок, содержащий заявку номер 1, то — оптимальный набор заявок для меньшего множества заявок , состоящего из тех заявок, для которых .

Пример: Размен монет

Задача. Монетная система некоторого государства состоит из монет достоинством a₁ = 1 < a₂ < ... < a_n. Требуется выдать сумму S наименьшим возможным количеством монет.

Жадный алгоритм решения этой задачи таков. Берётся наибольшее возможное количество монет достоинства a_n: . Таким же образом получаем, сколько нужно монет меньшего номинала, и т. д.

Для данной задачи жадный алгоритм не всегда даёт оптимальное решение. Например, сумму в 10 копеек монетами в 1, 5 и 6 коп. жадный алгоритм разменивает так: 6 коп. — 1 шт., 1 коп. — 4 шт., в то время как правильное решение — 2 монеты по 5 копеек. Тем не менее, на всех реальных монетных системах жадный алгоритм даёт правильный ответ.

Алгоритм Хаффмана (англ. Huffman) — адаптивный жадный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью. Был разработан в 1952 году доктором Массачусетского технологического института Дэвидом Хаффманом. Коды Хаффмана широко используются при сжатия информации (в типичной ситуации выигрыш может составить от 20% до 90% в зависимости от тина файла). Алгоритм Хаффмана находит оптимальные коды символов (исходя из частоты использования этих символов в сжимаемом тексте) с помощью жадного выбора.

Пусть в файле длины 100 000 известны частоты символов.

Мы хотим построить двоичный код, в котором каждый символ представляется в виде конечной последовательности битов, называемой кодовым словом.

	а	b	с	d	е	f
Количество (в тысячах)
Равномерный код
Неравномерный код

 

При использовании равномерного кода, в котором все кодовые слова имеют одинаковую длину, на каждый символ (из шести имеющихся) надо потратить как минимум три бита, например, а — 000, b — 001,.. .,f — 101. На весь файл уйдет 300 000 битов .

Рис.1. Представление равномерного кода в виде дерева.

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

Рис.2. Представление неравномерного кода в виде дерева.

 

. Один такой код показан на рис.2: буква а изображается однобитовой последовательностью 0, а буква f четырёхбитовой последовательностью 1 100. При такой кодировке на весь файл уйдёт (45- 1 + 13-3+ 12-3+ 16-3 + 9-1 +5-1) * 1000 = 221000 битов, что даёт около 25% экономии.

 

Этот метод кодирования состоит из двух основных этапов:

1. Построение оптимального кодового дерева.

2. Построение отображения код-символ на основе построенного дерева.

 

Общая схема построения дерева Хаффмана (рис.3):

1. Составим список кодируемых символов (при этом будем рассматривать каждый символ как одноэлементное бинарное дерево, вес которого равен весу символа).

2. Из списка выберем 2 узла с наименьшим весом (под весом можно понимать частоту использования символа — чем чаще используется, тем больше весит).

3. Сформируем новый узел и присоединим к нему, в качестве дочерних, два узла выбранных из списка. При этом вес сформированного узла положим равным сумме весов дочерних узлов.

4. Добавим сформированный узел к списку.

5. Если в списке больше одного узла, то повторить 2-5.

 

Рис.3. Этапы построения дерева Хаффмана

Контрольные вопросы

1. В чем принцип работы жадного алгоритма?

2. Какие типы задач можно решать с помощью жадного алгоритма?

3. Что понимается под методом Хаффмана?

4. Где применяется метод Хаффмана?

5. Как строится дерево Хаффмана?

6. Как вычислить размер исходного текста и сжатого?

Задания для практической работы

Задание состоит из нескольких этапов:

1. Получить у преподавателя индивидуальный текст для сжатия.

2. Создать программный модуль, который

- из исходного текста получает список кодируемых символов;

- Рассчитать размер несжатого файла;

- С учетом полученных вероятностей, построить дерево Хаффмана;

- Рассчитать размер сжатого файла.

3. Провести сравнительный анализ сжатия при разных характеристика исходного файла.

Алгоритмы сортировок

Сортировка выбором

Один из самых простых алгоритмов сортировки работает следующим образом. Сначала отыскивается наименьший элемент массива, затем он меняется местами с… Изложенный метод называется сортировкой выбором, поскольку он работает по…   A S O R T I N G E X A M …

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

Метод сортировки заключается в том, что отдельно анализируется каждый конкретный элемент, который затем помещается в надлежащее место среди других,… Как и в случае сортировки выбором, элементы, находящиеся слева от текущего…   A S O R T I N G E X A M …

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

Метод сортировки, который многие обычно осваивают раньше других из-за его исключительной простоты, называется пузырьковой сортировкой (bubble sort),… Предположим, что мы всегда передвигаемся по массиву справа налево. Если… В процессе пузырьковой сортировки элементы с малыми значениями устремляются влево. Поскольку сортировка производится в…

Быстрая сортировка

Алгоритм быстрой сортировки обладает привлекательными особенностями: он принадлежит к категории обменных (in-place) сортировок (т.е., требует всего… Его недостатком является то, что он неустойчив, для его выполнения в наихудшем… Быстрый метод сортировки функционирует по принципу "разделяй и властвуй". Он делит сортируемый массив на две…

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

Рассматривается сортировка слиянием (mergesort), которая является дополнением быстрой сортировки в том, что она состоит из двух рекурсивных вызовов… Одним из наиболее привлекательных свойств сортировки слиянием является тот… Сортировка слиянием — это устойчивая сортировка, и данное обстоятельство склоняет чашу весов в ее пользу в тех…

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

Итак, мы постепенно переходим от более-менее простых к сложным, но эффективным методам. В качестве некоторой прелюдии к основному методу, рассмотрим перевернутую… Пример действий для массива a[0]... a[7]: 44 55 12 42 94 18 06 67 исходный массив 44 55 12 42 67 18 06 |94 94…

Контрольные вопросы

1. Опишите алгоритм работы сортировки методом выбора.

2. Опишите алгоритм работы сортировки методом вставки.

3. Опишите алгоритм работы сортировки методом пузырька.

4. Опишите алгоритм работы быстрой сортировки.

5. Опишите алгоритм работы сортировки слиянием.

6. Опишите алгоритм работы пирамидальной сортировки.

7. Какой из алгоритмов является более стабильным?

8. Какой из алгоритмов сортировки быстродейственен?

 

Задания для практической работы

Реализовать все алгоритмы сортировки. Провести сравнительные характеристики работы алгоритмов при одинаковых входных параметрах. Протестировать работу всех сортировок, изменяя размерность входных данных.

 

Алгоритмы поиска

Введение

Некоторые алгоритмы поиска информации мы рассмотрели:

- Поиск первого подходящего в дереве на основе полного обходаОшибка! Закладка не определена.

- Поиск в дереве максимального (минимального) значения

- Поиск и включение в двоичное дерево

- Обходы в графах

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

Для неупорядоченных массивов используются одни методы поиска, а для упорядоченных массивов используются другие методы поиска.

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

Алгоритм последовательного поиска имеет очень простой вид: предполагая, что массив неотсортирован (неупорядочен), требуется проведения последовательного просмотра массива. Просмотр начинается с первого элемента и завершается либо найденным элементом, либо достижением конца массива При прямом последовательном поиске в среднем проверяются n/2 элементов. В лучшем случае будет проверяться только один элемент, а в худшем случае будут проверятся n элементов.

Двоичный поиск

Например, для поиска числа 4 в массиве 1 2 3 4 5 6 7 8 9 указанным методом сначала делается проверка среднего элемента, которым является число 5.…

Работа со словарем. Иоиск и вставка. Хеширование.

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

Файл dictionary.h

classHashDictionary { private:

Файл dictionary.cpp

intHashDictionary::code(char c) { returnstrchr("abcdefghijklmnopqrstuvwxyz", c) + 1;

Файл "hashtable.h".

// Класс, представляющий хеш-таблицу пар (ключ, значение), причем // ключом является строка, а значением может быть произвольный объект. //В таблице хранятся не сами эти объекты, а ссылки на них.

Поиск подстроки в строке

 

Часто приходится сталкиваться со специфическим поиском, так называемом поиском подстроки в строке. Его можно определить следующим образом. Пусть задана строка S из N элементов и строка p из M элементов. Описаны они так:

string S[N], P[M];

Задача поиска подстроки P в строке S заключается в нахождении первого слева вхождения P в S, т.е. найти значение индекса i, начиная с которого

S[i] = P, S[i + 1] = P,…, S[i + M – 1] = P[M – 1].

Разберем самый очевидный, самый «прямолинейный» алгоритм поиска.

Алгоритм прямого поиска подстроки в строке

1. Установить i на начало строки S, т.е. i = 0. 2. Проверить, не вышло ли i + M за границу N строки S. Если да, то алгоритм… 3. Начиная с i-го символа s, провести посимвольное сравнение строк S и p, т. е. S[i] и P, S[i+1] и P,…, S[i + M – 1] и…

Пример 1

k
D[k]	–1				–1				–1
P[k]	a	b	c	d	a	b	c	e	f

 

 

S

a

b

c

a

b

k

a

b

c

d

a

a

b

c

d

a

b

c

d

e

a

b

c

d

a

b

c

e

f

h

P

a

b

c

d

a

b

c

e

f

i

P

a

b

c

d

a

b

c

e

f

i

P

a

b

c

d

a

b

c

e

f

i

P

a

b

c

d

a

b

c

e

f

i

P

a

b

c

d

a

b

c

e

f

i

P

a

b

c

d

a

b

c

e

f

i

P

a

b

c

d

a

b

c

e

f

i

Блок-схема КМП-поиска имеет вид:

Рис.6. Блок-схема КМП-поиска.

 

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

Во-первых, рассмотрим самый плохой случай для линейного поиска.

Как было показано, число сравнений в линейном поиске равно M(N – M +1). Рассмотрим, как в этом случае работает КМП-поиск.

 

k		…	M - 2	M - 1
D[k]	–1	…	–1	M - 2
P[k]	a	…	a	b

 

S	a	…	a	a	a	…	a	…	a	b
P	a	…	a	b
i				M - 1
P		…	a	a	b
i					M - 1
…						…
P							a	…	a	b
i										M - 1

 

При значениях индекса i = 0, 1, …, M - 2 символы строки и образца совпадают: S[j] = P[i]. При i = M - 1 обнаруживается несовпадение и образец сдвигается так, что i = M - 2, т.е. на одну позицию, при этом символ S[j] сравнивается с символом P[M - 2]. Таким образом, символы строки, начиная с j = M - 1 (кроме последнего), сравниваются сначала с P[M - 1], а затем с P[M - 2], т.е. подвергаются двум сравнениям. Остальные символы строки сравниваются с символами образца лишь один раз. Таким образом, общее число сравнений есть 2N - M + 1, что в общем случае существенно меньше, чем в линейном поиске.

Во-вторых, индекс j, движущийся по строке, может только увеличиваться. Это позволяет искать образец в строке, заданной не массивом, а файлом, не используя дополнительных массивов для хранения информации.

Контрольные вопросы

1. Перечислите основные алгоритмы поиска в массивах.

2. Опишите принцип работы последовательного алгоритма поиска.

3. Опишите принцип работы двоичного алгоритма поиска.

4. Как реализован принцип хеширования.

5. Какая должна быть хеш-функция?

6. Когда возникает коллизия и как она разрешается?

7. Перечислите основные алгоритмы поиска подстроки в строке.

8. В чем суть линейного алгоритма поиска?

9. Опишите алгоритм БМ-поиска.

10. Опишите агоритм БМП-поиска.

11. Какой из алгоритмов поиска оптимальнее?

12. Какой алгоритм поиска быстродейственее?

Задания для практической работы

I. Реализовать алгоритмы последовательного и двоичного поиска. Провести сравнительный анализ при разных входных данных.

II. Хеширование:

1. Задан текст программы на языке Паскаль. Определить частоту использования:

а) идентификаторов;

б) ключевых слов:

в) символьных констант.

2. Задан текстовый файл. Сформировать список слов, употребляющихся в тексте более пяти раз.

3. Задан текстовый файл. Сформировать набор словосочетаний по два и более слова, встречающихся в тексте не менее двух раз.

4. Задан набор записей следующей структуры: табельный номер. ФИО. заработная плата. По табельном}* номеру найти остальные сведения.

5. Задан набор записей следующей структуры: номер телефона. ФИО адрес. По номеру телефона найти сведения о ФИО владельца и его адресе.

Задан набор записей следующей структуры: название кинофильма, режиссер, список актеров, краткое содержание. По заданному названию фильма найти остальные сведения.

6. Задан набор записей следующей структуры: номер автомобиля, его марка и ФИО владельца. По номеру автомобиля найти остальные сведения.

7. Задан список имен людей. Определить частоту использования каждого имени в некотором тексте.

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

9. Исследовать зависимость числа коллизий от коэффициента заполненности хеш-таблицы.

10.Из файла, содержащего текст на русском языке, слова помещаются в хеш-таблицу. Определить среднее число коллизий для нескольких заданных хеш-функций.

III. Реализовать и провести сравнительный анализ приведенных алгоритмов поиска подстроки в строке.