华中科技大学软件课程设计报告

1、软件课程设计光电 1006陈光辉U201013489软件课程设计报告班级：光电1006姓名：陈光辉学 号： U2010134891软件课程设计光电 1006陈光辉U201013489目录1 软件设计.41.1设计目的 .41.2设计要求 .41.3二叉树 .4(1).二叉树的定义 .错误！未定义书签。(2).二叉树的存储结构. 5(3).二叉树的遍历 .51.4程序分析 .错误！未定义书签。(1).程序结构 .错误！未定义书签。(2).程序功能 .错误！未定义书签。(3).程序注释 .错误！未定义书签。1.5程序流程图 .7(1).主程序 .8(2).二叉树的建立 .9(3).二叉树的查询 .

2、10(4).二叉树的打印 .112 软件测试.错误！未定义书签。2.1测试环境 .错误！未定义书签。2.2测试过程 .错误！未定义书签。(1).源程序的测试 .错误！未定义书签。(2).加入遍历程序 .错误！未定义书签。2软件课程设计光电 1006陈光辉U201013489(3).友好界面 .错误！未定义书签。3算法改进.错误！未定义书签。3.1问题发现 .错误！未定义书签。(1).出现的问题 .错误！未定义书签。(2).解决的方案 .错误！未定义书签。3.2程序优化 .184开发体会.185附录：源代码清单 .19注释程序 .196参考文献.253软件课程设计光电 1006陈光辉U20101

3、34891. 软件设计1.1设计目的继续巩固 C 语言的基础，其中需要熟练掌握的有函数变量、 程序控制、输入输出、调试环境、结构体等。熟练运用 C 语言的知识实现有序二叉树的建立、 查找和打印；了解非线性数据结构，并且掌握二叉树的三种遍历方式：先序遍历、中序遍历和后序遍历，并编程实践它们的实现、应用方法。1.2设计要求（1）学习结构体、链表等数据结构，以及查找、选择排序等基本算法，结合指针，文件等相关知识进行简单界面设计，能够实现友好的交互；（2）读懂源程序（用链式结构实现二叉树的建立、查询和打印） ，为程序写出注释，并画出程序的流程图；（3）将程序输入计算机，编译、连接并运行；（4）编写二叉

4、排序树的前序遍历程序、中序遍历程序和后序遍历程序。1.3二叉树(1). 定义 . 树（ tree ）：树是由 n（ n 0）个结点组成的有限集合。对于 n=0 的树称为空树，对于 n>0 的任意一棵非空树，有一个特殊的结点称为根结点（ root ），根结点没有前趋结点；剩下的结点被分成 n>=0 个互不相交的集合 T1、T2、.Tn，而且，这些集合的每一个又都是树。树T1、T2、.Tn被称作根的子树 (Subtree) 。 . 二叉树是指树的深度为2 的有序树；它是一棵由一个根结点（ root ）与两棵互不相交的分别被称为左子树和右子树所组成的非空树，左子树和右子树又同样都是一棵二

5、叉树。这是二叉树的递归定义。 二叉树可以是空集合， 根可以有空的左子树或空的右子树。二叉树是一种最简单、最重要的树，在计算机领域有着广泛的应用。 . 表示方法：通常用一个圆圈表示一个结点，并在圆圈中标一个字母，或一个数字，或一个字符串， 作为结点的名字或结点值， 以区别不同的结点。 在根结点与它的子树的根结点之间加一条连线，表示它们之间的逻辑关系。如下图表示：4软件课程设计光电 1006陈光辉U201013489这是一个满二叉树用结构体表示二叉树，如下表：左节点数据右节点编程时二叉树的定义方法是，先定义一个结构体struct treechar info;/ 字符变量 info ，用于保存数据s

6、truct tree *left, *right; / 定义子树和右子树指针(2). 二叉树的存储结构 . 数据结构的定义：数据结构由某一数据元素及该集合中所有数据元素之间的关系组成。包括数据的逻辑结构、数据的存储结构和对数据的操作。数据结构的形式定义为： 数据结构是一个二元组。 记为：Data_Structure=（D，S）二叉树是基本数据结构之一，在数据操作方面具有一定优势。 . 存储结构：包括顺序存储和链式存储。 . 顺序存储：通常用于存储具有线性结构的数据。 将逻辑上相邻的结点存储在连续存储区域 M 的相邻的存储单元中，使得逻辑相邻的结点一定是物理位置相邻。 . 链式存储：在结点的存储

