数据结构 实验三文档格式.docx
《数据结构 实验三文档格式.docx》由会员分享，可在线阅读，更多相关《数据结构 实验三文档格式.docx（30页珍藏版）》请在冰点文库上搜索。
};
任务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&
前序遍历（递归）
任务2：
voidGetLeafRecursive（ostream&
（递归）查找叶结点
voidGetLeaf（ostream&
（非递归）查找叶结点
利用二叉树前序遍历的非递归算法，加入判断条件，若当前结点为叶节点才进行访问。
voidLTR（ostream&
（递归）叶结点到根结点的路径
voidLTRRecursive（ostream&
（非递归）叶结点到根结点的路径
遇到叶节点时，将栈中内容弹出，得到路径；
非叶节点则继续向下遍历，并将该节点压栈
voidCreate（istream&
in,ostream&
初始化
stringTopological_Sort（）
拓扑排序
voidDFS（ostream&
out,intv）
深度优先遍历
voidBFS（ostream&
广度优先遍历
三、测试
1.方案
测试数据：
X=（-b+（b^2-4*a*c）^s）/（2*a）
直接运行即可
2.结果
四、总结与讨论
本设计还存在的问题有：
1、无法判断输入错误的表达式并结束程序。
2、无法处理等号左边为表达式的情况
可以做的改进：
1、在处理时增加catch块捕捉异常，如果出现异常则说明表达式错误。
2、在处理等号时，将左边的表达式和右边的表达式分开，单独生成树，然后拼接到等号的节点上。
附：
程序模块的源代码
任务一、二：
//表达式
classExpression
protected:
//中缀表达式
stringInfix;
//后缀表达式
stringPostfix;
//所有节点
stack<
Tnode*>
nodes;
//树根
Tnode*root;
//判断是否是运算符
boolisOperator（charop）
if（op=='
（'
||op=='
）'
+'
-'
*'
/'
||op=='
^'
||op=='
='
）
returntrue;
else
returnfalse;
//栈内优先级
intInStackPriority（charc）
switch（c）
{
case'
:
return1;
return3;
return5;
return7;
return6;
return0;
default:
return-1;
}
//栈外优先级
intOutStackPriority（charc）
return2;
return4;
//从中缀表达式转换为后缀表达式
//Infix：
中缀表达式
stringToPostfix（stringInfix）
stack<
char>
a;
//操作符栈
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）<
OutStackPriority（Infix[i]））//若栈外操作符优先级高，则入栈
{
a.push（Infix[i]）;
i++;
}
elseif（InStackPriority（ch1）>
OutStackPriority（Infix[i]））//若栈顶操作符优先级高，则出栈，并加入结果字符串
{
postfix=postfix+ch1;
a.pop（）;
}
else
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;
t;
//临时栈
//自下而上生成树
inti=1;
while（Postfix[i]!
isOperator（Postfix[i]））//操作数则把其值赋给新的结点，压栈
p=newTnode（Postfix[i]）;
t.push（p）;
//先把操作符的值赋给新的结点，然后取2个栈顶元素分别设为该结点的左右孩子
if（!
t.empty（））
p->
rchild=t.top（）;
//若栈非空则弹栈并设为结点的右孩子
t.pop（）;
lchild=t.top（）;
//若栈非空则弹栈并设为结点的左孩子
//新结点压栈
//将其与根节点合并
rchild=p;
returnroot;
//后序遍历
voidpostOrder（Tnode*p,ostream&
{
if（p）
postOrder（p->
lchild,out）;
rchild,out）;
out<
<
p->
data;
//前序遍历
voidpreOrder（Tnode*p,ostream&
preOrder（p->
//（递归）叶结点
voidleafRecursive（Tnode*p,ostream&
if（p!
=NULL）{
if（p->
lchild==NULL&
rchild==NULL）
out<
data<
"
;
else{
leafRecursive（p->
leafRecursive（p->
//（非递归）叶结点
voidleaf（Tnode*p,ostream&
t;
Tnode*null=newTnode（）;
t.push（null）;
while（p!
=null）
if（p->
lchild==NULL&
rchild==NULL）
p->
data<
p=t.top（）;
rchild!
=NULL）
t.push（p->
rchild）;
lchild!
p=p->
lchild;
if（p->
out<
//（递归）叶结点到根结点的路径
voidlpRecursive（Tnode*p,stringt[],intlen,ostream&
=NULL）
for（inti=len-1;
i>
=0;
i--）
t[i]<
endl;
t[len]=p->
len++;
lpRecursive（p->
lchild,t,len,out）;
rchild,t,len,out）;
len--;
//（非递归）叶结点到根结点的路径
voidlp（Tnode*p,ostream&
structSnode
Tnode*ptr;
booltag;
};
Snodew,t;
Snode>
s;
tmp;
do
while（p!
w.ptr=p;
w.tag=0;
s.push（w）;
intcircle=1;
while（circle&
!
s.empty（））
w=s.top（）;
s.pop（）;
p=w.ptr;
switch（w.tag）
//从左子树退回，修改tag为右边
case0:
w.tag=1;
circle=0;
p=p->
rchild;
break;
//从右子树退回
case1:
if（p->
{
out<
tmp=s;
while（!
tmp.empty（））
{
t=tmp.top（）;
tmp.pop（）;
out<
t.ptr->
}
}
s.empty（））;
out<
endl;
Expression（stringinfix）
Infix=infix;
Postfix=ToPostfix（Infix）;
root=CreateTree（）;
~Expression（）
deleteroot;
while（nodes.empty（）!
=true）
deletenodes.top（）;
nodes.pop（）;
//out：
输出流
voidPostView（ostream&
postOrder（root,out）;
voidPreView（ostream&
preOrder（root,out）;
//递归遍历叶节点
voidGetLeafRecursive（ostream&
leafRecursive（root,out）;
//非递归遍历叶节点
voidGetLeaf（ostream&
leaf（root,out）;
voidLTR（ostream&
lp（root,out）;
voidLTRRecursive（ostream&
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）"
infix<
Expressionex（infix）;
前序表达式为：
ex.PreView（cout）;
后序表达式为：
ex.GetPostExpression（）<
（递归）叶结点：
ex.GetLeafRecursive（cout）;
（非递归）叶结点：
ex.GetLeaf（cout）;
（递归）叶结点到根结点的路径：
ex.LTRRecursive（cout）;
（非递归）叶结点到根结点的路径：
ex.LTR（cout）;
system（"
pause"
return0;
}
任务三：
#include"
stdafx.h"
#defineMAXLENGTH100
classALGraph
AdjListAdjlist;
intNodeCount;
intEdgeCount;
//深度优先遍历（递归）
//v：
访问的顶点
//visited：
记录是否被访问过的数组
voidDFS_internal（ostream&
out,intv,boolvisited[]）
Adjlist[v].Vertex<
'
'
visited[v]=true;
EdgeNode*edge=Adjlist[v].FirstEdge;
while（edge!
if（visited[edge->
AdjVex]==false）
DFS_internal（out,edge->
AdjVex,visited）;
edge=edge->
Next;
//输入一个图
voidCreate（istream&
intn,e;
请输入顶点数和边数：
in>
n>
e;
NodeCount=n;
EdgeCount=e;
请输入顶点：
for（inti=0;
i<
n;
i++）
intvertex;
in>
vertex;
Adjlist[i].Vertex=vertex;
Adjlist[i].FirstEdge=NULL;
请输入边（以“Vi,Vj”的形式输入）"
for（inti=
升级会员 