毕业设计-数据结构【b】线段树及其应用.doc

东北大学信息科学与工程学院
数据结构课程设计报告

题目 线段树及其应用
课题组长 余灏然

课题组成员 魏嘉 张越
专业名称 计算机科学与技术

班级 计算机1307

指导教师 杨雷

2015 年 1月

课程设计任务书
题目：
线段树及其应用
问题描述：
在实际应用中，常遇到与区间有关的操作，比如统计若干矩形并集的面积，记录一个区间的最大最小值及总量，并在区间的插入、删除和修改中维护这些数据。线段树的定义是利用树形二分结构所建立的一种数据结构，能够高效的完成这些操作。

设计要求：
设计线段树的抽象数据类型及其实现。
（1） 实现线段树的ADT。
（2）实现线段树的简单应用。

指导教师签字：

2014年12月28日

目录
1 课题概述 1
1.1 课题任务 1
1.2 课题原理 1
1.3 相关知识 2
2 需求分析 2
2.1 课题调研 2
2.2 用户需求分析 2
3 方案设计 2
3.1 总体功能设计 2
3.2 数据结构设计 2
3.3 函数原型设计 2
3.4 主算法设计 3
3.5 用户界面设计 3
4 方案实现 4
4.1 开发环境与工具 4
4.2 程序设计关键技术 4
4.3 个人设计实现（按组员分工）
4.3.1余灏然设计实现 4
4.3.2 魏嘉设计实现 9
4.3.3 张越设计实现 15

5 测试与调试 17
5.1 个人测试（按组员分工） 17
5.1.1 余灏然测试 17
5.1.2 魏嘉测试 25
5.1.3 张越测试 27

5.2 组装与系统测试 30
5.3 系统运行 31
6 课题总结 32
6.1 课题评价 32
6.2 团队协作 32
6.3 个人设计小结（按组员分工） 32
6.3.1 余灏然设计小结 32
6.3.2 魏嘉设计小结 32
6.3.3 张越设计小结 33

7 附录A 课题任务分工 34
A-1 课题程序设计分工 34
A-2 课题报告分工 35
附录B 课题设计文档（光盘）
B-1课程设计报告（电子版）
B-2源程序代码（*.H，*.CPP）
B-3工程与可执行文件）
B-4屏幕演示录像文件（可选）
附录C 用户操作手册（可选） 36
C.1 运行环境说明 36
C.2 操作说明 36

1课题概述
1.1 课题任务
在实际应用中，常遇到与区间有关的操作，比如统计若干矩形并集的面积，记录一个区间的最大最小值及总量，并在区间的插入、删除和修改中维护这些数据。线段树的定义是利用树形二分结构所建立的一种数据结构，能够高效的完成这些操作。我们选择利用线段树这种结构来建立一个车票购票系统。

【设计要求】
设计线段树的抽象数据类型及其实现。
（1） 实现线段树的ADT。
（2） 实现线段树的简单应用。
1.2 课题原理
线段树，类似区间树，是一个完全二叉树，它在各个节点保存一条线段（数组中的一段子数组），主要用于高效解决连续区间的动态查询问题，由于二叉结构的特性，它基本能保持每个操作的复杂度为O(lgN)!

流程图如下：
开始

退出
管理功能
购票与查询

删除树
修改站点
重新生成线段树
查询
购票

退出

1.3相关知识
前序遍历树，将树变成链表，用于存储；
Si与Sj用于测试，可删除；
2需求分析
2.1 课题调研
线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。
对于线段树中的每一个非叶子节点[a,b]，它的左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2+1,b]。因此线段树是平衡二叉树，最后的子节点数目为N，即整个线段区间的长度。
2.2 用户需求分析
利用线段树高效快速的运行车票出售系统。
功能需求
（1）输入功能和显示功能
（2）购买车票、查询车票余额
（3）添加、修改、删除站点信息
（4）读取文件功能和保存文件功能
（5）需要用户友好的界面以便用户方便使用

3方案设计
3.1 总体功能设计
线段树
3.2 数据结构设计
前序遍历树，将树变成链表，用于存储。
3.3 函数原型设计
函数原型
功能描述
void TreeToList(Tree T,list<SaveData> &p)
前序遍历树，将树变成链表，用于存储。
void ListToTree(Tree &T,list<SaveData>::iterator &iterP)
链表还原成树
int Loading(Tree &T)
读取数据将数据还原成树
void print(list<staname> &p)
显示乘车顺序
Tree Find(int a, Tree T)
寻找叶子
void BuyTicket(int a,int b,int n,Tree &T)
购票
void Check()
检查数据文件
void welcome()
初始界面显示
void Inquire(Tree T,list<staname> &p)
查询车票数量
void intitle(list<staname> &p)
站号对应站名的处理