7、结构中附加指针字段来存储结点间的逻辑关系。链接法中数据结点包括两部分： 数据字段存放结点本身的数据， 指针字段存放指向其后继结点的指针。 链接方法适用于那些需要经常进行增删结点的复杂数据结构。对于一般的二叉树，采用的是链式存储结构，其形式定义为：TypedefstructBTnodeElementtypedata;StructBTnode*LChild ;StructBTnode*RChild ;*BTree;BTreeBT ;/BT指向二叉树的根结点(3). 二叉树的遍历5软件课程设计光电 1006陈光辉U201013489遍历：是指按照某种顺序访问二叉树中的所有结点，使得二叉树中的每个结点

8、被访问一次而且仅被访问一次。 先序遍历：若二叉树为空，则遍历结束，否则：a) 访问根结点；b) 先序遍历左子树；c) 先序遍历右子树。先序遍历的程序如下：void xianxu(struct tree *root)if(root=NULL)/ 指针为空，则提示二叉树为空printf(" 这是一个空的二叉树 !n");return;elseprintf("%c",root->info);/前序遍历：先是根结点if(root->left!=NULL)xianxu(root->left);/ 递归访问左结点if(root->right!

9、=NULL)xianxu(root->right);/ 递归访问右结点 .中序遍历：若二叉树为空，则遍历结束，否则：a) 中序遍历左子树；b) 访问根结点；c) 中序遍历右子树。中序遍历的程序如下：void zhongxu(struct tree *root)if(root=NULL)printf(" 这是一个空的二叉树 !n"); / 指针为空，则提示二叉树为空 return;elseif(root->left!=NULL)zhongxu(root->left);/ 中序遍历：递归先访问左结点printf("%c",root->

10、info);/ 然后父结点if(root->right!=NULL)zhongxu(root->right); / 最后递归访问右结点 .后序遍历：若二叉树为空，则遍历结束，否则：a) 后序遍历左子树；6软件课程设计光电 1006陈光辉U201013489b) 后序遍历右子树；c) 访问根结点。后序遍历的程序如下：void houxu(struct tree *root)if(root=NULL)printf(" 这是一个空的二叉树 !n"); / 指针为空，则提示二叉树为空 return;elseif(root->left!=NULL)/ 后序遍历：首先

11、递归访问左结点houxu(root->left);if(root->right!=NULL)/ 然后递归访问右结点houxu(root->right);printf("%c",root->info);/ 最后父结点1.4程序分析（1）程序结构程序由 7 个部分构成：定义结构指针变量创建二叉树 struct tree *create_btree(struct tree *root,struct tree *r,char info)定义结构指针变量查找二叉树 struct tree *search_btree(struct tree *root,char

12、 key);打印二叉树函数 void print_btree(struct tree *r,int l); 前序遍历程序 void xianxu(struct tree *root);中序遍历程序 void zhongxu(struct tree *root);后序遍历程序 void houxu(struct tree *root);还有就是主程序，调用上述函数来实现二叉树的创建、查找、打印以及遍历（2）程序功能用链式结构实现二叉树的建立、查询和打印，编写二叉树的前序遍历程序、中序遍历程序和后序遍历程序实现对二叉树的访问。 附加的功能还有， 比如弄够对输入的结点进行计数。而且此程序加入了很多人

13、性化的界面， 有很多人机交互的内容， 系统用户进入界面控制后，对不同的功能操作提示不同，更加方便操作。(3). 程序注释程序的注释在后面的程序附录有详细的描述1.5程序流程图7软件课程设计光电 1006陈光辉U201013489（1）主程序的流程图如下：开始定义字符数组接收数据空格作为输入结束标志提示输入输入字符是二叉树是否建立否否建立根结点并保存数据输入数据是否为空是调用函数打印新建的二叉树提示输入要查找的数据提 示继 续调用函数查寻输入的数据查找Key 是否为真继续创建新的子树结束8软件课程设计光电 1006陈光辉U201013489（ 2）二叉树的创建流程图如下：开始否r=0是开辟内存是

