Контрольная по "Программированию бинарных деревьев на языке СС++"

2       Разработка алгоритма задачи

2.1 Описание данных, используемых для решения задачи

В данной задаче использовались следующие данные:  

исходные (входные) данные:

struct traine {                    //структура - дерево

    unsigned long time;            //время отправления в секундах

    unsigned short number;        //номер поезда

    char *station;                //имя станции

    traine *left,*right;};        //указатели на левую и правую ветку дерева

выходные результаты решения: 

•              производит вывод всего дерева;

•              вводит номер поезда и выводит все данные об этом поезде;

•              вводит название станции назначения и выводит данные о всех поездах, следующих до этой станции.

2.2 Описание схемы программы

Схема алгоритма отображает последовательность операций в программе.

Произведено выделение основных этапов в виде подпрограмм, выполняющих сле­дующие действия:             

      ввод исходных данных;

      вывод полученных результатов (поиск удовлетворяющей заявки, вывод всего списка) на экран .

Все подпрограммы выполнены в виде процедур. Основные процедуры и про­грамма выполнены на листе.  При этом описание функционального назначения блоков алгоритма приведено в комментариях.

3 Кодирование программы

3.1 Описание структуры разрабатываемого пакета

Программа курсовой работы разработана  в среде визуального  программирования  С++   и  состоит из исполняемого файла с расширением .cpp.

Программа выполнена на основе структурного программирования(в виде бинарного дерева)  и содержит следующие процедуры и функции:

