数据结构【b】线段树及其应用.doc

东北大学信息科学与工程学院 数据结构课程设计报告 题目 线段树及其应用 课题组长 余灏然 课题组成员 魏嘉 张越 专业名称 计算机科学与技术 班级 计算机1307 指导教师 杨雷 2015 年 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.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,listSaveData p) 前序遍历树，将树变成链表，用于存储。 void ListToTree(Tree T,listSaveData::iterator iterP) 链表还原成树 int Loading(Tree T) 读取数据将数据还原成树 void print(liststaname 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,liststaname p) 查询车票数量 void intitle(liststaname p) 站号对应站名的处理 3.4主算法设计 线段树是