14、否小于当前结点的新插入的结点为空提示：Outof左结点是memory左右结点的初始化，并将r 置于根结点处插入左结点插入右结点否父结点是否建立是新结点是否在左否r 的左右结点结点之前赋初值是将其值赋给左结点将其值赋给右结点返回新建的结点结束9软件课程设计光电 1006陈光辉U201013489（ 3）二叉树的查找流程图如下：开始二叉树是否为空否当前接点不是要查找要查找的接点是否小于当前左结点否是右结点的首地址左结点的首地址赋给 root赋给 root是否查找到结点否提示查找失败是是提示查找成功提示Emptybtree返回首地址结束10软件课程设计光电 1006陈光辉U201013489（ 4）

15、二叉树打印的流程图如下：开始定义整型变量，表示当前结点的高度是指针为空否递归打印二叉树的左结点返回是否小于结点的高度是打印二叉树的根结点打印 l*2 个空格递归打印二叉树的右结点结束11软件课程设计光电 1006陈光辉U2010134892. 软件测试1.2测试环境程序是在开发软件Microsoft Visual C+上运行调试的。2.2 测试过程(1).源程序的测试：二叉树的建立、查询和打印的源程序在VC中运行后的结果是：但是在这过程中，我发现当你输入比上次结点深度更浅的结点进行再次查找时，就会出现查找失败的现象。(2).加入三种遍历程序在主程序中运行后，可以选择遍历方式。如下图所示，输入一

16、个简单的二叉树后前序遍历的结果是：(3). 友好界面程序中加入了很多人机交互的内容，在进入操作界面后，对于不同的指令有不同的提示例如：12软件课程设计光电 1006陈光辉U2010134893 算法改进3.1 问题发现(1). 出现的问题问题一：在二叉树的查找程序中，输入第一个数据时可以成功查找，而且依次输入深度更深的结点进行查找时也可成功， 但是如果查找的结点比当前结点的深度要浅，比如是其父结点，这是就会提示 Empty btree 或者 Search Failure。问题二：在三种遍历程序中，当输入的结点为零时，就会提示二叉树为空。但是后来发现当指针为空时依然出现一个没有结果的遍历。 比如

17、下图，选择中序遍历时没有显示问题三：在选择遍历方式时，我定义的是一个 int 的变量 i，而且选择 1,2,3,之外的选项时回报错并提示你重新选择。 但是当输入的选项不是整型数值而是字母是， 就13软件课程设计光电 1006陈光辉U201013489意外的发现程序进入了一个死循环，如下图所示 ： 问题四：为了给程序加一个出口，我在查询的时候加一个人机交互的界面。当不继续查找结点时就会退出程序。 修改以后，虽然选择没有问题， 但是发现计算机在进入这个界面时总是会自动先选择，从而总会有一个报错的提示！(2). 解决的方案问题一的解决方案方案一：仔细分析源程序， 问题是在选择排序查找时， 把每次比较

18、的第一个数据的首地址赋给结构体指针变量 struct tree *root，所以每比较一次指针向后移动一位，而二叉树的遍历是每次访问并且仅访问一次， 当再来查找前面的结点时就无法访问了。对此，我首先想到的方案是在建立程序内再定义一个指针变量， 用于把比较的第一个数据首地址赋给它。代码如下：struct tree *search_btree(struct tree *root,char key)struct tree *r;r=root;if (!r)printf("Empty btreen");return root;while(root->info!=key)if(

19、key<root->info)r=root->left;elser=root->right;if(r=0)14软件课程设计光电 1006陈光辉U201013489printf("Search Failuren");break ;if (r !=0)printf("Successful searchn key=%cn",r->info);return root ;但是并没有达到预期结果结果。后来在同学的提示下， 我发现这个方案并不可取。 因为，新定义的指针在选择比较的过程中也会每次指向下一位数据。方案二：在 主 程 序 中 ，

20、 在 查 找 的 循 环 内 ， 把 root=search_btree(root,c); 改 为search_btree(root,c);， 改进的代码如下所示：while (key)/ 查找指定值的结点printf("Enter a key to find:");/ 输入要查找的数据scanf("%s",&c);search_btree(root,c);/ 查寻输入的数据printf("press to continuen");这样没有把要查找的数据地址赋给 root 指针，指针变量一直指向根结点，不会移动。结果解决了 b

