10计本《数据结构课程设计报告》1.docx

10计本《数据结构课程设计报告》1.docx

《10计本《数据结构课程设计报告》1.docx》由会员分享，可在线阅读，更多相关《10计本《数据结构课程设计报告》1.docx（18页珍藏版）》请在冰点文库上搜索。

10计本《数据结构课程设计报告》1

安徽省巢湖学院计算机与信息工程学院

课程设计报告

课程名称《数据结构》

课题名称二叉排序树

专业计算机科学与技术

班级

学号

姓名xxxx

联系方式

指导教师xxxxx

2011年12月25日

目录

1、数据结构课程设计任务书１

1.1、题目１

1.2、要求１

2、总体设计１

2.1、功能模块设计１

2.2、所有功能模块的流程图１

3、详细设计１

3.1、程序中所采用的数据结构及存储结构的说明１

3.2、算法的设计思想２

4、调试与测试：

２

4.1、调试方法与步骤：

２

4.2、测试结果的分析与讨论：

３

5、时间复杂度的分析：

４

6、源程序清单和执行结果４

7、C程序设计总结８

8、致谢８

9、参考文献８

1.数据结构课程设计任务书

1.1、题目

二叉排序树

1.2、要求

（1）用BiTreeCreatBST创建二叉排序树模块；

（2）用DeleteNode实现删除模块；

（3）用voidInsertBST1实现插入模块；

（4）用BiTreesearchBST1实现查找模块 ；

2.总体设计

2.1、功能模块设计

根据课程设计题目的功能要求，各个功能模块的组成框图如下：

3.详细设计

3.1程序中采用的数据结构及储存结构说明：

模块功能说明：

如函数功能、入口及出口参数说明，函数调用关系描述等；

1）主函数模块

Main（）

{

建立n个关键字的二叉排序树并输出；

从二叉树排序树T中删除任意结点,其关键字为key；

在二叉树排序树T中，插入一个结点t,其关键字为key；

在二叉排序树T中递归查找关键字等于key2的数据元素；

}

2）创建二叉排序树模块

BiTreeCreatBST（intn）

{

建立n个关键字的二叉排序树；

从键盘输入调建立n个关键字依次用InsertBST1（插入函数）；

返回根结点T；

输出过程；

}

3）删除模块

DeleteNode（BiTree&T,intx）

{

从二叉树排序树T中删除任意结点,其关键字为x；

可以实现删除根结点、叶子结点以及其它任意结点的功能；

}

4）插入模块

voidInsertBST1（BiTree&T,BiTNode*s）

{

在二叉树排序树T中，插入一个结点s（递归算法）；

被CreatBST函数调用；

}

5）查找模块

BiTreesearchBST1（BiTreeT,TElemTypekey）

{

在根指针T所指二叉排序树中递归查找关键字等于key的数据元素；

若成功，返回指向该数据元素结点的指针；

否则返回空指针；

}

3.2算法的设计思想

1、二叉排序树的查找，即给定值先与根结点比较，若相等则查找成功，否则根据根据他们之间的大小关系，分别在左子树或右子树查找。

2、二叉排序树的插入，插入的一定是叶子结点，根据查找结果决定插入位置。

3、二叉排序树的删除分三种情况：

1）若*p结点为叶子结点，即PL和PR均为空树。

由于删除叶子结点不破坏整棵树的结构，则只需改其双亲结点的指针即可。

2）若*p结点只有左子树PL或者只有右子树PR，此时只要令PL或PR直接成为其双亲结点*f的左子树即可。

3）若*p的左右子树均不空。

令*p的左子树为*s的左子树，*p的右子树为*s的右子树，如图。

4、调试与测试

4.1、调试方法与步骤：

第一步：

创建一个二叉树；

第二步：

查找一个结点；

第三步：

删除一个结点；

第四步：

插入一个结点；

4.2、测试结果的分析与讨论：

1,程序运行时菜单显示如下：

当输入的二叉树序列为：

