数据结构 实验三.docx

数据结构 实验三.docx

《数据结构 实验三.docx》由会员分享，可在线阅读，更多相关《数据结构 实验三.docx（30页珍藏版）》请在冰点文库上搜索。

数据结构实验三

设计三

树和二叉树

一、设计目的

1.掌握二叉树，二叉树排序数的概念及存储方法。

2.掌握二叉树的遍历算法。

3.熟练掌握编写实现树的各种运算的算法。

4.熟悉图的各种存储方法。

5.掌握遍历图的递归和非递归的算法。

6.理解图的有关算法。

二、设计内容

1．任务描述

1、编写一个程序，用二叉树来表示代数表达式，树的每个结点包括一个运算符，代数表达式由输入得到（其中只包含=，+，-，*，/和用一个字母表示的数且没有错误，并且按照先乘除后加减的原则），并输出表达式的前缀式和后缀式。

2、对于1中的代数表达式二叉树，分别用递归和非递归的方法编写程序完成如下功能：

输出所有的叶子结点的数据项值；输出所有从叶子节点到根结点的路径。

3、对于下图所示的有向图G，编写一个程序完成如下功能：

建立G的邻接表存储结构；输出拓扑排序序列；输出从顶点0开始的深度优先遍历序列（递归算法）和广度优先遍历序列（非递归算法）。

2．问题的表示方案

对任务1、2，使用一个类表示二叉树中各结点，类中的属性包括结点的数据及指向结点左右孩子的指针。

对任务3，使用三个结构体分别表示边、顶点、图。

其中边结构体包括了边上另一顶点的位置、边的权重、下一条边的指针；顶点结构体包括顶点数据及该顶点边链表的头指针；图结构体包括顶点数组及图的顶点、边数量。

1.主要数据类型与变量

任务1、2：

//树的节点

classTnode

{

public:

stringdata;

Tnode*lchild;

Tnode*rchild;

Tnode（）

{

data=string（""）;

lchild=rchild=NULL;

}

Tnode（stringch）

{

data=ch;

lchild=rchild=NULL;

}

Tnode（charch）

{

data=string（""）;

data+=ch;

}

};

任务3：

//边表节点

typedefstructnode

{

intAdjVex;

node*Next;

}EdgeNode;

//顶点节点

typedefstruct

{

intVertex;

EdgeNode*FirstEdge;

}VertexNode;

//边表

typedefVertexNodeAdjList[MAXLENGTH];

2.算法或程序模块

任务1：

intisOperator（charop）

功能:

判断是否为操作符。

intInStackPriority（charc）

功能：

判断操作符的栈内优先级。

intOutStackPriority（charc）

功能：

判断操作符的栈外优先级。

stringToPostfix（stringInfix）

功能：

将输入的中缀表达式转换为后缀表达式。

Tnode*CreateTree（）

功能：

创建二叉树

具体算法：

首先处理输入的X和=，将=作为根节点，X作为其子节点。

然后将除去X和=的后缀表达式进入处理流程：

顺序读取该后缀表达式，遇到操作数则把其值赋给新的结点，压栈；遇到操作符，先把操作符的值赋给新的结点，然后取2个栈顶元素分别设为该结点的左右孩子，再压栈。

voidPostView（ostream&out）

功能：

后序遍历（递归）

voidPreView（ostream&out）

功能：

前序遍历（递归）

任务2：

voidGetLeafRecursive（ostream&out）

功能：

（递归）查找叶结点

voidGetLeaf（ostream&out）

功能：

（非递归）查找叶结点

具体算法：

利用二叉树前序遍历的非递归算法，加入判断条件，若当前结点为叶节点才进行访问。

voidLTR（ostream&out）

功能：

（递归）叶结点到根结点的路径

voidLTRRecursive（ostream&out）

功能：

（非递归）叶结点到根结点的路径

具体算法：

遇到叶节点时，将栈中内容弹出，得到路径；非叶节点则继续向下遍历，并将该节点压栈

任务3：

voidCreate（istream&in,ostream&out）

功能：

初始化

stringTopological_Sort（）

功能：

拓扑排序

voidDFS（ostream&out,intv）

功能：

深度优先遍历

voidBFS（ostream&out,intv）

功能：

广度优先遍历

三、测试

1.方案

任务1、2：

测试数据：

X=（-b+（b^2-4*a*c）^s）/（2*a）

任务3：

直接运行即可

2.结果

四、总结与讨论

本设计还存在的问题有：

1、无法判断输入错误的表达式并结束程序。

2、无法处理等号左边为表达式的情况

可以做的改进：

1、在处理时增加catch块捕捉异常，如果出现异常则说明表达式错误。

2、在处理等号时，将左边的表达式和右边的表达式分开，单独生成树，然后拼接到等号的节点上。

附：

程序模块的源代码

