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

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