数据结构 实验三

设计三树和二叉树一、设计目的掌握二叉树，二叉树排序数的概念及存储方法。掌握二叉树的遍历算法。熟练掌握编写实现树的各种运算的算法。熟悉图的各种存储方法。掌握遍历图的递归和非递归的算法。理解图的有关算法。二、设计内容任务描述1、编写一个程序，用二叉树来表示代数表达式，树的每个结点包括一个运算符，代数表达式由输入得到（其中只包含=,+，-，*，/和用一个字母表示的数且没有错误，并且按照先乘除后加减的原则），并输出表达式的前缀式和后缀式。2、对于1中的代数表达式二叉树，分别用递归和非递归的方法编写程序完成如下功能：输出所有的叶子结点的数据项值；输出所有从叶子节点到根结点的路径。3、对于下图所示的有向图G，编写一个程序完成如下功能：建立G的邻接表存储结构；输出拓扑排序序列；输出从顶点0开始的深度优先遍历序列（递归算法）和广度优先遍历序列（非递归算法）。问题的表示方案对任务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、2：测试数据：X=(-b+(b"2-4*a*c)"s)/(2*a)任务3：直接运行即可结果n芸先意果历黑01324（递归）:（非递归）Q432

：043n芸先意果历黑01324（递归）:（非递归）Q432

：043四、总结与讨论・C:俊据结构实验\图的邻接矩K轲口邻接表存储\Debugk图的邻爵®轲口邻接表存.本设计还存在的问题有：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;〃所有节点stack<Tnode*>nodes;〃树根Tnode*root;〃判断是否是运算符boolisOperator(charop){if(op=='(，||op==')'||op=='+'||op=='-'||op=='*'||op=='/'||op=="||op=='=‘)returntrue;elsereturnfalse;}〃栈内优先级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){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{a.pop();if(ch1=='(')i++;//栈外的“)”与栈内的“(”配对时，直接出}}while(a.top()!='#'){postfix=postfix+a.top();//将栈中剩余的操作符全部弹出a.pop();}returnpostfix;}//创建树Tnode*CreateTree(){//先处理乂和=Tnode*root=newTnode("=");root->lchild=newTnode(Infix[0]);Tnode*p=NULL;stack<Tnode*>t;//临时栈//自下而上生成树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<<p->data;}}//前序遍历voidpreOrder(Tnode*p,ostream&out){if(p){out<<p->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<<p->data<<””;else(leafRecursive(p->lchild,out);leafRecursive(p->rchild,out);}}}//(非递归)叶结点voidleaf(Tnode*p,ostream&out){stack<Tnode*>t;Tnode*null=newTnode();t.push(null);while(p!=null)if(p->lchild==NULL&&p->rchild==NULL){out<<p->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<<p->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<<p->data<<””;for(inti=len-1;i>=0;i--)out<<t[i]<<"”;out<<endl;}else{t[len]=p->data;len++;lpRecursive(p->lchild,t,len,out);lpRecursive(p->rchild,t,len,out);len--;}}//(非递归)叶结点到根结点的路径voidlp(Tnode*p,ostream&ut){structSnode{Tnode*ptr;booltag;};Snodew,t;stack<Snode>s;stack<Snode>tmp;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<<p->data<<””;tmp=s;while(!tmp.empty()){t=tmp.top();tmp.pop();out<<t.ptr->data<<}out<<endl;}}}}while(!s.empty());out<<endl;}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<<infix<<endl;Expressionex(infix);cout<<"前序表达式为："；ex.PreView(cout);cout<<endl;cout<<”后序表达式为："<<ex.GetPostExpression()<<endl;cout<<"(递归)叶结点："；ex.GetLeafRecursive(cout);cout<<endl;cout<<〃(非递归)叶结点：〃；ex.GetLeaf(cout);cout<<endl;cout<<〃(递归)叶结点到根结点的路径：〃<<endl;ex.LTRRecursive(cout);cout<<endl;cout<<〃(非递归)叶结点到根结点的路径："<<endl;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&>ut,int、，boolvisited[]){out<<Adjlist[v].Vertex<<'';visited[v]=true;EdgeNode*edge=Adjlist[v].FirstEdge;while(edge!=NULL){if(visited[edge->AdjVex]==false)

DFS_internal(out,edge->AdjVex,edge=edge->Next;}}public://输入一个图voidCreate(istream&in,ostream&out){intn,e;out<<"请输入顶点数和边数："<<endl;in>>n>>e;NodeCount=n;EdgeCount=e;out<<"请输入顶点："<<endl;for(inti=0;i<n;i++){intvertex;in>>vertex;Adjlist[i].Vertex=vertex;Adjlist[i].FirstEdge=NULL;}out<<"请输入边(以“Vi,Vj”的形式输入)for(inti=0;i<e;i++){inta,b;in>>a>>b;//向表头插入该边，并将该边指向原表头EdgeNode*edge=newEdgeNode;edge->AdjVex=b;edge->Next=Adjlist[a].FirstEdge;Adjlist[a].FirstEdge=edge;}}〃从内置图初始化voidCreateByInitialGraph(){NodeCount=5;EdgeCount=7;for(inti=0;i<NodeCount;i++){Adjlist[i].Vertex=i;Adjlist[i].FirstEdge=NULL;}visited);<<endl;EdgeNode*edge=newEdgeNode;edge->AdjVex=1;edge->Next=Adjlist[0].FirstEdge;Adjlist[0].FirstEdge=edge;edge=newEdgeNode;edge->AdjVex=2;edge->Next=Adjlist[1].FirstEdge;Adjlist[1].FirstEdge=edge;edge=newEdgeNode;edge->AdjVex=3;edge->Next=Adjlist[0].FirstEdge;Adjlist[0].FirstEdge=edge;edge=newEdgeNode;edge->AdjVex=4;edge->Next=Adjlist[0].FirstEdge;Adjlist[0].FirstEdge=edge;edge=newEdgeNode;edge->AdjVex=4;edge->Next=Adjlist[2].FirstEdge;Adjlist[2].FirstEdge=edge;edge=newEdgeNode;edge->AdjVex=2;edge->Next=Adjlist[3].FirstEdge;Adjlist[3].FirstEdge=edge;edge=newEdgeNode;edge->AdjVex=4;edge->Next=Adjlist[3].FirstEdge;Adjlist[3].FirstEdge=edge;}〃拓扑排序stringTopological_Sort(){stringresult;intinDegree[MAXLENGTH];//建立入度表for(inti=0;i<NodeCount;i++)inDegree[i]=0;for(inti=0;i<NodeCount;i++){EdgeNode*now=Adjlist[i].FirstEdge;while(now!=NULL){inDegree[now->AdjVex]++;now=now->Next;}}//开始拓扑排序stack<int>NullInDegreeNodes;〃查找入度为0的点入栈for(inti=0;i<NodeCount;i++){if(inDegree[i]==0)NullInDegreeNodes.push(i);}//开始主循环while(NullInDegreeNodes.empty()!=true){〃出栈，进入结果ostringstreamout;out<<NullInDegreeNodes.top();result+=out.str();//删去该节点EdgeNode*edge=Adjlist[NullInDegreeNodes.top()].FirstEdge;NullInDegreeNodes.pop()