Теоретические положения Деревья. Основные понятия
 Скачать 452 Kb.
|
ЗаданиеОсуществить программную реализацию одного из деревьев, выбранных из табл. 1 приложения, в соответствии с заданным номером варианта. Программой должны выполняться функции (п. 1.1) по работе с деревом. Следует предусмотреть удобный пользовательский интерфейс, позволяющий создавать дерево и осуществлять его обработку. По результатам работы программы необходимо оценить зависимость среднего времени операции произвольного доступа к элементу от размера дерева (количества уровней и количества узлов). В программе следует предусмотреть генерацию дерева заданной степени, предоставляя пользователю возможность указывать среднюю степень узла и дисперсию. Например, если для некоторого дерева среднее равно шести, а дисперсия – двум, то в среднем по дереву у каждого узла будет примерно от 4 до 8 потомков (необходимо учитывать также максимальную степень дерева). Для генерации количества узлов следует использовать закон распределения, указанный в табл. 1 для выбранного варианта задания. К сгенерированному дереву должны быть применимы все реализованные функции. Помимо перечисленных в п. 1.1, обязательными являются функции просмотра дерева, просмотра последовательностей обхода дерева. Можно реализовать иные дополнительные функции.Контрольные вопросы
2.2. Лабораторная работа №2 «Программирование алгоритмов реализации и обработки древовидных структур специального вида» Цель работы Получение навыков создания и обработки АВЛ- и B-деревьев, анализ эффективности работы с ними. Задание Осуществить программную реализацию АВЛ- или B-дерева заданного порядка, с указанным типом ключа, выбрав из табл. 2 приложения соответствующие номеру варианта исходные параметры. Программа должна предоставлять удобный пользовательский интерфейс, позволяющий создавать дерево (формировать пользователем или генерировать автоматически) и осуществлять предусмотренные виды его обработки. Набор функций, необходимых для работы с деревом, должен включать, как минимум: генерацию дерева, поиск с включением узла, удаление узла, удаление дерева. С помощью статистического анализа необходимо определить формы зависимостей скоростей работы алгоритмов построения, поиска и включения, удаления и (или) перестраивания от размера дерева и построить соответствующие графики. Контрольные вопросы 1. АВЛ-деревья. 2. Поиск с включением в АВЛ-дерево, исключение из АВЛ-дерева.
2.3. Лабораторная работа №3 «Программирование алгоритмов реализации и обработки графов» Цель работы Получение навыков реализации алгоритмов обхода графов и построения минимальных остовных деревьев. Задание Осуществить программную реализацию алгоритма обработки графа, выбрав из табл. 3 приложения алгоритм и начальные параметры, в соответствии с заданным номером варианта. В программе необходимо предусмотреть удобный пользовательский интерфейс, позволяющий создавать граф (пользователем или генерировать автоматически), выполнять требуемый алгоритм и визуализировать этапы выполнения алгоритма и результаты. Контрольные вопросы 1. Определение графа. 2. Алгоритмы обхода графа в глубину и по уровням. 4. Алгоритм Дейкстры-Прима построения МОД. 5. Алгоритм Крускала построения МОД. 3. Содержание отчета1. Титульный лист.
Отчет может также включать краткие теоретические сведения.4. Библиографический список
Приложение Таблица 1 Задания к лабораторной работе №1
Таблица 2 Задания к лабораторной работе №2
Таблица 3 Задания к лабораторной работе №3
Нелинейные структуры данных Методические указания для студентов к лабораторным работам по курсу «Структуры и алгоритмы компьютерной обработки данных» Составитель: Журавлева Марина Гарриевна Редактор: Федюшина Е. А. Подписано в печать Формат 60х84 1/16. Бумага офсетная. Ризография. Печ.л. 1,5. Тираж 100 экз. Заказ N . Липецкий государственный технический университет. 398600 Липецк, ул. Московская, 30. Типография ЛГТУ. 398600 Липецк, ул. Московская, 30. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||