課程設計報告-表達式類型的實現-方銳洲.doc

《課程設計報告-表達式類型的實現-方銳洲.doc》由會員分享，可在線閱讀，更多相關《課程設計報告-表達式類型的實現-方銳洲.doc（36頁珍藏版）》請在裝配圖網上搜索。

<<數據結構>> 課程設計 表達式類型的實現 學 院 計算機學院 專 業(yè) 計算機科學與技術 年級班別 2006級01班 學 號 3106006394 學生姓名 方銳洲 輔導教師__ 吳偉民_______ 成 績_______ ______ 2008年7月 3 日 ~~~~~~~~~~表達式類型的實現~~~~~~~~~~ 目錄： 一、需求分析------------------------3 二、概要設計-----------------------3-6 1、數據類型的聲明： 2、表達式的抽象數據類型定義 3、整體設計 三、詳細設計----------------------7-13 1、二叉樹的存儲類型 2、順序棧的存儲類型 3、表達式的基本操作 4、主程序和其他偽碼算法 5、函數的調用關系 四、設計和調試分析-------------------14 五、用戶手冊------------------------14 六、測試--------------------------15-18 七、課程設計的心得和心得以及問題-----18 八、參考文獻------------------------19 九、附錄：程序清單-----------------19-35 一、需求分析【課程設計要求】 【問題的描述】 一個表達式和一棵二叉樹之間，存在著自然的對應關系。寫一個程序，實現基于二叉樹表示的算術表達式Expression的操作。 【基本要求】 【一】【必做部分】 假設算術表達式Expression內可以含有變量（a-z）,常量（0-9）和二元運算符（+，-，*，/，^（乘冪））。實現以下操作： （1）ReadExpr(E)――以字符序列的形式輸入語法正確的前綴表達式并構造表達式E。 （2）WriteExpr(E)――用帶括號的中綴表達式輸出表達式E。 （3）Assign(V，c)――實現對變量V的賦值（V=c），變量的初值為0。 （4）Value(E)――對算術表達式E求值。 （5）CompoundExpr(p,E1,E2)――構造一個新的復合表達式（E1）p（E2）。 【二】【選做部分】 （1）以表達式的原書寫形式輸入，支持大于0的正整數常量； （2）增加常數合并操作MergeConst(E)——合并表達式E中所有常數運算。例如，對表達式E=(2+3-a)*(b+3*4)進行合并常數的操作后，求得E=(5-a)*(b+12) 【測試數據】 1) 分別輸入0；a;-91;+a*bc;+*5x2*8x;+++*3^*2^x2x6并輸出。 2) 每當輸入一個表達式后，對其中的變量賦值，然后對表達式求值。 3) 還有很多測試的數據，詳細請見附上的文件Test.txt。 二、概要設計 1、數據類型的聲明： 在這個課程設計中，采用了鏈表二叉樹的存儲結構，以及兩個順序棧的輔助存儲結構 /*頭文件以及存儲結構*/ #include #include #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW 0 typedef int Status; 2、表達式的抽象數據類型定義 ADT Expression{ 數據對象D：D是具有數值的常量C和沒有數值的變量V； 數據關系：R={<(V或者C)P(V或者C)>|V,C∈D, <(V或者C)P(V或者C)>表示由運算符P結合起來的表達式E} 基本操作： Status Input_Expr(&string,flag) 操作結果：以字符序列的形式輸入語法正確的前綴表達式，保存到字符串string； 參數flag表示輸出的提示信息是什么，輸入成功返回OK，否則，返回ERROR。 void judge_value(&E,&string,i) 初始條件：樹E存在，表達式的前綴字符串string存在； 操作結果：判斷字符string[i]，如果是0-9常量之間，二叉樹結點E存為整型；否則，存為字符型。 Status ReadExpr(&E,&exprstring) 初始條件：表達式的前綴形式字符串exprstring存在； 操作結果：以正確的前綴表示式exprstring并構造表達式E，構造成功，返回OK，否則返回ERROR。 Status Pri_Compare(c1,c2) 初始條件：c1和c2是字符； 操作結果：如果兩個字符是運算符，比較兩個運算符的優(yōu)先級，c1比c2優(yōu)先，返回OK，否則返回ERROR。 void WriteExpr(&E) 初始條件：表達式E存在； 操作條件：用帶括弧的中綴表達式輸入表達式E。 void Assign(&E,V,c,&flag) 初始條件：表達式E存在，flag為標志是否有賦值過； 操作結果：實現對表達式E中的所有變量V的賦值(V=c)。 long Operate(opr1,opr,opr2) 初始條件：操作數opr1和操作數opr2以及操作運算符opr; 操作結果：運算符運算求值，參數opr1,opr2為常量，opr為運算符，根據不同的運算符，實現不同的運算，返回運算結果。 Status Check(E) 初始條件：表達式E存在； 操作結果：檢查表達式E是否還存在沒有賦值的變量，以便求算數表達式E的值。 long Value(E) 初始條件：表達式E存在； 操作結果：對算術表達式求值，返回求到的結果。 void CompoundExpr(P,&E1,E2) 初始條件：表達式E1和E2存在； 操作條件：構造一個新的復合表達式(E1)P(E2)。 Status Read_Inorder_Expr(&string,&pre_expr) 操作結果：以表達式的原書寫形式輸入，表達式的原書寫形式字符串string變?yōu)樽址畃re_expr，后調用reversal_string()函數反轉得到前綴表達式pre_expr。得到正確的前綴表達式返回OK，否則，返回ERROR。 void MergeConst(&E) 操作結果：常數合并操作，合并表達式E中所有常數運算。 }ADT Expression 3、整體設計 在這個課程設計中，有兩個源代碼文件：expression.h和expression.c。 在expression.h文件中，包含了各個存儲結構的聲明和輔助存儲結構的兩個棧的基本操作；在expression.c文件中，是實現課程設計要求的各個函數。 《一》expression.h文件的整體結構 1、各個存儲結構的聲明； 2、兩個除了棧名和棧存儲的元素不一樣的順序棧的基本操作。其基本操作如下： 對于棧SqStack: Status InitStack(SqStack *S) /* 構造一個空棧S */ Status StackEmpty(SqStack S) /* 若棧S為空棧，則返回TRUE，否則返回FALSE */ Status Push(SqStack *S,SElemType e) /* 插入元素e為新的棧頂元素 */ Status Pop(SqStack *S,SElemType *e) /* 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR */ Status GetTop(SqStack S,SElemType *e) /* 若棧不空，則用e返回S的棧頂元素，并返回OK；否則返回ERROR */ 對于棧SqStack1: Status InitStack1(SqStack1 *S) /* 構造一個空棧S */ Status StackEmpty1(SqStack1 S) /* 若棧S為空棧，則返回TRUE，否則返回FALSE */ Status Push1(SqStack1 *S,SElemType1 e) /* 插入元素e為新的棧頂元素 */ Status Pop1(SqStack1 *S,SElemType1 *e) /* 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR */ Status GetTop1(SqStack1 S,SElemType1 *e) /* 若棧不空，則用e返回S的棧頂元素，并返回OK；否則返回ERROR */ 順序棧的基本操作的算法見程序清單。 《二》expression.c文件的整體結構 1、主程序模塊的整體流程 可以從主菜單函數可以明了的了解的程序的整體流程，主菜單函數menu()如下： char menu() { char choice; printf("\n****************************************"); printf("\n 1 >>>輸入正確的前綴表達式"); printf("\n 2 >>>帶括弧的中綴表示式輸出"); printf("\n 3 >>>對變量進行賦值"); printf("\n 4 >>>對算數表達式求值"); printf("\n 5 >>>構造一個新的復合表達式"); printf("\n 6 >>>以表達式的原書寫形式輸入"); printf("\n 7 >>>合并表達式中所有常數運算"); printf("\n 0 >>>退出"); printf("\n****************************************"); printf("\n請輸入你的選擇>>>>>"); choice=getche(); return choice; } 在主函數中，采用多分支程序設計語句switch()使程序產生不同的流向，從而達到實現課程設計的各個要求。 void main() { while(1) { 清屏； switch(主菜單) { 根據不同的選擇，調用不同的操作函數，完成各個操作； } } } 2、本程序有四個模塊，主程序模塊，二叉樹模塊，兩個順序棧模塊。四者的調用關系如下： 主程序模塊 二叉樹模塊 順序棧SqStack模塊 順序棧SqStack1模塊 主程序模塊中的對于表達式的存儲結構調用了二叉樹模塊，而在構造表達式的二叉樹模塊中又調用了順序棧SqStack模塊，主程序中在將原表達式形式輸入表達式轉換為前綴表達式操作中調用了順序棧SqStack1模塊。 三、詳細設計 1、二叉樹的存儲類型 /*二叉樹結點類型*/ typedef enum{INT,CHAR}ElemTag;/*INT為整型數據num，CHAR為字符型數據c*/ typedef struct TElemType { ElemTag tag;/*{INT,CHAR}指示是整型還是字符型*/ union { int num;/*tag=INT時，為整型*/ char c;/*tag=CHAR時，為字符型*/ }; } TElemType; /*二叉樹的二叉鏈表存儲表示 */ typedef struct BiTNode { TElemType data; struct BiTNode *lchild,*rchild; /* 左右孩子指針 */ }BiTNode,*BiTree; 二叉樹的基本操作已經在構造表達式和表達式中的基本操作中根據不同的功能和實際情況修改了，詳細見各個函數操作的算法設計。 2、順序棧的存儲類型 /*棧的順序存儲表示 */ #define STACK_INIT_SIZE 10 /* 存儲空間初始分配量 */ #define STACKINCREMENT 2 /* 存儲空間分配增量 */ /*兩個順序棧*/ typedef struct SqStack { SElemType *base; /* 在棧構造之前和銷毀之后，base的值為NULL */ SElemType *top; /* 棧頂指針 */ int stacksize; /* 當前已分配的存儲空間，以元素為單位 */ }SqStack; /* 順序棧SqStack */ typedef struct SqStack1 { SElemType1 *base; /* 在棧構造之前和銷毀之后，base的值為NULL */ SElemType1 *top; /* 棧頂指針 */ int stacksize; /* 當前已分配的存儲空間，以元素為單位 */ }SqStack1; /* 順序棧SqStack1 */ 相關的基本操作見上面的“expression.h文件的整體結構”的說明，詳細的算法設計見附錄的程序清單。 3、表達式的基本操作 Status Input_Expr(char *string,int flag); /*以字符序列的形式輸入語法正確的前綴表達式，保存到字符串string*/ /*參數flag=0表示輸出的提示信息是"請輸入正確的前綴表示式："*/ /*flag=1表示輸出的提示信息為"請以表達式的原書寫形式輸入正確表示式："*/ void judge_value(BiTree *E,char *string,int i); /*判斷字符string[i]，如果是0-9常量之間，二叉樹結點存為整型；否則，存為字符型*/ Status ReadExpr(BiTree *E,char *exprstring); /*以正確的前綴表示式并構造表達式E*/ Status Pri_Compare(char c1,char c2); /*如果兩個字符是運算符，比較兩個運算符的優(yōu)先級，c1比c2優(yōu)先，返回OK，否則返回ERROR*/ void WriteExpr(BiTree E); /*用帶括弧的中綴表達式輸入表達式*/ void Assign(BiTree *E,char V,int c,int *flag); /*實現對表達式中的所有變量V的賦值(V=c)，參數flag為表示是否賦值過的標志*/ long Operate(int opr1,char opr,int opr2); /*運算符運算求值，參數opr1,opr2為常量，opr為運算符，根據不同的運算符，實現不同的運算，返回運算結果*/ Status Check(BiTree E); /*檢查表達式是否還存在沒有賦值的變量，以便求算數表達式的值*/ long Value(BiTree E); /*對算術表達式求值*/ void CompoundExpr(char P,BiTree *E1,BiTree E2); /*構造一個新的復合表達式*/ Status Read_Inorder_Expr(char *string,char *pre_expr); /*以表達式的原書寫形式輸入，表達式的原書寫形式字符串string變?yōu)樽址畃re_expr，后調用reversal_string()函數反轉得到前綴表達式pre_expr*/ void MergeConst(BiTree *E); /*常數合并操作函數，合并表達式E中所有常數運算*/ 下面列出部分基本操作的偽碼算法，未列出的請見程序清單。 其中部分基本操作的偽碼算法如下： Status ReadExpr(BiTree *E,char *exprstring) {/*以正確的前綴表示式并構造表達式E*/ 申請根結點空間(*E)=(BiTree)malloc(sizeof(BiTNode));并且左右孩子指針置空； 表達式只有一個字符，二叉樹只有根結點； 否則 { judge_value(E,exprstring,0);將exprstring[0]存入二叉樹的結點中 InitStack(&S);/*初始化棧*/ Push(&S,q); Push(&S,q); 入棧，根結點入棧兩次是為判斷先序輸入的表達式是不是正確的表達式 for(i=1;i=len判斷輸入的表達式是正確的； 正確返回OK，錯誤返回ERROR; } } void WriteExpr(BiTree E) {/*用帶括弧的中綴表達式輸入表達式*/ if(E)/*樹不為空*/ { 先遞歸左子樹; WriteExpr(E->lchild); 其中要考慮何時帶括弧輸出： if(Pri_Compare(E->data.c,E->lchild->data.c)) E->data.c比E->lchild->data.c優(yōu)先,帶括弧輸出左子樹; 訪問輸出根結點的值; 后遞歸右子樹; WriteExpr(E->lchild); 其中要考慮何時帶括弧輸出： if(Pri_Compare(E->data.c,E->lchild->data.c)) E->data.c比E->lchild->data.c優(yōu)先,帶括弧輸出右子樹; } } void Assign(BiTree *E,char V,int c,int *flag) {/*實現對表達式中的所有變量V的賦值(V=c)，參數flag為表示是否賦值過的標志*/ if(*E)/*樹不空*/ { if((*E)->data.tag==CHAR&&(*E)->data.c==V) {如果找到要賦值的變量，賦值；*flag=1;} Assign(&((*E)->lchild),V,c,flag);/*遞歸左子樹*/ Assign(&((*E)->rchild),V,c,flag);/*遞歸左子樹*/ } } long Operate(int opr1,char opr,int opr2) {/*運算符運算求值，參數opr1,opr2為常量，opr為運算符，根據不同的運算符，實現不同的運算，返回運算結果*/ switch(opr) { 根據不同的運算符，進入不同分支求出result； 后返回result; } } Status Check(BiTree E) {/*檢查表達式是否還存在沒有賦值的變量，以便求算數表達式的值*/ if(E&&E->data.tag==CHAR)/*樹不為空*/ { 如果找到沒有賦值的變量，返回ERROR； if(Check(E->lchild))/*遞歸左子樹*/ Check(E->rchild);/*遞歸右子樹*/ } } long Value(BiTree E); {/*對算術表達式求值*/ if(E)/*樹不為空*/ { 如果是葉子結點，返回葉子的結點的值； return Operate(Value(E->lchild),E->data.c,Value(E->rchild));后根遍歷的次序對表達式求值； } } void CompoundExpr(char P,BiTree *E1,BiTree E2); {/*構造一個新的復合表達式*/ E=(BiTree)malloc(sizeof(BiTNode));/*申請一個結點存放運算符P*/ E->lchild=(*E1);/*結點的左孩子為E1*/ E->rchild=E2;/*結點的右孩子為E2*/ (*E1)=E;/*(*E1)為根結點*/ } Status Read_Inorder_Expr(char *string,char *pre_expr); {/*以表達式的原書寫形式輸入，表達式的原書寫形式字符串string變?yōu)樽址畃re_expr，后調用reversal_string()函數反轉得到前綴表達式pre_expr*/ InitStack1(&S);/*初始棧*/ c=string[len-1];從字符串的最后一個字符開始向前掃描, len=strlen(string); while(!StackEmpty1(S)&&i>=0)/*棧不為空且i大于等于0*/ { if(c==()字符為(, Pop1(&S,&c); while(c!=))假如c不為),出棧; else if(c==))字符為)，入棧, Push1(&S,c); else if(c>=0&&c<=9) 字符為0-9之間，循環(huán)掃描string前一個字符，后確定常量的大小; else if((c>=a&&c<=z)||(c>=A&&c<=Z)) 字符為a-z或A-Z之間的變量; else if(c==*||c==/)字符為運算符*或/ 比較優(yōu)先級，后確定是入棧還是出棧； else if(c==+||c==-)字符為運算符+或- 比較優(yōu)先級，后確定是入棧還是出棧； else if(c==^)字符為運算符^ 優(yōu)先級最大，不用比較，直接入棧； else {printf("\n輸入的表達式有誤！");return ERROR;} 其他字符，錯誤，返回ERROR。 下一個字符，繼續(xù)循環(huán)。 } *pre_expr=\0;/*字符串結束符*/ 判斷構造是否成功，成功返回OK；否則返回ERROR; } void MergeConst(BiTree *E); {/*常數合并操作函數，合并表達式E中所有常數運算*/ if((*E)->lchild&&(*E)->rchild)左右孩子不為空 { if((*E)->lchild->data.tag==INT&&(*E)->rchild->data.tag==INT) 假如左右孩子為常量，合并,并且刪除常量的結點； else { MergeConst(&((*E)->lchild));/*遞歸左孩子*/ MergeConst(&((*E)->rchild));/*遞歸右孩子*/ } } } 4、主程序和其他偽碼算法 void main() { while(1) { switch(menu()) { case 1:/*輸入正確的前綴表達式*/ if(Input_Expr(Expr_String,0))輸入正確的前綴表達式 if(ReadExpr(&E,Expr_String))構造表達式 {flag=1;printf("\n表達式構造成功！");} case 2:/*帶括弧的中綴表示式輸出*/ if(flag==1) WriteExpr(E); else printf("\n表達式未構造成功！請構造成功的表達式！"); case 3:/*對變量進行賦值*/ if(flag==1) { flushall();/*清理緩沖區(qū)*/ V=getchar(); scanf(&c); Assign(&E,V,c,&Assign_flag); } else printf("\n表達式未構造成功！請構造成功的表達式！"); case 4:/*對算數表達式求值*/ if(flag==1) { if(Check(E)) {result=Value(E); WriteExpr(E);printf(result);} } else printf("\n表達式未構造成功！請構造成功的表達式！"); case 5:/*構造一個新的復合表達式*/ if(flag==1) { flushall();/*清理緩沖區(qū)*/ if(Input_Expr(string,1)) { if(Read_Inorder_Expr(string,Expr_String)) {/*按原表達式形式輸入*/ reversal_string(Expr_String); if(ReadExpr(&E1,Expr_String)) { flag=1;P=getchar(); CompoundExpr(P,&E,E1); } else printf("\n復合新的表達式失?。≌埌慈我怄I返回主菜單！"); } } } case 6:/*以表達式的原書寫形式輸入*/ if(Input_Expr(string,1)) if(Read_Inorder_Expr(string,Expr_String)) { reversal_string(Expr_String); if(ReadExpr(&E,Expr_String)) {flag=1;printf("\n表達式構造成功！");} } case 7:/*合并表達式中所有常數運算*/ if(flag==1) MergeConst(&E); case 0:/*退出*/ } } } 5、函數的調用關系 除了主函數main()外，其他各個函數相對于其它函數來說是獨立的，函數的使用都由主函數main()調用使用的，可以簡單的說，各個函數都是主函數下的從函數。 四、設計和調試分析 1、在起初設計上，針對前綴表達式的要求構造表達式E，常量的范圍限定在0-9之間，后在這個構造表達式的架構上逐個逐個實現對表達式上的操作；后擴展到以表達式的原書寫形式輸入，整體架構是不變的，只是增加一些細節(jié)的處理功能。這樣的設計從開始到最后都處于可擴展的模塊化設計。 2、在算法設計中，構造表達式樹的時候，本來以為使用遞歸構造表達式會很難做到出錯處理的，所以采用了順序棧輔助構造方法，并且盡可能地對程序進行完善，出錯處理。但是經過與同學的相互討論和研究，發(fā)現自己的想法犯了很大的錯誤，遞歸構造表達式對于出錯處理很簡單也很完善，這一點讓我加深了遞歸的使用和理解。 3、在對各個功能操作的實現上，時間復雜度大多數是O(n)，空間上增加了輔助棧，空間復雜度為O(n+s)。而在以原表達式形式輸入操作上，實際上是對字符串的操作，將一串原表達式字符串處理為前綴表達式字符串而已，算法時間復雜度取決于輸入的字符串的長度n，即O(n)，空間復雜度為O(2n+s)。整體的算法設計沒有什么可取之處，對于減少時間復雜度和空間復雜度上沒有什么細細考慮。 4、在調試的過程中，花費時間最為多的是對輸入錯誤表達式的出錯處理，更改增加的代碼幾乎都是為了出錯處理，但是，覺得這樣的調試才更能鍛煉一個人的編程能力。課程設計注重的不單單只是基本程序的完成，更多注重的是出錯處理和界面的美化！ 五、用戶手冊 1、本程序的運行環(huán)境為DOS操作系統(tǒng)，執(zhí)行文件為：expression.exe； 2、進入演示程序后首先出現一個主菜單，主菜單界面如下： 3、之后輸入你的選擇，進入你所要進行的操作中。 六、測試 《一》選擇‘1’進入測試輸入正確的前綴表達式操作 1、輸入的前綴表達式為一個不大于9常量：‘8’ 2、輸入前綴表達式為一個變量：‘Z’ 3、輸入前綴表達式為一個簡單的運算表達式：‘-91’ 4、輸入前綴表達式為一個較為復雜的、帶有變量的表達式：‘+++*3^x3*2^x2x6’ 5、輸入前綴表達式‘*-+23a+b*34’，輸出帶括弧的表達式 6、輸入錯誤的前綴表達式：‘+999’和‘+*5^x2*8x&’ 《二》選擇‘3’進入測試對變量的賦值 1、對前綴表達式‘3*x^3+2*x^2+x+6’中變量x進行賦值，賦值為5 2、對前綴表達式‘a+b*c’中的變量b進行賦值，賦值為6 3、對前綴表達式‘5*x^2+8*x’中不存在的變量y進行賦值，賦值為4 《三》選擇‘4’進入測試求算數表達式的值 1、求算數表達式‘9+8’的值 2、求算數表達式‘（65+98）*（9^2+(21-96)）’的值 3、求仍存在變量的表達式‘3+a*9-6’的值 《四》選擇‘5’進入構造新的復合表達式 1、未構造表達式E時 2、已構造了表達式E時 《五》選擇‘6’進入以原表達式形式輸入構造表達式 1、構造表達式‘6*a+9/b-(a+2^3)’ 輸出的結果少了括弧，這個是程序中的一個BUG，程序的判定帶括弧輸出表達式時判斷兩個優(yōu)先級別時的一個很大的BUG，一個本人自己沒法解決的BUG。 2、構造表達式‘(((3+2)*9)-(6/3)*9+1)/8+18*3’ 輸出的結果簡化了多余的括弧，這一點是一個很大的優(yōu)化。 3、構造表達式‘66++’，出錯處理 4、構造表達式‘6+-b+9*9’，出錯處理 5、構造表達式‘9+a+(6+5))*a’,出錯處理多余輸入的括弧 6、構造表達式‘6#9+8*6’，出錯處理輸入非運算符和非變量常量的表達式 《六》選擇‘7’進入合并常數操作 1、構造表達式‘(2+3-a)*(b+3*4)’，后合并常數操作 2、構造表達式‘（3+3*4）*(1*2+8/2)’，經過多次合并，得出最后結果 這個合并常數操作唯一的缺點就是要多次操作，但是，這個缺點也不能說為缺點，它可以很清晰的反映出表達式求值的步驟！ 經過對各個操作的測試，可以這樣總結的說，基本完成了課程設計的要求，雖說其中有一些操作還存在BUG需要去完善改進。 七、課程設計的心得和體會以及問題 此次課程設計相對于我來說，難度適中，相對于這個學期寫的那些小算法來說，這個課程設計能充分發(fā)揮出學習數據結構后的能力；而相對于之前做的設計性實驗，又有了實際的應用，現實應用度增加。 從接觸C語言編程到現在，我就覺得：編程不是簡簡單單的寫出程序，更多的是出錯處理和界面設計。這次課程設計中，更讓我深刻體會到這個道理。編出大體的程序架構，花費了我的時間不多，而花費了我很多時間的是在調試和測試數據上！這次課程設計，不僅訓練了我對Visual C++6.0的調試器的操作的熟練度；而且，讓我在發(fā)現問題解決問題中深刻地理解到完善程序的重要性。 這次課程設計在技術上的學習上，我覺得，讓我更懂得遞歸！遞歸的使用更加熟練，遞歸的分析更加清晰，遞歸的思想更加深化！ 做課程設計，我覺得，第一點是架構，一個好的架構，可以讓細節(jié)更完善；在這次課程設計中，我首先確定的是一個架構——前綴表達式構造表達式為架構——其余的操作都是在這個架構上增加擴充。第二點是調試測試分析，一個完善的程序是要經過千錘百煉的，也能做到更加完善；第三點是心得的總結！ 總的來說，這次課程設計，讓我學了很多，總結了很多！ 八、參考文獻 嚴蔚敏，吳偉民著，數據結構（C語言版），北京：清華大學出版社，2007 譚浩強著，C程序設計（第三版），北京：清華大學出版社，2005 九、附錄：程序清單 源程序文件名清單： expression.h //包含頭文件，存儲結構的聲明，以及兩個順序棧的基本操作 exprssion.c //包含主程序和表達式的基本操作 《一》文件expression.h /*頭文件以及存儲結構*/ #include #include #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW 0 typedef int Status; /*二叉樹結點類型*/ typedef enum{INT,CHAR}ElemTag;/*INT為整型數據num，CHAR為字符型數據c*/ typedef struct TElemType { ElemTag tag;/*{INT,CHAR}指示是整型還是字符型*/ union { int num;/*tag=INT時，為整型*/ char c;/*tag=CHAR時，為字符型*/ }; } TElemType; /*二叉樹的二叉鏈表存儲表示 */ typedef struct BiTNode { TElemType data; struct BiTNode *lchild,*rchild; /* 左右孩子指針 */ }BiTNode,*BiTree; typedef BiTree SElemType;/*棧SqStack的元素*/ typedef char SElemType1; /*棧SqStack1的元素*/ /*棧的順序存儲表示 */ #define STACK_INIT_SIZE 10 /* 存儲空間初始分配量 */ #define STACKINCREMENT 2 /* 存儲空間分配增量 */ /*兩個順序棧*/ typedef struct SqStack { SElemType *base; /* 在棧構造之前和銷毀之后，base的值為NULL */ SElemType *top; /* 棧頂指針 */ int stacksize; /* 當前已分配的存儲空間，以元素為單位 */ }SqStack; /* 順序棧 */ typedef struct SqStack1 { SElemType1 *base; /* 在棧構造之前和銷毀之后，base的值為NULL */ SElemType1 *top; /* 棧頂指針 */ int stacksize; /* 當前已分配的存儲空間，以元素為單位 */ }SqStack1; /* 順序棧 */ /*順序棧的基本操作*/ Status InitStack(SqStack *S) { /* 構造一個空棧S */ (*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!(*S).base) exit(OVERFLOW); /* 存儲分配失敗 */ (*S).top=(*S).base; (*S).stacksize=STACK_INIT_SIZE; return OK; } Status StackEmpty(SqStack S) { /* 若棧S為空棧，則返回TRUE，否則返回FALSE */ if(S.top==S.base) return TRUE; else return FALSE; } Status Push(SqStack *S,SElemType e) { /* 插入元素e為新的棧頂元素 */ if((*S).top-(*S).base>=(*S).stacksize) /* 棧滿，追加存儲空間 */ { (*S).base=(SElemType *)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!(*S).base) exit(OVERFLOW); /* 存儲分配失敗 */ (*S).top=(*S).base+(*S).stacksize; (*S).stacksize+=STACKINCREMENT; } *((*S).top)++=e; return OK; } Status Pop(SqStack *S,SElemType *e) { /* 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR */ if((*S).top==(*S).base) return ERROR; *e=*--(*S).top; return OK; } Status GetTop(SqStack S,SElemType *e) { /* 若棧不空，則用e返回S的棧頂元素，并返回OK；否則返回ERROR */ if(S.top>S.base) { *e=*(S.top-1); return OK; } else return ERROR; } /*順序棧的基本操作*/ Status InitStack1(SqStack1 *S) { /* 構造一個空棧S */ (*S).base=(SElemType1 *)malloc(STACK_INIT_SIZE*sizeof(SElemType1)); if(!(*S).base) exit(OVERFLOW); /* 存儲分配失敗 */ (*S).top=(*S).base; (*S).stacksize=STACK_INIT_SIZE; return OK; } Status StackEmpty1(SqStack1 S) { /* 若棧S為空棧，則返回TRUE，否則返回FALSE */ if(S.top==S.base) return TRUE; else return FALSE; } Status Push1(SqStack1 *S,SElemType1 e) { /* 插入元素e為新的棧頂元素 */ if((*S).top-(*S).base>=(*S).stacksize) /* 棧滿，追加存儲空間 */ { (*S).base=(SElemType1 *)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType1)); if(!(*S).base) exit(OVERFLOW); /* 存儲分配失敗 */ (*S).top=(*S).base+(*S).stacksize; (*S).stacksize+=STACKINCREMENT; } *((*S).top)++=e; return OK; } Status Pop1(SqStack1 *S,SElemType1 *e) { /* 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR */ if((*S).top==(*S).base) return ERROR; *e=*--(*S).top; return OK; } Status GetTop1(SqStack1 S,SElemType1 *e) { /* 若棧不空，則用e返回S的棧頂元素，并返回OK；否則返回ERROR */ if(S.top>S.base) { *e=*(S.top-1); return OK; } else return ERROR; } 《二》文件expression.c #include"expression.h" /*全局變量*/ int save_number[31];/*在按原表達式輸入形式中，輸入的常量保存到數組save_number中，常量最多為30個，0單元不用*/ char Expr_String[30];/*存放表達式的字符串*/ /*以字符序列的形式輸入語法正確的前綴表達式，保存到字符串string*/ /*參數flag=0表示輸出的提示信息是"請輸入正確的前綴表示式："*/ /*flag=1表示輸出的提示信息為"請以表達式的原書寫形式輸入正確表示式："*/ Status Input_Expr(char *string,int flag) { if(flag==0)printf("\n請輸入正確的前綴表示式："); else printf("\n請以表達式的原書寫形式輸入正確表示式："); flushall();/*清理緩沖區(qū)*/ gets(string);/*從鍵盤輸入一串字符串作為表達式*/ if(strlen(string)==1)/*輸入的表達式字符串長度為1*/ if(string[0]==+||string[0]==-||string[0]==*||string[0]==/||string[0]==^)/*輸入的表達式只有一個運算符*/ { printf("\n表達式只有一個字符，為運算符，錯誤！");return ERROR;} else if((string[0]>=0&&string[0]<9)||(string[0]>=a&&string[0]<=z)||(string[0]>=A&&string[0]<=Z)) /*輸入的表達式只有一個數字或字符*/ { printf("\n表達式只有一個字符！");return OK;} else {printf("\n輸入的字符不是運算符也不是變量常量，錯誤！");return ERROR;} return OK; } /*判斷字符string[i]，如果是0-9常量之間，二叉樹結點存為整型；否則，存為字符型*/ void judge_value(BiTree *E,char *string,int i) { if(string[i]>=0&&string[i]<=9)/*為常量*/ {(*E)->data.tag=INT;(*E)->data.num=string[i]-48;} else if(string[i]>=1&&string[i]<=20)/*為常量，常量存于數組save_number中*/ {(*E)->data.tag=INT;(*E)->data.num=save_number[string[i]];} else/*為變量*/ {(*E)->data.tag=CHAR;(*E)->data.c=string[i];} } /*以正確的前綴表示式并構造表達式E*/ Status ReadExpr(BiTree *E,char *exprstring) { SqStack S; int i,len;/*len為表達式的長度*/ BiTree p,q; (*E)=(BiTree)malloc(sizeof(BiTNode));/*申請二叉樹的根結點的空間*/ (*E)->lchild=NULL; (*E)->rchild=NULL; len=strlen(exprstring);/*len賦值為表達式的長度*/ if(len==1)/*表達式長度為1時，二叉樹只有根結點*/ judge_value(E,exprstring,0);/*將exprstring[0]存入二叉樹的結點中*/ else { judge_value(E,exprstring,0);/*將exprstring[0]存入二叉樹的結點中*/ InitStack(&S);/*初始化棧*/ q=(*E); Push(&S,q);/*入棧*/ Push(&S,q);/*入棧，根結點入棧兩次是為判斷先序輸入的表達式是不是正確的表達式*/ for(i=1;ilchild=NULL; p->rchild=NULL; if(exprstring[i]==+||exprstring[i]==-||exprstring[i]==*||exprstring[i]==/||exprstring[i]==^) {/*為運算符，運算符入棧，左孩子不空，向左孩子走，否則，如果右孩子不空，向右孩子走*/ if(!q->l