数据结构课程设计报告

《数据结构课程设计报告》由会员分享，可在线阅读，更多相关《数据结构课程设计报告（22页珍藏版）》请在装配图网上搜索。

1、涉外经济学院课程设计报告课程名称：数据结构报告题目：二叉树的基本操作学生：肖琳桂、康政、小东、帆所在学院：信息科学与工程学院专业班级：软工本1402学生学号：144300211、02、14、08指导教师：春庭2015年 12月 31日课程设计任务书报告题目二叉树的基本操作完成时间2周学生肖琳桂康政专业班级软工本1402指导教师春庭职称讲师总体设计要求和主要功能设计一个程序，实现二叉树的创建以及二叉树的遍历（包括先序遍历、中序遍 历、后序遍历和层次遍历），计算并输出二叉树的深度和结点个数，功能要求：1. 二叉树以二叉链表存储，结点数据类型采用字符表示，按二叉树的先序遍 历序列创建。2. 用文本编

2、辑器编写一个data.txt的文件，包含3个以上创建按二叉树的先 序遍历序列（即序列中包含空树节点），每个序列长度不少于10个，在运行程序时 自动载入，也可以由键盘输入创建二叉树。丨3. 菜单功能：创建二叉树（二级菜单说明选择文件中的第几个，输出创建二 叉树的深度及结点数，若失败则有相应提示），遍历序列（显示先序，中序，后序 和层次遍历结果），结点的孩子信息，退出系统。工作容及时间进度安排第17周：周1 周2 :立题、论证方案设计周3周5 :程序设计及程序编码第18周：周1 周3 :程序调试周4-周5 :验收答辩摘要本课程设计主要说明如何在C+编程环境下实现二叉树的遍历，遍历方式包 括:二叉树

3、的先序遍历、中序遍历、后序遍历，层次遍历等四种遍历方式。同时 此次课程设计还包括了求二叉树深度和结点个数，结点的孩子信息，以及对文件 的操作，用文件读取的方式实现对二叉树的建立。以通过此次课程设计，使学生 充分掌握树的基本操作，以及对线性存储结构的理解。同时，在对树的遍历的操 作过程中，同样是运用递归的方式实现遍历，在对树实现层次操作的时候，要求 用循环队列的操作方式来实现层次遍历。此次课程设计对数据结构容综合性的运 用的要求较高。关键词：二叉树，先序遍历，中序遍历，后序遍历，层次遍历，节点，线性存储, 节点的孩子信息目录课程设计任务书1一、需求分析41问题描述 42功能要求 4二、概要设计5

4、1. 总体设计图 52. 数据结构设计 53. 算法设计 54. 主要模块及模块之间的关系 5三、详细设计 61. 结构体（或类）设计 62. 主要模块实现的流程图 63. 算法设计 7四、测试运行81登录和主界面运行效果图 82运行说明 83. 运行效果图 8五、结论与心得 101. 总体评价 102. 所做的工作及体会 10六、程序附录（源代码）12七、参考文献 18一、需求分析 1问题描述设计一个二叉树。二叉树形象地说即树中每个节点最多只有两个分支，它是 一种重要的数据类型。可以运用于建立家谱，公司所有的员工的职位图，以及各 种事物的分类和各种机构的职位图表等。二叉树是通过建立一个链式存

5、储结构， 达到能够实现前序遍历，中序遍历，后序遍历，层次遍历。以及能够从输入的数 据中得知二叉树的叶子结点的个数，二叉树的深度。在此，二叉树的每一个结点 中必须包括：值域，左指针域，右指针域。我们抽象出下列问题：实现文件操作， 运用文件输入流，将已经写好二叉树序列的 txt 文本文件，加载到程序中，实现 文件创建二叉树。然后采用链表存储的方式遍历二叉树(先序遍历、中序遍历、 后序遍历、层次遍历)。层次遍历运用循环队列的方法实现，需要重新定义队头 和队尾，以及队列的最大长度，并且在屏幕上实现输出显示。2功能要求(1) 用菜单的形式实现操作界面，提供(14)个功能选项，功能分别为创 建二叉树、遍历

6、序列、节点的孩子信息、退出系统。(2) 创建二叉树。要求用文件读取和键盘输入两种不同的方式实现二叉树的 创建。二级菜单说明，输出创建二叉树的深度及结点数，若失败则有相应提示。(3) 遍历序列。显示先序，中序，后序和层次遍历结果。先序遍历、中序遍 历、后序遍历用递归的方法实现遍历。层次遍历，用循环队列的方法实现。(4) 每次实现一项操作之后，要有相应的提示返回菜单。二、概要设计1.总体设计图历主菜单创建二叉树遍历序列节点的孩子信 息退出系统键 盘 输 入文 件 输 入中 序 遍先 序 遍 历2.数据结构设计数据元素为字符，逻辑结构为树形结构，存储结构为二叉链式存储，系统操 作的数据元素主要是创建

