Реализация алгоритмов вычислительной математики с разработкой соответственного программного обеспечения для ЭВМ
Автор: Lysenkoff • Ноябрь 25, 2018 • Курсовая работа • 5,365 Слов (22 Страниц) • 675 Просмотры
Министерство образования и науки Украины
Государственное высшее учебное заведение
Приазовский государственный технический университет
Кафедра автоматизации и компьютеризации
КУРСОВОЙ ПРОЕКТ
По дисциплине: «Численные методы»
Тема: «Реализация алгоритмов вычислительной математики с разработкой соответственного программного обеспечения для ЭВМ»
Выполнил
Ст. гр И-16-МА
Вариант 16
Проверила
Кобыш Е.И.
Мариуполь 2016
Задание №1. Бинарное дерево.
Введение
Бинарное дерево — иерархическая структура данных, в которой каждый узел имеет не более двух потомков (детей). Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками.
Для практических целей обычно используют два подвида бинарных деревьев — двоичное дерево поиска и двоичная куча.
Существует следующее рекурсивное определение двоичного дерева:
<дерево> ::= ( <данные> <дерево> <дерево> ) | nil .
То есть двоичное дерево либо является пустым, либо состоит из данных и двух поддеревьев (каждое из которых может быть пустым). Очевидным, но важным для понимания фактом является то, что каждое поддерево в свою очередь тоже является деревом. Если у некоторого узла оба поддерева пустые, то он называется листовым узлом (листовой вершиной) или терминальным элементом.
Уровень корня дерева всегда равен нулю, а уровень всех его потомков определяется удаленностью от него.
Постановка задачи
В исходном задании курсового проекта дано бинарное дерево следующего вида:
[pic 1]
Рис.1 – Полное двоичное дерево
Корнем дерева является узел А. Узлы B, C, D, E, F, G являются узлами ветвления. Узлы H, I, J, K, L, M, N, O – листья дерева. Корень и каждый узел ветвления имеют не больше двух наследников (правый и левый наследник), которым являются родителями. Листья не имеют наследников; корень не имеет родителя.
Исходное бинарное дерево имеет 4 уровня: 0, 1, 2, 3.
Обозначим уровень символом , а количество вершин , тогда для бинарного дерева будет справедливо равенство , т. е. количество вершин на k-ом уровне не может иметь значение большее, чем степень двойки этого уровня.[pic 2][pic 3][pic 4]
Количество элементов для данного дерева:
[pic 5]
Каждый элемент дерева имеет свой ключ, определяющий его место в дереве и связанное значение. Необходимо реализовать алгоритм вывода данных, содержащихся в этом дереве, уровень-за-уровнем, начиная с корня.
Математическая постановка задачи
Для обхода дерева по горизонтали с корня, необходимо представить таблицу данных для этого случая обхода.
[pic 6]
A | B | C | D | E | F | G | H | I | J | K | L | M | N | O |
k=0 | k=1 | k=2 | k=3 |
Математически, задача сводится к сортировке методом дерева. В каждом узле дерева будут находиться связанные строковые данные, ключ узла (соответствующий порядковому номеру буквы в алфавите). Параметром сортировки строковых данных и сопоставления их с ключом будет являться длина введенной пользователем строки, получаемая функцией str.len().
Входные и выходные данные, их структура и представление в ЭВМ
Пользователь вводит последовательно 15 строк символьной информации, после чего происходит считывание количества символов в строке. По этому критерию осуществляется сортировка методом двоичного дерева поиска. Осуществляется последовательный вывод имени ячейки (узла дерева A..O) и соответствующего ей поля символьной информации. В программе реализован алгоритм бинарного дерева поиска и бинарной кучи.
Блок-схема алгоритма решения задачи
[pic 7]
Рис.2 – Блок-схема работы двоичного дерева поиска
Листинг программы
#include
#include
...