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

《数据结构b线段树及其应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、东北大学信息科学与工程学院数据结构课程设计报告题目线段树及其应用课题组长余灏然课题组成员魏嘉张越专业名称计算机科学与技术班级计算机1307指导教师杨雷2015年1月课程设计任务书题目：线段树及其应用问题描述：在实际应用中，常遇到与区间有关的操作，比如统计若干矩形并集的面积，记录一个区间的最大最小值及总量，并在区间的插入、删除和修改中维护这些数据。线段树的定义是利用树形二分结构所建立的一种数据结构，能够高效的完成这些操作。设计要求：设计线段树的抽象数据类型及其实现。（1）实现线段树的ADT。（2）实现线段树的简单应用。　　　　　　　　　　　　指导教师签字：2

2、014年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系统运行

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操作说明361课题概述1.1课题任务在实际应用中，常遇到与区间有关的操作，比如统计若干矩形并集的面积，记录一个区间的

4、最大最小值及总量，并在区间的插入、删除和修改中维护这些数据。线段树的定义是利用树形二分结构所建立的一种数据结构，能够高效的完成这些操作。我们选择利用线段树这种结构来建立一个车票购票系统。【设计要求】设计线段树的抽象数据类型及其实现。（1）实现线段树的ADT。（2）实现线段树的简单应用。1.2课题原理线段树，类似区间树，是一个完全二叉树，它在各个节点保存一条线段（数组中的一段子数组），主要用于高效解决连续区间的动态查询问题，由于二叉结构的特性，它基本能保持每个操作的复杂度为O(lgN)!流程图如下：开始退出管理功能购票与查询删除树修改站点重新生成线段树查询购

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

6、点信息（4）读取文件功能和保存文件功能（5）需要用户友好的界面以便用户方便使用3方案设计3.1总体功能设计线段树3.2数据结构设计前序遍历树，将树变成链表，用于存储。3.3函数原型设计函数原型功能描述voidTreeToList(TreeT,list&p)前序遍历树，将树变成链表，用于存储。voidListToTree(Tree&T,list::iterator&iterP)链表还原成树intLoading(Tree&T)读取数据将数据还原成树voidprint(list&p)显示乘车顺序TreeF

7、ind(inta,TreeT)寻找叶子36voidBuyTicket(inta,intb,intn,Tree&T)购票voidCheck()检查数据文件voidwelcome()初始界面显示voidInquire(TreeT,list&p)查询车票数量voidintitle(list&p)站号对应站名的处理3.4主算法设计线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。对于线段树中的每一个非叶子节点[a,b]，它的左儿子表示的区间为[a,(a+b)/2]，右儿子

8、表示的区间为[(a+b)/2+1,b]。因此线段树是平衡二叉树，最