表達(dá)式類型的實(shí)現(xiàn)

1、*理工大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告題目：表達(dá)式類型的實(shí)現(xiàn) 院（系）：計(jì)算機(jī)工程學(xué)院 學(xué)生姓名: * 班級(jí)： 計(jì)算111 學(xué)號(hào):2011070*起迄日期: 2012.7.82012.7.19 指導(dǎo)教師: * 一、需求分析1.問(wèn)題描述：本程序通過(guò)輸入前綴表達(dá)式建立一顆二叉樹(shù)，通過(guò)中序遍歷建立好的二叉樹(shù)輸出帶括號(hào)的中綴表達(dá)式。然后中序遍歷二叉樹(shù)對(duì)表達(dá)式中的未知數(shù)x進(jìn)行賦值。通過(guò)后序遍歷二叉樹(shù)計(jì)算表達(dá)式的值。根據(jù)兩顆二叉樹(shù)和輸入的運(yùn)算符構(gòu)造復(fù)合表達(dá)式。另外，通過(guò)中序遍歷二叉樹(shù)對(duì)表達(dá)式進(jìn)行化簡(jiǎn)。 2.基本功能以字符序列的形式輸入語(yǔ)法正確的前綴表示式并構(gòu)成表達(dá)式E用帶括號(hào)的中綴表達(dá)式輸出表達(dá)式E實(shí)現(xiàn)對(duì)變量x的

2、賦值，變量初始值為0對(duì)算術(shù)表達(dá)式求值構(gòu)造新的復(fù)合表達(dá)式（E1）P（E2）對(duì)表達(dá)式進(jìn)行化簡(jiǎn) 3.輸入輸出本程序運(yùn)算數(shù)的輸入輸出局限于無(wú)符號(hào)整型數(shù)據(jù)，運(yùn)算符的輸入輸出包括“+、-、*、/、”二、 概要設(shè)計(jì)1.設(shè)計(jì)思路：本程序以字符序列的形式輸入語(yǔ)法正確的前綴表達(dá)式，在輸入表達(dá)式的過(guò)程中判斷輸入的字符是運(yùn)算數(shù)還是運(yùn)算符并將其保存到樹(shù)節(jié)點(diǎn)中相應(yīng)的位置，表達(dá)式輸入結(jié)束的同時(shí)也就構(gòu)成一顆二叉樹(shù)。根據(jù)建立好的二叉樹(shù)，可以采用中序遍歷二叉樹(shù)的方法輸出正常順序的表達(dá)式。在中序遍歷二叉樹(shù)時(shí)，訪問(wèn)存放運(yùn)算符的結(jié)點(diǎn)時(shí)要判斷其與雙親結(jié)點(diǎn)中運(yùn)算符的優(yōu)先級(jí)關(guān)系來(lái)判斷是否要添加括號(hào)。在給表達(dá)式中的未知數(shù)x賦值時(shí)，本程序采用的

3、是中序遍歷二叉樹(shù)的方法，遇到存放x的結(jié)點(diǎn)就將數(shù)值賦值給其數(shù)據(jù)域的變量。然后通過(guò)后序遍歷二叉樹(shù)的方法就行表達(dá)式求值。構(gòu)造復(fù)合表達(dá)式可以分別建立兩顆二叉樹(shù)，然后將這兩顆二叉樹(shù)作為新申請(qǐng)的運(yùn)算符結(jié)點(diǎn)的左右孩子結(jié)點(diǎn)。在化簡(jiǎn)表達(dá)式時(shí)，先判斷運(yùn)算符結(jié)點(diǎn)的兩個(gè)孩子節(jié)點(diǎn)是不是運(yùn)算數(shù)結(jié)點(diǎn)（不包括x結(jié)點(diǎn)）。如果兩個(gè)孩子節(jié)點(diǎn)是運(yùn)算數(shù)結(jié)點(diǎn)，就計(jì)算出這個(gè)子表達(dá)式的值并用其代替這個(gè)運(yùn)算符結(jié)點(diǎn)。 2.數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：抽象數(shù)據(jù)類型二叉樹(shù)的定義如下：ADT BinaryTree 數(shù)據(jù)對(duì)象D：D是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R：若D=，則R=，稱BinaryTree為空二叉樹(shù)；若D，則R=H，H是如下二元關(guān)系：（1）在D