21、ug问题二的解决方案：方案一：把每个遍历函数在增加一个形参 size，也就是结点的个数。 当结点数为零时，将空指针赋给 root ，这样就会提示二叉树为空。以前序遍历函数为例：void xianxu(struct tree *root ， intzize)if(size=0)/ 指针为空，则提示二叉树为空printf(" 这是一个空的二叉树 !n");return;If(root!=NULL)printf("%c",root->info); / 前序遍历：先是根结点 if(root->left!=NULL)15软件课程设计光电 1006陈光辉

22、U201013489xianxu(root->left); / 递归访问左结点 if(root->right!=NULL)xianxu(root->right);/ 递归访问右结点但是也没有达到预期结果， 以下面的为例，输入 5 查找成功，但是第三次查找时，程序就无法进行啦方案二：在主程序内调用选择遍历方式的循环内部进行修改， 即当输入的结点数为 0 时，把一个空指针 NULL赋给 root ，这样当二叉树为空时就可以退出程序了，而且修改比上次简单多了！修改的代码如下：while(flag=1)/ 如果选择错误则一直循环scanf("%d",&i)

23、;/ 输入选择遍历二叉树的方式if(size=0)/ 结点数为零，则 root 指针为空root=NULL;0 个时，选择前序遍历就会提示为空！ ！如下图示：输入的结点数为16软件课程设计光电 1006陈光辉U201013489问题三的解决方案：方案一：将整型变量改为 char 类型的变量，并将其 ASCII码值赋给另外一个整型变量c.但是结果无正确选择啦：方案二：在同学的指导下，我定义一个字符串数组 string100, 然后取其第一个元素作为选项。比如： *string=1 则是先序遍历，可是结果和方案一的错误一样。方案三：还是把选择变量改为 char 类型的，在输 入的时候直接用字符 变

24、量 scanf("%c",&i); 选择的条件为： if(i='1')这样再次选择不符合的字符就不会报错了，例如问题四的解决方案：这个 bug 是键盘缓存区的问题，需要在输入时加一个释放键盘缓冲区的系统函数 fflush(stdin); 这样就 OK 了！17软件课程设计光电 1006陈光辉U2010134893.2 程序优化在创建有序二叉树的循环内，我定义了一个变量，每循环一便计数一次，这样创建的二叉树的结点数就可打印出来了；在适当的地方加人机交互的提示，可以输入指令选择二叉树的遍历方式；给程序加了一个出口，在查询结点的时候。每次询问是否继续，如果

25、选择否就可以退出程序释放键盘缓冲区， 这样在几人交互的时候计算机就不会自动作出一个错误选择！4 开发体会在刚上学我就听别人说过软件课程设计很难， 要求我们开发一个小软件出来。那个时候我对软件开发的概念还很模糊， 或者说根本不知道， 因为那时候对电脑的接触还是很少。 学过大学计算机基础还有 C 语言之后，只知道很难， 就有点畏惧感，加上期末这两门课考试结果都很不理想，一点信心都没有！说实话，第一节课上老师说我们课设的题目是二叉树我就更加没有底气啦！因为数据结构这一章我学的很不咋样，而且 C 语言已经扔下有一个学期之久了，一点头绪也没有。 第一次上机课要求我们把用链式结构实现二叉树建立、 查询和打

26、印的源程序注释好， 并画出流程图。 源程序我看了几天也没有弄懂， 跟别说注释了，还有就是在 VC上运行的结果也是看不懂，觉得怎么看都不像我所知道的二叉树。头几次，我基本上都是在看老师给的资料 PPT和 word，但是，感觉里面的东西太简略。 二叉树的定义还有查找等等都要用到结构体和指针变量， 而且源程序里面用的很复杂，比如，结构体的套嵌，结构体指针，还有递归打印二叉树结点等。本来这一块也是自己比较薄弱的， 但是本着自己对编程的爱好， 我觉得这些都是自己有必要弄懂的！为了配合自己把这些做好，首先是要把那些基础知识巩固好，我在图书馆借了一本用 C 语言描述的数据结构的书， 帮助自己理解！ 有个大致