3.4主算法设计
线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。
对于线段树中的每一个非叶子节点[a,b]，它的左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2+1,b]。因此线段树是平衡二叉树，最后的子节点数目为N，即整个线段区间的长度。
3.5 用户界面设计
Dos界面

输入后：

4 方案实现
4.1 开发环境与工具
主要编程环境：Microsoft Visual Studio C++6.0
编程工具：C++。

4.2 程序设计关键技术
线段树及其应用：
（1）C#语言的学习和Microsoft Visual Studio 2008的使用方法，因为未学习过此语言，学会使用C#和开发工具是程序设计的关键。
（2）线段树的实现问题，线段树的实现还是相对复杂的，我们从网上，书籍查阅了许多资料，进行了多次debug才完成此部分。
（3）多人程序的融合性问题，由于没怎么接触过多人写程序，每个人写的程序必须能够很好组合。

4.3 个人设计实现（按组员分工）
4.3.1 余灏然设计实现
Main函数
#include"head.h"
#include"save.cpp"
#include"StationName.cpp"
#include"buy.cpp"
#include"check.cpp"
#include"inquire.cpp"
#include"frame.cpp"

void main()
{
list<staname> p;
Tree T;
int i,j,a,b,n,t=0; //t值用于判断第一次"重新生成线段树"时是否执行DelData(T),t=0不执行 t=1执行
Check(); //检查数据文件是否丢失
t=Loading(T); //读取线段树数据
Loading2(p); //读取站名链表数据
welcome();
while(1)
{
system("cls");frame();
gotoxy(25,8);cout<<"1.购票与查询";
gotoxy(25,9);cout<<"2.管理功能";
gotoxy(25,10);cout<<"3.退出";
gotoxy(25,12);cout<<"----请选择功能:";
cin>>i;
system("cls");
if(i==1)
{
while(1)
{
print(p);
cout<<endl<<"1.购票车票 2.查询车余额 3.返回 ---请选择：";
cin>>j;
if(j==1)
{
cout<<"请分别输入出发站、到达站号及购买票数：";
cin>>a>>b>>n;
if(a<b) BuyTicket(a,b,n,T);
if(a>b) BuyTicket2(a,b,n,T);
}
if(j==2) Inquire(T,p);
if(j==3) break;

}
}
if(i==2)
{
while(1)
{
system("cls");
cout<<"请选择(1.重新生成线段树 2.改变站名对应站号 3.删除树并初始化 4.返回 ): ";
cin>>j;
if(j==1)
{
cout<<"请输入线段区间(a,b) [必须符合0<a<b]: ";
cin>>a>>b;
if(t) DelData(T);
CreateTree(T,a,b);SaveTree(T);
t=1;
}
if(j==2) intitle(p);
if(j==3) DelData(T);
if(j==4) break;
}
}
if(i==3) exit(0);
} //while尾

}

save.cpp
#include"head.h"
void TreeToList(Tree T,list<SaveData> &p) //前序遍历树，将树变成链表，用于存储，
{
SaveData a;
if(T!=NULL)
{
a.k=1;
a.Si=T->i; a.Sj=T->j;
a.Snum=T->num; a.Snum2=T->num2;
p.push_back(a);
TreeToList(T->lchild,p);
TreeToList(T->rchild,p);
}
else
{
a.k=0;

// a.Si=-1;a.Sj=-1; //Si与Sj用于测试，可删除

p.push_back(a);

}
}

void SaveTree(Tree T)
{
FILE *fp;
SaveData h;
list<SaveData> p;
list<SaveData>::iterator iterP=p.begin();
TreeToList(T,p);
iterP=p.begin();
fp=fopen("TicketData.dat","wb");
while(1)
{
h.k=iterP->k;h.Si=iterP->Si;h.Sj=iterP->Sj;
h.Snum=iterP->Snum;h.Snum2=iterP->Snum2;
fwrite(&h,sizeof(SaveData),1,fp);
iterP++;
if(iterP==p.end()) break;
}
SaveData t;
t.k=-1; //t->k=-1表链表尾
fwrite(&t,sizeof(SaveData),1,fp);
fclose(fp);
// cout<<"存储成功！"<<endl;
}