7、一个二叉树，遍历序列。3. 算法设计 本系统主要用到的算法有先序遍历、中序遍历、后序遍历、层次遍历、创建 二叉树和查找节点。从子菜单界面只能返回到主菜单界面，而不是退出程序。4. 主要模块及模块之间的关系运行程序后直接进入“菜单主界面”模块，菜单显示分为4 个模块，（14） 分别为创建二叉树、遍历序列、节点的孩子信息、退出系统。主界面中的各个模 块都是独立运行，每完成一项操作后，返回主菜单模块。通过相应定义的函数（外 部接口）实现，部数据的改变由模块部完成。三、详细设计1. 结构体（或类）设计 typedef char TElemType; typedef struct BiTNode TEl

8、emType date; struct BiTNode *lchild,*rchild;BiTNode,*BiTree;2. 主要模块实现的流程图3.算法设计先序遍历：void PreOrderTraverse(BiTree T) if(T) coutdate;PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild); 中序遍历：void InOrderTraver(BiTree T) if(T) InOrderTraver(T-lchild); coutdate;InOrderTraver(T-rchild); 后序遍历：void PostO

9、rderTraver(BiTree T) if(T) PostOrderTraver(T-lchild); PostOrderTraver(T-rchild); coutdate; 层次遍历：void ccbl(BiTNode *b) BiTNode *p;BiTNode *qMaxSize;int qm,h;qm=h=-1; h+; qh=b;while(qm != h) qm=(qm+1)%MaxSize; p=qqm; printf(%c ,p-date); if(p-lchild!=NULL) h=(h+1)%MaxSize; qh=p-lchild; if(p-rchild!=NUL

10、L) h=(h+1)%MaxSize;qh=p-rchild; 四、测试运行1登录和主界面运行效果图白cents and. SettingsAd*inist rator面 1 栈的基本操祚 程序SDebug.菜单信息;博瀏馨单请选择：小C: XDociuent s and Sett ing s AdAiiLi st r at o r面、機的基本操作 程序4Debug.H结点的孩壬信息：L如果节点不责在不返回任何信貳按任意犍返回子菜单） 騎入要去找的书点小R节点曲圭孩子=Bp点的右孩子=c扁按任意键继续-表 学生情况统计表序号性 别出生日期学号专业联系备注1康政男1994.12144300202

11、软件工程组长2肖琳桂男1996.08144300211软件工程3小东男1994.07144300214软件工程4帆男1995.08144300208软件工程五、结论与心得1.总体评价在此次的课程设计中，由于不够细心，在程序设计中犯了一些错误，花了挺 多的时间。但是经过一番思考并且在老师的帮助下，找到了导致程序错误的原因， 经过几次修改和调试，程序能正常运行，并且能够完成课程设计任务中的大部分 功能。同时在此次的课程设计中让我更深刻的了解了二叉树的基本操作，增加了 对专业只是学习的兴趣。我想在以后的学习中，我们会继续努力，希望在计算机 方面有好的成绩，也感老师给我们这次课程设计的机会，让我们认识

12、到了自身的 不足，让我们能够不断地完善自己!2.所做的工作及体会肖琳桂：编写程序和课程设计报告。课程设计中我主要担任程序设计的编写和设计报 告的编写工作，经过两个星期的上机实践学习，使我对数据结构有了更进一步的 认识和理解，也知道了要想学好它要重在实践，要通过不断的上机操作才能更好 地学习它。通过实践我发现我的很多不足之处，然感觉理论上已经掌握，但在运 用到实践的过程中仍有意想不到的困惑，因为自己对知识点的掌握不够熟悉，但 通过学习有很大改进。在这次课程设计中使我知道了二又树的先序、中序、后序、层次遍历。同时， 还包括了求二叉树深度和结点个数，结点的孩子信息，以及对文件的操作，用文 件读取的方

13、式实现对二叉树的建立。充分掌握树的基本操作，以及对线性存储结 构的理解。也培养了我如何去把握一件事情，如何去做一件事情，又如何完成一 件事情的方法和技巧。在设计过程中，和同学们相互探讨，相互学习，相互监督。我学会了运筹帷 幌，学会了宽容，学会了理解，也学会了做人与处世，这次课程设计对找来说受 益良多。在今后的日子里，我会认真对待每一件事情，争取做到最好，努力将知识与 实践相结合，不断巩固，加深所学的知识，做到学以致用。另外感老师的细心教导，以及同学们的帮助。康政：编写程序和课程设计报告。我在小组中做了编写程序和撰写报告的工作。在 编写程序时，遇到很多困难，例如缺少声明，调用函数错误等等。通过网

