Программная реализация добавления данных в упорядоченное двоичное дерево
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
?верить текущий элемент: если он не пустой, то просматривается правое поддерево. Далее начинается цикл, в котором с помощью отступа и выводом данных currentdata, элементы будут отображаться на консоли в удобном для просмотра виде. После этого идет просмотр левого поддерева и т.д.
)функция void Clear(struct binar_tree **current): как и в предыдущих двух функциях, очистка дерева начинается с той самой проверки текущего элемента: если он не равен NULL, то очищаются левые и правые поддеревья, удаляется текущий элемент, счетчик count уменьшается на единицу, и, если этот самый счетчик равен нулю, то текущему значению присваивается NULL.
В главной функции программы реализовано меню, в котором пользователь может выбрать любое действие, которое ему необходимо:
) добавление элемента
) просмотр дерева
) очистка дерева
) выход (с помощью функции exit(1)).
Все эти действия реализованы с помощью оператора switch (s), где s - номер выбранного действия (целое число). Если выбранное действие не соответствует ни одному из предложенных, то выводится сообщение об ошибке выбора действия.
Исходный код данной программы представлен в Приложении I.
Экспериментальный раздел
Для того чтобы проверить, работает ли программа правильно, выполнены ли все условия задачи, необходимо провести тестирование. Процесс тестирование разделен на 3 этапа:
1)Проверка в нормальных условиях (программа должна показать правильные результаты для характерных совокупностей данных):
Сначала выбранным действием №2 осуществляется просмотр дерева, чтобы убедиться, пустое оно или нет. Затем действием №1 добавляется первый элемент 70. Он записывается в вершину дерева, затем второй элемент 50, который будет находиться слева от вершины, т.к. 50 меньше, чем 70, и третий элемент 90, который запишется справа от вершины, т.к. он больше 70. И в конце действием №2 просматривается полученное дерево. Результат работы программы представлен на рисунке 5.
Рисунок 5 - Результат работы программы при нормальных условия
2)Проверка в экстремальных условиях (проверка работоспособности программы для граничных значений области изменения входных переменных, реакция программы на нулевые примеры и т.д.):
Если при выборе действия №1 - добавление элемента вводить с клавиатуры вещественные числа или символы, то произойдет сбой работы программы, т.к. тип вводимых данных исключительно целые числа. Если добавить число 0 в корень дерева, то добавленные отрицательные и положительные числа будут добавляться по правилам добавления, которые были описаны выше и никаких сбоев программы не произойдет. Результат работы программы при добавлении нуля и отрицательных чисел представлен на рисунке 6.
Рисунок 6 - Результат работы программы при экстремальных условиях
3)Проверка в исключительных ситуациях (проверяется, что произойдет, если программе придется иметь дело с данными, выходящими за рамки обработки ограниченного набора данных):
Если при выборе действия №1 - добавления элемента вводить с клавиатуры очень большое число, например 10000000000, то в дерево добавляются большие отрицательные числа и работа программы не корректна. Результат работы программы представлен на рисунке 7.
Рисунок 7 - Результат работы программы в исключительных ситуациях
Заключение
В процессе выполнения курсового проекта был изучен теоретический материал о бинарных деревьях и их свойствах, разработан алгоритм добавления элементов в упорядоченное двоичное дерево с использованием динамических структур данных и его программная реализация на языке высоко уровня Си. Также данная программа была протестирована в 3 случаях, которые были описаны в экспериментальном разделе.
Список использованных источников
1) Левитин А.В. Алгоритмы: введение в разработку и анализ. - М.: Издательский дом Вильямс, 2006. - 65 c.
) Ахо А.В., Хопкрофт Д., Ульман Д.Д. Структуры данных и алгоритмы. - М.: Издательский дом Вильямс, 2000. - 92 с.
3) Материалы сайта Программирование на языке C/C++.">, [Электронный ресурс] - www.procpp.ru .
) Материалы сайта Интуит.">, [Электронный ресурс] - .
Приложение I
Листинг программы добавления данных в упорядоченное двоичное дерево:
#include "stdafx.h"
#include "stdlib.h"
#include "conio.h"
#include "locale.h"Add(struct binar_tree **current, int data); //добавлениеShow(struct binar_tree *current, int l); //просмотрClear(struct binar_tree **current); //очисткаbinar_tree
{data, count;_tree *left, *right;
};_tree *root = NULL; //корень дереваcount = 0; //счетчикmain()
{number, s;(LC_ALL, "rus");
{("\tМЕНЮ \n");("1.Добавить элемент \n");("2.Просмотр дерева \n");("3.Очистить дерево \n");("0.Выход \n");("Выбранное действие: ");("%d", &s);(s)
{1:("\nВведите элемент: ");("%d", &number);(&root, number);("\nЭлемент добавлен \n\n");("--------------------------- \n\n");;2:(root!=NULL)
{("\n");(root,0);
}("\nДерево пустое \n\n");("--------------------------- \n\n");;3:(&root);("\nДерево очищено \n\n");("--------------------------- \n\n");;0:(1);:("\nОшибка!!! \n\n");("--------------------------- \n\n");;
}
} while(s != 0);
_getch();
}Add(binar_tree **current, int data)
{(*current != NULL)
{(dataright, data);
(*current)->count++;
}
{
*current = new binar_tree;
(*current)->data = data;
(*current)->left = NULL;
(*current)->right = NULL;
(*current)->count = 1;++;
}
}Show(binar_tree *current, int l)
{(current != NULL)
{(current->right, l+1);(int i=0; ileft, l+1);
}
}Clear(binar_tree **current)
{(*current != NULL)
{(&(*current)->left);(&(*current)-&