毕业设计-数据结构【b】线段树及其应用.doc
《毕业设计-数据结构【b】线段树及其应用.doc》由会员分享,可在线阅读,更多相关《毕业设计-数据结构【b】线段树及其应用.doc(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);els
12、ea.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(SaveD
13、ata),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
14、-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) / 判断是不是链
15、表尾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(Tr
16、ee 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() brea
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 毕业设计 数据结构 线段 及其 应用
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【精****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。