Разработка шаблона класса для работы с двоичными деревьями

ТИТУЛЬНИК 

Оглавление

 

 

 

Введение

 

В последнее время значительно возрос объём и оборот информации во всех сферах жизнедеятельности человека. И процесс накопления, обработки и использования знаний постоянно ускоряется. В связи с этим возникает необходимость использования средств, позволяющих эффективно хранить, обрабатывать и распределять накопленные данные.

Компьютерный  учет имеет свои особенности и  радикально отличается от обычного. Компьютер  не только облегчает учет, сокращая время, требующееся на оформление и  обобщение накопленных данных.

Целью данного курсового проекта является разработка шаблона класса для работы с двоичными деревьями.

Для разработки программы была выбрана среда Turbo C++ фирмы Borland.

 

1. Выбор технологии, языка и среды программирования

 

Вначале разработки нового проекта перед каждым программистом  стоит непростая задача — выбор системы программирования. От ее успешного решения зависит то, насколько просто и быстро можно будет реализовать поставленную задачу и насколько эффективным получится конечный результат. Более того, неудачный выбор системы программирования может поставить под сомнение возможность завершения проекта из-за несоответствия возможностей системы программирования и требований к решаемой задаче.

На сегодняшний  день на рынке существует много различных  систем программирования от разных производителей, которые конкурируют между собой. Наиболее крупные из производителей — это Microsoft и Borland. При выборе системы программирования в данной работе был выбран продукт Turbo C++ фирмы Borland.

 

2. Анализ и уточнение требований к программному продукту

1. Анализ процесса обработки информации и выбор структур данных для ее хранения

 

Для работы с  одномерными массивами был разработан шаблонный класс BinTree и вспомогательный класс TreeNode, представляющий собой узлы дерева:

 

template <class T> class TreeNode

{

    public:

    TreeNode  *_lchild;

    TreeNode  *_rchild;

    T 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;

}

2. Выбор методов и разработка основных алгоритмов решения задачи

 

Для реализации одномерного массива был разработан шаблонный класс, позволяющий работать с двоичными деревьями:

1. Добавлять элементы;
2. Удалять элементы и минимальные элементы;
3. Находить элементы и минимальные улементы;
4. Выводить элементы на экран;

 

 

3. Проектирование интерфейса пользователя

1. Разработка форм ввода-вывода информации

 

При запуске  программы на экране появляется меню для работы с двоичным деревом (рисунок 1.).

Рисунок 1. Меню программы

 

 

1. Построение классов предметной области

 

1. Уточнение структуры классов предметной области и разработка алгоритмов методов

 

Структура класса TreeNode представлена ниже.

template <class T> class TreeNode

{

    public:

    TreeNode  *_lchild;

    TreeNode  *_rchild;

    T val;

    TreeNode(T);

    virtual ~TreeNode(void);

};

Данный класс  содержит указатели на правое и левое  поддерево (_lchild и _rchild), элемент val, содержащий данные, конструктор и деструктор для создания и удаления узла.

Структура класса BinTtree представлена ниже.

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);

};

Данный класс  содержит указатель на корень дерева (root).

Метод isEmpty используется для того, чтобы узнать, пусто ли дерево.

Конструктор BinTree и деструктор ~BinTree служат для создания и удаления дерева.

Методы find и findMin служат для поиска заданного элемента и минимального элемента в дереве.

Метод inorder служит для вывода элементов дерева.

Метод insert служит для вставки элемента.

Методы remove и removeMin служит для удаления заданного элемента и минимального элемента из дерева.

 

 

4. Выбор стратегии тестирования и разработка тестов

 

Для тестирования написанного класса была написана программа, в которой в качестве элементов дереваются целые числа типа int.

Были последовательно  введены 3 числа 12, 13, 5.

После выбора четвертого пункта меню, на экран были выведены числа в порядке возрастания (рис. 2).

 

Рисунок 2. Результаты тестирования

 

В результате тестирования ошибок выявлено не было.

 

 

Заключение

 

Таким образом, в данной работе разработан шаблон класса для работы с двоичными деревьями.

В качестве элементов дерева могут выступать любые типы данных.

В ходе выполнения работы были изучены принципы объектно-ориентированного программирования, создания шаблонов класса, динамические структуры.

 

Список использованных источников

1. Буч, Г. Объектно-ориентированный анализ и проектирование с примерами приложений на С++: пер. с англ./ Г. Буч. – М.: БИНОМ, СПб.: Невский диалект, 1999. – 560 с.
2. Давыдов, В. Г. Технологии программирования С++ : учеб. пособие / В. Г. Давыдов. – СПб.: БХВ-Петербург, 2005. – 672 с.
3. Дейтел, Х. М. Как программировать на С++ : пер. с англ. / Х. М. Дейтел, П. Дж. Дейтел. – М.: Бином-Пресс, 2005. – 1248 с.
4. Кубенский, А. А. Структуры и алгоритмы обработки данных: объектно-ориентированный подход и реализация на С++ : учеб. пособие / А. А. Кубенский. – СПб.: БХВ-Петербург, 2004. – 464 с.
5. Павловская, Т. А. С/C++. Программирование на языке высокого уровня : учебник / Т. А. Павловская. – СПб.: Питер, 2009. – 461 с.
6. Павловская, Т. А. С++. Объектно-ориентированное программирование : практикум / Т. А. Павловская, Ю. А. Щупак. – СПб.: Питер, 2004. – 265 с.
7. Страуструп, Б. Язык программирования С++ : пер. с англ. / Б. Страуструп. – СПб.; М.: Невский диалект, БИНОМ, 1999. – 991 с.  
8. Шилдт, Г. Искусство программирования на С++ / Г. Шилдт. – СПб.: БХВ-Петербург, 2005. – 496 с.

 

 

Приложение А. Техническое задание

 

Создать шаблон класса для работы с двоичными деревьями. Предусмотреть возможность добавления элемента в дерево, удаление элемента, вывод элементов в дереве, поиск элемента, поиск и удаление минимального элемента.

Написать программу, использующую созданный шаблон для создания дерева.

 

 

Приложение Б. Руководство пользователя

 

Для работы с  предметным указателем необходимо запустить  на выполнении программу demoarr.exe.

Для работы с  созданным классом, необходимо объявить переменную необходимого типа:

DynArray<int, 1, 3> A;

DynArray<int, 1, 3> B;

DynArray<int, 1, 3> C;

DynArray<double, 1, 3> F;

Для вывода массива  можно использовать стандартные  потоки: