數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告(精選.)

word.word.數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告題目：表達(dá)式類型的實(shí)現(xiàn)（難度系數(shù)：1.2）學(xué)院專業(yè)年級班別計(jì)算機(jī)計(jì)算機(jī)科學(xué)與技術(shù)2015級8班學(xué)生姓名指導(dǎo)教師編號成績楊嘉慧李楊2017年1月報(bào)告：報(bào)告內(nèi)容：□詳細(xì)□完整□基本完整□不完整設(shè)計(jì)方案：□非常合理□合理□基本合理□較差算法實(shí)現(xiàn)：□全部實(shí)現(xiàn)□基本實(shí)現(xiàn)□部分實(shí)現(xiàn)□實(shí)現(xiàn)較差測試樣例：□完備□比較完備□基本完備□不完備文檔格式：□規(guī)范□比較規(guī)范□基本規(guī)范□不規(guī)范答辯：□理解題目透徹，問題回答流利□理解題目較透徹，回答問題基本正確□部分理解題目，部分問題回答正確□未能完全理解題目，答辯情況較差總評成績：□優(yōu)□良□中□及格□不及格運(yùn)行環(huán)境：CodeBlocks完成的題目：表達(dá)式類型的實(shí)現(xiàn)(難度系數(shù)：1.2)選做的內(nèi)容：(4)在表達(dá)式內(nèi)增加對三角函數(shù)等初等函數(shù)的操作。一、需求分析【課程設(shè)計(jì)要求】【問題的描述】一個(gè)表達(dá)式和一棵二叉樹之間，存在著自然的對應(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)以下操作：ReadExpr(E)――以字符序列的形式輸入語法正確的前綴表達(dá)式并構(gòu)造表達(dá)式E。WriteExpr(E)用帶括號的中綴表達(dá)式輸出表達(dá)式E。Assign(V,c)——實(shí)現(xiàn)對變量V的賦值(V=c)，變量的初值為0。(4)Value(E)――對算術(shù)表達(dá)式E求值。(5)CompoundExpr(p,El,E2)構(gòu)造一個(gè)新的復(fù)合表達(dá)式(E1)p(E2)?！径俊具x做部分】以表達(dá)式的原書寫形式輸入，支持大于0的正整數(shù)常量；增加常數(shù)合并操作MergeConst(E)——合并表達(dá)式E中所有常數(shù)運(yùn)算。例如，對表達(dá)式E=(2+3-a)*(b+3*4)進(jìn)行合并常數(shù)的操作后，求得E=(5-a)*(b+12)增加對求偏導(dǎo)數(shù)的運(yùn)算Diff(E,V)——求表達(dá)式E對V的導(dǎo)數(shù)在表達(dá)式內(nèi)增加對三角函數(shù)等初等函數(shù)的操作?！緶y試數(shù)據(jù)】分別輸入0；a;-91;+a*bc;+*5x2*8x;+++*3"*2"x2x6并輸出。每當(dāng)輸入一個(gè)表達(dá)式后，對其中的變量賦值，然后對表達(dá)式求值。二、【概要設(shè)計(jì)】1、數(shù)據(jù)類型的聲明：在這個(gè)課程設(shè)計(jì)中，采用了鏈表二叉樹的存儲結(jié)構(gòu)，以及兩個(gè)順序棧的輔助存儲結(jié)構(gòu)/*頭文件以及存儲結(jié)構(gòu)*/#include<stdio.h>#include<conio.h>#include<stdlib.h>#include<string.h>#defineTRUE1#defineFALSE0#defineOK1#defineERROR0typedefintStatus;2、表達(dá)式的抽象數(shù)據(jù)類型定義基本操作：voidjudge_str(&E,&string1)初始條件：樹E存在，表達(dá)式的前綴字符串string存在；操作結(jié)果：判斷字符string[i],如果是'0'-'9'常量之間，二叉樹結(jié)點(diǎn)E存為整型；否則，存為字符型。StatusReadExpr(&E,&string1)初始條件：表達(dá)式的前綴形式字符串exprstring存在；操作結(jié)果：以正確的前綴表示式exprstring并構(gòu)造表達(dá)式E,構(gòu)造成功，返回0K,否則返回ERROR。StatusPri_Compare(cl,c2)初始條件：cl和c2是字符；操作結(jié)果：如果兩個(gè)字符是運(yùn)算符，比較兩個(gè)運(yùn)算符的優(yōu)先級，c1比c2優(yōu)先,返回OK,否則返回ERRORovoidWriteExpr(&E)初始條件：表達(dá)式E存在；操作條件：用帶括弧的中綴表達(dá)式輸入表達(dá)式E。voidAssign(&E,V,c)初始條件：表達(dá)式E存在，flag為標(biāo)志是否有賦值過；操作結(jié)果：實(shí)現(xiàn)對表達(dá)式E中的所有變量V的賦值(V=c)。longOperate(opr1,opr,opr2)初始條件：操作數(shù)oprl和操作數(shù)opr2以及操作運(yùn)算符opr;操作結(jié)果：運(yùn)算符運(yùn)算求值，參數(shù)oprl,opr2為常量，opr為運(yùn)算符，根據(jù)不同的運(yùn)算符，實(shí)現(xiàn)不同的運(yùn)算，返回運(yùn)算結(jié)果。StatusCheck(E)初始條件：表達(dá)式E存在；操作結(jié)果：檢查表達(dá)式E是否還存在沒有賦值的變量，以便求算數(shù)表達(dá)式E的值。longValue(E)初始條件：表達(dá)式E存在；操作結(jié)果：對算術(shù)表達(dá)式求值，返回求到的結(jié)果。voidCompoundExpr(P,&E1,E2)初始條件：表達(dá)式E1和E2存在；操作條件：構(gòu)造一個(gè)新的復(fù)合表達(dá)式(E1)P(E2)。3、整體設(shè)計(jì)在這個(gè)課程設(shè)計(jì)中，有一個(gè)源代碼文件：expression,。在expression.c文件中，是實(shí)現(xiàn)課程設(shè)計(jì)要求的各個(gè)函數(shù)。主程序的流程以及各程序模塊之間的調(diào)用關(guān)系：1、各個(gè)存儲結(jié)構(gòu)的聲明；2、順序棧的基本操作。其基本操作如下：對于棧SqStack:StatusInitStack(SqStack*S)/*構(gòu)造一個(gè)空棧S*/StatusStackEmpty(SqStackS)/*若棧S為空棧，則返回TRUE，否則返回FALSE*/StatusPush(SqStack*S,SElemTypee)/*插入元素e為新的棧頂元素*/StatusPop(SqStack*S,SElemType*e)/*若棧不空，則刪除S的棧頂元素，用e返回其值，并返回0K；否則返回ERROR*/StatusGetTop(SqStackS,SElemType*e)/*若棧不空，則用e返回S的棧頂元素，并返回OK；否則返回ERROR*/3、本程序有三個(gè)模塊，主程序模塊，二叉樹模塊，一個(gè)個(gè)順序棧模塊。三者者的調(diào)用關(guān)系如下：三、【詳細(xì)設(shè)計(jì)】1、二叉樹的存儲類型/*二叉樹結(jié)點(diǎn)類型*/typedefenum{INT,CHAR}ElemTag;/*INT為整型數(shù)據(jù)num，CHAR為字符型數(shù)據(jù)c*/typedefstructTElemType{ElemTagtag;/*{INT,CHAR}指示是整型還是字符型*/union{intnum;/*tag=INT時(shí)，為整型*/charc;/*tag二CHAR時(shí)，為字符型*/};}TElemType;/*二叉樹的二叉鏈表存儲表示*/typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;/*左右孩子指針*/}BiTNode,*BiTree;二叉樹的基本操作已經(jīng)在構(gòu)造表達(dá)式和表達(dá)式中的基本操作中根據(jù)不同的功能和實(shí)際情況修改了，詳細(xì)見各個(gè)函數(shù)操作的算法設(shè)計(jì)。2、順序棧的存儲類型/*棧的順序存儲表示*/#defineSTACK_INIT_SIZE10/*存儲空間初始分配量*/#defineSTACKINCREMENT2/*存儲空間分配增量*//*順序棧*/typedefstructSqStack{SElemType*base;/*在棧構(gòu)造之前和銷毀之后，base的值為NULL*/SElemType*top;/*棧頂指針*/intstacksize;/*當(dāng)前已分配的存儲空間，以元素為單位*/}SqStack;/*順序棧SqStack*/3、表達(dá)式的基本操作StatusInput_Expr(char*string,intflag);/*以字符序列的形式輸入語法正確的前綴表達(dá)式，保存到字符串string*//*參數(shù)flag=0表示輸出的提示信息是〃請輸入正確的前綴表示式：〃*//*flag=1表示輸出的提示信息為〃請以表達(dá)式的原書寫形式輸入正確表示式:"*/voidjudge_str(BiTree*E,char*string,inti);/*判斷字符string[i],如果是'0'-'9'常量之間，二叉樹結(jié)點(diǎn)存為整型；否則，存為字符型*/StatusPri_Compare(charc1,charc2);/*如果兩個(gè)字符是運(yùn)算符，比較兩個(gè)運(yùn)算符的優(yōu)先級，c1比c2優(yōu)先，返回0K,否則返回ERROR*/voidWriteExpr(BiTreeE);/*用帶括弧的中綴表達(dá)式輸入表達(dá)式*/voidAssign(BiTree*E,charV,intc,int*flag);/*實(shí)現(xiàn)對表達(dá)式中的所有變量V的賦值(V=c)，參數(shù)flag為表示是否賦值過的標(biāo)志*/longOperate(intopr1,charopr,intopr2);/*運(yùn)算符運(yùn)算求值，參數(shù)opr1,opr2為常量，opr為運(yùn)算符，根據(jù)不同的運(yùn)算符，實(shí)現(xiàn)不同的運(yùn)算，返回運(yùn)算結(jié)果*/StatusCheck(BiTreeE);/*檢查表達(dá)式是否還存在沒有賦值的變量，以便求算數(shù)表達(dá)式的值*/longValue(BiTreeE);/*對算術(shù)表達(dá)式求值*/voidCompoundExpr(charP,BiTree*E1,BiTreeE2);/*構(gòu)造一個(gè)新的復(fù)合表達(dá)式*/4、主程序和其他偽碼算法voidmain(){BiTreeE1,E2;charV,P;intc;ReadExpr(&E1);printf("\nE1帶括弧的中綴表示式為：")；WriteExpr(E1);while(Check(E1)==TRUE){printf("\n請輸入要賦值的字符：")；V=getchar();printf("請輸入要將賦值為：")；scanf("%d",&c);Assign(&E1,V,c);getchar();WriteExpr(E1);printf("\n輸入未知數(shù)后E1表達(dá)式為：")；WriteExpr(E1);}printf("\nE1表達(dá)式的值為：％d",Value(E1));ReadExpr(&E2);printf("\nE2帶括弧的中綴表示式為：")；WriteExpr(E2);Assign(&E2,V,c);CompoundExpr(P,&E1,E2);5、函數(shù)的調(diào)用關(guān)系除了主函數(shù)main()外，其他各個(gè)函數(shù)相對于其它函數(shù)來說是獨(dú)立的，函數(shù)的使用都由主函數(shù)main()調(diào)用使用的，可以簡單的說，各個(gè)函數(shù)都是主函數(shù)下的從函數(shù)。四、【調(diào)試分析】開始設(shè)計(jì)時(shí)我設(shè)想建樹時(shí)可以設(shè)定五個(gè)域，左右孩子，標(biāo)志tag,int型值域，char型值域。但是在存儲時(shí)發(fā)現(xiàn)每個(gè)字符只需占一個(gè)域就可以，所以我又采用共同體這樣節(jié)約了內(nèi)存。在算法設(shè)計(jì)中，構(gòu)造表達(dá)式樹的時(shí)候，本來以為使用遞歸構(gòu)造表達(dá)式會很難做到出錯處理的，所以采用了順序棧輔助構(gòu)造方法，并且盡可能地對程序進(jìn)行完善，出錯處理。但是經(jīng)過與同學(xué)的相互討論和研究，發(fā)現(xiàn)自己的想法犯了很大的錯誤，遞歸構(gòu)造表達(dá)式對于出錯處理很簡單也很完善，這一點(diǎn)讓我加深了遞歸的使用和理解。也就是三角函數(shù)問題，我最頭疼的地方。首先開始運(yùn)行時(shí)會出現(xiàn)錯誤無法輸出正確結(jié)果。通過網(wǎng)上搜索，我發(fā)現(xiàn)對于三角函數(shù)的定義類型必須是double，這樣的話，如果要改的話，差不多改大半程序，所以我就讓此功能單獨(dú)出來，由提示讓用戶手動完成。在調(diào)試的過程中，花費(fèi)時(shí)間最為多的是對輸入錯誤表達(dá)式的出錯處理，更改增加的代碼幾乎都是為了出錯處理，但是，覺得這樣的調(diào)試才更能鍛煉一個(gè)人的編程能力。五、【用戶使用說明】打開程序，按屏幕上的提示輸入數(shù)據(jù)，隨后就可以看到結(jié)果了。六、【測試結(jié)果】1.輸入0D八c■丈彳半kesl-e.Bve［口」回輸人語迭正確的前綴表示式：0|ei昔括呱的中綴表丁式為：0表達(dá)弍的疽為：02.輸入a雖情輸入語法正確的前綴麥?zhǔn)臼?a!役法*岀表這式的固:tt-內(nèi)有a內(nèi).弍役：2弍.示壽：達(dá)？奏盡一勞表：.綴籍值E1為屮42^1賦第弧中要要知式墓人A*達(dá)SS人衰E1表請請2輸E13.輸入-91[=丨?回請輸賈話法正確的前綴表示式：說輸入+a*bc回Id:\c交件\|:已曲&,曰＜亡潔輸Pl邙夫11■佛的前錮辰下式：+a*hc綴亠為有a龍疚-1示壽..MH石篇值±H回Id:\c交件\|:已曲&,曰＜亡潔輸Pl邙夫11■佛的前錮辰下式：+a*hc綴亠為有a龍疚-1示壽..MH石篇值±H肇販弧屮妾更抬、*八帶U心握也E1書請島沒-1達(dá)脣：KEl亠知中更旻1+-?知有C式?jīng)].1達(dá)脣..妻宀石MS伯51知中更尋力

F

表：?1/

箍

SX&鋒—#M域表請肓11+1矍請請1+揄11輸入+*5x2*8x

■D:\cS{^\keshe.cxe請輸入語法正確的前綴羔亍弍；3SF*25xt舉郵耀緩矗為值!沒法衣出表達(dá)式的苴3*1^3+2*1^20+6普藝鶉膳烈式和鬧?琢沖訃CompoundExpr(P,&E1,E2)合并操作T7D:#T7D:#文件'Itch詩輸入語法正爾的前綴表示式一7FTF曲3'2xxA2'x3'2xxA2'x巧沒法求出表達(dá)式的值3+2*1a2+1+6+a*bc式役1示葬:_￡;綴士為表式綴達(dá)12前莖亠?力L_T-的LUS值1*E1為確中g(shù)s2+g正$第丄餐法弧中要要2*召-uSMTNW+寥入入3+未-±入i齧就驟麟示針翥遷啟息達(dá)弍冊七、【附錄】#include<stdio.h>#include<math.h>#include<conio.h>#include<stdlib.h>#include<string.h>#defineTRUE1#defineFALSE0#defineOK1#defineERROR0typedefintStatus;typedefenum{INT,CHAR}ElemTag;typedefstructTElemType{ElemTagtag;union{intnum;charc;};}TElemType;typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;typedefBiTreeSElemType;#defineSTACK_INIT_SIZE10#defineSTACKINCREMENT2typedefstructSqStack{SElemType*base;SElemType*top;intstacksize;}SqStack;StatusInitStack(SqStack*S){(*S).base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!(*S).base)exit(OVERFLOW);(*S).top=(*S).base;(*S).stacksize=STACK_INIT_SIZE;returnOK;}StatusStackEmpty(SqStackS){if(S.top==S.base)returnTRUE;elsereturnFALSE;}StatusPush(SqStack*S,SElemTypee){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;returnOK;}StatusPop(SqStack*S,SElemType*e){if((*S).top==(*S).base)returnERROR;*e=*--(*S).top;returnOK;}StatusGetTop(SqStackS,SElemType*e){if(S.top>S.base){*e=*(S.top-1);returnOK;}elsereturnERROR;}voidjudge_str(BiTree*E,char*string,inti){if(string[i]>='0'&&string[i]<='9'){(*E)->data.tag=INT;(*E)->data.num=string[i]-48;}else{(*E)->data.tag=CHAR;(*E)->data.c=string[i];}}StatusReadExpr(BiTree*E){SqStackS;inti,len;BiTreep,q;(*E)=(BiTree)malloc(sizeof(BiTNode));(*E)->lchild=NULL;(*E)->rchild=NULL;charstring1[50];printf("\n請輸入語法正確的前綴表示式：")；gets(string1);len=strlen(string1);if(len==1)judge_str(E,string1,0);else{judge_str(E,string1,0);InitStack(&S);q=(*E);Push(&S,q);Push(&S,q);for(i=1;i<len&&!StackEmpty(S);i++){p=(BiTree)malloc(sizeof(BiTNode));judge_str(&p,string1,i);p->lchild=NULL;p->rchild=NULL;if(string1[i]=='+'||string1[i]=='-'||string1[i]=='*'||string1[i]=='/'||stringl[i]=='「){if(!q->lchild){q->lchild=p;Push(&S,p);q=p;}else{q->rchild=p;Push(&S,p);q=p;}}else{if(!q->lchild){q->lchild=p;Pop(&S,&q);}else{q->rchild=p;Pop(&S,&q);}}if(StackEmpty(S)&&i>=len)returnOK;else{printf("\n輸入的表達(dá)式有誤！")；returnERROR;}}}StatusPri_Compare(charc1,charc2){if((cl=='“T|cl=='*T|cl=='-T|cl=='+T|cl=='/')&&(c2二二'“’||c2=='*'||c2=='-'||c2=='+'||c2=='/')){if(cl=='「){辻(c2!='"‘)returnOK;elsereturnERROR;}elseif(c1=='*'||c1=='/'){辻(c2=='"T|c2=='*T|c2=='/')returnERROR;elsereturnOK;}elsereturnERROR;}elsereturnERROR;}voidWriteExpr(BiTreeE){if(E){if(E->lchild&&E->lchild->data.tag==CHAR){if(Pri_Compare(E->data.c,E->lchild->data.c)){printf("(");WriteExpr(E->lchild);printf(")");elseWriteExpr(E->lchild);}elseWriteExpr(E->lchild);if(E->data.tag==INT){printf("%d",E->data.num);}elseprintf("%c",E->data.c);if(E->rchild&&E->rchild->data.tag==CHAR){if(Pri_Compare(E->data.c,E->rchild->data.c)){printf("(");WriteExpr(E->rchild);printf(")");}elseWriteExpr(E->rchild);}elseWriteExpr(E->rchild);}}StatusCheck(BiTreeE){if(E&&E->data.tag==CHAR){if(E-〉data.c!二'*'&&E-〉data.c!二'&&E-〉data.c!二'&&E-〉data.c!二'+'&&E->data.c!='/'){printf(〃\n表達(dá)式中仍存在變量沒有賦值！沒法求出表達(dá)式的值！〃)；returnTRUE;}if(!Check(E-〉lchild))Check(E-〉rchild);}}voidAssign(BiTree*E,charV,intc){if(*E){if((*E)-〉data.tag==CHAR&&(*E)-〉data.c==V){(*E)-〉data.tag=INT;(*E)->data.num=c;;}Assign(&((*E)->lchild),V,c);Assign(&((*E)->rchild),V,c);}}longpower(intx,intexp){longresult;inti;for(i=1,result=1;i<=exp;i++)result*=x;returnresult;}longOperate(intopr1,charopr,intopr2){longresult;switch(opr){case'+':result=opr1+opr2;returnresult;break;case'-':result=opr1-opr2;returnresult;break;case'*':result=opr1*opr2;returnresult;break;case'/':result=opr1/opr2;returnresult;break;case'"':result二power(oprl,opr2);returnresult;break;default:break;}}doubleOperate1(charopr,doubleopr1){doubleresult1;switch(opr){case'~':/*正玄sin*/resultl二sin(oprl);returnresultl;break;case'!':/*余弦*/resultl二cos(oprl);returnresultl;break;case'@':/*正切*/result1=tan(opr1);returnresult1;break;default:break;}}longValue(BiTreeE){if(E){if(!E->lchild&&!E->rchild