數(shù)據(jù)結(jié)構(gòu) 實(shí)驗(yàn)三

設(shè)計(jì)三樹(shù)和二叉樹(shù)一、設(shè)計(jì)目的掌握二叉樹(shù)，二叉樹(shù)排序數(shù)的概念及存儲(chǔ)方法。掌握二叉樹(shù)的遍歷算法。熟練掌握編寫實(shí)現(xiàn)樹(shù)的各種運(yùn)算的算法。熟悉圖的各種存儲(chǔ)方法。掌握遍歷圖的遞歸和非遞歸的算法。理解圖的有關(guān)算法。二、設(shè)計(jì)內(nèi)容任務(wù)描述1、編寫一個(gè)程序，用二叉樹(shù)來(lái)表示代數(shù)表達(dá)式，樹(shù)的每個(gè)結(jié)點(diǎn)包括一個(gè)運(yùn)算符，代數(shù)表達(dá)式由輸入得到（其中只包含=,+，-，*，/和用一個(gè)字母表示的數(shù)且沒(méi)有錯(cuò)誤，并且按照先乘除后加減的原則），并輸出表達(dá)式的前綴式和后綴式。2、對(duì)于1中的代數(shù)表達(dá)式二叉樹(shù)，分別用遞歸和非遞歸的方法編寫程序完成如下功能：輸出所有的葉子結(jié)點(diǎn)的數(shù)據(jù)項(xiàng)值；輸出所有從葉子節(jié)點(diǎn)到根結(jié)點(diǎn)的路徑。3、對(duì)于下圖所示的有向圖G，編寫一個(gè)程序完成如下功能：建立G的鄰接表存儲(chǔ)結(jié)構(gòu)；輸出拓?fù)渑判蛐蛄校惠敵鰪捻旤c(diǎn)0開(kāi)始的深度優(yōu)先遍歷序列（遞歸算法）和廣度優(yōu)先遍歷序列（非遞歸算法）。問(wèn)題的表示方案對(duì)任務(wù)1、2,使用一個(gè)類表示二叉樹(shù)中各結(jié)點(diǎn)，類中的屬性包括結(jié)點(diǎn)的數(shù)據(jù)及指向結(jié)點(diǎn)左右孩子的指針。對(duì)任務(wù)3,使用三個(gè)結(jié)構(gòu)體分別表示邊、頂點(diǎn)、圖。其中邊結(jié)構(gòu)體包括了邊上另一頂點(diǎn)的位置、邊的權(quán)重、下一條邊的指針；頂點(diǎn)結(jié)構(gòu)體包括頂點(diǎn)數(shù)據(jù)及該頂點(diǎn)邊鏈表的頭指針；圖結(jié)構(gòu)體包括頂點(diǎn)數(shù)組及圖的頂點(diǎn)、邊數(shù)量。1.主要數(shù)據(jù)類型與變量任務(wù)1、2：〃樹(shù)的節(jié)點(diǎn)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;}};任務(wù)3：〃邊表節(jié)點(diǎn)typedefstructnode{intAdjVex;node*Next;}EdgeNode;//頂點(diǎn)節(jié)點(diǎn)typedefstruct{intVertex;EdgeNode*FirstEdge;}VertexNode;//邊表typedefVertexNodeAdjList[MAXLENGTH];2.算法或程序模塊任務(wù)1：intisOperator(charop)功能:判斷是否為操作符。intInStackPriority(charc)功能：判斷操作符的棧內(nèi)優(yōu)先級(jí)。intOutStackPriority(charc)功能：判斷操作符的棧外優(yōu)先級(jí)。stringToPostfix(stringInfix)功能：將輸入的中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式。Tnode*CreateTree()功能：創(chuàng)建二叉樹(shù)具體算法：首先處理輸入的X和二，將=作為根節(jié)點(diǎn)，X作為其子節(jié)點(diǎn)。然后將除去X和二的后綴表達(dá)式進(jìn)入處理流程：順序讀取該后綴表達(dá)式，遇到操作數(shù)則把其值賦給新的結(jié)點(diǎn)，壓棧；遇到操作符，先把操作符的值賦給新的結(jié)點(diǎn)，然后取2個(gè)棧頂元素分別設(shè)為該結(jié)點(diǎn)的左右孩子，再壓棧。voidPostView(ostream&out)功能：后序遍歷(遞歸)voidPreView(ostream&out)功能：前序遍歷(遞歸)任務(wù)2：voidGetLeafRecursive(ostream&out)功能：(遞歸)查找葉結(jié)點(diǎn)voidGetLeaf(ostream&out)功能：(非遞歸)查找葉結(jié)點(diǎn)具體算法：利用二叉樹(shù)前序遍歷的非遞歸算法，加入判斷條件，若當(dāng)前結(jié)點(diǎn)為葉節(jié)點(diǎn)才進(jìn)行訪問(wèn)。voidLTR(ostream&out)功能：(遞歸)葉結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑voidLTRRecursive(ostream&out)功能：(非遞歸)葉結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑具體算法：遇到葉節(jié)點(diǎn)時(shí)，將棧中內(nèi)容彈出，得到路徑；非葉節(jié)點(diǎn)則繼續(xù)向下遍歷，并將該節(jié)點(diǎn)壓棧任務(wù)3：voidCreate(istream&in,ostream&out)功能：初始化stringTopological_Sort()功能：拓?fù)渑判騰oidDFS(ostream&out,intv)功能：深度優(yōu)先遍歷voidBFS(ostream&out,intv)功能：廣度優(yōu)先遍歷三、測(cè)試方案任務(wù)1、2：測(cè)試數(shù)據(jù)：X=(-b+(b"2-4*a*c)"s)/(2*a)任務(wù)3：直接運(yùn)行即可結(jié)果n蕓先意果歷黑01324（遞歸）:（非遞歸）Q432

