《【数据结构】【b】线段树及其应用正文终稿》由会员分享，可在线阅读，更多相关《【数据结构】【b】线段树及其应用正文终稿（41页珍藏版）》请在金锄头文库上搜索。
1、东北大学信息科学与工程学院数据结构课程设计报告题目 线段树及其应用课题组长 余灏然课题组成员 魏嘉 张越专业名称 计算机科学与技术班级 计算机1307指导教师 杨雷2015 年 1月课程设计任务书题目：线段树及其应用问题描述：在实际应用中，常遇到与区间有关的操作，比如统计若干矩形并集的面积，记录一个区间的最大最小值及总量，并在区间的插入、删除和修改中维护这些数据。线段树的定义是利用树形二分结构所建立的一种数据结构，能够高效的完成这些操作。设计要求：设计线段树的抽象数据类型及其实现。（1） 实现线段树的ADT。（2）实现线段树的简单应用。指导教师签字：2014年12月28日目录1 课题概述11.
2、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
3、课题评价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 课题任务在实际应用中，常遇到与区间有关的操作，比如统计若干矩形并集的面积，记录一个区间的最大最小值及总量，并在区间的插
4、入、删除和修改中维护这些数据。线段树的定义是利用树形二分结构所建立的一种数据结构，能够高效的完成这些操作。我们选择利用线段树这种结构来建立一个车票购票系统。【设计要求】设计线段树的抽象数据类型及其实现。（1） 实现线段树的ADT。（2） 实现线段树的简单应用。1.2 课题原理 线段树，类似区间树，是一个完全二叉树，它在各个节点保存一条线段（数组中的一段子数组），主要用于高效解决连续区间的动态查询问题，由于二叉结构的特性，它基本能保持每个操作的复杂度为O(lgN)!流程图如下：开始 退出 管理功能 购票与查询删除树修改站点重新生成线段树查询购票退出1.3相关知识前序遍历树，将树变成链表，用于存储
5、；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
6、 总体功能设计线段树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()检
7、查数据文件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
8、 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#includ
9、eStationName.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.购票与查询;
10、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);SaveTre
11、e(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.S