4、中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無(wú)前驅(qū)；（2）若D-root，則存在D_root=D1,Dr,且D1Dr=；（3）若D1，則D1中存在唯一的元素X1，<root，X1>H，且存在D1上的關(guān)系H1H；若Dr，則Dr中存在唯一的元素Xr，<root,Xr>H,且存在Dr上的關(guān)系HrH；H=<root,X1>,<root,Xr>,H1,Hr；（4）（D1，H1）是一顆符合本定義的二叉樹(shù)，稱為根的左子樹(shù)，（Dr，Hr）是一顆符合本定義的二叉樹(shù)，稱為根的右子樹(shù)?；静僮鳎篊reatBitTree (BitTree T,BitTree p)

5、;操作結(jié)果：根據(jù)前綴表達(dá)式先序構(gòu)造二叉樹(shù)。InOrderTraverse(BitTree T)初始條件：二叉樹(shù)T存在。操作結(jié)果：中序遍歷二叉樹(shù)T，輸出每個(gè)結(jié)點(diǎn)的數(shù)據(jù)域且僅一次。InOrder(BitTree T,int *num);初始條件：二叉樹(shù)T存在且存在x結(jié)點(diǎn)。操作結(jié)果：將num賦值給x。PostOrderTraverse(BitTree T);初始條件：二叉樹(shù)T。操作結(jié)果：后序遍歷二叉樹(shù)求表達(dá)式的值。ADT BinaryTree3.軟件結(jié)構(gòu)設(shè)計(jì)：BitTree ReadExpr(BitTree T);BitTree WriteExpr(BitTree T)BitTree Assign(

6、BitTree T);BitTree Value(BitTree T);Int main（）Void menu（）void CompoundExpr(BitTree T);void MergeConstruction(BitTree T);退出！三、 詳細(xì)設(shè)計(jì) 1. 定義程序中所有用到的數(shù)據(jù)及其數(shù)據(jù)結(jié)構(gòu)，及其基本操作的實(shí)現(xiàn)；typedef struct BitNodechar data;int opnd;struct BitNode *lchild;struct BitNode *rchild;struct BitNode *parent;BitNode,*BitTree;2主函數(shù)和其他函數(shù)的

