表達式類型的實現(xiàn)

..**理工大學數(shù)據結構課程設計報告題目： 表達式類型的實現(xiàn) 院〔系： 計算機工程學院 學生姓名: ** __計算111學號: 2011070** 起迄日期:——2012.7.19 指導教師: *** 一、需求分析1.問題描述：本程序通過輸入前綴表達式建立一顆二叉樹,通過中序遍歷建立好的二叉樹輸出帶括號的中綴表達式。然后中序遍歷二叉樹對表達式中的未知數(shù)x進行賦值。通過后序遍歷二叉樹計算表達式的值。根據兩顆二叉樹和輸入的運算符構造復合表達式。另外,通過中序遍歷二叉樹對表達式進行化簡。2.基本功能⑴以字符序列的形式輸入語法正確的前綴表示式并構成表達式E⑵用帶括號的中綴表達式輸出表達式E⑶實現(xiàn)對變量x的賦值,變量初始值為0⑷對算術表達式求值⑸構造新的復合表達式〔E1P〔E2⑹對表達式進行化簡3.輸入輸出本程序運算數(shù)的輸入輸出局限于無符號整型數(shù)據,運算符的輸入輸出包括"+、-、*、/、^"二、概要設計1.設計思路：本程序以字符序列的形式輸入語法正確的前綴表達式,在輸入表達式的過程中判斷輸入的字符是運算數(shù)還是運算符并將其保存到樹節(jié)點中相應的位置,表達式輸入結束的同時也就構成一顆二叉樹。根據建立好的二叉樹,可以采用中序遍歷二叉樹的方法輸出正常順序的表達式。在中序遍歷二叉樹時,訪問存放運算符的結點時要判斷其與雙親結點中運算符的優(yōu)先級關系來判斷是否要添加括號。在給表達式中的未知數(shù)x賦值時,本程序采用的是中序遍歷二叉樹的方法,遇到存放x的結點就將數(shù)值賦值給其數(shù)據域的變量。然后通過后序遍歷二叉樹的方法就行表達式求值。構造復合表達式可以分別建立兩顆二叉樹,然后將這兩顆二叉樹作為新申請的運算符結點的左右孩子結點。在化簡表達式時,先判斷運算符結點的兩個孩子節(jié)點是不是運算數(shù)結點〔不包括x結點。如果兩個孩子節(jié)點是運算數(shù)結點,就計算出這個子表達式的值并用其代替這個運算符結點。2.數(shù)據結構設計：抽象數(shù)據類型二叉樹的定義如下：ADTBinaryTree{

數(shù)據對象D：D是具有相同特性的數(shù)據元素的集合。數(shù)據關系R：若D=φ,則R=φ,稱BinaryTree為空二叉樹；若D≠φ,則R={H},H是如下二元關系：〔1在D中存在唯一的稱為根的數(shù)據元素root,它在關系H下無前驅；〔2若D-{root}≠φ,則存在D_{root}={D1,Dr},且D1∩Dr=φ；〔3若D1≠φ,則D1中存在唯一的元素X1,<root,X1>∈H,且存在 D1上的關系H1∈H；若Dr≠φ,則Dr中存在唯一的元素Xr,<root,Xr> ∈H,且存在Dr上的關系Hr∈H；H={<root,X1>,<root,Xr>,H1,Hr}；〔4〔D1,{H1}是一顆符合本定義的二叉樹,稱為根的左子樹,〔Dr,{Hr} 是一顆符合本定義的二叉樹,稱為根的右子樹?；静僮鳎篊reatBitTree<BitTreeT,BitTreep>;操作結果：根據前綴表達式先序構造二叉樹。InOrderTraverse<BitTreeT>初始條件：二叉樹T存在。操作結果：中序遍歷二叉樹T,輸出每個結點的數(shù)據域且僅一次。InOrder<BitTreeT,int*num>;初始條件：二叉樹T存在且存在x結點。操作結果：將num賦值給x。PostOrderTraverse<BitTreeT>;初始條件：二叉樹T。操作結果：后序遍歷二叉樹求表達式的值。}ADTBinaryTree3.軟件結構設計：BitTreeReadExpr<BitTreeT>;BitTreeReadExpr<BitTreeT>;BitTreeWriteExpr<BitTreeT>BitTreeWriteExpr<BitTreeT>BitTreeAssign<BitTreeT>;BitTreeAssign<BitTreeT>;BitTreeValue<BitTreeT>;BitTreeValue<BitTreeT>;Intmain〔Voidmenu〔Intmain〔Voidmenu〔voidCompoundExpr<BitTreeT>;voidCompoundExpr<BitTreeT>;voidMergeConstruction<BitTreeT>;voidMergeConstruction<BitTreeT>;退出！退出！三、詳細設計定義程序中所有用到的數(shù)據及其數(shù)據結構,及其基本操作的實現(xiàn)；typedefstructBitNode{ chardata; intopnd; structBitNode*lchild; structBitNode*rchild; structBitNode*parent;}BitNode,*BitTree;2．主函數(shù)和其他函數(shù)的偽碼算法；<1>主函數(shù)：intmain<>{ BitTreeT=NULL; T=<BitTree>malloc<sizeof<BitNode>>; if<T==NULL> {printf<"有錯\n">;} else { flag=0; menu<T>; } return0;}菜單函數(shù)：voidmenu<BitTreeT>{ intsel=0; do { printf<"\n\n">; printf<"<1>以字符序列的形式輸入語法正確的前綴表示式并構造表達式\n">; printf<"<2>用帶括弧的中綴表達式輸出表達式\n">; printf<"<3>實現(xiàn)對變量x的賦值〔x=c,變量的初值為0\n">; printf<"<4>對算術表達式求值\n">; printf<"<5>造一個新的復合表達式〔E1P<E2>\n">; printf<"<6>表達式化簡\n">; printf<"<0>退出\n">; printf<"請輸入您的選擇:">; scanf<"%d",&sel>;printf<"%d",sel>; system<"cls">; switch<sel> { case1:T=ReadExpr<T>;break; case2:T=WriteExpr<T>;break; case3:T=Assign<T>;break; case4:T=Value<T>;break; case5:CompoundExpr<T>;break; case6:MergeConstruction<T>;break; case0:printf<"已退出!\n">;break; } }while<sel!=0>;}構建二叉樹函數(shù)：BitTreeCreatBitTree<BitTreeT,BitTreep>{ charch; ch=getche<>; if<In<ch>==0> { printf<"\n表達式有誤,請重新輸入:\n">; T=CreatBitTree<T,p>; returnT; } T=<BitTree>malloc<sizeof<BitNode>>; if<T==NULL> {printf<"有錯\n">;} else { if<In<ch>==2> { if<ch=='x'> { xflag=1; assg=0; T->data=ch; T->opnd=0; } else { T->data='N'; T->opnd=ch-'0'; } } elseif<In<ch>==1> { T->data=ch; T->opnd=0; } T->parent=p; p=T; if<In<ch>==2> { T->lchild=NULL; T->rchild=NULL; } elseif<In<ch>==3> { T->lchild=CreatBitTree<T->lchild,p>; T->rchild=NULL; } else { T->lchild=CreatBitTree<T->lchild,p>; T->rchild=CreatBitTree<T->rchild,p>; } } returnT;}中序遍歷二叉樹輸出帶括號中綴表達式的函數(shù)：voidInOrderTraverse<BitTreeT>{ 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->data>; } InOrderTraverse<T->rchild>; printf<">">; } else { InOrderTraverse<T->lchild>; if<T->data=='N'> { printf<"%d",T->opnd>; } else { printf<"%c",T->data>; } InOrderTraverse<T->rchild>; }}}中序遍歷二叉樹給變量x賦值的函數(shù)：voidInOrder<BitTreeT,int*num>{ if<T==NULL> return; else { if<Precede<T->data,T->parent->data>==-1> { printf<"<">; InOrder<T->lchild,num>; if<T->data=='N'> { printf<"%d",T->opnd>; } elseif<T->data=='x'> {T->opnd=*num; printf<"%d",T->opnd>; } else printf<"%c",T->data>; InOrder<T->rchild,num>; printf<">">; } else {InOrder<T->lchild,num>; if<T->data=='N'> {printf<"%d",T->opnd>;} elseif<T->data=='x'> { T->opnd=*num; printf<"%d",T->opnd>; } else printf<"%c",T->data>; InOrder<T->rchild,num>; }}}后序遍歷二叉樹求表達式值的函數(shù)：voidPostOrderTraverse<BitTreeT>{if<T==NULL> return; else { PostOrderTraverse<T->lchild>; PostOrderTraverse<T->rchild>; if<In<T->data>==2> return; elseif<In<T->data>==1> T->opnd=calculate<T->lchild->opnd,T->data,T->rchild->opnd>;}}構造復合表達式的函數(shù)：voidCompoundExpr<BitTreeT>{ charoptr; BitTreeT1=NULL,T2=NULL; BitTreep; p=T1; printf<"請以字符序列的形式輸入語法正確的前綴表示式E1:\n">; T1=CreatBitTree<T1,p>; T1->parent=T1; printf<"\n二叉樹構造成功!\n">; p=T2; printf<"請以字符序列的形式輸入語法正確的前綴表示式E2:\n">; T2=CreatBitTree<T2,p>; T2->parent=T2; printf<"\n二叉樹構造成功!\n">; printf<"請輸入運算符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;}化簡函數(shù)表達式的函數(shù)：voidMergeConstruction<BitTreeT>{inta=1; printf<"化簡后表達式為:">; while<a==1> {a=0; huajian<T,&a>; } InOrderTraverse<T>; printf<"\n">;}voidhuajian<BitTreeT,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->data,T->rchild->opnd>; T->data='N'; T->lchild=NULL; T->rchild=NULL; *a=1; } huajian<T->rchild,a>; }}開始主要函數(shù)的程序流程圖,實現(xiàn)設計中主程序和其他子模塊的算法,以流程圖的形式表示。開始輸入選項輸入選項yesCreatBitTree<BitTreeT,BitTreep>yesCreatBitTree<BitTreeT,BitTreep>ReadExpr<T>;選項1ReadExpr<T>;選項1nonoInOrderTraverse<BitTreeT>InOrderTraverse<BitTreeT>yesWriteExpr<BitTreeT>WriteExpr<BitTreeT>選項2nonoyesyesInOrder<BitTreeT,int*num>AssignInOrder<BitTreeT,int*num>Assign<BitTreeT>選項3nonoyesyesPostOrderTraverse<BitTreeT>Value<BitTreeT>PostOrderTraverse<BitTreeT>Value<BitTreeT>選項4nonoyesyesCreatBitTree<BitTreeT,BitTreep>CompoundExr<BitTreeT>選項5CreatBitTree<BitTreeT,BitTreep>CompoundExr<BitTreeT>選項5nonoyesyesHuajian<BitTreeT,int*a>MergeConstruction<BitTreeT>Huajian<BitTreeT,int*a>MergeConstruction<BitTreeT>選項6nonoyesyes選項0選項0nono結束結束畫出函數(shù)之間的調用關系圖。BitTreeReadExpr<BitTreeT>;BitTreeReadExpr<BitTreeT>;CreatBitTree<BitTreeT,BitTreep>CreatBitTree<BitTreeT,BitTreep>BitTreeWriteExpr<BitTreeT>BitTreeWriteExpr<BitTreeT>InOrderTraverseInOrderTraverse<BitTreeT>BitTreeAssign<BitTreeT>;BitTreeAssign<BitTreeT>;InOrder<BitTreeT,int*num>InOrder<BitTreeT,int*num>Voidmenu〔Intmain〔BitTreeValue<BitTreeT>;Voidmenu〔Intmain〔BitTreeValue<BitTreeT>;PostOrderTraverse<BitTreeT>PostOrderTraverse<BitTreeT>voidCompoundExpr<BitTreeT>;voidCompoundExpr<BitTreeT>;CreatBitTree<BitTreeT,BitTreep>CreatBitTree<BitTreeT,BitTreep>voidMergeConstruction<BitTreeT>;voidMergeConstruction<BitTreeT>;HuajianHuajian<BitTreeT,int*a>調試分析實際完成的情況說明〔完成的功能,支持的數(shù)據類型等；〔1以字符序列的形式輸入正確的前綴表達式。〔2用帶括號的中綴表達式輸出表達式。〔3實現(xiàn)對變量x的賦值,初始值為0。〔4對算術表達式求值?！?構造新的復合表達式?！?>對表達式化簡。2.程序的性能分析,包括時空分析；本程序實現(xiàn)了通過遍歷二叉樹對表達式的求值,化簡等操作。此外,可以增加一些其他的操作或者增加一些其他的運算操作。3.上機過程中出現(xiàn)的問題及其解決方案；構建的二叉樹為空。解決方案：通過傳地址的方式調用二叉樹操作函數(shù)。運行程序是無法輸入字符。解決方案：用ch=getche<>;語句接收字符。使用數(shù)學函數(shù)時出錯。解決方案：添加頭文件#include<math.h>。程序中可以改進的地方說明；本程序運算數(shù)的輸入輸出局限于無符號整型數(shù)據,運算符的輸入輸出包括"+、-、*、/、^"?？梢酝ㄟ^改進實現(xiàn)對浮點型數(shù)據的計算。另外,可以增加一些其他的運算,例如三角函數(shù),指數(shù)函數(shù)等等。程序中可以擴充的功能及設計實現(xiàn)假想。程序可以增加對操作符sin,cos,tan,cot