：043n蕓先意果歷黑01324（遞歸）:（非遞歸）Q432

：043四、總結(jié)與討論?C:俊據(jù)結(jié)構(gòu)實(shí)驗(yàn)\圖的鄰接矩K軻口鄰接表存儲(chǔ)\Debugk圖的鄰爵?軻口鄰接表存.本設(shè)計(jì)還存在的問(wèn)題有：1、無(wú)法判斷輸入錯(cuò)誤的表達(dá)式并結(jié)束程序。2、無(wú)法處理等號(hào)左邊為表達(dá)式的情況可以做的改進(jìn)：1、在處理時(shí)增加catch塊捕捉異常，如果出現(xiàn)異常則說(shuō)明表達(dá)式錯(cuò)誤。2、在處理等號(hào)時(shí)，將左邊的表達(dá)式和右邊的表達(dá)式分開(kāi)，單獨(dú)生成樹(shù)，然后拼接到等號(hào)的節(jié)點(diǎn)上。附：程序模塊的源代碼任務(wù)一、二：〃樹(shù)的節(jié)點(diǎn)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;}};//表達(dá)式classExpression{protected:〃中綴表達(dá)式stringInfix;〃后綴表達(dá)式stringPostfix;〃所有節(jié)點(diǎn)stack<Tnode*>nodes;〃樹(shù)根Tnode*root;〃判斷是否是運(yùn)算符boolisOperator(charop){if(op=='(，||op==')'||op=='+'||op=='-'||op=='*'||op=='/'||op=="||op=='=‘)returntrue;elsereturnfalse;}〃棧內(nèi)優(yōu)先級(jí)intInStackPriority(charc){switch(c){case(:return1;case'+':case'-':return3;case'*':case/:return5;case):return7;case:return6;case'=':return0;default:return-1;}}〃棧外優(yōu)先級(jí)intOutStackPriority(charc){switch(c){case(:return7;case'+':case'-':return2;case'*':case/:return4;case:return6;case):return1;case'=':return0;default:return-1;}}〃從中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式//Infix：中綴表達(dá)式stringToPostfix(stringInfix){stack<char>a;//操作符棧a.push('#');stringpostfix;//結(jié)果字符串inti=0;charch1;while(!a.empty()&&Infix[i]!='\0')//當(dāng)棧非空且字符串未讀取完時(shí)循環(huán){if(!isOperator(Infix[i]))//操作數(shù)直接加入結(jié)果字符串{postfix=postfix+Infix[i];i++;}else{ch1=a.top();//取棧頂操作符if(InStackPriority(ch1)<OutStackPriority(Infix[i]))//若棧外操作符優(yōu)先級(jí)高，則入棧{a.push(Infix[i]);i++;}elseif(InStackPriority(ch1)>OutStackPriority(Infix[i]))//若棧頂操作符優(yōu)先級(jí)高，則出棧，并加入結(jié)果字符串{postfix=postfix+ch1;a.pop();}else{a.pop();if(ch1=='(')i++;//棧外的“)”與棧內(nèi)的“(”配對(duì)時(shí)，直接出}}while(a.top()!='#'){postfix=postfix+a.top();//將棧中剩余的操作符全部彈出a.pop();}returnpostfix;}//創(chuàng)建樹(shù)Tnode*CreateTree(){//先處理乂和=Tnode*root=newTnode("=");root->lchild=newTnode(Infix[0]);Tnode*p=NULL;stack<Tnode*>t;//臨時(shí)棧//自下而上生成樹(shù)inti=1;while(Postfix[i]!='='){if(!isOperator(Postfix[i]))//操作數(shù)則把其值賦給新的結(jié)點(diǎn)，壓棧{p=newTnode(Postfix[i]);i++;t.push(p);}else{p=newTnode(Postfix[i]);//先把操作符的值賦給新的結(jié)點(diǎn)，然后取2個(gè)棧頂元素分別設(shè)為該結(jié)點(diǎn)的左右孩子if(!t.empty()){p->rchild=t.top();//若棧非空則彈棧并設(shè)為結(jié)點(diǎn)的右孩子t.pop();}if(!t.empty()){p->lchild=t.top();//若棧非空則彈棧并設(shè)為結(jié)點(diǎn)的左孩子t.pop();}t.push(p);//新結(jié)點(diǎn)壓棧i++;}〃將其與根節(jié)點(diǎn)合并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);}}//(遞歸)葉結(jié)點(diǎn)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);}}}//(非遞歸)葉結(jié)點(diǎn)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();}}}}//(遞歸)葉結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑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--;}}//(非遞歸)葉結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑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){//從左子樹(shù)退回，修改tag為右邊case0:w.tag=1;s.push(w);circle=0;p=p->rchild;break;//從右子樹(shù)退回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);}//遞歸遍歷葉節(jié)點(diǎn)//out：輸出流voidGetLeafRecursive(ostream&out){leafRecursive(root,out);〃非遞歸遍歷葉節(jié)點(diǎn)//out：輸出流voidGetLeaf(ostream&out){leaf(root,out);}//(非遞歸)葉結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑voidLTR(ostream&out){lp(root,out);}//(遞歸)葉結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑voidLTRRecursive(ostream&out){stringt[100];lpRecursive(root,t,0,out);}//獲取后綴表達(dá)式stringGetPostExpression(){returnPostfix;}};int_tmain(intargc,_TCHAR*argv[]){cout<<"請(qǐng)輸入表達(dá)式："；stringinfix;//cin>>infix;infix="X=(-b+(b"2-4*a*c)"5)/(2*a)〃；cout<<infix<<endl;Expressionex(infix);cout<<"前序表達(dá)式為："；ex.PreView(cout);cout<<endl;cout<<”后序表達(dá)式為："<<ex.GetPostExpression()<<endl;cout<<"(遞歸)葉結(jié)點(diǎn)："；ex.GetLeafRecursive(cout);cout<<endl;cout<<〃(非遞歸)葉結(jié)點(diǎn)：〃；ex.GetLeaf(cout);cout<<endl;cout<<〃(遞歸)葉結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑：〃<<endl;ex.LTRRecursive(cout);cout<<endl;cout<<〃(非遞歸)葉結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑："<<endl;ex.LTR(cout);system("pause");return0;}任務(wù)三：#include"stdafx.h”#defineMAXLENGTH100〃邊表節(jié)點(diǎn)typedefstructnode{intAdjVex;node*Next;}EdgeNode;//頂點(diǎn)節(jié)點(diǎn)typedefstruct{intVertex;EdgeNode*FirstEdge;}VertexNode;//邊表typedefVertexNodeAdjList[MAXLENGTH];classALGraph{protected:AdjListAdjlist;intNodeCount;intEdgeCount;//深度優(yōu)先遍歷(遞歸)//out：輸出流//v：訪問(wèn)的頂點(diǎn)//visited：記錄是否被訪問(wèn)過(guò)的數(shù)組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://輸入一個(gè)圖voidCreate(istream&in,ostream&out){intn,e;out<<"請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)："<<endl;in>>n>>e;NodeCount=n;EdgeCount=e;out<<"請(qǐng)輸入頂點(diǎn)："<<endl;for(inti=0;i<n;i++){intvertex;in>>vertex;Adjlist[i].Vertex=vertex;Adjlist[i].FirstEdge=NULL;}out<<"請(qǐng)輸入邊(以“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;}}〃從內(nèi)置圖初始化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;}〃拓?fù)渑判騭tringTopological_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;}}//開(kāi)始拓?fù)渑判騭tack<int>NullInDegreeNodes;〃查找入度為0的點(diǎn)入棧for(inti=0;i<NodeCount;i++){if(inDegree[i]==0)NullInDegreeNodes.push(i);}//開(kāi)始主循環(huán)while(NullInDegreeNodes.empty()!=true){〃出棧，進(jìn)入結(jié)果ostringstreamout;out<<NullInDegreeNodes.top();result+=out.str();//刪去該節(jié)點(diǎn)EdgeNode*edge=Adjlist[NullInDegreeNodes.top()].FirstEdge;NullInDegreeNodes.pop()