华中科技大学软件课程设计报告_华中科技大学课程设计
华中科技大学软件课程设计报告由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“华中科技大学课程设计”。
软件课程设计报告
班 级：姓 名：学 号：
光 信0 8 0 4 廖 娟
U 2 0 0 8 1 3 1 9 7 光信0804廖娟
U200813197
目 录软件设计............................................4
1.1 设计题目及目的.................................4 1.2 设计思想.......................................4 1.3 背景知识.......................................4(1).定义：.....................................4(2).存储结构:.................................5(3).遍历二叉树：...............................6 1.4 程序结构及功能划分.............................7(1).廖娟#注释.cpp..............................7(2).廖娟#软件课程设计.cpp......................8 1.5 程序流程......................................10 2 软件测试...........................................14
2.1 测试环境......................................14 2.2 廖娟#注释.cpp 的测试过程.......................14 2.3 廖娟#软件课程设计.cpp 的测试过程...............15(1).程序运行前的初始界面.......................15(2).输入数据及二叉树打印的画面.................16(3).选择操作的提示画面.........................16(4).程序测试时的画面..........................17 3 算法改进...........................................19
3.1问题发现......................................19 软件课程设计
2010年1月
(1).问题一：..................................20(2).问题二：.................................21 3.2解决方案......................................21(1).问题一改进方案：.........................21(2).问题二改进方案：.........................22 4 开发体会...........................................23 附录：源代码清单......................................25
廖娟#注释.cpp.....................................25 廖娟#软件课程设计.cpp.............................29 参考文献.............................................35光信0804廖娟
U200813197软件设计
1.1 设计题目及目的设计题目：二叉树的查找--用链表结构实现二叉树建立、查询、打印的源程序。
设计目的：基于C语言的基础，熟练运用结构体等扩展数据手段，定义应用数据、并进行运用。本题要求掌握数据的链式存储结构，并编程实践它们的实现、应用方法。
1.2 设计思想
利用结构体，链表等数据结构，以及折半查找、选择排序等基本算法，结合指针，文件等相关知识，利用C语言编写链式结构实现二叉树的建立、打印、查询、先序遍历、中序遍历、后序遍历等基本功能，并将这些功能用独立的子函数实现，通过主函数的调用实现相应的功能。
1.3 背景知识
(1).定义：
二叉树是由n(n>=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。
这也是一个递归定义。二叉树可以是空集合，二叉树结点的子树软件课程设计
2010年1月
要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。二叉树的定义方法:
Struct tree { char info;struct tree *left, *right;
}(2).存储结构:
存储结构分为顺序存储结构和链式存储结构。
a.顺序存储结构：从树根起，自上层至下层，每层自左至右的给所有结点编号缺点是有可能对存储空间造成极大的浪费，在最坏的情况下，一个深度为H且只有H个结点的右单支树确需要2h-1个结点存储空间。而且，若经常需要插入与删除树中结点时，顺序存储方式不是很好！光信0804廖娟
U200813197
b.链式存储结构：
存储二叉树经常用二叉链表法
(3).遍历二叉树：
假如以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，遍历整个二叉树则有DLR、LDR、LRD、DRL、RDL、RLD六种遍历方案。若规定先左后右，则只有前三种情况，分别规定为：
DLR——先（根）序遍历，LDR——中（根）序遍历，软件课程设计
2010年1月
LRD——后（根）序遍历。①．先序遍历二叉树的操作定义为： 若二叉树为空，则空操作；否则 A.访问根结点； B.先序遍历左子树； C.先序遍历右子树。
②．中序遍历二叉树的操作定义为： 若二叉树为空，则空操作；否则 A.中序遍历左子树； B.访问根结点； C.中序遍历右子树。
③．后序遍历二叉树的操作定义为： 若二叉树为空，则空操作；否则 A.后序遍历左子树； B.后序遍历右子树； C.访问根结点。
1.4 程序结构及功能划分
(1).廖娟#注释.cpp
主要分为主函数、创建二叉树子函数、二叉树查询子函数、二叉树打印子函数四个部分。其基本功能分块，如下图所示：光信0804廖娟
U200813197
(2).廖娟#软件课程设计.cpp 在 廖娟#注释.cpp 的基础上进行了一些算法改进，进行了简单的界面设计，能够实现友好的交互，系统用户进入界面控制后，对不同的功能操作提示不同，此外加入了二叉排序树的前序遍历程序、中序遍历程序和后序遍历程序。
①．先序遍历源代码：
void PreorderTraversal(struct tree *root){ if(root==0)return;printf(“%c”,root->info);软件课程设计
2010年1月
PreorderTraversal(root->left);PreorderTraversal(root->right);} ②．中序遍历源代码：
void InorderTraversal(struct tree *root){ if(!root)return;InorderTraversal(root->left);printf(“%c”,root->info);InorderTraversal(root->right);} ③．后序遍历源代码：
void PostorderTraversal(struct tree *root){ if(!root)return;PostorderTraversal(root->left);PostorderTraversal(root->right);printf(“%c”,root->info);} 光信0804廖娟
U200813197
1.5 程序流程
廖娟#注释.cpp的主程序的流程图如下：软件课程设计
2010年1月
创建二叉树的流程图如下：光信0804廖娟
U200813197
二叉树查询的流程图如下:软件课程设计
2010年1月
二叉树打印的流程图如下:光信0804廖娟
U200813197软件测试
2.1 测试环境
Microsoft Visual C++
2.2 廖娟#注释.cpp 的测试过程
但是在测试的过程中也发现了一些问题，设计示例给出的源代码中存在几个问题在下图所示操作中暴露出来了：软件课程设计
2010年1月
具体的解决方案见算法改进。
2.3 廖娟#软件课程设计.cpp 的测试过程
输入50个数字(或字母)，对 廖娟#软件课程设计.cpp 进行测试。(1).程序运行前的初始界面光信0804廖娟
U200813197
(2).输入数据及二叉树打印的画面
(3).选择操作的提示画面软件课程设计
2010年1月
(4).程序测试时的画面
①．选择1，进行先序遍历； ②．选择2，进行中序遍历； ③．选择3，进行后序遍历；
④．选择4，进行查询结点，再输入要查询的结点e，找到了，输出：
Succeful search！!key=e
继续输入w，同样查询成功； ⑤．输入m，没找到，输出结果：
Search Failure！!光信0804廖娟
U200813197
⑥．再次选择3，进行后序遍历，与③输出相同；
再次选择2，进行中序遍历，与②输出相同； ⑦．再次选择4，进行查询结点，运行结果正常； ⑧．再次选择1，进行先序遍历，与①输出相同； ⑨．选择8，输入错误，没有对应的操作，输出：
您 的 输 入 有 误，请 重 新 输 入！!⑩．选择5，进行退出操作，输出：
光 信 0 8 0 4 ———— 廖 娟0 1 0 年 1 月软件课程设计
2010年1月算法改进
3.1问题发现
在完成第4项选做项目时，程序前面部分的创建、查询、打印二叉树的算法仍采用已给出的设计示例中的算法，但是在测试过程中发现存在问题。光信0804廖娟
U200813197
(1).问题一：
第一次先序遍历的输出结果为：edaf
第二次先序遍历的输出结果为：f 经过观察及调试发现问题在于查询二叉树子函数，其中root是根结点，运行查询后root就被移动了，所以再次要求先序遍历的结果就与第一次先序遍历的结果不同。
未改动前源代码如下：软件课程设计
2010年1月
(2).问题二：
设计示例中给出的函数运行后，没有退出的方式，即没有出口，程序无法正常退出。
3.2解决方案
(1).问题一改进方案：
函数内部定义一个指针tree *t，用 *t指向根结点，这样进行查询操作后根结点就不会移动了。
改动后源代码如下：光信0804廖娟
U200813197
(2).问题二改进方案：
在switch语句中增加：
case 5:
printf(“
光 信 0 8 0 4 ———— 廖 娟nn”);printf(“0 1 0 年 1 月nn”);return;来实现退出程序的操作，具体解决方案见
廖娟#软件课程设计.cpp 的源代码。软件课程设计
2010年1月开发体会
刚刚拿到软件课程设计的题目时，我震惊了，二叉树？这是什么东西，上学期学习C语言的时候好像没学到二叉树啊。听了老师的介绍才知道做这个题目的软件课程设计还要先学习一下数据结构中关于二叉树部分的知识，当时我真的是有些不知所措，本就不怎么好的C语言加上完全不会的数据结构二叉树使我开始怀疑：三个星期后我可以完成这份关于二叉树的查找的软件课程设计吗？
最初的几天也确实很没有头绪，只是想着想把老师给的资料都看了，看完了之后走一步算一步吧，可是看完了之后发现仍然没有很大的收获，连怎么二叉树到底有什么用都不知道，对于这个题目依然是十分陌生。可是时间紧迫啊，于是找了位学习过数据结构的同学借了本数据结构的书，研究了一番，在加上在网上搜索了一番终于有些头绪了，知道这份课设到底要我们做什么了！
接下来的几天，随着了解的加深，自己开始慢慢的做课设了，当然从和同学的交流中，我也学到了很多。这之后我一步步的完成了对设计示例的注释，对递归算法的理解，以及先序遍历、中序遍历、后序遍历程序的书写，最终完成了程序的开发。程序开发中我记忆最深刻的就是编写选择操作的提示界面和初始界面的时候，为了使界面更加友好，加入了一些人性化的语句，以及为了出现欢迎界面进行的许多次试验，慢慢的我觉得这个过程十分有趣，看着自己编排的界面出现在面前心中还是有些许成就感的。当然除了这些还有很令我头疼的光信0804廖娟
U200813197
程序调试过程：在程序的调试阶段，发现程序中有许多问题，有的根本不知道从哪入手解决问题，甚至不知道为什么会出现错误，也因此耗费了很多时间，让我苦闷了很久。
在这段时间里，因为有软件课程设计，让我学到了很多知识，收获了很多我，自我感觉自己解决问题的能力提高了，并且掌握了软件开发的一些基本的方法和技巧。还记得写课设报告的时候，花了一天的时间把报告里面的所有图都画完了，从刚开始的不会用画图软件，到后来慢慢摸索最后熟练运用，画图的速度是越来越快了，让我后来甚是欣慰。
经过了这一次的软件课程设计，我感受到了C语言的魅力，也深切的体会到了“学海无涯”这四个字的分量。在以后的日子里，我所需要学习的东西还有很多很多，应了那句“书山有路勤为径，学海无涯苦作舟。”软件课程设计
2010年1月
附录：源代码清单
廖娟#注释.cpp #include /* C++头文件，实现输入输出的头文件
*/ #include
/* 定义二叉树结构
*/ struct tree
{
char info;
// 定义char型变量，存放数据
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);/* 定义子函数，作用打印二叉树
*/ void print_btree(struct tree *r,int l);
/* O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ */ /* 主函数
*/ void main(){
char s[100],c,key=' ';
struct tree *root=0;
// 定义结构指针根结点，初始化为0
/* 读入二叉树的各个结点的值，并将其插入到二叉树中
*/
do {
printf(“Enter a letter:”);
gets(s);
// 数据输入过程
if(!root)
root=create_btree(root,root,*s);
// 如果二叉树还未建立，则建立根结点并保存数据
else
create_btree(root,root,*s);// 如果二叉树已建立，则建立新的子树
}
while(*s);
// 直到s字符串为空，停止输入
print_btree(root,0);光信0804廖娟
U200813197
/* 查找具有指定值的结点
*/ key='1';while(key){
printf(“Enter a key to find:”);
scanf(“%s”,&c);
root=search_btree(root,c);
printf(“pre to continuen”);} }
/* Btree.C 结束
*/
/* O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ */ /* 创建二叉树
*/ struct tree *create_btree(struct tree *root,struct tree *r,char info)/* 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”);
return 0;
}
r->left= 0;
r->right=0;
r->info=info;
// root为空，则插入后保存至根结点处
if(root)
// 如果二叉树存在,则将新建结点与二叉树连接起来
{
if(infoinfo)
root-> left=r;
else
root-> right=r;
// 按左结点
}
else
// 如果根结点不存在，即二叉树不存在，则将新建一个二叉树
{
r->right=0;
r->left=0;软件课程设计
2010年1月
}
return r;}
/* if = = 0 接下页
*/
/* 判断要插入的节点应该在当前节点的左子树或右子树，递归插入
*/ if(info info)
create_btree(r,r->left,info);if(info>=r->info)
create_btree(r,r->right,info);}
/* create_btree(root,r,info)*/
/* O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ */ /* 查询数据
*/ struct tree *search_btree(struct tree *root,char key)/* struct tree *root:要查询的二叉树首地址
char key:要查询的数据
*/ {
if(!root)
// 如果二叉树指针为空，输出Empty btree {
printf(“Empty btreen”);
return root;
}
while(root->info!=key)
{
if(keyinfo)
// 按照“左结点
root=root->left;
else
root=root->right;
if(root==0)
// 如果指针为空，则退出查找
{
printf(”Search Failuren“);
break;
} } /* while(root->info!=key)*/ if(root!=0)
// 如果二叉树指针不为空，即查找成功给出信息，返回
printf(”Succeful searchn key=%cn“,root->info);return root;} /* *search_btree(root,key)*/
/* O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ */ 光信0804廖娟
U200813197
/* 打印二叉树
*/ void print_btree(struct tree *r,int l)/* struct tree *r:二叉树首地址
int l:当前结点的高度，根结点为0
输出的二叉树为正常树逆旋转90°后成镜像的结果
*/ {
int i;if(r == 0)
return;
//如果传入指针为0，则返回
print_btree(r->left,l+1);
//打印左结点
for(i=0;i
printf(” “);
//打印空格，用来排版控制格式
printf(”%cn“,r->info);
//打印根结点
print_btree(r->right,l+1);
//打印右结点 } /*
*print_btree(root,0)
*/软件课程设计
2010年1月
廖娟#软件课程设计.cpp #include /* C++头文件，实现输入输出的头文件
*/ #include
/* 定义二叉树结构
*/ struct tree
{
char info;
// 定义char型变量，存放数据
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);/* 定义子函数，作用打印二叉树
*/ void print_btree(struct tree *r,int l);/* 定义子函数，作用先序遍历
*/ void PreorderTraversal(struct tree *root);/* 定义子函数，作用中序遍历
*/ void InorderTraversal(struct tree *root);/* 定义子函数，作用后序遍历
*/ void PostorderTraversal(struct tree *root);
/* O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ */ /* 主函数
*/ void main(){
char s[100],c;
int n;struct tree *root=0;
// 定义结构指针根结点，初始化为0
printf(”
###“);printf(”##
##“);printf(”##
软件课程设计: 二叉树的查找
##“);printf(”##
##“);printf(”##
班 级: 光 信0 8 0 4
##“);光信0804廖娟
U200813197
printf(”##
##“);printf(”##
姓 名: 廖 娟
##“);printf(”##
##“);printf(”##
学 号: U 2 0 0 8 1 3 1 9 7
##“);printf(”##
##“);printf(”
###“);printf(”n“);printf(”
程 序 运 行 开 始 啦！!nn“);
/* 读入二叉树的各个结点的值，并将其插入到二叉树中
*/
do {
printf(” 请 输 入 一 个 字 符:“);
gets(s);
// 数据输入过程
printf(”n“);
if(!root)
root=create_btree(root,root,*s);
// 如果二叉树还未建立，则建立根结点并保存数据
else
create_btree(root,root,*s);
// 如果二叉树已建立，则建立新的子树
}
while(*s);
// 直到s字符串为空，停止输入
printf(” 打 印 的 二 叉 树 如 下:n“);print_btree(root,0);
printf(”
###“);
printf(”##
##“);
printf(”##
★★★★★★★★★
请输入您想要执行的操作!:
★★★★★★★★★
##“);
printf(”##
##“);
printf(”##
选择1—————————————进行先序遍历
##“);
printf(”##
##“);软件课程设计
2010年1月
printf(”##
选择2—————————————进行中序遍历
##“);
printf(”##
##“);
printf(”##
选择3—————————————进行后序遍历
##“);
printf(”##
##“);
printf(”##
选择4—————————————进行查询结点
##“);
printf(”##
##“);
printf(”##
选择5—————————————进行退出操作
##“);
printf(”##
##“);
printf(”##
★★★★★★★★★
温馨提示:请选择数字键0～5 ★★★★★★★★★
##“);
printf(”##
##“);
printf(”
###“);while(1){
scanf(”%d“,&n);
switch(n)
{
case 1:
printf(” 先 序 遍 历 为:n“);
PreorderTraversal(root);
printf(”nn“);
break;
case 2:
printf(” 中 序 遍 历 为:n“);
InorderTraversal(root);
printf(”nn“);
break;
case 3:
printf(” 后 序 遍 历 为:n“);
PostorderTraversal(root);
printf(”nn“);
break;
case 4:
光信0804廖娟
U200813197
printf(” 请 输 入 您 要 查 询 的 结 点:n“);
scanf(”%s“,&c);
printf(” 您 要 查 询 的 结 点 为:n“);
root=search_btree(root,c);
printf(”n“);
break;
case 5:
printf(”
光 信 0 8 0 4 ———— 廖 娟nn“);
printf(”0 1 0 年 1 月nn“);
return;
default:
printf(” 您 的 输 入 有 误，请 重 新 输 入！!n“);
break;
}
} } /* Btree.C 结束
*/
/* O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ */ struct tree *create_btree(struct tree *root,struct tree *r,char info)/* 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“);
return 0;
}
r->left= 0;
r->right=0;
r->info=info;
// root为空，则插入后保存至根结点处
if(root)
// 如果二叉树存在,则将新建结点与二叉树连接起来
软件课程设计
2010年1月
{
if(infoinfo)
root-> left=r;
else
root-> right=r;
// 按左结点
}
else
// 如果根结点不存在，即二叉树不存在，则将新建一个二叉树
{
r->right=0;
r->left=0;
}
return r;}
/* if = = 0 接下页
*/
/* 判断要插入的节点应该在当前节点的左子树或右子树，递归插入
*/ if(info info)
create_btree(r,r->left,info);if(info>=r->info)
create_btree(r,r->right,info);}
/* *create_btree(root,r,info)*/
/* O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ */ /* 查询数据
*/ struct tree *search_btree(struct tree *root,char key)/* struct tree *root:要查询的二叉树首地址
char key:要查询的数据
*/ {
tree *t;t=root;if(!t)
// 如果二叉树指针为空，输出Empty btree {
printf(” Empty btree！!n“);
return root;
}
while(t->info!=key)
{
if(keyinfo)
// 按照”左结点
t=t->left;
else
t=t->right;
if(t==0)
// 如果指针为空，则退出查找
光信0804廖娟
U200813197
{
printf(“ Search Failure！!n”);
break;
} } /* while(root->info!=key)*/ if(t!=0)
// 如果二叉树指针不为空，即查找成功给出信息，返回
printf(“ Succeful search！!n key=%cn”,t->info);return root;} /* *search_btree(root,key)*/
/* O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ */ /* 打印二叉树
*/ void print_btree(struct tree *r,int l)/* struct tree *r:二叉树首地址
int l:当前结点的高度，根结点为0
输出的二叉树为正常树逆旋转90°后成镜像的结果
*/ {
int i;if(r == 0)
return;
//如果传入指针为0，则返回
print_btree(r->left,l+1);
//打印左结点
for(i=0;i
printf(“ ”);
//打印空格，用来排版控制格式
printf(“%cn”,r->info);
//打印根结点
print_btree(r->right,l+1);
//打印右结点 } /*
*print_btree(root,0)
*/
/* O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ */ /* 先序遍历
*/ void PreorderTraversal(struct tree *root){ if(root==0)
return;printf(“%c”,root->info);PreorderTraversal(root->left);PreorderTraversal(root->right);}
软件课程设计
2010年1月
/* O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ */ /* 中序遍历
*/ void InorderTraversal(struct tree *root){ if(!root)
return;InorderTraversal(root->left);printf(“%c”,root->info);InorderTraversal(root->right);}
/* O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ O(∩_∩)O~ */ /* 后序遍历
*/ void PostorderTraversal(struct tree *root){ if(!root)
return;PostorderTraversal(root->left);PostorderTraversal(root->right);printf(“%c”,root->info);}
参考文献
《数据结构》（c语言版）严蔚敏
吴伟民 编著 清华大学出版社 《C语言程序设计》 谭浩强 编著 清华大学出版社 《C程序上机指导》 谭浩强 编著 清华大学出版社
《标准c语言程序设计及应用》 周纯杰 编著 华中科技大学出版社