void ListToTree(Tree &T,list<SaveData>::iterator &iterP) //链表还原成树
{
if(iterP->k==0) { T=NULL; iterP++;}
else
{
if(!(T=(Btree*)malloc(sizeof(Btree)))) exit(-1);
T->i=iterP->Si; T->j=iterP->Sj;T->num=iterP->Snum; T->num2=iterP->Snum2;
iterP++;
ListToTree(T->lchild,iterP);
ListToTree(T->rchild,iterP);
}
}

int Loading(Tree &T) //读取数据将数据还原成树
{
list<SaveData> p;
list<SaveData>::iterator iterP;
FILE *fp;
SaveData h;
fp=fopen("TicketData.dat","rb");
fread(&h,sizeof(SaveData),1,fp);
if(h.k==-1)
{ cout<<"--------无数据内容。"<<endl; fclose(fp); return 0; }
while(h.k!=-1) // 判断是不是链表尾
{
p.push_back(h);
fread(&h,sizeof(SaveData),1,fp);
}
fclose(fp);
iterP=p.begin();
ListToTree(T,iterP);

// cout<<"数据读取成功，已生成树。"<<endl;

return 1;
}

int DelData(Tree T)
{
DestroyTree(T);
FILE *fp;
fp=fopen("TicketData.dat","wb+"); // 不写入内容，即可清除数据
fclose(fp);
return 1;
}

inquire.cpp
#include"head.h"
Tree Find(int a, Tree T);
void Inquire(Tree T,list<staname> &p) //查询车票数量
{
int i=0;
Tree t;
list<staname>::iterator iterP=p.begin();
cout<<endl<<endl<<endl<<"当前相邻两站间的车票余额："<<endl<<endl;
while(1)
{
t=Find(iterP->k,T);
cout<<iterP->k<<"号站-"<<iterP->name<<" ===> ";
iterP++;
cout<<iterP->k<<"号站-"<<iterP->name <<": ";
cout<<(max - t->num)<<endl;
iterP++;
if(iterP==p.end()) break;
else iterP--;
}
cout<<endl; iterP--;
while(1)
{
cout<<iterP->k<<"号站-"<<iterP->name<<" ===> ";
iterP--;
cout<<iterP->k<<"号站-"<<iterP->name<<": ";
t=Find(iterP->k,T);
cout<<(max - t->num2)<<endl;
iterP--;
if(iterP==p.end()) break;
else iterP++;
}

}

4.3.2 魏嘉设计实现
head.h
#ifndef _HEAD_H
#define _HEAD_H // 运用 #ifndef避免重复定义
#include"iostream"
#include"stdio.h"
#include"windows.h"
#include"conio.h"
#include <list>
using namespace std;
#define max 100 //每站票数的最大上限
typedef struct Node{
int i,j; //分别表示线段树左右节点
int num; //存储数据，表示当前已出售票数
int num2; //返程
struct Node *lchild,*rchild;
}Btree,*Tree;

typedef struct station{
int k; //站点所对应的数字
char name[20];
}staname;

typedef struct save{
int k; //k=1时储存节点信息， k=0时代表空格不存储其他信息,k=-1时表示链表尾 (NULL不知为何不好使=A=)
int Si,Sj;
int Snum;
int Snum2;
}SaveData;

int CreateTree(Tree &T,int a,int b)
{
if(b<a || a<1 || b<1) // b大于a或a,b不大于零时，则提示输入错误
{
cout<<" error !"<<endl;
return NULL;
}

T=(Btree*)malloc(sizeof(Btree));
T->i=a; T->j=b; T->num=-1; T->num2=-1; // 只有树的叶子节点才用于存储数据，其他非叶子节点令其值为-1
if(b-a>1)
{
CreateTree(T->lchild,a,(a+b)/2);
CreateTree(T->rchild,(a+b)/2,b);
}
else
{
T->lchild=NULL;
T->rchild=NULL;
T->num=0; //初始化为0
T->num2=0;
}
return 1;
}

void DestroyTree(Tree &T) //删除时用这个，判断树是否已为空，若不空则执行Destroy(Tree T);
{
int Destroy(Tree T);
if(T->num==-1) { Destroy(T); cout<<"线段树已销毁。"<<endl; } //如果树不为空，则T->num=-1
else cout<<"树已为空，无需销毁。"<<endl;
}
int Destroy(Tree T) //完全销毁线段树
{
if(T==NULL) return 1;
Destroy(T->lchild);
Destroy(T->rchild);
free(T);
return 1;
}