27、的把握之后， 我再来开始调程序。 同时在网上查找一些资料， 帮助自己看懂源程序。 在同学们的帮助下，我基本上能看懂程序里面那些函数的功能和用法， 也完成了程序的注释。接下来就是画流程图了， 能够把那些语句看懂， 在对流程图的符号规则有个大致了解后，也能自己独立完成了！收获最大的过程是调程序的时候！在参考书的辅助下，首先我加入了二叉树的前序遍历、中序遍历和后序遍历程序， 看到创建的二叉树能够用三种方式准确无误遍历的时候， 真心体会到了课设的乐趣， 有一种成就感！ 为了使运行后的程序更加美观、更加人性化，我试着插入一些人机交互的语句。期间遇到过很多bug，比如我试图用选择的方式进行遍历时，循环条件

28、没有限制完善，运行后一直提示错误；查询二叉树时当查找比当前深度 n 更小的结点时就不 Fail ；没有释放键盘缓存区，人机交互时计算机总会自动作出一次错误选择 我请教了编18软件课程设计光电 1006陈光辉U201013489程比自己好的同学， 加上自己的理解最终解决了一个一个的问题， 也许我完成的东西很简单、 也不尽完善， 但是这些确实都是我自己努力的成果， 感觉到了自己的进步、学到了东西就够了，我想这也是软件课程设计的教学目的。接下来，我试着对程序做进一步的优化和改进。发现问题后，和同学一起讨论分析，并进行反复的调试，一直到最后达到自己预期的结果。我想，知识的积累就是在这过程中的点点滴滴。

29、每当解决一个 bug 时就会很有成就感！虽然，软课设开始时间不长，只有短短的 3 个星期，而且对于我自己来说，起步也很低， 但是在这过程中， 体会到了学习的快乐。 当自己的修改和优化能够成功运行，那种快乐和成就感不言而喻， 也只有自己认真对待、 努力完成才能够体会！也许，自己的成果对别人、对于开发要求来说并不算什么，但是自己尝试努力的过程中真正学到了东西才是最重要的， C 语言是一门很重要的课程，在将来很多方面都会用到， 虽然已经结课了， 但是自己学到的东西是很浅的。 通过这次课设，让我的编程知识有了进一步的拓展， 也让我知道了要学的东西还很多很多，要走的路还很长，不管遇到什么课题，都不要有畏

30、难情绪，万事开头难，一旦自己投入进去后就会发现学习的快乐， 激发自己学习的欲望和兴趣！ 还有很重要的一点，就是遇到问题要敢于问、善于问，敢于问老师、助教，和同学一起讨论，去学习他们不同的思维方式， 在这过程中自己肯定也会发现很多遗漏或者不曾注意过的问题，从而增加知识的积累，也体会其中的快乐！5. 附录：源代码清单注释程序：源程序注释改进后如下：/*工程： test文件： c1.cpp注释 人：陈光辉时间： 201112*/#include<iostream.h>#include<stdio.h>struct tree / 二叉树的定义char info;/ 字符变量，用

31、于保存数据struct tree *left,*right;/ 定义左子树和右子树指针;struct tree *create_btree(struct tree *root,struct tree *r,char info);/ 定义结构指针变量，创建二叉树struct tree *search_btree(struct tree *root,char key);/ 定义结构指针变量，查找二叉树voidprint_btree(struct tree *r,int l);/ 打印二叉树函数的申明void xianxu(struct tree *root);/ 前序遍历函数申明19软件课程设计光

32、电 1006陈光辉U201013489void zhongxu(struct tree *root);/ 中序遍历函数申明void houxu(struct tree *root);/ 后序遍历函数申明/*主函数*/void main ()intflag,key,size=0;/ 错误标志flag 继续循环 ;size 表示输入的结点数， key 表示是否退出查找标志char s100,c ;/ 定义字符数组，用于接收输入的字符struct tree *root=0 ;/ 定义结构指针根结点并初始化printf("*软件课程设计 *n");printf("*n&q

33、uot;);printf("*班级：光电 1006 班*n");printf("*姓名：陈光辉*n");printf("*学号：U201013489*n");printf("*n");printf("*n");printf(" 请您输入数据，创建一个有序二叉树： n"); do printf("Enter a letter:");/ 输入字符，创建一个有序的二叉树size+;gets(s);if (!root)/ 若二叉树还没有建立，则建立根结点并保存数据