7、偽碼算法；(1)主函數(shù)：int main()BitTree T=NULL;T=(BitTree )malloc(sizeof(BitNode); if(T=NULL)printf("有錯(cuò)n");elseflag=0;menu(T);return 0;(2) 菜單函數(shù)：void menu(BitTree T)int sel=0;doprintf("nn");printf(" (1) 以字符序列的形式輸入語(yǔ)法正確的前綴表示式并構(gòu)造表達(dá)式 n");printf(" (2) 用帶括弧的中綴表達(dá)式輸出表達(dá)式 n");prin

8、tf(" (3) 實(shí)現(xiàn)對(duì)變量x的賦值（x=c）,變量的初值為0 n");printf(" (4) 對(duì)算術(shù)表達(dá)式求值 n");printf(" (5) 造一個(gè)新的復(fù)合表達(dá)式（E1）P(E2) n");printf(" (6) 表達(dá)式化簡(jiǎn)n");printf(" (0) 退出 n");printf(" 請(qǐng)輸入您的選擇:");scanf("%d",&sel);printf("%d",sel);system("cls"

9、;);switch(sel)case 1: T=ReadExpr(T);break;case 2: T=WriteExpr(T);break;case 3: T=Assign(T);break;case 4: T=Value(T);break;case 5: CompoundExpr(T);break;case 6: MergeConstruction(T);break;case 0: printf(" 已退出!n");break;while(sel!=0);(3) 構(gòu)建二叉樹(shù)函數(shù)：BitTree CreatBitTree (BitTree T,BitTree p) cha

10、r ch;ch=getche();if(In(ch)=0)printf("n表達(dá)式有誤,請(qǐng)重新輸入:n");T = CreatBitTree (T,p);return T;T=(BitTree )malloc(sizeof(BitNode); if(T=NULL)printf("有錯(cuò)n");elseif(In(ch)=2)if(ch='x')xflag=1;assg=0;T->data = ch;T->opnd = 0;elseT->data = 'N'T->opnd = ch-'0'

11、;else if(In(ch)=1)T->data = ch;T->opnd = 0;T->parent = p; p=T; if(In(ch)=2) T->lchild = NULL;T->rchild = NULL; else if(In(ch)=3) T->lchild = CreatBitTree(T->lchild ,p );T->rchild = NULL; else T->lchild = CreatBitTree(T->lchild ,p ); T->rchild = CreatBitTree(T->rch

12、ild ,p ); return T;(4) 中序遍歷二叉樹(shù)輸出帶括號(hào)中綴表達(dá)式的函數(shù)：void InOrderTraverse(BitTree T)if(T=NULL)return ;else if(Precede(T->data , T->parent->data )=-1) printf("(");InOrderTraverse(T->lchild);if(T->data = 'N')printf("%d",T->opnd);else printf("%c",T->dat

13、a); InOrderTraverse(T->rchild); printf(")");elseInOrderTraverse(T->lchild); if(T->data = 'N')printf("%d",T->opnd);else printf("%c",T->data); InOrderTraverse(T->rchild); (5) 中序遍歷二叉樹(shù)給變量x賦值的函數(shù)：void InOrder(BitTree T,int *num)if(T=NULL)return; else

14、 if(Precede(T->data , T->parent->data )=-1) printf("(");InOrder(T->lchild,num); if(T->data = 'N')printf("%d",T->opnd);else if(T->data = 'x')T->opnd = *num;printf("%d",T->opnd );else printf("%c",T->data);InOrder(T-&

15、gt;rchild,num); printf(")");elseInOrder(T->lchild,num); if(T->data = 'N')printf("%d",T->opnd);else if(T->data = 'x')T->opnd = *num;printf("%d",T->opnd );else printf("%c",T->data);InOrder(T->rchild,num); (6) 后序遍歷二叉樹(shù)求表達(dá)式值的

16、函數(shù)：void PostOrderTraverse(BitTree T)if(T=NULL)return; else PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild);if(In(T->data )=2)return;else if(In(T->data )=1)T->opnd = calculate(T->lchild ->opnd ,T->data ,T->rchild ->opnd ); (7) 構(gòu)造復(fù)合表達(dá)式的函數(shù)：void CompoundExpr(BitT

17、ree T)char optr;BitTree T1=NULL,T2=NULL;BitTree p;p=T1;printf("請(qǐng)以字符序列的形式輸入語(yǔ)法正確的前綴表示式E1:n");T1=CreatBitTree (T1,p);T1->parent = T1; printf("n二叉樹(shù)構(gòu)造成功!n");p=T2;printf("請(qǐng)以字符序列的形式輸入語(yǔ)法正確的前綴表示式E2:n");T2=CreatBitTree (T2,p);T2->parent = T2; printf("n二叉樹(shù)構(gòu)造成功!n");

18、printf("請(qǐng)輸入運(yùn)算符p:");getchar();scanf("%c",&optr);T->data = optr;T->opnd = 0;T->parent = T;T->lchild = T1;T->rchild = T2;T1->parent = T;T2->parent = T;flag=1;(8) 化簡(jiǎn)函數(shù)表達(dá)式的函數(shù)：void MergeConstruction(BitTree T)int a=1;printf("化簡(jiǎn)后表達(dá)式為: ");while(a=1)a=0;

19、huajian(T,&a);InOrderTraverse(T);printf("n");void huajian(BitTree T,int *a)if(T=NULL)return; else huajian(T->lchild,a); if(In(T->data )=1&&T->lchild ->data = 'N'&&T->rchild ->data = 'N')T->opnd = calculate(T->lchild ->opnd ,T-&

20、gt;data ,T->rchild ->opnd );T->data = 'N'T->lchild = NULL;T->rchild = NULL;*a=1;huajian(T->rchild,a); 開(kāi)始3. 主要函數(shù)的程序流程圖，實(shí)現(xiàn)設(shè)計(jì)中主程序和其他子模塊的算法，以流程圖的形式表示。輸入選項(xiàng)yesCreatBitTree (BitTree T,BitTree p)ReadExpr(T);選項(xiàng)1noInOrderTraverse(BitTree T)yesWriteExpr(BitTree T)選項(xiàng)2noyesInOrder(BitTr

21、eeT,int *num)Assign(BitTree T)選項(xiàng)3noyesPostOrderTraverse(BitTree T)Value(BitTree T)選項(xiàng)4noyesCreatBitTree (BitTree T,BitTree p) CompoundExr(BitTree T)選項(xiàng)5noyesHuajian(BitTree T,int *a)MergeConstruction(BitTreeT)選項(xiàng)6noyes選項(xiàng)0no結(jié)束4. 畫(huà)出函數(shù)之間的調(diào)用關(guān)系圖。BitTree ReadExpr(BitTree T);CreatBitTree (BitTree T,BitTree p)

22、BitTree WriteExpr(BitTree T)InOrderTraverse(BitTree T)BitTree Assign(BitTree T);InOrder(BitTreeT,int *num)Void menu（）Int main（）BitTree Value(BitTree T);PostOrderTraverse(BitTree T)void CompoundExpr(BitTree T);CreatBitTree (BitTree T,BitTree p) void MergeConstruction(BitTree T);Huajian(BitTree T,int

23、*a)四、 調(diào)試分析 1. 實(shí)際完成的情況說(shuō)明（完成的功能，支持的數(shù)據(jù)類型等）；（1）以字符序列的形式輸入正確的前綴表達(dá)式。（2）用帶括號(hào)的中綴表達(dá)式輸出表達(dá)式。（3）實(shí)現(xiàn)對(duì)變量x的賦值，初始值為0。（4）對(duì)算術(shù)表達(dá)式求值。（5）構(gòu)造新的復(fù)合表達(dá)式。（6) 對(duì)表達(dá)式化簡(jiǎn)。 2.程序的性能分析，包括時(shí)空分析；本程序?qū)崿F(xiàn)了通過(guò)遍歷二叉樹(shù)對(duì)表達(dá)式的求值，化簡(jiǎn)等操作。此外，可以增加一些其他的操作或者增加一些其他的運(yùn)算操作。 3.上機(jī)過(guò)程中出現(xiàn)的問(wèn)題及其解決方案；（1） 構(gòu)建的二叉樹(shù)為空。解決方案：通過(guò)傳地址的方式調(diào)用二叉樹(shù)操作函數(shù)。（2） 運(yùn)行程序是無(wú)法輸入字符。解決方案：用ch=getche();語(yǔ)