struct traine {                    //структура - дерево

void show_all(traine *temp){    //функция вывода всего дерева - рекурсивный обход

void show_number(traine *temp, unsigned short number){ //поиск элемента с нужным номером, с учётом отсортированности дерева

void show_station(traine *temp, char st[50],bool &f){ //переменная f нужна для определения, был ли найден хотя бы 1 поезд, т.к. обход производится «втупую», т.к. дерево сортировано не по имени станции

int main() {    //главная функция

4 Тестирование программы

4.1 Внешний вид программы

Запуск программы производится из среды C++ нажатием клавиш F5. При запуске программа сама просит ввести все необходимые данные и сохраняет результаты в текстовый файл.

Основное окно программы имеет вид:

Рис. 1 – Основное окно программы

это диалоговое окно-меню, где выбирается необходимая операция;

При выборе первой операции (ввод данных) программа будет выглядеть следующим образом:

Рис. 2 – Выбор первой операции

При выборе второй операции программа будет выглядеть следующим образом:

Рис. 3 – Выбор второй операции

Рис. 4 – Выбор третьей операции

Рис. 5 – Выбор четвертой операции

Заключение

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

При работе над программой пройдены все этапы создания программных продуктов. Получены навыки в описании бинарного дерева, разработке алгоритма программы, составлении текста программы и проведении тестирования программы. Использована среда программирования C++.

Список используемой литературы:

1. Б.Керниган, Д.Ритчи, А.Фьюер. Язык программирования Си. Задачи по языку Си. М.: Финансы и статистика, 2008.
2. М.Уэйт, С.Прата, Д.Мартин. Язык Си. Руководство для начинающих. - М.: Мир, 1998.
3. М.Болски. Язык программирования Си. Справочник. - М.: Радио и связь, 1998.
4. Л.Хэнкок, М.Кригер. Введение в программирование на языке Си. - М.: Радио и связь, 1990.
5. Р.Берри, Б.Микинз. Язык Си. Введение для программистов. - М.: Финансы и статистика, 1988.

6.       S.Dewhurst, K.Stark. Programming in C++. - Prentice Hall, 1989.

7.       M.Ellis, B.Stroustrup. The annotated C++ Reference Manual. - Addison-Wesley, 19

8.       ТО 04-2008

Приложение А

Листинг программы:

#include <iostream.h>

#include <conio.h>

#include <stdlib.h>

struct traine {                    //структура - дерево

    unsigned long time;            //время отправления в секундах

    unsigned short number;        //номер поезда

    char *station;                //имя станции

    traine *left,*right;};        //указатели на левую и правую ветку дерева

traine* add(traine *beg, unsigned short number, unsigned long time, char station[50])    //функция добавления элемента в дерево

{

if (!beg) {                        //если дерево пустое

traine *temp=new traine;

temp->number=number;

temp->time=time;

temp->station = new char[];

temp->station=station;

temp->left=0;

temp->right=0;

return temp;

    }                //если дерево не пустое, начинается рекурсивный вход в него

    else if ((number)>(beg->number)) {    //бОльшие номера идут в правое поддерево

beg->right=add(beg->right,number, time, station);

return beg;

    }

else {        //меньшие номера идут в левое поддерево

beg->left=add(beg->left,number, time, station);

return beg;}

}

void show_all(traine *temp){    //функция вывода всего дерева - рекурсивный обход слева направо

unsigned long d,h,m,s,t;

if (temp){

show_all(temp->left);

t=temp->time;s=t%60;t=(t-s)/60;m=t%60;t=(t-m)/60;h=t%24;d=(t-h)/24;//разложение времени на дни, часы, минуты и секунды

cout << “Train number:” << temp->number << endl << “Start time(d/h/m/s):” << d << “:” << h << “:” << m << “:” << s << endl << “Station:” << temp->station << endl;

show_all(temp->right);}

}

void show_number(traine *temp, unsigned short number){ //поиск элемента с нужным номером, с учётом отсортированности дерева

unsigned long d,h,m,s,t;

if (temp){

if (temp->number<number) {show_number(temp->right,number);}

else if (temp->number>number) {show_number(temp->left,number);}

else{

t=temp->time;s=t%60;t=(t-s)/60;m=t%60;t=(t-m)/60;h=t%24;d=(t-h)/24;

cout << “Train number:” << temp->number << endl << “Start time(d/h/m/s):” << d << “:” << h << “:” << m << “:” << s << endl << “Station:” << temp->station << endl;

return;}

    }

cout << “There is no such records\n”;}

void show_station(traine *temp, char st[50],bool &f){ //переменная f нужна для определения, был ли найден хотя бы 1 поезд, т.к. обход производится «втупую», т.к. дерево сортировано не по имени станции

if (temp){

if (st == (temp->station)) //если найден подходящий поезд

        {

f=1;

unsigned long d,h,m,s,t,f;

t=temp->time;s=t%60;t=(t-s)/60;m=t%60;t=(t-m)/60;h=t%24;d=(t-h)/24;

cout << “Train number:” << temp->number << endl << “Start time(d/h/m/s):” << d << “:” << h << “:” << m << “:” << s << f<<endl << “Station:” << temp->station << endl << endl;

        }

show_station(temp->right,st,f); //просмотр правого поддерева

show_station(temp->left,st,f);    //просмотр левого поддерева

    }

}

int main() {    //главная функция

    char k;        //временная переменная для чтения 1 символа для выбора пунктов меню

    bool f;        //переменная для использования с функцией поиска по имени станции

    char strtmp[80];    //временная переменная для чтения с клавиатуры

    traine *list=0;    //дерево, изначально являющееся пустым

    unsigned short d,h,m,s;    //переменные для разложения времени на дни, часы, минуты и секунды

    unsigned short number;    //временный номер

    char station[30];    //временная станция

do{//главный цикл меню

cout << “Enter your choice:\n[1] Add new record\n[2] View all records\n[3] View a specific train number\n[4] View all trains aimed to a specified station\n[0] Exit program\n”;

do{

cin >> k;//ввод выбора (а далее всё понятно и так)

if (k==’1’){

do{

cout << “Train number:\n”;

cin >> strtmp;

number=atoi(strtmp);

}while (!(number>0));

do{

cout << “Number of days:\n”;

cin >> strtmp;

d=atoi(strtmp);

cout << “Number of hours:\n”;

cin >> strtmp;

h=atoi(strtmp);

cout << “Number of minutes:\n”;

cin >> strtmp;

m=atoi(strtmp);

cout << “Number of seconds:\n”;

cin >> strtmp;

s=atoi(strtmp);

}while(d==0 && h==0 && m==0 && s==0);

cout << “Station name:\n”;

cin >> station;

list=add(list,number,s+m*60+h*3600+d*86400,station);

    }

else if (k==’2’){

if (list){

show_all(list);}

else {cout << “There is no trains\n”;}}

else if (k==’3’){

cout << “Enter a train number:”;

do{

cin >> strtmp;

number=atoi(strtmp);

}while (!(number>0));

show_number(list,number);}

else if (k==’4’){

cout << “Enter a station name:”;

cin >>station;

f=0;

show_station(list,station,f);

if (!f) {cout << “There is no trains\n”;}

    }

}while (!((k==’4’)||(k==’3’)||(k==’2’)||(k==’1’)||(k==’0’)));

}while (!(k=='0'));

return 1;}