{2,6,9,8,4}时，创建二叉排序树，并输出结果如下：

1.查找9结点时，运行结果如下：

2.删除结点6时运行结果如下：

3.插入结点7时运行结果如下：

5、时间复杂度的分析：

a）查找

由于查找需要访问所有结点，故时间复杂度为O（t）

b）删除

删除需要访问结点找到所要删除的结点，则时间复杂度是O（t）

c）插入

由于插入结点处即为查找和删除的结点处，即O（t）

6、源程序清单和执行结果

#include

usingnamespacestd;

typedefintKeyType;

typedefstructtree//声明树的结构

{

structtree*left;//存放左子树的指针

structtree*right;//存放又子树的指针

KeyTypekey;//存放节点的内容

}BSTNode,*BSTree;//声明二叉树的链表

BSTreeinsertBST（BSTreetptr,KeyTypekey）//在二叉排序树中插入结点

{//若二叉排序树tptr中没有关键字为key的结点，则插入，否则直接返回

BSTreef,p=tptr;//p的初值指向根结点

while（p）//查找插入位置，循环结束时，p是空指针，f指向待插入结点的双亲

{

if（p->key==key）//树中已有key，无须插入

returntptr;

f=p;//f保存当前查找的结点，即f是p的双亲

p=（keykey）?

p->left:

p->right;

}

p=（BSTree）malloc（sizeof（BSTNode））;//生成新结点

p->key=key;p->left=p->right=NULL;

if（tptr==NULL）//原树为空，新插入的结点为新的根

tptr=p;

else

if（keykey）

f->left=p;

else

f->right=p;

returntptr;

}

BSTreecreateBST（）//建立二叉树

{

BSTreet=NULL;//根结点

KeyTypekey;

cin>>key;

while（key!

=-1）

{

t=insertBST（t,key）;

cin>>key;

}

returnt;

}

voidinorder_btree（BSTreeroot）//中序遍历打印二叉排序树

{

BSTreep=root;

if（p!

=NULL）{

inorder_btree（p->left）;

cout<<""<key<<"";

inorder_btree（p->right）;

}

}

intsearchBST（BSTreet,KeyTypekey）//查找

{

if（key==t->key）

return1;

if（t==NULL）

return0;

if（keykey）

returnsearchBST（t->left,key）;

else

returnsearchBST（t->right,key）;

}

BSTreedeleteBST（BSTreetptr,KeyTypekey）//删除

{

BSTreep,tmp,parent=NULL;

p=tptr;

while（p）

{

if（p->key==key）

break;

parent=p;

p=（keykey）?

p->left:

p->right;

}

if（!

p）returnNULL;

tmp=p;

if（!

p->right&&!

p->left）/*p的左右子树都为空*/

{

if（!

parent）//要删根，须修改根指针

tptr=NULL;

elseif（p==parent->right）

parent->right=NULL;

else

parent->left=NULL;

free（p）;

}

elseif（!

p->right）//p的右子树为空，则重接p的左子树

{

p=p->left;

if（!

parent）//要删根，须修改根指针

tptr=p;

elseif（tmp==parent->left）

parent->left=p;

else

parent->right=p;

free（tmp）;

}

elseif（!

p->left）//的左子树为空，则重接p的左子树

{

p=p->right;

if（!

parent）//要删根，须修改根指针

tptr=p;

elseif（tmp==parent->left）

parent->left=p;

else

parent->right=p;

free（tmp）;

}

elseif（p->right&&p->left）//p有左子树和右子树，用p的后继覆盖p然后删去后继

{//另有方法：

用p的前驱覆盖p然后删去前驱||合并p的左右子树

parent=p;//由于用覆盖法删根，则不必特殊考虑删根

p=p->right;

while（p->left）

{

parent=p;

p=p->left;

}

tmp->key=p->key;

if（p==parent->left）

parent->left=NULL;

else

parent->right=NULL;

free（p）;

}

returntptr;

}

intmain（）

