数据结构设计说明书.docx
《数据结构设计说明书.docx》由会员分享，可在线阅读，更多相关《数据结构设计说明书.docx（21页珍藏版）》请在冰点文库上搜索。
数据结构设计说明书
摘要
数据结构是研究与数据之间的关系，我们称这一关系为数据的逻辑结构，简称数据结构。
当数据的逻辑结构确定以后，数据在物理空间中的存储方式，称为数据的存储结构。
相同的逻辑结构可以具有不同的存储结构，因而有不同的算法。
本次课程设计，程序中的数据采用“树形结构”作为其数据结构。
具体采用的是“二叉排序树”，并且使用“一维数组”来作为其存储结构。
一维数组顺序表存储结构是用一组地址连续的存储单元依次自上而下、自左而右存储完全二叉树上的结点元素；本课程设计实现了二叉排序树的创建、中序遍历、计算二叉排序树的平均查找长度和删除二叉排序树中某个结点。
本课程主要介绍了本课题的开发背景，所要完成的功能和开发的过程。
重点说明了系统的设计思路、总体设计、各个功能模块的设计与实现方法。
关键词：
二叉排序树的实现；C语言；数据结构；线性表；顺序表；中序遍历。
附录.....................................................................14
A）课题背景的介绍
1.1课题背景
随着经济的迅速发展，各行各业纷纷应用计算机数据信息管理。
当然数据信息是一个很笼统的概念，随着现代信息的大量增加，其处理难度也越来越大，如何对各个数据信息进行更好的树立，这就是我们研究这个课题的目的。
在计算机迅速发展的今天，将计算机这一信息处理器应用于实际数据问题问题的信息计算已是势必所然，而且这也将数据信息处理带来前所未有的改变。
采用计算机对数据的信息处理是信息科学化和现代化的重要标志，它也给各行各业带来了明显的经济效益。
主要体现在：
极大地提高了工作人员的工作效率，大大地减少了以往的手工操作的各种弊端，同时也加强和规范掌握对于数据信息的计算。
1.2目的
本课题运用C语言进行开发，C语言能够简单的进行编译一些程序，来实现对一些问题的解决。
它虽然比较简单的处理一些问题，但却有更高的效率。
它能够被大多数用户所接受，因为它能够呈现出清晰的界面，是人们能够很好的理解。
能在一些方面给人们更好的服务，成为人们的好帮手。
经过这一个学期对《数据结构》的学习，我们都学到了不少东西，可能有些学的还不够理想，但无论如何这些知识都为我们的下一步学习打下了坚实的基础。
做这么一个课程设计，一方面是为了检查我们一个学期以来的学习成果，另一方面也是为了让我们进一步的掌握和运用它，同时也让我们认清自己的不足之处和薄弱环节，加以弥补和加强。
B）需求分析
2.1课程设计题目、任务及要求
C）
D）系统总体设计
3.1系统模块划分
二叉排序树是一种动态树表。
二叉排序树的定义：
二叉排序树或者是一棵空树， 或者是一棵具有如下性质的二叉树：
⑴若它的左子树非空，则左子树上所有结点的值均小于根结点的值；
⑵若它的右子树非空，则右子树上所有结点的值均大于根结点的值；
⑶左、右子树本身又各是一棵二叉排序树。
3.2二叉排序树的生成过程
二叉排序树的生成，采用递归方式的边查找边插入的方式。
如图
3.3主要功能模块设计
程序主要设计了五个功能：
首先是创建二叉排序树，完成后出现任务菜单，菜单中设计了四个模块：
退出，中序遍历，计算平均查找长度和删除结点。
主函数流程如下：
图3.1.1主函数流程图
4系统详细设计
4.1主函数菜单模块
该模块功能主要是给用户提供清晰的可操作界面，易于人机操作，并能很好的调用其他各模块，使程序更加优化，思路更加清晰，结构更加明了，提高了程序的实用性。
其算法如下：
Voidmain（）
{nodeT=NULL;
Intnum;
Intch=0;
Nodep=NULL;
Printf（"pleaseinputalistonumbersendwithzero:
"）;
Do{scanf（"%d,&num"）;
If（!
num）printf（"youhavefinishedyourinput!
\n"）;
ElseinsertBST（&T,num）;
}while（num）;
Printf（"\n\n--themenuoftheopperation---\n"）;/*主程序菜单*/
Printf（"\n0:
exit"）;
Printf（"\n1:
inordertravelthetree"）;
Printf（"\n2:
delete"）;
While（ch==ch）
{printf（"\nchoosetheopperationtocontinue:
"）;
Scanf（"%d，&ch"）;
Switch（ch）{
Case0:
exit（0）;/*0--退出*/
Case1:
printf（"Theresultofinordertraverseis:
\n"）;
InorderTraverse（&T）;/*1--中序遍历*/
Break;
Case2:
printf（"Pleaseinputthenumberyouwanttodelete:
"）;
Scanf（"%d,&num"）;/*3--删除某个结点*/
If（searchBST（T,num,NULL,&p））
{
T=delete（T,num）;
Printf（"Youhavedeletethenumbersuccessfully!
\n"）;
InorderTravers（&T）;
}
Elseprintf（"Nonode%dyouwanttodelete!
",num）;
Break;
Default:
printf（"Youinputiswrong!
Pleaseinputagain!
\n"）;
Break;
Default:
printf（"Yourinputiswrong!
Pleaseinputagain!
\n"）;
Break;/*输入无效字符*/
}
}
}
4.2查找模块
该模块是给用户提供查找功能。
其查找过程是：
若二叉排序树为空，则查找失败，结束查找，返回信息NULL；否则，将要查找的值与二叉排序树根结点的值进行比较，若相等，则查找成功，结束查找，返回被查找到结点的地址，若不等，则根据要查找的值与根结值的大小关系决定时到根结点的左子树还是右子树中继续查找（查找过程同上），直到查找成功或者查找失败为止。
其算法如下:
scarchBST（node,intkey,nodef,node*p）/*查找函数*/
{
If（!
t）{*p=f;return
（1）;}/*查找不成功*/
Elseif（key==t->data）searchBST（t->lchild,key,t,p）;/*在左子树中继续查找*/
ElsesearchBST（t->rchild,key,t,p）;/*在右子树中继续查找*/
}
4.3插入模块
在二叉排序树种插入新结点，要保证插入后的二叉树仍符合二叉排序树的定义。
插入过程；若二叉排序树为空，则待插入结点*p作为根结点插入到空树中；当非空时，将待插结点关键字p->item和树根关键字t->item进行比较，若p->item=t->item，则无须插入，若p->itemitem，则插入到根的左子树中，若p->item>t->item，则插入到根的右子树中。
而子树种的插入过程和在树中的插入过程相同，如此进行下去，直到把结点*p作为一个新的树叶插入到二叉排序树中，或者直到发现数已有相同关键字的结点为止。
其算法如下：
insertBST（node*t,intkey）/*插入函数*/
{
Nodep=NULL,s=NULL;
If（!
searchBST（*t,key,NULL,&p））/*查找不成功*/
{
S=（node）malloc（size（BSTnode））;
S->data=key;
S->lchild=s->rchild=NULL;
If（!
p）*t=s;/*被插结点*s为新的根结点*/
Elseif（keydata）p->lchild=s;/*被查结点*s为左孩子*/
Elsep->rchild=s;/*被插结点*s为右孩子*/
Return
（1）；
}
Elsereturn（0）;/*树中已有关键字相同的结点，不再插入*/
}
4.4中序遍历模块
遍历（Traversal）是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。
访问结点所做的操作依赖于具体的应用问题。
二叉树共有三个部分组成，即根结点，根结点的左子树，根结点的右子树。
限定以从左至右方式共有三种遍历方式，即前序遍历，中序遍历，后序遍历。
中序遍历的原则：
若被遍历的二叉树为非空，则依次执行如下操作：
A）以中序遍历方式遍历左子树；
B）访问根结点；
C）以中序遍历方式遍历右子树。
其算法如下：
inorderTraverse（node*t）/*中序遍历函数*/
{
If（*t）{
If（inorderTraverse（&（*t）->lchild））/*中序遍历根的左子树*/
Printf（"%d",（*t）->data）;/*中序遍历根的右子树*/
}
Return
（1）;
}
4.5删除模块
删除模块：
删除结点函数，采用边查找边删除的方式。
如果没有查找到，则不对树做任何的修改；如果查找到结点，则分四种情况分别进行讨论：
E）该结点左右子树均为空，可以直接进行删除；
F）该结点仅左子树为空，右子树不为空，用右子树的根结点取代被删除结点的位置；
G）该结点仅右子树为空，左子树不为空；
H）该结点左右子树均不为空，找到被删除结点右子树中最小的结点，并用该结点取代被删除节点的位置。
其算法如下：
NodeDelete（node,intkey）/*删除函数*/
{
Nodep=t,q=NULL,s,f;
While（p!
=NULL）/*查找要删除的点*/
{
If（p->data==key）break;
Q=p;
If（p->data>key）p=p->lchild;
Elsep=p->rchild;
}
If（p==NULL）returnt;/*查找失败*/
If（p->lchild==NULL）/*p指向当前要删除的结点*/
{
If（q==NULL）t=p->rchild;/*q指向要删除的父母*/
Elseif（q->lchild==p）q->lchild=p->rchild;/*p为q的左孩子*/
Elseq->rchild=p->rchild;/*p为q的右孩子*/
Free（p）;
}
Else{/*p的左孩子不为空*/
F=p;
S=p->lchild;
While（s->rchild）/*左拐后向右走到底*/
{
F=s;
S=s->rchild;
}
If（f==p）f->lchild;/*重接f的左子树*/
Eslef->rchild=s->lchild/*重接f的右子树*/
P->data=s->data;
Free（s）;
}
Returnt;
}
5系统连编与运行
一个应用系统设计和创建完成后，还必须进行连编，以便生成一个可执行文件供最终用户使用。
连编完成后还要运行，以检查整个系统的完整性和准确性，同时还可增加程序代码的保密性。
（1）先进行编译，编译过之后再选择计算机运行。
如图9所示：
6总结
通过这次课程设计我也着实又感受了一次编程的乐趣，从中也学到了不少知识。
我在学习运用数据结构编程之前，并没能深刻体会到这一点，直到这次课程设计，我才有所领悟。
这次实验中我也出现过一些比较严重的错误。
在用一维数组顺序表结构编写程序时我错误的运用静态链表来实现函数功能。
这是我对基本概念理解的模糊不清造成的。
我原以为只要采用一维数组作为存储结构它就一定也是顺序表结构，而实质上这根本是两个不相干的概念。
后来在同学的指点下我意识到自己的错误。
不过收获也很不少。
至少我又练习了运用静态链表来实现同样的功能，同时我也发现两者在很多函数上是互通的，只需稍作修改即可移植。
另外程序的不足之处是不能实现对0这个数字的存储，可以通过改变数字的存储结构方式来实现，如使用二叉链表来作为数据的存储结构，即可实现该功能。
总之，我会继续我的兴趣编写程序的，相信在越来越多的尝试之后，自己会不断进步不断提高的。
参考文献
[1]谭浩强.C程序设计[M].北京：
清华大学出版社.2005.
[2]严蔚敏.数据结构（C语言版）[M].北京：
清华大学出版社.2008.
[3]陈雁.数据结构[M].北京：
高等教育出版社，2004.
[4]张磊.C程序设计教程.北京：
中国铁道出版社.2007.
[5]冯舜玺.数据结构与算法分析—C语言描述（原书第2版）.北京：
机械工业出版社，2004.1
[6]张海藩.《软件工程》，清华大学出版社，2008
[7]杨明军、董亚卓、汪黎.《C++实用教程（第一版）》.人民邮电出版社.2002
[8]张荣梅、梁晓林.《VisualC++实用教程（第一版）》.冶金工业出版社.2004
附录
二叉链表存储结构:
1.源程序:
#include
#include
usingnamespacestd;
boolrut=false;
classjie{
public:
intdata;
jie*left;
jie*right;
};
voidinsert1（jie**root,jie*s）//插入
{
if（*root==NULL）{*root=s;}
elseif（（*root）->data>s->data）insert1（&（*root）->left,s）;
elseinsert1（&（*root）->right,s）;
}
voidcreate（jie**root,intn,inta[]）//以数组A构造二叉树（root为根）
{
jie*s;
for（inti=1;i<=10;i++）
{
s=newjie;
s->data=a[i];
s->left=NULL;s->right=NULL;
insert1（&（*root）,s）;
//*root=s;
}
//cout<<"checksuccessfully\n";
}
voidcheck（jie*root,intkey）//检查某节点是否存在在以root为根的树里
{
if（root->data==key）rut=true;
elseif（root==NULL）rut=false;
elseif（root->data>key&&root->left!
=NULL）check（root->left,key）;
elseif（root->dataright!
=NULL）check（root->right,key）;
}
voidergotic（jie*root）//中序遍历
{
jie*p=root;
if（p!
=NULL）
{
ergotic（p->left）;
cout<data<<"\t";
ergotic（p->right）;
}
}
jie*fin（jie*root）//找以root为根的最左的不为空的节点的父节点
{
jie*q=root;
jie*p=q;
while（q->left!
=NULL）{p=q;q=q->left;}
returnp;
}
voiddel（jie*root,intkey）//删除节点
{
jie*q=root;jie*f=q;
while（q->data!
=key&&q!
=NULL）
{
if（q->data>key）{f=q;q=q->left;}
else{f=q;q=q->right;}
}
if（q!
=NULL&&f->left==q）//q是其父节点f的左孩子时
{
jie*find,*p=NULL;
if（q->left==NULL&&q->right==NULL）f->left=NULL;
elseif（q->left!
=NULL&&q->right==NULL）{f->left=q->left;}
elseif（q->right->left!
=NULL）
{find=fin（q->right）;p=find->left;find->left=NULL;p->left=q->left;p->right=q->right;f->left=p;}
elseif（q->right->left==NULL）{q->right->left=q->left;f->left=q->right;}
}
elseif（q!
=NULL&&f->right==q）//q是其父节点f的右孩子时
{
jie*find,*p=NULL;
if（q->left==NULL&&q->right==NULL）f->right=NULL;
elseif（q->left!
=NULL&&q->right==NULL）{f->right=q->left;}
elseif（q->right->left!
=NULL）
{find=fin（q->right）;p=find->left;find->left=NULL;p->left=q->left;p->right=q->right;f->right=p;}
elseif（q->right->left==NULL）{q->right->left=q->left;f->right=q->right;}
}
}
intmain（）
{
inta[11];//a[0]忽略不用
printf（"请输入11个整数:
\n"）;
inti=1;
for（i=1;i<=10;i++）
{
scanf（"%d",&a[i]）;
}
system（"cls"）;
cout<<"在插入二叉排序树之前的序列顺序：
\n";
for（i=1;i<=10;i++）
cout<cout<<"\n";
jie*root=NULL;//定义二叉树的根
create（&root,10,a）;//以数组a，以root为根构造二叉排序树
cout<<"二叉排序树构造成功！
\n";
if（root==NULL）cout<<"空树\n";//p=root;
cout<<"中序遍历此二叉排序树，结果为：
\n";
ergotic（root）;cout<<"\n";//中序遍历
cout<<"请输入要删除的关键字：
\n";
intsun;cin>>sun;
check（root,sun）;
if（rut==false）cout<<"你输入的关键字不在树里\n";
else{del（root,sun）;cout<<"删除以后中序遍历得到的结果为：
\n";ergotic（root）;}
cout<<"\n";
return0;
}
运行效果:
升级会员 