任务一、二：

//树的节点

classTnode

{

public:

stringdata;

Tnode*lchild;

Tnode*rchild;

Tnode（）

{

data=string（""）;

lchild=rchild=NULL;

}

Tnode（stringch）

{

data=ch;

lchild=rchild=NULL;

}

Tnode（charch）

{

data=string（""）;

data+=ch;

}

};

//表达式

classExpression

{

protected:

//中缀表达式

stringInfix;

//后缀表达式

stringPostfix;

//所有节点

stacknodes;

//树根

Tnode*root;

//判断是否是运算符

boolisOperator（charop）

{

if（op=='（'||op=='）'||op=='+'||op=='-'||op=='*'||op=='/'||op=='^'||op=='='）

returntrue;

else

returnfalse;

}

//栈内优先级

intInStackPriority（charc）

{

switch（c）

{

case'（':

return1;

case'+':

case'-':

return3;

case'*':

case'/':

return5;

case'）':

return7;

case'^':

return6;

case'=':

return0;

default:

return-1;

}

}

//栈外优先级

intOutStackPriority（charc）

{

switch（c）

{

case'（':

return7;

case'+':

case'-':

return2;

case'*':

case'/':

return4;

case'^':

return6;

case'）':

return1;

case'=':

return0;

default:

return-1;

}

}

//从中缀表达式转换为后缀表达式

//Infix：

中缀表达式

stringToPostfix（stringInfix）

{

stacka;//操作符栈

a.push（'#'）;

stringpostfix;//结果字符串

inti=0;

charch1;

while（!

a.empty（）&&Infix[i]!

='\0'）//当栈非空且字符串未读取完时循环

{

if（!

isOperator（Infix[i]））//操作数直接加入结果字符串

{

postfix=postfix+Infix[i];

i++;

}

else

{

ch1=a.top（）;//取栈顶操作符

if（InStackPriority（ch1）

{

a.push（Infix[i]）;

i++;

}

elseif（InStackPriority（ch1）>OutStackPriority（Infix[i]））//若栈顶操作符优先级高，则出栈，并加入结果字符串

{

postfix=postfix+ch1;

a.pop（）;

}

else

{

a.pop（）;

if（ch1=='（'）i++;//栈外的“）”与栈内的“（”配对时，直接出栈

}

}

}

while（a.top（）!

='#'）{

postfix=postfix+a.top（）;//将栈中剩余的操作符全部弹出

a.pop（）;

}

returnpostfix;

}

//创建树

Tnode*CreateTree（）

{

//先处理X和=

Tnode*root=newTnode（"="）;

root->lchild=newTnode（Infix[0]）;

Tnode*p=NULL;

stackt;//临时栈

//自下而上生成树

inti=1;

while（Postfix[i]!

='='）

{

if（!

isOperator（Postfix[i]））//操作数则把其值赋给新的结点，压栈

{

p=newTnode（Postfix[i]）;

i++;

t.push（p）;

}

else

{

p=newTnode（Postfix[i]）;//先把操作符的值赋给新的结点，然后取2个栈顶元素分别设为该结点的左右孩子

if（!

t.empty（））

{

p->rchild=t.top（）;//若栈非空则弹栈并设为结点的右孩子

t.pop（）;

}

if（!

t.empty（））

{

p->lchild=t.top（）;//若栈非空则弹栈并设为结点的左孩子

t.pop（）;

}

t.push（p）;//新结点压栈

i++;

}

}

//将其与根节点合并

root->rchild=p;

returnroot;

}

//后序遍历

voidpostOrder（Tnode*p,ostream&out）

{

if（p）

{

postOrder（p->lchild,out）;

postOrder（p->rchild,out）;

out<data;

}

}

//前序遍历

voidpreOrder（Tnode*p,ostream&out）

{

if（p）

{

out<data;

preOrder（p->lchild,out）;

preOrder（p->rchild,out）;

}

}

//（递归）叶结点

voidleafRecursive（Tnode*p,ostream&out）

{

if（p!

=NULL）{

if（p->lchild==NULL&&p->rchild==NULL）

out<data<<"";

else{

leafRecursive（p->lchild,out）;leafRecursive（p->rchild,out）;

}

}

}

//（非递归）叶结点

voidleaf（Tnode*p,ostream&out）

{

stackt;

Tnode*null=newTnode（）;

t.push（null）;

while（p!

=null）

{

if（p->lchild==NULL&&p->rchild==NULL）

{

out<data<<"";

if（!

t.empty（））

{

p=t.top（）;

t.pop（）;

}

}

if（p->rchild!

=NULL）

t.push（p->rchild）;

if（p->lchild!

=NULL）

p=p->lchild;

else

{

if（p->lchild==NULL&&p->rchild==NULL）

out<data<<"";

if（!

t.empty（））

{

p=t.top（）;

t.pop（）;

}

}

}

}

//（递归）叶结点到根结点的路径

voidlpRecursive（Tnode*p,stringt[],intlen,ostream&out）

{

if（p!

=NULL）

{

if（p->lchild==NULL&&p->rchild==NULL）

{

out<data<<"";

for（inti=len-1;i>=0;i--）

out<

out<

}

else

{

t[len]=p->data;

len++;

lpRecursive（p->lchild,t,len,out）;

lpRecursive（p->rchild,t,len,out）;

len--;

}

}

}

//（非递归）叶结点到根结点的路径

voidlp（Tnode*p,ostream&out）

{

structSnode

{

Tnode*ptr;

booltag;

};

Snodew,t;

stacks;

stacktmp;

do

{

while（p!

=NULL）

{

w.ptr=p;w.tag=0;s.push（w）;

p=p->lchild;

}

intcircle=1;

while（circle&&!

s.empty（））

{

w=s.top（）;s.pop（）;p=w.ptr;

switch（w.tag）

{

//从左子树退回，修改tag为右边

case0:

w.tag=1;s.push（w）;

circle=0;

p=p->rchild;

break;

//从右子树退回

case1:

if（p->lchild==NULL&&p->rchild==NULL）

{

out<data<<"";

tmp=s;

while（!

tmp.empty（））

{

t=tmp.top（）;

tmp.pop（）;

out<data<<"";

}

out<

}

}

}

}

while（!

s.empty（））;

out<

}

public:

Expression（stringinfix）

{

Infix=infix;

Postfix=ToPostfix（Infix）;

root=CreateTree（）;

}

~Expression（）

{

deleteroot;

while（nodes.empty（）!

=true）

{

deletenodes.top（）;

nodes.pop（）;

}

}

//后序遍历

//out：

输出流

voidPostView（ostream&out）

{

postOrder（root,out）;

}

//前序遍历

//out：

输出流

voidPreView（ostream&out）

{

preOrder（root,out）;

}

//递归遍历叶节点

//out：

输出流

voidGetLeafRecursive（ostream&out）

{

leafRecursive（root,out）;

}

//非递归遍历叶节点

//out：

输出流

voidGetLeaf（ostream&out）

{

leaf（root,out）;

}

//（非递归）叶结点到根结点的路径

voidLTR（ostream&out）

{

lp（root,out）;

}

//（递归）叶结点到根结点的路径

voidLTRRecursive（ostream&out）

{

stringt[100];

lpRecursive（root,t,0,out）;

}

//获取后缀表达式

stringGetPostExpression（）

{

returnPostfix;

}

};