34、root=create_btree(root,root,*s);else/ 若二叉树建立则继续创建新的子树create_btree(root,root,*s);while (*s) ;/ 如果输入数据为空则退出循环，终止输入print_btree(root,0);/ 新建二叉树的打印size=size-1;/size 表示结点数printf(" 您输入的结点数为： %dnn",size);printf("*n");printf(" 请选择遍历二叉树的方式：n");/ 选择访问的方式：人机交互printf("1.前序遍历 n&

35、quot;);printf("2.中序遍历 n");printf("3.后序遍历 n");printf("*n"); printf(" 请您选择序号： ");while(flag=1)/ 如果选择错误则一直循环20软件课程设计光电 1006陈光辉U201013489char i;/ 定义字符变量 i（用于选择遍历方式），scanf("%c",&i);/ 输入选择遍历二叉树的方式if(size=0)/ 结点数为零，则root 指针为空root=NULL;if(i='1')p

36、rintf(" 前序遍历的结果是 :n");/ 打印前序遍历的结果xianxu(root);printf("n");break;else if(i='2')printf(" 中序遍历的结果是 :n");/ 打印中序遍历的结果zhongxu(root);printf("n");break;else if(i='3')printf(" 后序遍历的结果是 :n"); / 打印后序遍历的结果 houxu(root);printf("n");break;

37、elseflag=1;printf(" 错误的选择 ! n");printf(" 请您重新选择： ");printf("*n");/ 为了美观while (key=1)/ 循环查找结点printf(" 请您选择是否进行查找结点？:1.是2.否n");/给程序设置一个出口，当选择否就会退出循环fflush(stdin);/ 释放键盘缓存区char k;scanf("%c",&k);if(k='1')printf("Enter a key to find:"

38、;);/ 输入要查找的数据21软件课程设计光电 1006陈光辉U201013489scanf("%s",&c);search_btree(root,c);/ 查寻输入的数据printf("n");else if (k='2')break;elsekey=1;printf(" 错误的选择 ! n");printf(" 请您重新选择： ");printf("结束程序n");/ 退出程序/* Btree.C 结束*/*二叉树建立子程序*/struct tree *create_

39、btree(struct tree *root,struct tree *r,char info)if (r =0 )/ 如果当前位置无结点，则插入新的结点r=new (struct tree);/ same as function: malloc(sizeof()if ( r = 0)printf("Out of memoryn"); /如果新插入的结点为空，则提示Out ofmemoryreturn 0 ;r->left = 0;/ 新结点的左子树初始化r->right=0;/ 新结点的右子树初始化r->info=info;/ 将新结点 r 置于根结点

40、处if (root)/* 如果二叉树已经建立 ,则将新建结点连接到建立的二叉树，按照左子树、结点、右子树的顺序 */if(info<root->info)/ 判断新结点顺序在二叉树的左结点之前root -> left=r;/ 将其值赋给左结点elseroot -> right=r;/ 否则将其值赋给右结点else/ 如果二叉树不存在 ,新建二叉树22软件课程设计光电 1006陈光辉U201013489r->right=0;r->left = 0;returnr;/ 返回新建的结点/*if = = 0 接下页*/if (info < r->info

41、)/ 新结点跟当前左子结点比较，没有就加为左子结点create_btree(r,r->left,info);/ 插入左结点if(info>=r->info)create_btree(r,r->right,info);/ 否则插入右结点 /*create_btree(root,r,info)*/*二叉树查询子程序*/struct tree *search_btree(struct tree *root,char key)if (!root)printf("Empty btreen");/ 如果二叉树为空，则提示：Empty btreereturn root;while(root->info!=key)/ 如果当前结点不是要查找的结点if(key<root->info)/ 要查找的结点小于当前结点，当前结点指向当前的左结点root=root->left;/ 将二叉树左子树的首地址赋给rootelse/ 要查找的结点大于当前结点， 则当前结点指向当前的右结点