软件综合算法设计报告.docx

软件综合算法设计报告.docx

《软件综合算法设计报告.docx》由会员分享，可在线阅读，更多相关《软件综合算法设计报告.docx（28页珍藏版）》请在冰点文库上搜索。

软件综合算法设计报告

软件综合算法设计说明书

项目名称:

用顺序和二叉链表作存储结构实现二叉排序树

学院名称:

信息与电气工程学院

学生姓名:

XXX

学生学号:

XXX

专业班级:

计算机科学与技术XXX班

同组人员：

XXX

指导教师:

XXX

摘要

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。

本课程设中的二叉排序树，可以用顺序存储和链式存储两种算法计算。

本课程设中的二叉排序树，一共要实现四项基本的功能。

它们分别是二叉搜索树的创建、中序遍历、查找结点和删除结点。

关键词：

二叉排序树；中序遍历；搜索结点；删除结点；C\C++

目录

一、第一章课题介绍…………………………………………………3

1.课题背景…………………………………………………………3

2.课题目的…………………………………………………………3

3.课程设计的要求…………………………………………………3

二、第二章课程设计的需求分析……………………………………3

1.问题分析和任务定义……………………………………………3

2.设计任务流程……………………………………………………3

3.课程设计思想……………………………………………………5

4.逻辑设计…………………………………………………………5

4.1.主要函数……………………………………………………5

4.2.各函数之间的流程图………………………………………5

5.物理设计…………………………………………………………9

5.1.二叉排序树…………………………………………………9

5.2.中序遍历…………………………………………………10

5.3.查找………………………………………………………11

5.4.删除………………………………………………………11

5.5.插入………………………………………………………13

三、第三章程序设计………………………………………………14

1.源代码…………………………………………………………14

2.各功能截图……………………………………………………20

3.结果分析………………………………………………………21

四、体会总结…………………………………………………………22

五、参考文献…………………………………………………………22

第一章课题介绍

1课题背景

随着经济的迅猛发展，各行各业纷纷应用计算机数据管理。

在计算机迅猛发展的今天，将计算机这一信息处理器应用于实际数据问题已是势必所然。

采用计算机对数据信息的处理是信息现代化和科学化的重要标志。

2课题目的

本课题运用c语言编写一些简易的程序来实现对一些问题的解决，检验本学期数据结构课程的掌握度。

让学生了解并掌握软件算法设计的方法与步骤，具备初步的独立分析问题、解决问题的能力。

积累项目设计及程序调试、测验的经验，提高综合运用的能力，培养软件工作者所具备的科学工作方法和作风。

3课程设计的要求

简要描述题目要求，选定数据结构，写出算法，上机调试出正确的代码，总结和整理实验报告。

第二章课程设计的需求分析

1问题分析和任务定义

用顺序和二叉链表作存储结构实现二叉排序树：

（1）以回车（'\n'）为输入结束标志,输入数列L，生成一棵二叉排序树T；

（2）对二叉排序树T作中序遍历，输出结果；

（3）输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历（执行操作2）；否则输出信息“无x”。

2设计任务流程

NO!

无结点x

存在含x的结点，则删除该结点，并作中序遍历

输入元素x，查找二叉排序树T

OK!

图1任务流程图

3课程设计思想

建立二叉排序树采用边查找边插入的方式。

查找函数采用递归的方式进行查找。

如果查找到相等的则插入其左子树。

然后利用插入函数将该元素插入原树。

对二叉树进行中序遍历采用递归函数的方式。

在根结点不为空的情况下，先访问左子树，再访问根结点，最后访问右子树。

删除结点函数，采用边查找边删除的方式。

如果没有查找到，进行提示；如果查找到结点则将其左子树最右边的节点的数据传给它，然后删除其左子树最右边的节点。

4逻辑设计

4.1主要函数

SearchBT（）

InsertBT（）

InorderTraverse（）

Delete（）

Main（）

4.2各函数之间的流程图

插入子函数InsertBT（）的流程图：

图2子函数InsertBT（）的流程图

主函数流程图：

图3主函数流程图

子函数SearchBT（）的流程图

图4子函数SearchBT（）的流程图

子函数InorderTraverse（）流程图

No

Repeat

Yes

Repeat

图5子函数中序遍历的流程图

5物理设计

5.1二叉排序树

二叉排序树的定义：

