《數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計(jì)》表達(dá)式求值 實(shí)驗(yàn)報(bào)告

《《數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計(jì)》表達(dá)式求值 實(shí)驗(yàn)報(bào)告》由會員分享，可在線閱讀，更多相關(guān)《《數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計(jì)》表達(dá)式求值 實(shí)驗(yàn)報(bào)告（13頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、實(shí)驗(yàn)課程名稱 專 業(yè) 班 級 學(xué) 生 姓 名 學(xué) 號 指 導(dǎo) 教 師 20 至 20 學(xué)年第 學(xué)期第 至 周算術(shù)表達(dá)式求值演示1、 概述 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)，要求學(xué)生在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示、數(shù)據(jù)結(jié)構(gòu)的選擇和應(yīng)用、算法的設(shè)計(jì)及其實(shí)現(xiàn)等方面，加深對課程基本內(nèi)容的理解。同時(shí)，在程序設(shè)計(jì)方法以及上機(jī)操作等基本技能和科學(xué)作風(fēng)方面受到比較系統(tǒng)和嚴(yán)格的訓(xùn)練。在這次的課程設(shè)計(jì)中我選擇的題目是算術(shù)表達(dá)式求值演示。表達(dá)式計(jì)算是實(shí)現(xiàn)程序設(shè)計(jì)語言的基本問題之一，也是棧的應(yīng)用的一個(gè)典型例子。設(shè)計(jì)一個(gè)程序，演示用算符優(yōu)先法對算術(shù)表達(dá)式求值的過程。深入了解棧和隊(duì)列的特性，以便在解決實(shí)際問題中靈活運(yùn)用它們，同時(shí)加深對這

2、種結(jié)構(gòu)的理解和認(rèn)識。二、 系統(tǒng)分析1 以字符列的形式從終端輸入語法正確的、不含變量的整數(shù)表達(dá)式。利用已知的算符優(yōu)先關(guān)系，實(shí)現(xiàn)對算術(shù)四則混合運(yùn)算表達(dá)式的求值，并仿照教科書的例子在求值中運(yùn)算符棧、運(yùn)算數(shù)棧、輸入字符和主要操作的變化過程。2 一般來說，計(jì)算機(jī)解決一個(gè)具體問題時(shí)，需要經(jīng)過幾個(gè)步驟：首先要從具體問題抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué)模型，然后設(shè)計(jì)一個(gè)解決此數(shù)學(xué)模型的算法，最后編出程序，進(jìn)行測試，調(diào)試直至得到想要的答案。對于算術(shù)表達(dá)式這個(gè)程序，主要利用棧，把運(yùn)算的先后步驟進(jìn)行分析并實(shí)現(xiàn)簡單的運(yùn)算！為實(shí)現(xiàn)算符優(yōu)先算法，可以使用兩個(gè)棧，一個(gè)用以寄存運(yùn)算符，另一個(gè)用以寄存操作數(shù)和運(yùn)算結(jié)果。3 演示程序是以用戶

3、于計(jì)算機(jī)的對話方式執(zhí)行，這需要一個(gè)模塊來完成使用者與計(jì)算機(jī)語言的轉(zhuǎn)化。4 程序執(zhí)行時(shí)的命令： 本程序?yàn)榱耸褂镁唧w，采用菜單式的方式來完成程序的演示，幾乎不用輸入什么特殊的命令，只需按提示輸入表達(dá)式即可。（要注意輸入時(shí)格式，否者可能會引起一些錯(cuò)誤）5. 測試數(shù)據(jù)。三、 概要設(shè)計(jì)一個(gè)算術(shù)表達(dá)式中除了括號、界限符外，還包括運(yùn)算數(shù)據(jù)和運(yùn)算符。由于運(yùn)算符有優(yōu)先級別之差，所以一個(gè)表達(dá)式的運(yùn)算不可能總是從左至右的循序執(zhí)行。每次操作的數(shù)據(jù)或運(yùn)算符都是最近輸入的，這與棧的特性相吻合，故本課程設(shè)計(jì)借助棧來實(shí)現(xiàn)按運(yùn)算符的優(yōu)先級完成表達(dá)式的求值計(jì)算。算法設(shè)計(jì)程序包含三個(gè)模塊(1) 主程序模塊，其中主函數(shù)為void m

4、ain輸入表達(dá)式；根據(jù)要求進(jìn)行轉(zhuǎn)換并求值；輸出結(jié)果；(2) 表達(dá)式求值模塊實(shí)現(xiàn)具體求值。(3) 表達(dá)式轉(zhuǎn)換模塊實(shí)現(xiàn)轉(zhuǎn)換。各個(gè)函數(shù)之間的調(diào)用關(guān)系主函數(shù)表達(dá)式轉(zhuǎn)換表達(dá)式求值數(shù)據(jù)輸入輸出輸出 棧的抽象數(shù)據(jù)類型定義ADT SqStack數(shù)據(jù)對象：D=ai| ai ElemSet,i=1,2,3，n,n0數(shù)據(jù)關(guān)系：R1=| ai-1,ai D,i=1,2,3,，n 約定其中ai端為棧底，an端為棧頂。 操作集合：(1)void InitStack1(SqStack1 &S1);/聲明棧建立函數(shù)(2)void InitStack2(SqStack2 &S2);/聲明棧建立函數(shù)(3)void evaluat

5、e(SqStack1 &S1,SqStack2 &S2);/確定如何入棧函數(shù)(4)void Push1(SqStack1 &S1,char e);/聲明入棧函數(shù)(5)void Push2(SqStack2 &S2,float e);/聲明入壓棧函數(shù)(6)char GetTop1(SqStack1 &S1);/聲明取棧頂元素函數(shù)(7)float GetTop2(SqStack2 &S2);/聲明取棧頂元素函數(shù)(8)char Pop1(SqStack1 &S1);/聲明出棧函數(shù)(9)float Pop2(SqStack2 &S2);/聲明出棧函數(shù)(10)char Compare(char m,ch

6、ar n);/聲明比較函數(shù)(11)float Operate(float a,char rheta,float b);/聲明運(yùn)算函數(shù)(12)void DispStack1(SqStack1 &S1);/從棧底到棧頂依次輸出各元素(13)void DispStack2(SqStack2 &S2);/從棧底到棧頂依次輸出各元素 ADT SqStack結(jié)構(gòu)分析:棧中的數(shù)據(jù)節(jié)點(diǎn)是通過數(shù)組來存儲的。因?yàn)樵贑語言中數(shù)組是用下標(biāo)從零開始的，因此我們在調(diào)用他們的數(shù)據(jù)是要特別注意。指針變量的值要么為空(NULL)，不指向任何結(jié)點(diǎn)；要么其值為非空，即它的值是一個(gè)結(jié)點(diǎn)的存儲地址。注意，當(dāng)P為空值時(shí)，則它不指向任何結(jié)

7、點(diǎn)，此時(shí)不能通過P來訪問結(jié)點(diǎn)，否則會引起程序錯(cuò)誤。如果輸入的數(shù)字不符合題目要求，則會產(chǎn)生錯(cuò)誤結(jié)果。算法的時(shí)空分析：時(shí)間和空間性能分析：時(shí)間上，對于含n個(gè)字符的表達(dá)式，無論是對其進(jìn)行合法性檢測還是對其進(jìn)行入棧出棧操作n次，因此其時(shí)間復(fù)雜度為O(n)?？臻g上，由于是用數(shù)組來存儲輸入的表達(dá)式，用棧來存儲運(yùn)算中的數(shù)據(jù)和運(yùn)算符，而棧的本質(zhì)也用到的數(shù)組，數(shù)組在定義時(shí)必須確定其大小。在不知表達(dá)式長度的情況下確定數(shù)組的長度確非易事，此時(shí)極易造成空間的浪費(fèi)，因此空間性能不是很好。四、 詳細(xì)設(shè)計(jì)源程序#includeusing namespace std;#define STACK_INIT_SIZE 100#d

8、efine STACKINCREMENT 10typedef struct /運(yùn)算符棧char *base;char *top;int stacksize;SqStack1;typedef struct /運(yùn)算數(shù)棧float *base;float *top;int stacksize;SqStack2;void InitStack1(SqStack1 &S1);/聲明棧建立函數(shù)void InitStack2(SqStack2 &S2);/聲明棧建立函數(shù)void evaluate(SqStack1 &S1,SqStack2 &S2);/確定如何入棧函數(shù)void Push1(SqStack1 &

9、S1,char e);/聲明入棧函數(shù)void Push2(SqStack2 &S2,float e);/聲明入壓棧函數(shù)char GetTop1(SqStack1 &S1);/聲明取棧頂元素函數(shù)float GetTop2(SqStack2 &S2);/聲明取棧頂元素函數(shù)char Pop1(SqStack1 &S1);/聲明出棧函數(shù)float Pop2(SqStack2 &S2);/聲明出棧函數(shù)char Compare(char m,char n);/聲明比較函數(shù)float Operate(float a,char rheta,float b);/聲明運(yùn)算函數(shù)void DispStack1(SqS

10、tack1 &S1);/從棧底到棧頂依次輸出各元素void DispStack2(SqStack2 &S2);/從棧底到棧頂依次輸出各元素/*主函數(shù)*/void main()SqStack1 S1;/定義運(yùn)算符棧SqStack2 S2;/定義運(yùn)算數(shù)棧/freopen(data1.in,r,stdin);/freopen(data1.out,w,stdout);InitStack1(S1);/調(diào)用棧建立函數(shù)InitStack2(S2);/調(diào)用棧建立函數(shù)evaluate(S1,S2);/調(diào)用確定如何入棧函數(shù)cout按任意鍵結(jié)束!endl;/*運(yùn)算符棧函數(shù)*/void InitStack1(SqSt

11、ack1 &S1)/構(gòu)造一個(gè)空棧S1S1.base=(char *)malloc(STACK_INIT_SIZE *sizeof(char);if(!S1.base)cout=S1.stacksize)/如果棧滿，追加存儲空間S1.base=(char *)realloc(S1.base,(S1.stacksize+STACKINCREMENT)*sizeof(char);if(!S1.base)cout存儲分配失??！;elseS1.top=S1.base+S1.stacksize;S1.stacksize=S1.stacksize+STACKINCREMENT;*S1.top=e;S1.to

12、p=S1.top+1;/將元素壓入棧中，指針上移char GetTop1(SqStack1 &S1)/取棧頂元素char e;if(S1.top=S1.base)coutnttt運(yùn)算符棧已空!n;else e=*(S1.top-1);return e;void DispStack1(SqStack1 &S1)/從棧底到棧頂依次輸出各元素char e,*p;if(S1.top=S1.base)cout ;elsep=S1.base;while(pS1.top)e=*p;p+;coute;char Pop1(SqStack1 &S1)/出棧char e;if(S1.top=S1.base)cout

13、nttt運(yùn)算符棧已空!n;e=*(-S1.top);return e;/*運(yùn)算數(shù)棧函數(shù)*/void InitStack2(SqStack2 &S2)/構(gòu)造一個(gè)空棧S2S2.base=(float *)malloc(STACK_INIT_SIZE *sizeof(float);if(!S2.base)cout=S2.stacksize)/棧滿，追加存儲空間S2.base=(float *)realloc(S2.base,(S2.stacksize+STACKINCREMENT)*sizeof(float);if(!S2.base)cout存儲分配失?。?elseS2.top=S2.base+S2

14、.stacksize;S2.stacksize=S2.stacksize+STACKINCREMENT;*S2.top=e;S2.top=S2.top+1;/將元素e入棧，指針上移void DispStack2(SqStack2 &S2)/從棧底到棧頂依次輸出各元素float e,*p;if(S2.top=S2.base)cout ;elsep=S2.base;while(pS2.top)e=*p;p+;coute;float GetTop2(SqStack2 &S2)/取棧頂元素float e;if(S2.top=S2.base) coutntt運(yùn)算數(shù)棧已空!;else e=*(S2.top

15、-1);return e;float Pop2(SqStack2 &S2)/出棧float e;if(S2.top=S2.base)coutntt運(yùn)算數(shù)棧已空!;e=*(-S2.top);return e;/*確定如何入棧函數(shù)*/void evaluate(SqStack1 &S1,SqStack2 &S2)char c;float t,e;int n=0,i=1,j=0,k=0,l=0;char chSTACK_INIT_SIZE;int s=1;int flag=0,flag2=0;float p1,p2;char ch1;Push1(S1,#);/將#入棧，作為低級運(yùn)算符coutch;c

16、=ch0;coutn對表達(dá)式求值的操作過程如下：n_n步驟t運(yùn)算符棧S1t運(yùn)算數(shù)棧S2t輸入字符tt主要操作;while(c!=#|GetTop1(S1)!=#) coutn_n; couti+t;DispStack1(S1);couttt;DispStack2(S2);couttt;if(flag=1)k-;flag=0;if(flag2)k+=flag2;flag2=0;for(l=0;lk;l+)cout ;for(j=k;chj!=0;j+)cout=0)e=float(c-48);n+;if(n=1)t=e;else if(n1)t=t*10+e;c=chs+;if(n=-1)e=f

17、loat(c-48);t=t+e/10;c=chs+;if(c=.)n=-1;c=chs+; if(c=0&c=9)|c=.)flag2+;goto as;if(c9)Push2(S2,t); coutttPush2(S2,t);else/輸入的是運(yùn)算符n=0;/非運(yùn)算型數(shù)據(jù)計(jì)數(shù)器清零switch(Compare(GetTop1(S1),c)/比較運(yùn)算符的優(yōu)先級case :/棧頂元素優(yōu)先級低，則入棧且繼續(xù)輸入Push1(S1,c);coutttPush1(S1,c);c=chs+;break;case =:/棧頂元素優(yōu)先級相等，脫括號并接收下一字符Pop1(S1);cout:/棧頂元素優(yōu)先級高

18、，則退棧并將運(yùn)算結(jié)果入棧p1=Pop2(S2);p2=Pop2(S2);ch1=Pop1(S1);Push2(S2,Operate(p2,ch1,p1);coutttOperate(p2,ch1,p1);flag=1;break;coutn_n;coutit#ttGetTop2(S2)tt;for(j=0;jk;j+) cout ;cout#ttRETURN(GETTOP(S2);coutn_n;if(S2.top-1=S2.base)/顯示表達(dá)式最終結(jié)果coutn表達(dá)式的結(jié)果為：GetTop2(S2)endl;else coutn表達(dá)式出錯(cuò)!n;char Compare(char m,cha

19、r n)/運(yùn)算符的優(yōu)先級比較if(n=+|n=-)/輸入符號為+、- if(m=(|m=#)return ;/棧頂元素為(、#,此時(shí)棧頂符號優(yōu)先級低，返回;/否則，棧頂符號優(yōu)先級高,返回else if(n=*|n=/)/輸入的符號為*、/if(m=)|m=*|m=/)return ;/棧頂元素為)、*、/,此時(shí)棧頂符號優(yōu)先級高，返回else return ;/否則，棧頂符號優(yōu)先級低,返回else if(n=()return;/輸入的符號為(,則直接返回;/否則，棧頂符號優(yōu)先級高,返回else /輸入符號為其他if(m=#)return=;/棧頂元素為#,此時(shí)優(yōu)先級同，返回=else retur

20、n ;/否則，棧頂符號優(yōu)先級高,返回float Operate(float a,char theta,float b)/運(yùn)算函數(shù)float tmp=0;if (theta=+)tmp=a+b;/從運(yùn)算符棧取出的符號為+，則運(yùn)算數(shù)棧的兩元素相加，并返回else if(theta=-)tmp=a-b;/從運(yùn)算符棧取出的符號為-，則運(yùn)算數(shù)棧的兩元素相減，并返回else if(theta=*)tmp=a*b;/從運(yùn)算符棧取出的符號為*，則運(yùn)算數(shù)棧的兩元素相乘，并返回else if(theta=/) /從運(yùn)算符棧取出的符號為/，則運(yùn)算數(shù)棧的兩元素相除，并返回if(b=0) coutn表達(dá)式出錯(cuò)!除數(shù)不能

21、為0!n;else tmp=a/b;return tmp;五、運(yùn)行與測試第六章 總結(jié)與心得數(shù)據(jù)結(jié)構(gòu)的研究不僅涉及到計(jì)算機(jī)硬件的研究，而且和計(jì)算機(jī)軟件的研究有著更密切的關(guān)系，無論是編譯程序還是操作系統(tǒng)，都涉及到數(shù)據(jù)元素在存儲器中的分配問題。在研究信息檢索時(shí)也必須考慮如何組織數(shù)據(jù)，以便使查找和存取數(shù)據(jù)元素更為方便。在課程設(shè)計(jì)中，應(yīng)該力求算法簡明易懂，而易于轉(zhuǎn)換為上機(jī)程序；如果程序反復(fù)多次使用，則應(yīng)該盡可能選用快速的算法；如果待解決的問題數(shù)據(jù)量極大，機(jī)器的存儲空間較小，則在編寫算法時(shí)應(yīng)該考慮如何節(jié)省空間。以后在編寫程序時(shí)就應(yīng)該注意到所編寫程序的時(shí)間復(fù)雜度，以及是否運(yùn)用了良好的算法，而不能只是像以前編

22、寫程序時(shí)單純使用C語言的知識，要充分考慮程序的性能，爭取編寫出更優(yōu)良的程序來。讓我對數(shù)據(jù)結(jié)構(gòu)有了更進(jìn)一步的認(rèn)識和了解，也讓我知道，要想學(xué)好它要重在實(shí)踐，理論與實(shí)際應(yīng)用相結(jié)合，提高了自己組織數(shù)據(jù)及編寫大型程序的能力，培養(yǎng)了基本的、良好的程序設(shè)計(jì)技能力。通過實(shí)際操作，我也發(fā)現(xiàn)我的好多不足之處：(1)用棧的結(jié)構(gòu)來解決表達(dá)式的求值，首先要解決的問題是如何將人們習(xí)慣書寫的表達(dá)式轉(zhuǎn)換成計(jì)算機(jī)容易處理的表達(dá)式。開始有些茫然，后來通過結(jié)合課本和同學(xué)的幫助完成了該課題。(2)對一些看似簡單的東西掌握不夠熟練，比如由于函數(shù)的調(diào)用參數(shù)問題不熟而造成了調(diào)試的困難。對于語法的掌握也欠缺成熟，需要進(jìn)一步掌握。(3)棧的結(jié)構(gòu)理解不夠清晰，造成了設(shè)計(jì)程序時(shí)理不清頭緒，需要對數(shù)據(jù)結(jié)構(gòu)有更深層次的理解。13