Автор: Пользователь скрыл имя, 20 Марта 2012 в 08:37, курсовая работа
Компьютерный учет имеет свои особенности и радикально отличается от обычного. Компьютер не только облегчает учет, сокращая время, требующееся на оформление и обобщение накопленных данных.
Целью данного курсового проекта является разработка шаблона класса для работы с двоичными деревьями.
Для разработки программы была выбрана среда Turbo C++ фирмы Borland.
Введение
1. Выбор технологии, языка и среды программирования
2. Анализ и уточнение требований к программному продукту
2.1. Анализ процесса обработки информации и выбор структур данных для ее хранения
2.2. Выбор методов и разработка основных алгоритмов решения задачи
3. Проектирование интерфейса пользователя
3.1. Разработка форм ввода-вывода информации
1. Построение классов предметной области
1.1. Уточнение структуры классов предметной области и разработка алгоритмов методов
4. Выбор стратегии тестирования и разработка тестов
Заключение
Список использованных источников
2
Создать шаблон класса для работы с двоичными деревьями. Предусмотреть возможность добавления элемента в дерево, удаление элемента, вывод элементов в дереве, поиск элемента, поиск и удаление минимального элемента.
Написать программу, использующую созданный шаблон для создания дерева.
2
Для работы с предметным указателем необходимо запустить на выполнении программу demoarr.exe.
Для работы с созданным классом, необходимо объявить переменную необходимого типа:
DynArray<int, 1, 3> A;
DynArray<int, 1, 3> B;
DynArray<int, 1, 3> C;
DynArray<double, 1, 3> F;
Для вывода массива можно использовать стандартные потоки:
cout << A;
Для сложения и вычитания массивов можно использовать следующую запись:
C=A+B
C=A-B
Для умножения и деления массива на число можно использовать следующую запись:
B=A*5;
C=B/18;
2
Файл BinTree.h
template <class T> class TreeNode
{
public:
TreeNode *_lchild;
TreeNode *_rchild;
int val;
TreeNode(T);
virtual ~TreeNode(void);
};
template<class T> TreeNode<T>::TreeNode(int v) :
val(v), _lchild(NULL), _rchild (NULL)
{
}
template<class T> TreeNode<T>::~TreeNode(void)
{
if (_lchild) delete _lchild;
if (_rchild) delete _rchild;
}
template<class T> class BinTree
{
private:
TreeNode<T> *root;
TreeNode<T> *_findMin(TreeNode<T> *);
void _remove(T, TreeNode<T> * &);
void _inorder(TreeNode<T> *, int);
public:
BinTree (void);
~BinTree (void);
int isEmpty (void);
T find(T);
T findMin(void);
void inorder (int);
void insert(T);
void remove(T);
T removeMin (void);
};
template<class T> BinTree<T>::BinTree() :
root (NULL)
{
}
template<class T> int BinTree<T>::isEmpty (void)
{
return (root == NULL);
}
template<class T> BinTree<T>::~BinTree (void)
{
if (root) delete root;
}
template<class T> T BinTree<T>::find (T val)
{
TreeNode<T> *n = root;
while (n)
{
int result = val - n->val;
if (result < 0)
n = n->_lchild;
else if (result > 0)
n = n->_rchild;
else
return n->val;
}
return NULL;
}
template<class T> T BinTree<T>::findMin (void)
{
TreeNode<T> *n = _findMin (root);
return (n ? n->val : NULL);
}
template<class T>
TreeNode<T> *BinTree<T>::_findMin (TreeNode<T> *n)
{
if (n == NULL)
return NULL;
while (n->_lchild)
n = n->_lchild;
return n;
}
template<class T> void BinTree<T>::inorder (int l)
{
_inorder(root, l);
}
template<class T>
void BinTree<T>::_inorder (TreeNode<T> *n, int l)
{
if (n == NULL) return;
_inorder(n->_lchild, l);
cout << n->val << endl;
_inorder(n->_rchild, l + 1);
}
template<class T> void BinTree<T>::insert(T val)
{
if (root == NULL) {
root = new TreeNode<T>(val);
return;
} else {
int result;
TreeNode<T> *p, *n = root;
while (n) {
p = n;
result = val - n->val;
if (result < 0)
n = p->_lchild;
else if (result > 0)
n = p->_rchild;
else
return;
}
if (result < 0)
p->_lchild = new TreeNode<T>(val);
else
p->_rchild = new TreeNode<T>(val);
}
}
template<class T> void BinTree<T>::remove(T val)
{
_remove(val, root);
}
template<class T>
void BinTree<T>::_remove(T val, TreeNode<T> * &n)
{
if (n == NULL) return;
int result = val - n->val;
if (result < 0)
_remove(val, n->_lchild);
else if (result > 0)
_remove (val, n->_rchild);
else
{
if (n->_lchild == NULL)
{
TreeNode<T> *old = n;
n = old->_rchild;
delete old;
}
else
if (n->_rchild == NULL)
{
TreeNode<T> *old = n;
n = old->_lchild;
delete old;
}
else
{
TreeNode<T> *m = _findMin(n->_rchild);
n->val = m->val;
_remove(m->val, n->_rchild);
}
}
}
template<class T> T BinTree<T>::removeMin (void)
{
T v = findMin();
remove (v);
return v;
}
Файл DemoArr.cpp
#include <iostream.h>
#include <conio.h>
#include "bintree.h"
BinTree<int> st;
int choice, El;
main()
{
choice = 0;
while (choice !=5)
{
clrscr();
cout << "1. Добавить элемент" << endl;
cout << "2. Удалить элемент" << endl;
cout << "3. Найти элемент" << endl;
cout << "4. Печать элементов" << endl;
cout << "5. Выход" << endl;
cin >> choice;
switch (choice)
{
case 1:
{
cout << "Введите элемент: " << endl;
cin >> El;
st.insert(El);
break;
}
case 2:
{
cout << "Введите элемент: " << endl;
cin >> El;
st.remove(El);
break;
}
case 3:
{
cout << "Введите элемент: " << endl;
cin >> El;
if (El == st.find(El))
cout << "Элемент найден" << endl;
else
cout << "Элемент не найден" << endl;
while (!kbhit()) {;}
break;
}
case 4:
{
st.inorder(0);
while (!kbhit()) {;}
break;
}
}
}
}
2
Информация о работе Работа со структурами данных: программирование бинарных деревьев на языке C /C++