数据结构b线段树及其应用

东北大学信息科学与工程学院数据结构课程设计报告题目 线段树及其应用课题组长 余灏然课题组成员 魏嘉 张越专业名称 计算机科学与技术班级 计算机1307指导教师 杨雷2015 年 1月课程设计任务书题目：线段树及其应用问题描述：在实际应用中，常遇到与区间有关的操作，比如统计若干矩形并集的面积，记录一个区间的最大最小值及总量，并在区间的插入、删除和修改中维护这些数据。线段树的定义是利用树形二分结构所建立的一种数据结构，能够高效的完成这些操作。设计要求：设计线段树的抽象数据类型及其实现。（1） 实现线段树的ADT。（2）实现线段树的简单应用。指导教师签字：2014年12月28日目录1 课题概述11.1 课题任务11.2 课题原理11.3 相关知识22 需求分析22.1 课题调研22.2 用户需求分析23 方案设计23.1 总体功能设计23.2 数据结构设计23.3 函数原型设计23.4 主算法设计33.5 用户界面设计34 方案实现44.1 开发环境与工具44.2 程序设计关键技术44.3 个人设计实现（按组员分工）4.3.1余灏然设计实现44.3.2 魏嘉设计实现94.3.3 张越设计实现155 测试与调试175.1 个人测试（按组员分工）175.1.1 余灏然测试175.1.2 魏嘉测试255.1.3 张越测试275.2 组装与系统测试305.3 系统运行316 课题总结326.1 课题评价326.2 团队协作326.3 个人设计小结（按组员分工）326.3.1 余灏然设计小结326.3.2 魏嘉设计小结326.3.3 张越设计小结337 附录A 课题任务分工34A-1 课题程序设计分工34A-2 课题报告分工35 附录B 课题设计文档（光盘）B-1课程设计报告（电子版）B-2源程序代码（*.H，*.CPP）B-3工程与可执行文件）B-4屏幕演示录像文件（可选）附录C 用户操作手册（可选）36C.1 运行环境说明36C.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 &p) 前序遍历树，将树变成链表，用于存储。void ListToTree(Tree &T,list:iterator &iterP)链表还原成树int Loading(Tree &T) 读取数据将数据还原成树void print(list &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 &p) 查询车票数量void intitle(list &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函数#includehead.h#includesave.cpp#includeStationName.cpp#includebuy.cpp#includecheck.cpp#includeinquire.cpp#includeframe.cppvoid main()list 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);cout1.购票与查询;gotoxy(25,9);cout2.管理功能;gotoxy(25,10);cout3.退出;gotoxy(25,12);couti;system(cls);if(i=1)while(1)print(p);coutendlj;if(j=1)coutabn;if(ab) BuyTicket2(a,b,n,T);if(j=2) Inquire(T,p);if(j=3) break;if(i=2)while(1)system(cls);coutj;if(j=1) cout请输入线段区间(a,b) 必须符合0aab;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#includehead.hvoid TreeToList(Tree T,list &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);elsea.k=0;/a.Si=-1;a.Sj=-1; /Si与Sj用于测试，可删除p.push_back(a);void SaveTree(Tree T)FILE *fp;SaveData h;list p;list: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: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 p;list: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#includehead.hTree Find(int a, Tree T);void Inquire(Tree T,list &p) /查询车票数量int i=0;Tree t;list:iterator iterP=p.begin();coutendlendlendl当前相邻两站间的车票余额：endlk,T);coutk号站-name ;iterP+;coutk号站-name : ;coutnum)endl;iterP+;if(iterP=p.end() break;else iterP-;coutendl;iterP-;while(1)coutk号站-name ;iterP-;coutk号站-namek,T);coutnum2)endl;iterP-;if(iterP=p.end() break;else iterP+;4.3.2 魏嘉设计实现head.h#ifndef _HEAD_H #define _HEAD_H / 运用 #ifndef避免重复定义 #includeiostream#includestdio.h#includewindows.h#includeconio.h#include using namespace std;#define max 100 /每站票数的最大上限typedef struct Nodeint i,j; /分别表示线段树左右节点int num; /存储数据，表示当前已出售票数int num2; /返程struct Node *lchild,*rchild;Btree,*Tree;typedef struct stationint k; /站点所对应的数字char name20;staname;typedef struct saveint 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(ba | a1 | b1) / b大于a或a,b不大于零时，则提示输入错误cout error !i=a; T-j=b; T-num=-1; T-num2=-1; / 只有树的叶子节点才用于存储数据，其他非叶子节点令其值为-1if(b-a1)CreateTree(T-lchild,a,(a+b)/2);CreateTree(T-rchild,(a+b)/2,b);elseT-lchild=NULL;T-rchild=NULL;T-num=0; /初始化为0T-num2=0;return 1;void DestroyTree(Tree &T) /删除时用这个，判断树是否已为空，若不空则执行Destroy(Tree T);int Destroy(Tree T);if(T-num=-1) Destroy(T); cout线段树已销毁。num=-1 else cout树已为空，无需销毁。lchild);Destroy(T-rchild);free(T);return 1;void PreOrder(Tree T) /前序遍历树if(T!=NULL)coutijlchild);PreOrder(T-rchild);elsecout!endl;void gotoxy(int x,int y) /光标移动 x为列坐标,y为行坐标COORD pos=x,y;HANDLE hOut=GetStdHandle(STD_OUTPUT_HANDLE);SetConsoleCursorPosition(hOut,pos);#endifStationName.cpp#includehead.h#includestring.hvoid intitle(list &p) /站号对应站名的处理void Loading2(list &p);void firstuse();list:iterator iterP;int i,j;char b20;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)coutk号站-nameendl;iterP+;if(iterP=p.end() break;fclose(fp);coutendlendl1.添加或更改站点(请从1开始按顺序添加) 2.重置清空 3.返回 endli;if(i=1);p.push_back(h);iterP=p.begin();fp=fopen(StationName.dat,wb);while(1)h.k=iterP-k;strcpy(,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 &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#includehead.hvoid print(list &p) /显示乘车顺序list:iterator iterP=p.begin();int i=1;coutendl乘车区间:endl;while(i)coutk号站:name;iterP+;if(i=5) coutendlendl; i=1;if( !( iterP=p.end() ) ) cout-;else break;i+;coutendli & T-num=0) return T; int m;m=(T-i+T-j)/2;if(alchild);else p=Find(a,T-rchild);return p;void BuyTicket(int a,int b,int n,Tree &T) / abvoid SaveTree(Tree T);Tree Find(int a, Tree T);int i;Tree p;for(i=a;i max-p-num ) break;if(i!=b) cout该区间的票数余额不足，无法进行购买。endl;elsefor(i=a;inum+=n;SaveTree(T);cout购票成功！bvoid SaveTree(Tree T);Tree Find(int a, Tree T);int i;Tree p;for(i=a;ib;i-)p=Find(i-1,T);if(n max-p-num2) break;if(i!=b) cout该区间的票数余额不足，无法进行购买。b;i-)p=Find(i-1,T);p-num2+=n;SaveTree(T);cout购票成功！endl;getchar();getchar();4.3.3 张越设计实现check.cpp#includehead.hvoid 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#includehead.hvoid 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车票出售系统endlendl;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 余灏然测试#includeiostream#include using namespace std;/*/typedef struct Nodeint i,j; /分别表示线段树左右节点int num; /存储数据，表示当前已出售票数int num2; /返程struct Node *lchild,*rchild;Btree,*Tree;int CreateTree(Tree &T,int a,int b)if(ba | a1 | b1) / b大于a或a,b不大于零时，则提示输入错误cout error !i=a; T-j=b; T-num=-1; T-num2=-1; / 只有树的叶子节点才用于存储数据，其他非叶子节点令其值为-1if(b-a1)CreateTree(T-lchild,a,(a+b)/2);CreateTree(T-rchild,(a+b)/2,b);elseT-lchild=NULL;T-rchild=NULL;T-num=0; /初始化为0T-num2=0;return 1;void DestroyTree(Tree &T) /删除时用这个，判断树是否已为空，若不空则执行Destroy(Tree T);int Destroy(Tree T);if(T-num=-1) Destroy(T); cout线段树已销毁。num=-1 else cout树已为空，无需销毁。lchild);Destroy(T-rchild);free(T);return 1;void PreOrder(Tree T) /前序遍历树if(T!=NULL)coutijlchild);PreOrder(T-rchild);elsecout!endl; /*以上部分为其他组员负责的，引用结果*/typedef struct saveint k; /k=1时储存节点信息， k=0时代表空格不存储其他信息,k=-1时表示链表尾 (NULL不知为何不好使=A=)int Si,Sj;int Snum;int Snum2;SaveData;void SaveTree(Tree T);void TreeToList(Tree T,list &p);int Loading(Tree &T);void ListToTree(Tree &T,list:iterator &iterP) ;int DelData(Tree T);void main()Tree T;int i,a,b;while(1)cout1.生成线段树树并将树存储到文件中endl2.从文件读取数据将树还原endl3.退出endl;couti;if(i=1)coutab;CreateTree(T,a,b);SaveTree(T);if(i=2)Loading(T);PreOrder(T);if(i=3) exit(0);void SaveTree(Tree T)FILE *fp;SaveData h;list p;list: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 TreeToList(Tree T,list &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);elsea.k=0;/a.Si=-1;a.Sj=-1; /Si与Sj用于测试，可删除p.push_back(a);int Loading(Tree &T) /读取数据将数据还原成树list p;list: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;void ListToTree(Tree &T,list: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 DelData(Tree T)DestroyTree(T);FILE *fp;fp=fopen(TicketData.dat,wb+); / 不写入内容，即可清除数据fclose(fp);return 1;#includeiostreamusing namespace std;typedef struct Nodeint i,j; /分别表示线段树左右节点int num; /存储数据，表示当前已出售票数int num2; /返程struct Node *lchild,*rchild;Btree,*Tree;void main()int i,j;Tree T;int CreateTree(Tree &T,int a,int b);void DestroyTree(Tree &T);int Destroy(Tree T);void PreOrder(Tree T);coutij;CreateTree(T,i,j);cout前序遍历二叉树，输出其i,j值，“!”为NULL ：endl;PreOrder(T);coutendl按