Уфимский государственный авиационный технический университет

ОТЧЕТ по лабораторной работе №5

по дисциплине:

«Функциональное программирование»

на тему:

«Произвольные структуры данных. Деревья. »

Выполнил: бакалавр гр. ПРО-223

Алексеева А.В.

Проверил: Фридлянд Александр Михайлович

Содержание

Содержание 2

1 задание 3

2 задание 4

3 задание 5

4 задание 6

5 задание 8

6 задание 9

Заключение 10

1. Цель работы (Вариант 3)

1. Создать модуль EvalTrees (описанный в тексте пособия Г.А. Макеева).

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

Для списка чисел [3,4,6,7] найти с помощью дерева вычислений:

a) -0.25

b) наименьшее целое число

3. Определить тип данных для бинарного поискового дерева: data Ord a => SearchTree a = Empty | Branches a (SearchTree a) (SearchTree a) deriving (Show, Eq), запросите и объясните тип функций-конструкторов-данных Empty и Branches, постройте с помощью этих функций простейшие деревья.

4. Реализовать в деревьях поиска функции добавления элементов, поиска с выводом (список просмотренных вершин до нужного элемента), проверки сбалансированности дерева и построения идеально сбалансированного дерева. Элементы дерева указаны в вариантах, достаточно 10-15 элементов.

Список чисел Фибоначчи

5. Определить тип данных для предложенного в варианте объекта.

Вектор на плоскости

6. Реализовать для определенного в зад.1 типа указанную функцию, переопределив ее. Придумать и реализовать еще 2-3 подходящие функции для работы с объектами вашего типа.

Функцию умножения (скалярного).

2 Результат выполнения работы

1. задание

Создать модуль EvalTrees (описанный в тексте пособия Г.А. Макеева).

Рисунок 1 Листинг кода задания №1.

2. задание

Для списка чисел [3,4,6,7] найти с помощью дерева вычислений:

a) -0.25

b) наименьшее целое число

Рисунок 2 Листинг кода задания №2.

Рисунок 3 Результат выполнения задания №2 пунктов a, b

3. задание

Определить тип данных для бинарного поискового дерева: data Ord a => SearchTree a = Empty | Branches a (SearchTree a) (SearchTree a) deriving (Show, Eq), запросите и объясните тип функций-конструкторов-данных Empty и Branches, постройте с помощью этих функций простейшие деревья.

Рисунок 4 Листинг кода задания №3 в текстовом редакторе

Рисунок 5 Результат выполнения задания №3. Часть 1.

Рисунок 6 Результат выполнения задания №3. Часть 2.

4. задание

Реализовать в деревьях поиска функции добавления элементов, поиска с выводом (список просмотренных вершин до нужного элемента), проверки сбалансированности дерева и построения идеально сбалансированного дерева. Элементы дерева указаны в вариантах, достаточно 10-15 элементов.

Список чисел Фибоначчи

Рисунок 7 Листинг кода задания №4 в текстовом редакторе

Рисунок 8 Построение дерева

Рисунок 9 Вычисление максимальной высоты дерева

Рисунок 10 Проверка сбалансированности дерева

Рисунок 11 Построение идеально сбалансированного поискового дерева, AVL

Рисунок 12 Очередная проверка на сбалансированность

5. задание

Определите тип данных для объекта:

• Вектор на плоскости

Рисунок 13 Листинг кода задания №5 в текстовом редакторе

Рисунок 14 Пример использования кода задания №5

6. задание

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

Какие функции реализовала я:

• сложение векторов

• скалярное умножение

• умножение векторов

Рисунок 15 Листинг кода задания №6 в текстовом редакторе

Рисунок 16 Результат выполнения задания №6

Заключение

В ходе выполнения лабораторной работы была решена поставленная задача:

Выполнены задания в соответствии со своим вариантом. Изучена работа с произвольными структурами данных, деревьями. Освоены следующие методы обработки деревьев: поиск с выводом, проверка сбалансированности дерева, построение идеально сбалансированного дерева AVL.

Реализовала:

• Модуль EvalTrees (описанный в тексте пособия Г.А. Макеева).

• Для заданного списка чисел и определенных операций в дереве вычислений вывод дерева с заданными результатами вычислений (или получить ответ, что это невозможно).

• Определение типа данных для бинарного поискового дерева: data Ord a => SearchTree a = Empty | Branches a (SearchTree a) (SearchTree a) deriving (Show, Eq), запрос и объяснение типов функций-конструкторов-данных Empty и Branches, построение с помощью этих функций простейших деревьев.

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

• Определение типа данных для предложенного в варианте объекта.

• Для определенного в зад.1 типа указанную функцию, переопределив ее. Придумать и реализовать еще 2-3 подходящие функции для работы с объектами данного типа.

Уфа – 2020