14、上搜查， 查询资料以及老师的指点帮助，完成了很多任务。作为基础不是很好的学生，我 在克服自己知识不足的过程中也在努力学习新的知识，运用不同的原理编写出不 同的算法。也学习到，算法不能盲目抄袭，很多东西是不同的，必须通过自己的 思考和努力的钻研才能写出一套完整的代码，不可心急，越是急越不可能精细的 完成任务。撰写报告的时候，很多地方因细节问题处理不好导致出了大大小小很 多漏洞，不能很精细的完成指定的任务。从中我也明白了，做一件事，尤其是耗 时的编写程序的问题，不能心急也不能马虎，也许一点点出错整个程序就会崩溃， 还要重新一点点的检查才能找出问题，大大降低了办事效率。所以，今后要做的 第一件事是慢

15、慢巩固检出，打好根基。第二件事是沉下心来认真做事，不能毛手 毛脚，从头到尾认真细致的做下去，避免出错惹出更多的麻烦。这次的程序设计 使我受益匪浅，学到了很多，做了很多。希望以后可以更多的做这种任务，巩固 知识，学习新的知识，有了这些经验可以做的更好。小东：查找资料和打印。这次我在小组中做的事情是查询资料和打印排版。虽然因 为我的专业底子差一点，现在暂时只能在程序设计时查找一些需要用到的专业资 料，帮助组员完成设计，但我相信下一次我不会仅此于此。这次程序设计我的收 获还是很大了，让我懂得了学好专业知识，并不是自己想象中的难，而是你自己 是否去努力了。在查找资料的过程中，我是边查边学自己不会的知识

16、点。查找途中也遇到了 一些当时不能理解的知识点，但经过同学的细心解答，最后一些难掌握的知识点 都被基本掌握。这让我懂得编程过程需要很大的耐心，而且要有良好的思维和扎 实的专业基础知识，所以我需要努力的学习，发现自身不足之处并努力改正他， 逐步提高自身的能力，不断取得进步。通过这次课程设计，我认识到知识运用的 重要性，并且努力加深对基础知识的理解，从中了解自己需要学习的东西并学会 自学。作为一名计算机专业的学生，今后我会加紧学习，学好专业知识，为将来 打下坚实的基础。帆：查找资料和打印。这次我在小组中做的事情是查询资料，打印排版。虽然这 些工作并不是主要任务，但是我用心对待，认真为做程序的同学查

17、找资料，为他 们挑选所需要的代码以及算法，及时反馈给他们信息。因为基础不是很好，经常 会剪裁到一些不是很合适的代码，我们通过共同分析，共同筛选，最终也获得了 很多收获。通过和他们一起分析代码，我也涨了很多知识。懂的了二叉树的算法， 数据类型等等。报告的排版也是一项需要耐心的工作，通过晚上的时间，我认认 真真的对所写的设计报告进行了排版，把一些不符合文本框架或者有代码错误的 都进行了细致的修改，保证了设计报告的质量。从这次的程序设计中，我学到了 很多。认认真真做一件事情不会有错，用什么态度做什么事会得到什么样的回报。 并且我认为数据结果也不是很难的科目，认真花时间去琢磨一定不会落下很多。 所以以

18、后我会细致做事，并在闲暇时间补习功课，争取尽快补习好原来的知识， 再学习新的知识为自己充电。六、程序附录(源代码) #include #include #include using namespace std;typedef char TElemType; #define MaxSize 1000 int i;typedef struct BiTNodeTElemType date; struct BiTNode *lchild,*rchild;BiTNode,*BiTree;void Des tory(B i Tree &T)；/ 函数声明char input255;void Interfa

19、ce()；void sjecs(BiTree &T)；void jp(BiTree &T)；/键盘 void wj(BiTree &T)；/文件 void CreateBiTree(BiTree &T)； int Count(BiTree T)； int Deep(BiTree T)；void PreOrderTraverse(BiTree T);/先序 void InOrderTraver(BiTree T);/ 中序 void Pos tO rderTraver(BiTree T)；/后序 void ccbl(BiTNode *b)；/层次遍历 void blxljm()；void loc

20、ate(BiTree T,char x)；void main()/主函数Interface()；BiTree T=NULL； bool End=false； char sel；char x;int p=1;int q=1;doInterface();fflush(stdin);char select=cin.get();system(cls);switch(select)casel：cout创建二叉树：n；sjecs(T)；break； case2: coutnt 遍历序列n； doblxljm()；coutn 选择：； fflush(stdin)； sel=cin.get()；p=1；swi