int_tmain（intargc,_TCHAR*argv[]）

{

cout<<"请输入表达式：

";

stringinfix;

//cin>>infix;

infix="X=（-b+（b^2-4*a*c）^5）/（2*a）";

cout<

Expressionex（infix）;

cout<<"前序表达式为：

";

ex.PreView（cout）;

cout<

cout<<"后序表达式为：

"<

cout<<"（递归）叶结点：

";

ex.GetLeafRecursive（cout）;

cout<

cout<<"（非递归）叶结点：

";

ex.GetLeaf（cout）;

cout<

cout<<"（递归）叶结点到根结点的路径：

"<

ex.LTRRecursive（cout）;

cout<

cout<<"（非递归）叶结点到根结点的路径：

"<

ex.LTR（cout）;

system（"pause"）;

return0;

}

任务三：

#include"stdafx.h"

#defineMAXLENGTH100

//边表节点

typedefstructnode

{

intAdjVex;

node*Next;

}EdgeNode;

//顶点节点

typedefstruct

{

intVertex;

EdgeNode*FirstEdge;

}VertexNode;

//边表

typedefVertexNodeAdjList[MAXLENGTH];

classALGraph

{

protected:

AdjListAdjlist;

intNodeCount;

intEdgeCount;

//深度优先遍历（递归）

//out：

输出流

//v：

访问的顶点

//visited：

记录是否被访问过的数组

voidDFS_internal（ostream&out,intv,boolvisited[]）

{

out<

visited[v]=true;

EdgeNode*edge=Adjlist[v].FirstEdge;

while（edge!

=NULL）

{

if（visited[edge->AdjVex]==false）

DFS_internal（out,edge->AdjVex,visited）;

edge=edge->Next;

}

}

public:

//输入一个图

voidCreate（istream&in,ostream&out）

{

intn,e;

out<<"请输入顶点数和边数：

"<

in>>n>>e;

NodeCount=n;

EdgeCount=e;

out<<"请输入顶点：

"<

for（inti=0;i

{

intvertex;

in>>vertex;

Adjlist[i].Vertex=vertex;

Adjlist[i].FirstEdge=NULL;

}

out<<"请输入边（以“Vi,Vj”的形式输入）"<

for（inti=