8 МИНИМАЛЬНЫЕ  ТРЕБОВАНИЯ ПРОГРАММЫ 

     Данная  программа была проверена на работоспособность  на компьютере со следующими параметрами: Intel Pentium I 150 MHz, 16 Mb RAM, MS DOS 7.0. Во время работы не было замечено никаких признаков нехватки ресурсов.

     Автор не сомневается, что данная программа  будет работоспособна и на компьютере с более низкими параметрами, а именно:

     а) процессор 386;

     б) объём RAM 4Mb;

     в) MS DOS 6.0;

     г) видеоадаптер 512Kb.

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

 

  выводы 

     Результатом проведенной работы является ПП под  названием ”WBT”. Программа демонстрирует  добавление, удаление и поиск в двоичном  дереве.

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

      Описанная структура данных в программе может заинтересовать школьников старших классов и студентов первого курса соответственной специальности.

      WBT прост в использовании и содержит достаточное количество подсказок, таким образом, даже неопытный пользователь сможет в нём легко разобраться.

      Автор планирует в дальнейшем усовершенствовать  данный ПП путём расширения возможностей программы:

      а) кроме демонстраций работы предоставить пользователю некий тест своих знаний;

     б) демонстрация других, не мене интересных структур данных. 

 

Список  литературы 

1. Д. Кнут Искусство  программирования, том 1. Основные алгоритмы, 3-е изд.: Пер. С англ. – М. : Издательский дом «Вильямс», 2001. – 720 с. : ил. – Парал. тит. англ.
2. Ричард Хэзфилд, Лоуренс Кирби и др. Искусство программирования на С. Фундаментальные алгоритмы, структуры данных и примеры приложений. Энциклопедия программиста: Пер. с англ./Ричард Хэзфилд, Лоуренс Кирби и др. – К.: Издательство «ДиаСофт», 2001. – 736 с.
3. Д. Кнут Искусство программирования, том 3. Основные алгоритмы, 3-е изд.: Пер. С англ. – М. : Издательский дом «Вильямс», 2001. – 720 с. : ил. – Парал. тит. англ.

 
 

 

  Приложение А

  ТЕХНИЧЕСКОЕ ЗАДАНИЕ 

     А.1 Общие сведения 

     Полное  название проектируемой программы: «Работа с двоичными деревьями». Ее условное обозначение «WBT».

     Программа проектируется студентом 2-го курса Донецкого государственного института искусственного интеллекта (ДГИИИ), факультета СКИТ, группы ПО-01б Ружицким Андреем Владиславовичем в качестве курсового проекта для кафедры программного обеспечения интеллектуальных систем (ПОИС) ДГИИИ.

     Программа проектируется на основании задания  на курсовой проект от 24.09.02, выданного  кафедрой ПОИС.

     Плановый  срок начала работы по созданию программы 24 сентября 2002г., срок окончания 26 декабря 2002г.

     А.2 Назначение и цели создания программы «WBT»

 

     Основная  функция программы «WBT» заключается в демонстрации принципа работы с двоичными деревьями. Данная программа должна будет представлять собой справочную систему, позволяющую ознакомиться с теоретическими сведениями о работе с двоичными деревьями.

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

      А.3 Требования к работе

     А.3.1 Требования к программному продукту

 

           В программе должно быть реализована следующая работа:

1. Определить и обосновать вид структур данных.
2. Решить задачу отображения выбранной структуры в памяти ЭВМ:

а) как данные расположены относительно друг друга;

б) какие данные хранятся в памяти;

в) какие данные будут содержаться в файлах, и как файлы устроены;

3. При составлении алгоритма определить операции (действия), которые, преимущественно, выполняются над данными в решаемой задачи:

а) доступ к элементу для использования  или изменения данных;

б) включение или добавление нового элемента;

в) исключение/удаление некоторого существующего  элемента;

г) упорядочивание одним из методов  сортировки;

д) ввод/вывод данных.

4. Особое внимание уделить процедурам сортировки и поиска, их вычислительной сложности и производительности.

 

      A.3.2 Требования к программе в целом 

      В целом к программе предъявляются  следующие требования: 

