570_Kurapova_E._V._Struktury_i_Algoritmy

Таблица 17

5.Реализовать графическую подпрограмму изображения дерева оптимального поиска на экране (с весом каждой вершины).*

ЛАБОРАТОРНАЯ РАБОТА 10

Тема: Дерево оптимального поиска (приближенные алгоритмы)

Цель работы: Изучение процесса программного построения почти оптимальных деревьев поиска.

1.Построить ДОП двумя приближенными алгоритмами из всех символов ФИО студента (вес символа – количество этого символа в наборе), вычислить средневзвешенные высоты построенных деревьев. В построенных деревьях найти первую букву фамилии и букву «Я». При тестировании программы можно использовать данный пример для проверки правильности построения дерева.

2.Реализовать программно алгоритмы А1 и А2 для построения почти оптимальных деревьев поиска.

3.Построить почти оптимальные деревья поиска из 100, 200,…, 500 вершин (данные в вершинах произвольные, но все различные) с помощью алгоритмов А1 и А2, распечатать их обход слева направо.

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

проанализировать полученные результаты. Таблица 18

21

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

СПИСОК РЕКОМЕНДОВАННОЙ ЛИТЕРАТУРЫ

1.Курапова Е.В., Мачикина Е.П. Структуры и алгоритмы обработки данных. Методическое пособие. Сиб. гос. ун-т телекоммуникаций и информатики. - Новосибирск, 2006.

2.Вирт Н. Алгоритмы и структуры данных: Новая версия для Оберона / Пер. с англ. - М.: ДМК Пресс, 2012.

3.Кнут Д. Искусство программирования: в 3т. Т.1. Основные алгоритмы. - 3-е изд. - М.: Издат. дом «Вильямс», 2010.

4.Кнут Д. Искусство программирования: в 3т. Т.3. Сортировка и поиск. - 3-е изд. - М.: Издат. дом «Вильямс», 2010.

5.Ахо А. В. Хопкрофт Д., Ульман Д. Д. Структуры данных и алгоритмы. Учеб. пособие/ Пер. с англ. - М.: Издат. дом «Вильямс», 2010.

6.Седжвик Р. Алгоритмы на C++. Фундаментальные алгоритмы и структуры данных. - М. : Издат. дом «Вильямс», 2011.

7.Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. - М.: Издат. дом «Вильямс», 2014.

8.Кубенский А. Структуры и алгоритмы обработки данных: объектно-ориентированный подход и реализация на С++. - СПб.: БХВ-Петербург, 2010.

22