{

KeyTypekey;

intflag,test;

charcmd;

BSTreeroot;

do

{

cout<<"\n\n"<

cout<<"\t\t*******请选择你要执行的操作:

********"<

cout<<"\n"<

cout<<"\t\tC.创建一棵二叉排序树\n";

cout<<"\t\tE.结束本程序\n";

cout<<"\n\n\t\t************************************"<

flag=0;

do

{

if（flag!

=0）

cout<<"选择操作错误！

请重新选择！

\n";

fflush（stdin）;

cin>>cmd;

flag++;

}while（cmd!

='c'&&cmd!

='C'&&cmd!

='a'&&cmd!

='A'）;

if（cmd=='c'||cmd=='C'）

{

cout<<"请输入你所要创建的二叉树的结点的值，以-1结束：

\n";

root=createBST（）;

do

{

flag=0;

cout<<"\n\n中序遍历二叉树：

"<

inorder_btree（root）;

cout<<"\n"<

cout<<"\t\t************请选择你要对这棵二叉树所做的操作:

**************"<

cout<<"\t\t****"<

cout<<"\t\t**S......查找你想要寻找的结点**"<

cout<<"\t\t**I......插入你想要插入的结点**"<

cout<<"\t\t**D......删除你想要删除的结点**"<

cout<<"\t\t**Q......结束对这棵二叉树的操作**"<

cout<<"\t\t****"<

cout<<"\t\t***********************************************************"<

do{

if（flag!

=0）

cout<<"选择操作错误！

请重新选择！

\n";

fflush（stdin）;

scanf（"%c",&cmd）;

flag++;

}while（cmd!

='s'&&cmd!

='S'&&cmd!

='i'&&cmd!

='I'&&cmd!

='d'&&cmd!

='D'&&cmd!

='q'&&cmd!

='Q'）;

switch（cmd）

{

case's':

case'S':

cout<<"请输入你要查找结点的关键字：

\n";

cin>>key;

test=searchBST（root,key）;

if（test==0）

cout<<"\n对不起，你所查找的结点"<

";

else

cout<<"\n成功找到结点\n"<

break;

case'i':

case'I':

cout<<"请输入你要插入结点的关键字：

\n";

cin>>key;

root=insertBST（root,key）;//注意必须将值传回根

break;

case'd':

case'D':

cout<<"请输入你要删除结点的关键字：

\n";

cin>>key;

root=deleteBST（root,key）;//注意必须将值传回根

if（root==NULL）

cout<<"\n对不起，你所删除的结点"<

\n";

else

cout<<"\n成功删除结点"<

break;

}

}while（cmd!

='q'&&cmd!

='Q'）;

}

}while（cmd!

='e'&&cmd!

='E'）;

return0;

}

7、C程序设计总结

通过这次的实验，我认识到：

仅仅掌握课本上的知识是不够的，在实际操作时，常常遇到一些问题，自己看不懂，更无法解决。

不过，经过自己不断的思考，尝试着去更改代码中出现的问题。

虽然开始很困难，但在老师和同学的帮助下，我逐渐的熟悉了许多操作，为后继工作的顺利进行做了准备。

个人的力量是薄弱的，我学会了咨询别人，不再胆怯，不再保守。

在过程中和同学相互讨论，询问老师，不断进步。

也许，我们可以说，编一个程仅仅是开始，调试和运行相比之下更难。

实践中收获的远比想象的多。

看到自己完成了所要求的任务，有一种无法用言语来形容的欣慰之感，这也是无法从学习书本知识中得到的。

8、致谢

能够完成这次课程设计必须感谢C语言课程老师张步群和C++语言程序设计老师许荣泉。

9、参考文献

[1]严蔚敏，吴伟民，数据结构（C语言版）北京：

清华大学出版社，1997.4

[2]谭浩强，C程序设计（第四版），北京：

清华大学出版社，2010.6

[3]郑莉，董渊，何江舟，C++语言程序设计北京：

清华大学出版社，2010.7