21、tch(sel)case1：coutn 先 序 遍 历 二 叉 树 的 输 出 顺 序 ：n；PreOrderTraverse(T)；coutn；system(pause)；system(cls)；brea k；case2： coutn 中序 遍 历 二叉 树 的 输出 顺 序 ：n；InOrderTraver(T)；coutn；system(pause)；system(cls)；break； case3： coutn 后序 遍 历 二叉 树 的 输出 顺 序 ：n；PostOrderTraver(T)；coutn；system(pause)；system(cls)；break；case4:

22、coutn层次遍历二叉树的输出顺序：n； ccbl(T)；coutn；system(pause)；system(cls)；break；case5: p=0；while(p)；break；case3: do system(cls)；q=1；coutx； locate(T，x)；system(pause)；system(cls)； coutq；if(q!=0&q!=1) cou t输入格式不对请重新输入n； while(q!=0&q!=l)；while(q)；break； case4:End=true；system(pause)；while(!End)；void locate(BiTree T,c

23、har x) /在二叉树T中查找值为x的节点BiTree p；p=T；if(T=NULL) return； else if(T-date=x) coutdate；if(T-lchild)coutt 节 点 的 左 孩 子 lchild-daterchild) coutt 节 点 的 右 孩 子 rchild-datelchild； if(p) locate(T-lchild,x); locate(T-rchild,x);void Int erface()/菜单界面函数system(cls);coutnt遍历序列n;coutttl.创建二叉树n；couttt2.遍历序列n;cou t tt3.结

24、点的孩子信息n;couttt4.退出系统n;couttt 请选择(14)：；coutntn;void blxljm()/遍历序列界面函数system(cls)；coutnt 二叉树n；c ou t t (如果没创建二叉树,不返回任何信息，按5返回主菜单) n ； coutttl.先序遍历二叉树n; couttt2.中序遍历二叉树n; couttt3.后序遍历二叉树n; couttt4.层次遍历二叉树n;couttt5.返回主菜单n;couttt 请选择(15)：；coutlchild)+Count(T-rchild);int Deep(B iT ree T)/计算二叉树的度 if(T=NULL

25、)return 0;int u=Deep(T-lchild);int v=Deep(T-rchild); if(uv)return (u+1);return (v+1);void sjecs(BiTree &T)/选择输入模式，新建二叉树bool End=false;if(T)Destory(T);T=NULL;cout请选择输入二叉树序列模式：(1：键盘输入2文件输入3返回主 菜单)endl；dochar Selection=cin.get()；switch( Selection)case1: jp(T)；break； case2:wj(T)；break； case3:End=true；wh

26、ile (!End)；void jp(BiTree & T)/键盘输入cou t输入按先序建立二叉树结点序列：t；cou t例如：ABDECFHGIJn；cou t input；int i=0；CreateBiTree(T)；int num=Count(T)；int deep=Deep(T)；cout二叉树创建成功！ n；cout此二叉树共有num个结点n； cout 且该二叉树的深度为： deep n；cou t请输入选项：；void wj(BiTree & T)/文件输入ifstream fi(a.txt)；if(!fi)coutinput；int i=0；CreateBiTree(T)；

27、int num=Count(T)；int deep=Deep(T)；cout二叉树创建成功！ n;cout此二叉树共有num个结点n; cout 且该二叉树的深度为： deepdate=inputi+； CreateBiTree(T-lchild)； CreateBiTree(T-rchild)；按3返回主菜单界面）按3返回主菜单界面）void PreOrderTraverse(BiTree T)/先序遍历if(T) coutdate;PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild);void InOrderTraver(BiTree

28、T)/ 中序遍历if(T)InOrderTraver(T-lchild); coutdate;InOrderTraver(T-rchild);void Pos tOrderTraver(B i Tree T)/后序遍历 if(T)PostOrderTraver(T-lchild);PostOrderTraver(T-rchild); coutdate;void ccbl(BiTNode *b) /层次遍历BiTNode *p;BiTNode *qMaxSize;int qm,h;qm=h=-1; h+; qh=b;while(qm != h)qm=(qm+1)%MaxSize;p=qqm;pr

29、intf(%c ,p-date);if(p-lchild!=NULL)h=(h+1)%MaxSize; qh=p-lchild;if(p-rchild!=NULL)h=(h+1)%MaxSize; qh=p-rchild;void Des to ry(B iT ree &T)/删除树if(T)Destory(T-lchild);Destory(T-rchild);free(T);七、参考文献莉，董渊，何江舟编著，C+语言程序设计，；清华大学，2010谭浩强.C程序设计(第三版)M.：清华大学，2005.严蔚敏数据结构(C语言版)，清华大学。教 师 评 语 及 设 计 成 绩教师评语：课程设计成绩：指导教师：（签名）日期：年月日