Работа со структурами данных: программирование бинарных деревьев на языке C /C++

ТИТУЛЬНИК

2

Оглавление

Введение

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

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

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

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

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

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

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

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

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

Заключение

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

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

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

Приложение В. Код программы

2

Введение

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

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

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

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

2

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

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

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

2

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

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.2.                       Выбор методов и разработка основных алгоритмов решения задачи

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

1.      Добавлять элементы;

2.      Удалять элементы и минимальные элементы;

3.      Находить элементы и минимальные улементы;

4.      Выводить элементы на экран;

2

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

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

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

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

2

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 служит для удаления заданного элемента и минимального элемента из дерева.

2

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

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

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

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

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

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

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 с.