北工大數(shù)據(jù)結(jié)構(gòu)上機(jī)實驗報告(共15頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上上機(jī)題三報告 姓名： 學(xué)號： 完成日期：2015年5月5日題目：表達(dá)式可以用表達(dá)式二叉樹來表示。對于簡單的四則運算表達(dá)式，請實現(xiàn)以下功能；（1）對于任意給出的前綴表達(dá)式（不帶括號）、中綴表達(dá)式（可以帶括號）或后綴表達(dá)式（不帶括號），能夠在計算機(jī)內(nèi)部構(gòu)造出一棵表達(dá)式二叉樹，并且以圖示顯示出來（字符圖或圖形的形式）。（2） 對于構(gòu)造好的內(nèi)部表達(dá)式二叉樹，按照用戶要求，輸出相應(yīng)的前綴表達(dá)式（不帶括號）、中綴表達(dá)式（可以帶括號）或后綴表達(dá)式（不帶括號）.1、 需求分析1. 輸入形式、輸入值的范圍；輸入前綴表達(dá)式（不帶括號）、中綴表達(dá)式（可以帶括號）或后綴表達(dá)式（不帶括號）2.

2、 輸出形式；表達(dá)式二叉樹，前綴表達(dá)式、中綴表達(dá)式和后綴表達(dá)式。3. 程序功能；用表達(dá)式二叉樹表示表達(dá)式，并轉(zhuǎn)換為前綴表達(dá)式、中綴表達(dá)式或后綴表達(dá)式。4. 測試數(shù)據(jù) 正確的輸入輸出： 錯誤的輸入輸出： 2、 概要設(shè)計1. ADT定義class TNode/節(jié)點類開始2. 主程序流程結(jié)束輸出各類表達(dá)式是是將表達(dá)式轉(zhuǎn)換為二叉樹表達(dá)式是否是否為中綴表達(dá)式是否為前綴表達(dá)式輸入表達(dá)式是否為后綴表達(dá)式否 3. 各程序模塊間的調(diào)用關(guān)系Main（） 刪除樹打印樹求前、中、后綴表達(dá)式模塊求二叉樹表達(dá)式模塊3、 詳細(xì)設(shè)計1. 實現(xiàn)ADT定義的數(shù)據(jù)類型class TNode/節(jié)點類 public:char oper;

3、/數(shù)據(jù)域，為簡便起見，操作數(shù)用單個字符代替TNode *left;TNode *right;int s;int t;/計算樹的層數(shù)使用TNode()/缺省構(gòu)造函數(shù) left=right=NULL; oper=0; TNode(char op)/賦值構(gòu)造函數(shù) left=right=NULL; oper=op;2. 算法描述表達(dá)式轉(zhuǎn)化為二叉樹void pre2tree(TNode *&p, string str)/前綴表達(dá)式生成二叉樹 碰到操作數(shù)則把其值賦給相應(yīng)的新申請的二叉樹結(jié)點，地址壓棧；碰到操作符則把其值賦給相應(yīng)的新申請的二叉樹，并從棧中彈出兩個地址，分別作為其左指針和右指針，然后再

4、把其地址壓棧，最后一個地址即為二叉樹的根結(jié)點地址。void post2tree(TNode *&p,string str)/后綴表達(dá)式生成二叉樹 /碰到操作數(shù)則把其值賦給相應(yīng)的新申請的二叉樹結(jié)點，若棧為空則地址壓棧，/碰到操作符則把其值賦給相應(yīng)的新申請的二叉樹結(jié)點，取棧頂元素，/若當(dāng)前元素的左孩子為空則設(shè)為其左孩子，/左孩子為滿則設(shè)為其右孩子,開始那個元素地址為根結(jié)點地址，開始時用變量root保存。void in2tree(TNode *&p, string str)/中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式生成二叉樹 從中綴表達(dá)式中自左至右依次讀入各個字符。  如果讀入操作數(shù)，直

5、接輸出到后綴表達(dá)式。 如果讀入的是運算符，并且運算符棧為空，則將該運算符直接進(jìn)棧；如果棧不為空， 則比較該運算符和棧頂運算符的優(yōu)先級。      若該運算符高于棧頂運算符的優(yōu)先級，則將該運算符直接進(jìn)棧； 若該運算符低于或等于棧頂運算符的優(yōu)先級，則將棧中高于或等于該運算符優(yōu)先級的元 素依次出棧輸出到后綴表達(dá)式中，然后再將該運算符進(jìn)棧。 在碰到開括號和棧為空前反復(fù)彈出棧中元素 若棧非空棧頂不是左括號且棧頂元素優(yōu)先級不低于輸入運算符時，/將棧頂元素彈出到后綴表達(dá)式二叉樹表達(dá)式轉(zhuǎn)化為表達(dá)式 void postOrder(T

6、Node *p) /先序遍歷 if(p) postOrder(p->left); postOrder(p->right); cout<<p->oper; void preOrder(TNode *p) /后序遍歷 if(p) cout<<p->oper; preOrder(p->left); preOrder(p->right); void inOrder(TNode *p)/中序遍歷，同時輸出不帶冗余括號的中綴表達(dá)式 if(p)if(p->left) if(如果當(dāng)前節(jié)點的左子樹是運算符，且運算符優(yōu)先級低于當(dāng)前運算符，那么左邊的

7、表達(dá)式要先計算，需要加括號) cout<<"(" inOrder(p->left); cout<<")" else/否則直接輸出左子樹 inOrder(p->left); cout<<p->oper;/輸出當(dāng)前節(jié)點 if(p->right) if(如果當(dāng)前節(jié)點的右子樹是運算符，且運算符優(yōu)先級不高于當(dāng)前運算符，那么右邊的表達(dá)式要先計算，需要加括號) cout<<"(" inOrder(p->right); cout<<")" e

8、lse inOrder(p->right); 4、 程序測試5、 用戶使用說明運行程序后，按照提示選擇表達(dá)式類型（-1：前綴表達(dá)式；0：中綴表達(dá)式；1：后綴表達(dá)式）然后輸入相應(yīng)的表達(dá)式，回車后可以得到二叉樹表達(dá)式及出前綴、中綴、后綴表達(dá)式6、 源程序#include <iostream>#include <stack>#include <queue>#include <string>#include<math.h>using namespace std;class TNode/節(jié)點類 public:char oper;/數(shù)據(jù)域，

9、為簡便起見，操作數(shù)用單個字符代替TNode *left;TNode *right;int s;int t;/計算樹的層數(shù)使用TNode()/缺省構(gòu)造函數(shù) left=right=NULL; oper=0; TNode(char op)/賦值構(gòu)造函數(shù) left=right=NULL; oper=op;bool isOper(char op)/判斷是否為運算符char oper='(',')','+','-','*','/',''for(int i=0;i<sizeof(oper);

10、i+) if(op=operi) return true; return false;int getOperOrder(char op)/返回運算符op所對應(yīng)的優(yōu)先級/ 左括號優(yōu)先級，加減號為，乘除號為，方冪為，右括號，棧底返回switch(op)case '(': return 1; case '+': case '-':return 2; case '*': case '/':return 3; case '':return 4; default: /定義在棧中的右括號和棧底字符的優(yōu)先級最低 r

11、eturn 0; void freeTree(TNode *&p) /遞歸刪除樹 if(p->left!=NULL) freeTree(p->left); if(p->right!=NULL) freeTree(p->right); delete(p); void postOrder(TNode *p) /先序遍歷 if(p) postOrder(p->left); postOrder(p->right); cout<<p->oper; void preOrder(TNode *p) /后序遍歷 if(p) cout<<

12、p->oper; preOrder(p->left); preOrder(p->right); void inOrder(TNode *p)/中序遍歷，同時輸出不帶冗余括號的中綴表達(dá)式 if(p)if(p->left) /如果當(dāng)前節(jié)點的左子樹是運算符，且運算符優(yōu)先級低于當(dāng)前運算符，/那么左邊的表達(dá)式要先計算，需要加括號if(isOper(p->left->oper)&& getOperOrder(p->left->oper)<getOperOrder(p->oper) cout<<"("

13、 inOrder(p->left); cout<<")" else/否則直接輸出左子樹 inOrder(p->left); cout<<p->oper;/輸出當(dāng)前節(jié)點 if(p->right) /如果當(dāng)前節(jié)點的右子樹是運算符，且運算符優(yōu)先級不高于當(dāng)前運算符，/那么右邊的表達(dá)式要先計算，需要加括號 if(isOper(p->right->oper)&& getOperOrder(p->right->oper)<=getOperOrder(p->oper) cout<<

14、;"(" inOrder(p->right); cout<<")" else inOrder(p->right); void post2tree(TNode *&p,string str)/后綴表達(dá)式生成二叉樹 /（a）碰到操作數(shù)則把其值賦給相應(yīng)的新申請的二叉樹結(jié)點，若棧為空則地址壓棧，/（b）碰到操作符則把其值賦給相應(yīng)的新申請的二叉樹結(jié)點，取棧頂元素，/若當(dāng)前元素的左孩子為空則設(shè)為其左孩子，/左孩子為滿則設(shè)為其右孩子,開始那個元素地址為根結(jié)點地址，開始時用變量root保存。stack <TNode*> nod

15、eStack;/用于保存節(jié)點指針的棧 char temp; int i=0; temp=stri+; while(temp!='0') if(temp!='0'&&!isOper(temp)/不是運算符，則進(jìn)棧 p=new TNode(temp);/以temp為結(jié)點值構(gòu)造二叉樹結(jié)點 nodeStack.push(p); temp=stri+;/讀入下一個 else /如果遇到符號，則彈棧，依次設(shè)為右節(jié)點和左節(jié)點p=new TNode(temp); if(nodeStack.size() p->right=nodeStack.top();/若

16、非空則彈棧并設(shè)為結(jié)點的右孩子 nodeStack.pop(); if(nodeStack.size() p->left=nodeStack.top();/若非空則彈棧并設(shè)為結(jié)點的左孩子 nodeStack.pop(); nodeStack.push(p); temp=stri+; void pre2tree(TNode *&p, string str)/前綴表達(dá)式生成二叉樹/碰到操作數(shù)則把其值賦給相應(yīng)的新申請的二叉樹結(jié)點，地址壓棧；/碰到操作符則把其值賦給相應(yīng)的新申請的二叉樹，并從棧中彈出兩個地址，/分別作為其左指針和右指針，然后再把其地址壓棧，最后一個地址即為二叉樹的根結(jié)點地址

17、。stack <TNode*> nodeStack; char temp; int i=str.size()-1; temp=stri-; while(temp!='0') if(temp!='0'&&!isOper(temp) p=new TNode(temp);/以temp為內(nèi)容來建立新的結(jié)點 nodeStack.push(p); temp=stri-; else p=new TNode(temp); if(nodeStack.size()/棧非空 p->left=nodeStack.top(); /則棧頂指針?biāo)附Y(jié)點設(shè)置成

18、當(dāng)前結(jié)點左孩子 nodeStack.pop(); if(nodeStack.size()/棧非空 p->right=nodeStack.top();/則棧頂指針?biāo)附Y(jié)點設(shè)置成當(dāng)前結(jié)點右孩子 nodeStack.pop();/棧頂元素左右孩子指針設(shè)置完畢彈出 nodeStack.push(p); temp=stri-; /當(dāng)?？涨覓呙璧阶詈髸r，樹根由P帶回void in2tree(TNode *&p, string str)/中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式生成二叉樹 stack<char> a; char temp; string Postfixexp="&quo

19、t; int i=0; temp=stri+; while(temp!='0') if(!isOper(temp)/操作數(shù)則直接進(jìn)數(shù)據(jù)棧 Postfixexp+=temp; temp=stri+; else if(temp='(')/進(jìn)棧 a.push(temp); temp=stri+; else if(temp=')') while(a.top()!='(')/脫括號 Postfixexp+=a.top(); a.pop();/在碰到開括號和棧為空前反復(fù)彈出棧中元素 a.pop(); temp=stri+; else if(t

20、emp='+'|temp='-'|temp='*'|temp='/')/出棧while(!a.empty()&&a.top()!='('&&getOperOrder(a.top()>=getOperOrder(temp)/若棧非空棧頂不是左括號且棧頂元素優(yōu)先級不低于輸入運算符時，/將棧頂元素彈出到后綴表達(dá)式中，并且str下標(biāo)加 Postfixexp+=a.top(); a.pop(); a.push(temp);temp=stri+; /end while(temp!='

21、;0') while(!a.empty() Postfixexp+=a.top();a.pop(); Postfixexp+='0' /cout<<Postfixexp; post2tree(p,Postfixexp);void count(TNode *p,int &height,int n)/求值函數(shù)/求樹的高度if(p->left=NULL&&p->right=NULL) if(n>height) height=n; if(p->left!=NULL)count(p->left,height,n+1

22、); if(p->right!=NULL) count(p->right,height,n+1);void paint(TNode *p)/打印樹 int height=0; int h=0; int i; using std:queue; queue<TNode*> aQueue; count(p,height,1);TNode *pointer=p; TNode *lastpointer; if(pointer) pointer->s=1; pointer->t=1; aQueue.push(pointer); while(!aQueue.empty()

23、 lastpointer=pointer; pointer=aQueue.front(); aQueue.pop(); if(pointer->s>h) cout<<endl; h=pointer->s; if(pointer->t=1) for(i=0;i<pow(2,height-pointer->s)-1;i+) cout<<" " else if(lastpointer->s!=pointer->s)for(i=0;i<(pointer->t-1)*(pow(2,height-poi

24、nter->s+1)-1)+(pointer->t-1)-1+pow(2,height-pointer->s);i+) cout<<" " else for(i=0;i<(pointer->t-lastpointer->t)*(pow(2,height-pointer->s+1)-1)+(pointer->t-lastpointer->t)-1;i+) cout<<" " cout<<pointer->oper; if(pointer->left!=NULL) pointer->left->s=pointer->s+1; pointer->left->t=pointer->t*2-