1. удобный  графический интерфейс;
2. справочная система;
3. удобное меню;
4. хранение информации на внешнем источнике данных;
5. обеспечивать удобный ввод данных.

 

      A.3.3 Требования к задачам и функциям, выполняемым программой 

      К задачам и функциям, выполняемых  “WBT” предъявляются следующие  требования:

1. обоснованный выбор вида структур данных;
2. реализация всех необходимых операций со структурами данных;
3. разработка алгоритма поиска;

 

     A.3.5 Требование к техническому обеспечению 

           К техническому обеспечению  предъявляются следующие требования:

а) IBM PC совместимый компьютер;

б) программный  продукт со всеми ресурсными файлами;

в) монитора VGA или лучше;

г) операционная система MS DOS или Windows. 

     А.4 Календарный план выполнения курсовой работы 

      Календарный план представлен в таблице А.1. 

Таблица А.1 –  Стадии разработки программы

Приложение  Б

РУКОВОДСТВО ПОЛЬЗОВАТЕЛЯ 

     Б.1 Общие сведения 

      Данный  ПП предназначен для предоставления пользователю демонстрации работы с БД и предоставления справочной информации о данной структуре.

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

     Интерфейс программы состоит из постоянной области подсказки и области отображения дерева (см. Приложение В рис В.1), а также появляющихся нескольких полей для ввода данных.

      Для запуска программы требуется  запустить файл Install.exe с поставляемой дискеты и, не меняя директории D:\Temp, извлечь файлы. Для повторного запуска программы следует запустить файл WBT.exe из директории D:\Temp. 

     Б.2 Ввод входных данных 

     Ввод  данных производится только с клавиатуры (нет смысла формировать файлы и считывать из них данные).  

     Б.3 Осуществление удаления, добавления и поиска данных 

          Удаление, добавление и поиск данных осуществляется посредством  нажатия определённых клавиш. Вводить можно только целые числа. Кроме того, стоит ограничитель ввода в 2 знака для избежания неправильной прорисовки БД. 

     Б.4 Использование справки и выход из программы 

     Программ  содержит три вида справочной информации: короткая подсказка о работе с программой, дополнительные сведения, вызываемые клавишей F1 и теоретические сведения о двоичных деревьях поиска (см. Приложение В рис В.2), вызываемые клавишей F2.

     Для выхода из программы нажмите кнопку F10. 
 
 
 
 
 
 

 

Приложение  В

ЭКРАННЫЕ  ФОРМЫ 
 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Рисунок В.1 – Интерфейс программы 
 

 

     Рисунок В.2 – Теоретические сведения

Приложение  Г

ЛИСТИНГ ПРОГРАММЫ

#include <conio.h>

#include <io.h>

#include <assert.h>

#include <limits.h>

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#include <graphics.h>

#include <fcntl.h>

#include <sys/stat.h>

#include <dos.h>

#include <string.h>

#include <alive\tr.h>

#include <alive\video2.h>

#include <alive\vfx.h>

#include <alive\winfont.h> 

int fp,flag;

/* A binary tree node. */

struct bin_node {

  int data;

  struct bin_node *left;

  struct bin_node *right;

}; 

/* A binary tree. */

struct bin_tree {

  struct bin_node *root;

  int count;

}; 

/* Creates and returns a new binary tree.  Returns a null pointer if a

   memory allocation error occurs. */

struct bin_tree *bin_create(void)

{

  struct bin_tree *tree = malloc(sizeof *tree);

  if (tree == NULL)

    return NULL;

  tree->root = NULL;

  tree->count = 0;

  return tree;

} 

/* Searches TREE for matching ITEM.  Returns 1 if found, 0

   otherwise. */

int bin_search(const struct bin_tree *tree, int item)

{

  const struct bin_node *node; 

  assert(tree != NULL);

  node = tree->root;

  for (;;) {

    if (node == NULL)

      return 0;

    else if (item == node->data)

       {

         if(flag) fp = item;

         return 1;

       }

    else if (item > node->data)

      node = node->right;

    else

      node = node->left;

  }

} 

/* Inserts ITEM into TREE.  Returns 1 if the item was inserted, 2 if

   an identical item already existed in TREE, or 0 if a memory

   allocation error occurred. */