24、句接收字符。（3） 使用數(shù)學(xué)函數(shù)時(shí)出錯(cuò)。解決方案：添加頭文件#include <math.h>。4. 程序中可以改進(jìn)的地方說(shuō)明；本程序運(yùn)算數(shù)的輸入輸出局限于無(wú)符號(hào)整型數(shù)據(jù)，運(yùn)算符的輸入輸出包括“+、-、*、/、”?？梢酝ㄟ^(guò)改進(jìn)實(shí)現(xiàn)對(duì)浮點(diǎn)型數(shù)據(jù)的計(jì)算。另外，可以增加一些其他的運(yùn)算，例如三角函數(shù)，指數(shù)函數(shù)等等。5. 程序中可以擴(kuò)充的功能及設(shè)計(jì)實(shí)現(xiàn)假想。程序可以增加對(duì)操作符sin，cos，tan，cot，log，ln等運(yùn)算符的識(shí)別，也可以增加對(duì)浮點(diǎn)型數(shù)據(jù)的操作的功能。五、測(cè)試結(jié)果（1）構(gòu)建二叉樹(shù)（2）輸出帶括號(hào)的中綴表達(dá)式：（3）對(duì)變量x賦值：（4）對(duì)算術(shù)表達(dá)式求值：（5）構(gòu)造復(fù)合表達(dá)式：（6）化簡(jiǎn)表達(dá)式：（7）錯(cuò)誤提示：六、用戶手冊(cè)第一步：輸入選項(xiàng)一，構(gòu)建二叉樹(shù)。如下圖：第二步：輸入前綴表達(dá)式：第三步：輸入選項(xiàng)二，輸出