課程設(shè)計(jì)報(bào)告-表達(dá)式類型的實(shí)現(xiàn)-方銳洲.doc

《課程設(shè)計(jì)報(bào)告-表達(dá)式類型的實(shí)現(xiàn)-方銳洲.doc》由會員分享，可在線閱讀，更多相關(guān)《課程設(shè)計(jì)報(bào)告-表達(dá)式類型的實(shí)現(xiàn)-方銳洲.doc（36頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

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