void PreOrder(Tree T) //前序遍历树
{

if(T!=NULL)
{
cout<<T->i<<T->j<<endl;
PreOrder(T->lchild);
PreOrder(T->rchild);
}
else
cout<<"!!"<<endl;
}

void gotoxy(int x,int y) //光标移动 x为列坐标,y为行坐标
{
COORD pos={x,y};
HANDLE hOut=GetStdHandle(STD_OUTPUT_HANDLE);
SetConsoleCursorPosition(hOut,pos);
}

#endif

StationName.cpp
#include"head.h"
#include"string.h"

void intitle(list<staname> &p) //站号对应站名的处理
{
void Loading2(list<staname> &p);
void firstuse();
list<staname>::iterator iterP;
int i,j;
char b[20];
staname h;
FILE *fp;
while(1)
{
system("cls");
iterP=p.begin();
fp=fopen("StationName.dat","rb");
fread(&h,sizeof(staname),1,fp);
while(h.k!=0)
{
cout<<iterP->k<<"号站----"<<iterP->name<<endl;
iterP++;
if(iterP==p.end()) break;
}
fclose(fp);
cout<<endl<<endl<<"1.添加或更改站点(请从1开始按顺序添加) 2.重置清空 3.返回 "<<endl<<"请选择：";
cin>>i;
if(i==1)
{
cout<<"请分别输入站号及站名 (站号误重复)";
cin>>h.k>>h.name;
p.push_back(h);
iterP=p.begin();
fp=fopen("StationName.dat","wb");
while(1)
{
h.k=iterP->k;
strcpy(h.name,iterP->name);
fwrite(&h,sizeof(staname),1,fp);
iterP++;
if(iterP==p.end()) break;
}
h.k=0;
fwrite(&h,sizeof(staname),1,fp);
fclose(fp);
}
if(i==2) { firstuse();p.clear(); Loading2(p);}
if(i==3) break;
}
}

void firstuse() //站名数据文件初始化
{
staname p;
p.k=0;
FILE *fp;
fp=fopen("StationName.dat","wb+");
fwrite(&p,sizeof(staname),1,fp);
fclose(fp);
}

void Loading2(list<staname> &p) //读取站名链表数据
{
staname h;
FILE *fp;
fp=fopen("StationName.dat","rb");
fread(&h,sizeof(staname),1,fp);
while(h.k!=0)
{
p.push_back(h);
fread(&h,sizeof(staname),1,fp);
}
}

buy.cpp
#include"head.h"

void print(list<staname> &p) //显示乘车顺序
{
list<staname>::iterator iterP=p.begin();
int i=1;
cout<<endl<<"乘车区间:"<<endl;
while(i)
{
cout<<iterP->k<<"号站:"<<iterP->name;
iterP++;
if(i==5) {cout<<endl<<endl; i=1;}
if( !( iterP==p.end() ) ) {cout<<"----";}
else break;
i++;
}
cout<<endl<<endl;
}

Tree Find(int a, Tree T) //寻找叶子
{
Tree p;
if(a==T->i && T->num>=0) { return T; }
int m;
m=(T->i+T->j)/2;
if(a<m) p=Find(a,T->lchild);
else p=Find(a,T->rchild);
return p;
}

void BuyTicket(int a,int b,int n,Tree &T) // a<b
{
void SaveTree(Tree T);
Tree Find(int a, Tree T);
int i;
Tree p;
for(i=a;i<b;i++)
{
p=Find(i,T);
if(n > max-p->num ) break;
}
if(i!=b) cout<<"该区间的票数余额不足，无法进行购买。"<<endl;
else
{
for(i=a;i<b;i++)
{
p=Find(i,T);
p->num+=n;
}
SaveTree(T);
cout<<"购票成功！"<<endl;
}
getchar();getchar();
}

void BuyTicket2(int a,int b,int n,Tree &T) // a>b
{
void SaveTree(Tree T);
Tree Find(int a, Tree T);
int i;
Tree p;
for(i=a;i>b;i--)
{
p=Find(i-1,T);
if(n > max-p->num2) break;
}
if(i!=b) cout<<"该区间的票数余额不足，无法进行购买。"<<endl;
else
{
for(i=a;i>b;i--)
{
p=Find(i-1,T);
p->num2+=n;
}
SaveTree(T);
cout<<"购票成功！"<<endl;
}
getchar();getchar();
}