二叉排序树或者是一棵空树， 或者是一棵具有如下性质的二叉树：

（1）每个结点都有一个作为搜索依据的关键码（key），所有结点的关键码互不相同；

（2）若它的左子树非空，则左子树上所有结点的值均小于根结点的值；

（3）若它的右子树非空，则右子树上所有结点的值均大于根结点的值；

（4）左、右子树本身又各是一棵二叉排序树

顺序存储结构：

typedefstructTnode{

    int  data;                      

struct  Tnode    *lchild,*rchild;    

    }*node,BSTnode;

链式存储结构：

typedefstructnode//记录类型

{

KeyTypekey;//关键字项

InfoTypedata;//其他数据域

structnode*lchild,*rchild;//左右孩子指针

}BTNode;

5.2二叉排序树的中序遍历（以顺序为例）

中序遍历二叉树算法的框架是：

若二叉树为空，则空操作；否则

中序遍历左子树（L）；

访问根结点（V）；

中序遍历右子树（R）。

中序遍历二叉树也采用递归函数的方式，先访问左子树,然后访问根结点,最后访问右子树.直至所有的结点都被访问完毕。

核心代码：

statusInorderTraverse（node*t）/*中序遍历函数*/

{

if（*t）{

if（InorderTraverse（&（*t）->lchild））/*中序遍历根的左子树*/

printf（"%d",（*t）->data）;/*输出根结点*/

if（InorderTraverse（&（*t）->rchild））;/*中序遍历根的右子树*/

}

returnOK;

}

5.3二叉排序树中元素的查找（以顺序为例）

在二叉排序树上进行查找，是一个从根结点开始，沿某一个分支逐层向下进行比较判等的过程。

若二叉排序树为空，则查找失败。

否则，将根结点的关键字与待查关键字进行比较，若相等，则查找成功；若根节点关键字大于待查值，则进入左子树重复次步骤，否则，进入右子树进行此步骤；若在查找过程中遇到二叉排序树的叶子节点时，还没有找到待查节点，则查找不成功。

核心代码：

statusSearchBT（nodet,intkey,nodef,node*p）/*查找函数*/

{

if（!

t）

{*p=f;returnERROR;}/*查找不成功*/

else

if（key==t->data）{*p=t;returnOK;}/*查找成功*/

else

if（keydata）SearchBT（t->lchild,key,t,p）;/*在左子树中继续查找*/

else

SearchBT（t->rchild,key,t,p）;/*在右子树中继续查找*/

}

5.4二叉排序树中元素的删除（以顺序为例）

对于二叉排序树，删去树上的一个结点相当于删去有序序列中的一个记录，只要在删除某个结点之后依旧保持二叉排序树的特性即可。

在二叉排序树中删除节点，首先要进行查找操作，以确定被删除的节点是否在二叉排序树中。

若不在，则不做任何操作；否则，假设要删除的节点为*p，节点*p的父节点为*f，并假设*p是*f的左孩子。

根据被删除节点*p有无孩子，删除部分可做以下3中情况讨论：

（1）若*p为叶子节点，则可令其父节点*f的左孩子指针域为空，直接将其删除。

（2）若*p节点只有右子树或左子树，则可以将p的左子树或右子树直接改为其双亲节点f的左子树。

（3）若*p既有左子树又有右子树；将节点*s为*p的中序前驱。

首先找到*p的中序前驱节点*s，然后用节点*s的值代替节点*p的值，再将节点*s删除，节点*s的原左子树改为*s的双亲节点*q的右子树；

核心代码：

nodeDelete（nodet,intkey）/*删除函数*/

{

nodep=t,q=NULL,s,f;

while（p!

=NULL）/*查找要删除的点*/

{

if（p->data==key）

break;

q=p;

if（p->data>key）p=p->lchild;

else

p=p->rchild;

}

if（p==NULL）

returnt;/*查找失败*/

if（p->lchild==NULL）/*p指向当前要删除的结点*/

{

if（q==NULL）t=p->rchild;/*q指向要删结点的父母*/

else

if（q->lchild==p）q->lchild=p->rchild;/*p为q的左孩子*/

else

q->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=s->lchild;/*重接f的左子树*/

elsef->rchild=s->lchild;/*重接f的右子树*/

p->data=s->data;

free（s）;

}

returnt;

}

5.5二叉排序树的插入（以顺序为例）

