Описание лабораторной работы
Цель работы
Цель работы — Изучение нелинейных структур данных. Исследование особенностей работы с поисковыми бинарными деревьями средствами языка программирования С/С++. Приобретение практических навыков по разработке и откладке программ, использующих древовидные структуры данных.
Индивидуальное задание
Вариант №8. Написать программу, содержащую функции создания дерева, обхода дерева, добавления элемента в дерево отображения структуры, а также функцию, вычисляет среднее арифметическое значение всех элементов непустого дерева по одному из полей таблицы, которое имеет числовое значение.
Теоретические сведения
Нелинейные структуры предназначены для отображения связей подчинённости элементов данных. Примером нелинейных структур являются иерархарические древовидные структуры. Для представления данных наибольшее распространение получили бинарные деревья.
Бинарным деревом называют динамическую структуру данных, состоящую из узлов, каждый из которых содержит, кроме данных, не более двух указателей на различные бинарные деревья (на правое и левое поддеревья). Узел дерева представляют в виде структуры, содержащей как минимум три поля:
struct tree {
int data; // целочисленные значения (поле данных)
struct tree *left; // указатель на левое поддерево
struct tree *right; // указатель на правое поддерево
}
Здесь данные, содержащиеся в узле, представлены целочисленным значением. Указатели на правое и левое поддеревья могут содержать адреса узлов, имеющих аналогичные поля, с которых начинаются, соответственно, левое и правое поддеревья. Иногда узлы дерева называют вершинами.
На каждый узел в бинарном дереве имеется только одна ссылка. Узел, не имеющий поддеревья, называют листом. Исходящие узлы называются предками, входящие – потомками. Узел дерева, который не имеет предка, называются корнем. Высота дерева определяется количеством уровней, на которых располагаются его узлы.
2. Выполнение лабораторной работы
Структурная схема алгоритма работы программы
Структурная схема алгоритма решения задачи представлена на рис. 2.1
Рис. 2.1 — Структурная схема алгоритма (функция main).
Продолжение Рис. 2.1
Рис. 2.2 — Структурная схема алгоритма (функция node* addtree).
Рис. 2.3 — Структурная схема алгоритма (функция listing).
Рис. 2.4 — Структурная схема алгоритма (функция browsing).
Рис. 2.5 — Структурная схема алгоритма (функция input).
Рис. 2.5 — Структурная схема алгоритма (функция menu).
Рис. 2.6 — Структурная схема алгоритма (функция node_count).
Рис. 2.7 — Структурная схема алгоритма (функция read_file).
Рис. 2.8 — Структурная схема алгоритма (функция write_file).
Рис. 2.9 — Структурная схема алгоритма (функция averageSalary).
Текст программы
#include <fstream.h>
#include <stdlib.h>
#include <string.h>
#include <iomanip.h>
#include <conio.h>
const int leng=20;
struct data{
char train[leng];
char start[leng];
char dest[leng];
char t_start[2];
char t_dest[2];
char cost[3];
};
struct node{
data elem;
node *left;
node *right;
};
node* addtree(node *top, const data &newnode);
int menu();
int node_count(node *top, int level, int &n);
void listing(node *top, int gap);
void browsing(node *top);
int write_file(ofstream &file, node *top);
int read_file(char *filename, node *&top);
data input();
int averageSalary(node* top);
int main() {
node *top=0;
char *file_name="E:\\file1.txt";
ofstream fout;
read_file(file_name,top);
while(1){
switch(menu()){
case 1: top=addtree(top,input());
break;
case 2: listing(top,1);
cout<<"press any key."<<endl; cin.get();
break;
case 3:
browsing(top);
cin.get();
break;
case 4: int level;
int n=0;
cout<<"Enter level value"<<endl;
cin>>level; cin.get();
cout<<"nodes: "<<node_count(top,level,n);
cin.get();
break;
case 5: fout.open(file_name);
if(!fout){cout<<"error"<<endl; return 1;}
write_file(fout,top);
cout<<"Data saved";
fout.close();
cin.get();
break;
case 6: cout<<"---------------------------------"<<endl;
cout<<"Srednya stoimost: "
<<averageSalary(top)<<" grn."<<endl;
cout<<"Najmite lubuy klavishy."<<endl; cin.get();
case 7: return 0;
default: cout<<"enter from 1 to 7"<<endl;
cin.get();
break;
}
}
}
node* addtree(node *top,const data& newmode)
{
if(!top){
top=new node;
if(!top)
{
cout<<"Uc4epnaHa naM9tb";
return NULL;
}
top->elem=newmode;
top->left=NULL;
top->right=NULL;
}
else
{
if(strcmp(top->elem.train,newmode.train)>0)
top->left=addtree(top->left,newmode);
else
top->right=addtree(top->right,newmode);
}
return top;
}
void listing(node *top, int gap)
{
if (top){
gap+=3;
listing(top->right,gap);
cout<<setw(gap)<<'*'<<top->elem.train<<endl;
listing(top->left,gap);
}
return;
}
void browsing(node *top)
{
if(top){
cout<<top->elem.train<<endl;
cout<<top->elem.start<<endl;
cout<<top->elem.dest<<endl;
cout<<top->elem.t_start<<endl;
cout<<top->elem.t_dest<<endl;
cout<<top->elem.cost<<endl;
browsing(top->left);
browsing(top->right);
}
return;
}
data input()
{
data a;
cout<<"Train number: "; cin>>a.train; a.train[3]='\0';
cout<<"Start station: "; cin>>a.start; a.start[leng]='0';
cout<<"Destination station: "; cin>>a.dest; a.dest[leng]='\0';
cout<<"Start time: "; cin>>a.t_start;a.t_start[3]='\0';
cout<<"Finish time"; cin>>a.t_dest;a.t_dest[3]='\0';
cout<<"Cost: "; cin>>a.cost;a.cost[3]='\0';
return a;
}
int menu()
{
char buf[10]; int item;
do{
clrscr(); cout<<endl;
cout<<"1 - Add elem to tree"<<endl;
cout<<"2 - Show tree struct"<<endl;
cout<<"3 - Brose tree"<<endl;
cout<<"4 - Summ of nodes ia tree"<<endl;
cout<<"5 - Write data to file"<<endl;
cout<<"6 - Vy4islenie sredney"<<endl;
cout<<"7- Vyxod"<<endl;
cout<<"Enter num of point menu: "; cin>>buf; cin.get();
item=atoi(buf);
if (!item) {
cout<<"Enter num from 1 to 7"<<endl;
cin.get();
}
}while (!item);
return item;
}
int node_count(node *top,int level,int &n)
{
if((level>=1)&&top){
if (level==1) n++;
n=node_count(top->left,level-1,n);
n=node_count(top->right,level-1,n);
}
return n;
}
int read_file(char* filename, node* &top)
{
ifstream fin(filename, ios::in | ios::nocreate);
if (!fin){
cout<<"Can not open file"<<endl;
return 1;
}
data a;
top=0;
while(fin.getline(a.train,leng))
{
fin.getline(a.start,leng);
fin.getline(a.dest,leng);
fin.getline(a.t_start,2);
fin.getline(a.t_dest,2);
fin.getline(a.cost,3);
top=addtree(top,a);
}
fin.close();
return 0;
}
int write_file(ofstream &file, node* top)
{
if(top){
file<<top->elem.train<<endl;
file<<top->elem.start<<endl;
file<<top->elem.dest<<endl;
file<<top->elem.t_start<<endl;
file<<top->elem.t_dest<<endl;
file<<top->elem.cost<<endl;
write_file(file,top->left);
write_file(file,top->right);
}
return 0;
}
int averageSalary(node* top)
{ int n=0;
float averag=0;
float cost=0;
node *temp1=top;
if (temp1)
{ //если узел существует, то
//запись корня поддерева
n=1;
cost=atoi(temp1->elem.cost);
averag=cost;
while(temp1)
{
temp1=temp1->left;
n++;
cost=atoi(temp1->elem.cost);
averag+=cost; //исследование левого поддерева
}
temp1=top;
while(temp1)
{
temp1=temp1->right;
n++;
cost=atoi(temp1->elem.cost);
averag+=cost; //исследование левого поддерева
}
averag=averag/(n-2);
return averag;
}
else {cout<<"Дерева нет"; return 0;}
}
Таблица переменных
В программе использованы переменные, представленные в таблице 2.1.
Таблица 2.1 — Используемые переменные
| Переменная | Тип | Значение |
| level | Int | Уровень дерева |
| n | Int | Количество вершин дерева |
| item | Int | Номер введенного пункта меню |
| averag | Float | Значение среднего оклада |
Результаты выполнения программы
.
Рис. 2.11 — Изображения окна UserScreen при выполнении программы(Вычисление среднего оклада).
Рис. 2.12 – Изображения окна UserScreen при выполнении программы (Добавление элемента).
Рис. 2.14 – Изображения окна UserScreen при выполнении программы (Отображение дерева).
Рис. 2.15 – Изображения окна UserScreen при выполнении программы (Подсчет ветвей на заданном уровне). 
Рис. 2.16 – Изображения окна UserScreen при выполнении программы(Просмотр структур дерева).
Выводы
Данная программа написана на языке программирования С++. Из динамических структур в программах чаще всего используются различные линейные списки, стеки, очереди и деревья. Была осуществлена работа с бинарными деревьями. Наиболее распространённым условием организации бинарных деревьев является упорядоченность. Элементы дерева в этом случае снабжаются ключевыми признаками. Если дерево организовано таким образом, что для каждого узла все ключи левого поддерева меньше ключа этого узла, а все ключи правого поддерева больше ключа этого узла, оно является упорядоченным и называется деревом поиска.
В результате данной программы был вычислен и выведен на экран значение средней стоимости проезда.