4.3.3 张越设计实现
check.cpp
#include"head.h"

void firstuse();

void Check() //检查数据文件
{
FILE *fp;
SaveData p;
if((fopen("TicketData.dat","rb"))==NULL )
{
cout<<"线段树数据丢失，按回车键将初始化";
getchar();
p.k=-1;
fp=fopen("TicketData.dat","wb+");
fwrite(&p,sizeof(SaveData),1,fp);
fclose(fp);
}
if((fopen("StationName.dat","rb"))==NULL )
{
cout<<"站名数据丢失，按回车键将初始化";
getchar();
firstuse();
}
}

frame.cpp
#include"head.h"

void frame() //边框
{
void gotoxy(int x,int y);
int i;
gotoxy(11,4);cout<<"┏";
gotoxy(13,4);
for(i=1;i<=27;i++)
cout<<"━";
cout<<"┓";
for(i=5;i<=18;i++)
{
gotoxy(11,i);cout<<"┃";
gotoxy(67,i);cout<<"┃";
}
gotoxy(11,18);cout<<"┗";
gotoxy(13,18);
for(i=1;i<=27;i++)
cout<<"━";
cout<<"┛";
gotoxy(13,5);
}

void welcome()
{
void frame();
void gotoxy(int x,int y);
int shine(int x,int y);
int i,j;
frame(); // 边框
gotoxy(32,9);
cout<<"车票出售系统"<<endl<<endl;
cout<<" 组长：余灏然 组员：魏嘉、张越";
gotoxy(57,19);
cout<<"<任意键进入>";
for(i=1;i<=1000;i++) //循环闪动显示". . .欢迎进入. . ."
{
for(j=22;j<=45;j+=2)
{
shine(j,14);
if(_kbhit())break; //若有按键按下则终止循环
}
if(_kbhit())break;
}
getch();
system("cls");
}

int shine(int x,int y) //字符闪动
{
gotoxy(x,y);
cout<<". . .欢迎进入. . .";
Sleep(700); //时间暂停
gotoxy(x,y);
cout<<" ";
return 0;
}
5 测试与调试
5.1 个人测试（按组员分工）
5.1.1 余灏然测试
#include"iostream"
#include <list>
using namespace std;

//**************************************************************************************//

typedef struct Node{
int i,j; //分别表示线段树左右节点
int num; //存储数据，表示当前已出售票数
int num2; //返程
struct Node *lchild,*rchild;
}Btree,*Tree;

int CreateTree(Tree &T,int a,int b)
{
if(b<a || a<1 || b<1) // b大于a或a,b不大于零时，则提示输入错误
{
cout<<" error !"<<endl;
return NULL;
}

T=(Btree*)malloc(sizeof(Btree));
T->i=a; T->j=b; T->num=-1; T->num2=-1; // 只有树的叶子节点才用于存储数据，其他非叶子节点令其值为-1
if(b-a>1)
{
CreateTree(T->lchild,a,(a+b)/2);
CreateTree(T->rchild,(a+b)/2,b);
}
else
{
T->lchild=NULL;
T->rchild=NULL;
T->num=0; //初始化为0
T->num2=0;
}
return 1;
}
void DestroyTree(Tree &T) //删除时用这个，判断树是否已为空，若不空则执行Destroy(Tree T);
{
int Destroy(Tree T);
if(T->num==-1) { Destroy(T); cout<<"线段树已销毁。"<<endl; } //如果树不为空，则T->num=-1
else cout<<"树已为空，无需销毁。"<<endl;
}
int Destroy(Tree T) //完全销毁线段树
{
if(T==NULL) return 1;
Destroy(T->lchild);
Destroy(T->rchild);
free(T);
return 1;
}

void PreOrder(Tree T) //前序遍历树
{

if(T!=NULL)
{
cout<<T->i<<T->j<<endl;
PreOrder(T->lchild);
PreOrder(T->rchild);
}
else
cout<<"!!"<<endl;
}

//********************************以上部分为其他组员负责的，引用结果**************************************//

typedef struct save{
int k; //k=1时储存节点信息， k=0时代表空格不存储其他信息,k=-1时表示链表尾 (NULL不知为何不好使=A=)
int Si,Sj;
int Snum;
int Snum2;
}SaveData;

void SaveTree(Tree T);
void TreeToLis