在二叉排序树中插入一个新节点，首先要查找该节点在二叉排序树中是否已经存在。

若二叉排序树中不存在关键字等于x的节点，则插入。

将一个关键字值为x的节点s插入到二叉排序树中，可以用下面的方法：

（1）若二叉排序树为空，则关键字为x的节点s成为二叉排序树的根

（2）若二叉排序树非空，则将x与二叉排序树根进行比较，如果x的值等于根节点关键值，则停止插入；如果x的根节点值小于根节点关键值，则将x插入左子树；如果x的值大于根节点关键字的值，则将x插入右子树。

在左右两个子树的插入方法与整个二叉排序树相同。

核心代码：

statusInsertBT（node*t,intkey）/*插入函数*/

{

nodep=NULL,s=NULL;

if（!

SearchBT（*t,key,NULL,&p））/*查找不成功*/

{

s=（node）malloc（sizeof（BTnode））;

s->data=key;

s->lchild=s->rchild=NULL;

if（!

p）*t=s;/*被插结点*s为新的根结点*/

else

if（keydata）p->lchild=s;/*被插结点*s为左孩子*/

elsep->rchild=s;/*被插结点*s为右孩子*/

returnOK;

}

else

returnERROR;/*树中已有关键字相同的结点，不再插入*/

}

第三章程序设计

1源代码

经过上机调试，通过的源代码如下：

（1）用顺序存储实现：

#include"stdio.h"

#include"stdlib.h"

#include"stddef.h"

//定义常量

#defineOK1

#defineERROR0

//定义数据类型

typedefintstatus;

//定义数据结构

typedefstructTnode{

intdata;//输入的数据

structTnode*lchild,*rchild;//结点的左右指针，分别指向结点的左右孩子

}*node,BTnode;

statusSearchBT（nodet,intkey,nodef,node*p）//查找函数

{

if（!

t）

{*p=f;returnERROR;}//查找不成功

elseif（key==t->data）{*p=t;returnOK;}//查找成功

elseif（keydata）SearchBT（t->lchild,key,t,p）;//在左子树中继续查找

else

SearchBT（t->rchild,key,t,p）;//在右子树中继续查找

}

statusInsertBT（node*t,intkey）//插入函数

{

nodep=NULL,s=NULL;

if（!

SearchBT（*t,key,NULL,&p））//查找不成功

{

s=（node）malloc（sizeof（BTnode））;

s->data=key;

s->lchild=s->rchild=NULL;

if（!

p）*t=s;//被插结点*s为新的根结点

else

if（keydata）p->lchild=s;//被插结点*s为左孩子

elsep->rchild=s;//被插结点*s为右孩子

returnOK;

}

else

returnERROR;//树中已有关键字相同的结点，不再插入

}

statusInorderTraverse（node*t）//中序遍历函数

{

if（*t）{

if（InorderTraverse（&（*t）->lchild））//中序遍历根的左子树

printf（"%d",（*t）->data）;//输出根结点

if（InorderTraverse（&（*t）->rchild））;//中序遍历根的右子树

}

returnOK;

}

nodeDelete（nodet,intkey）//删除函数

{

nodep=t,q=NULL,s,f;

while（p!

=NULL）//查找要删除的点

{

if（p->data==key）

break;

q=p;

if（p->data>key）p=p->lchild;

else

p=p->rchild;

}

if（p==NULL）

returnt;//查找失败

if（p->lchild==NULL）//p指向当前要删除的结点

{

if（q==NULL）t=p->rchild;//q指向要删结点的父母

else

if（q->lchild==p）q->lchild=p->rchild;//p为q的左孩子

else

q->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=s->lchild;//重接f的左子树

elsef->rchild=s->lchild;//重接f的右子树

p->data=s->data;

free（s）;

}

returnt;

}

voidmain（）

{

nodeT=NULL;

intnum;

ints=0,j=0,i=0;

intch=0;

nodep=NULL;

printf（"PleaseInputnumbers（以0结束）\n"）;

do{

scanf（"%d",&num）;

if（!

num）printf（"完成输入!

\n"）;

elseInsertBT（&T,num）;

}while（num）;

printf（"\n1:

选择中序输出"）;

printf（"\n2:

选择输入元素\n"）;

while（ch==ch）

{

scanf（"%d",&ch）;

switch（ch）{

case0:

exit（0）;//0－－退出

case1:

printf（"中序遍历输出结果为:

\n"）;

InorderTraverse（&T）;//1－－中序遍历

printf（"\n"）;

break;

case2:

printf（"输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历，否则输出无x="）;

scanf（"%d",&num）;//3－－删除某个结点

if（SearchBT（T,num,NULL,&p））

{

T=Delete（T,num）;

printf（"删除成功!

中序遍历输出：

"）;

InorderTraverse（&T）;

printf（"\nx="）;

}

else

printf（"无此结点",num）;

break;

default:

printf（"无此结点\n"）;

break;//输入无效字符

}

}

}

（2）二叉链表做存储结构：

#include"iostream"

usingnamespacestd;

classnode

{

public:

node（inti）:

data（i）,left（NULL）,right（NULL）{}

voidInorderTraverse（node*&root）//中序遍历

{

if（root!

=NULL）

{

InorderTraverse（root->left）;

printf（"%d",root->data）;

InorderTraverse（root->right）;

}

}

voidInsert（node*&ptr,intitem）//在查找树中插入元素

{

if（ptr==NULL）

ptr=newnode（item）;

elseif（itemdata）

Insert（ptr->left,item）;

elseInsert（ptr->right,item）;

}

node*find（node*&ptr,intitem）//在查找树中查找元素,找到返回所在结点指针，找不到返回空指针。

{

if（ptr==NULL）

returnNULL;

if（ptr->data==item）

returnptr;

elseif（itemdata）

find（ptr->left,item）;

elsefind（ptr->right,item）;

}

node*&findy（node*&ptr,intitem）//在查找树中查找肯定存在的元素,并返回其引用

{

if（ptr->data==item）

returnptr;

elseif（itemdata）

findy（ptr->left,item）;

elsefindy（ptr->right,item）;

}

node*rl（）{returnleft;}

node*rr（）{returnright;}

voidDelete（node*&ptr）//删除值为item所在结点

{

if（ptr->rl（）==NULL&&ptr->rr（）==NULL）

ptr=NULL;

elseif（ptr->rr（）==NULL）

ptr=ptr->rl（）;

else

ptr=ptr->rr（）;

}

private:

intdata;

node*left;//左孩子结点

node*right;//右孩子结点

};

intmain（）

{

intt,i=0,j;

printf（"输入结点个数:

"）;

cin>>t;

cout<<"\n输入"<

";

cin>>j;

node*x=newnode（j）;

for（;i

{

cin>>j;

x->Insert（x,j）;

}

printf（"\n中序遍历为:

"）;

x->InorderTraverse（x）;//作中序遍历

cout<<"\n输入操作（当输入-1时程序结束）"<

printf（"\n选择删除结点x="）;

cin>>j;

while（j!

=-1）

{

node*t=x->find（x,j）;//定位结点

if（t!

=NULL）

{

node*&y=x->findy（x,j）;

x->Delete（y）;

printf（"中序遍历为:

"）;

x->InorderTraverse（x）;

}

elsecout<<"无此结点";

cout<<"\n输入操作（当输入-1时程序结束）:

"<

cin>>j;

}

return0;

}

2各功能截图

图6初始界面（顺序）

图7插入结点界面（顺序）

图8中序遍历二叉树界面（顺序）

图9删除结点的界面（顺序）

图10综合算法界面（链表）

3结果分析

在二叉排序树中插入结点的时间复杂度O（n2）；平均查找长度n+1/2

在二叉排序树中删除结点的时间复杂度O（n2）；平均查找长度n+1/2

体会总结

通过这次课程设计我对二叉排序树更加深刻的理解，对其进行建树，插入，查询，遍历，删除等运算有了更进一步的认识。

为期两周的课程设计，有设计的快乐，也有困扰，其中在三个人的程序合并时出现了难题，组员的不同思想，不同方法，把程序设计弄的很复杂，经过一天的讨论，终于做出了统一的程序。

课程设计中也发现了自己的不足，对课本的认识不够，程序有的没有读明白，研究的不深、不透。

在做实验报告时，对于排版等不是很熟练，还要参考书本。

本程序实现了课程设计的要求，但还有不足的地方，以顺序存储的程序中，必须以0作为结束才可以，希望以后能够解决。

总而言之，这次课程设计给了我很大启发，我明白了