《數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計》表達式求值 實驗報告

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

1、 實驗課程名稱 專 業(yè) 班 級 學(xué) 生 姓 名 學(xué) 號 指 導(dǎo) 教 師 20 至 20 學(xué)年第 學(xué)期第 至 周 算術(shù)表達式求值演示 1、 概述

2、 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計，要求學(xué)生在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示、數(shù)據(jù)結(jié)構(gòu)的選擇和應(yīng)用、算法的設(shè)計及其實現(xiàn)等方面，加深對課程基本內(nèi)容的理解。同時，在程序設(shè)計方法以及上機操作等基本技能和科學(xué)作風(fēng)方面受到比較系統(tǒng)和嚴格的訓(xùn)練。 在這次的課程設(shè)計中我選擇的題目是算術(shù)表達式求值演示。表達式計算是實現(xiàn)程序設(shè)計語言的基本問題之一，也是棧的應(yīng)用的一個典型例子。設(shè)計一個程序，演示用算符優(yōu)先法對算術(shù)表達式求值的過程。深入了解棧和隊列的特性，以便在解決實際問題中靈活運用它們，同時加深對這種結(jié)構(gòu)的理解和認識。 二、 系統(tǒng)分析 1． 以字符列的形式從終端輸入語法正確的、不含變量的整數(shù)表達式。利用已知的算符

3、優(yōu)先關(guān)系，實現(xiàn)對算術(shù)四則混合運算表達式的求值，并仿照教科書的例子在求值中運算符棧、運算數(shù)棧、輸入字符和主要操作的變化過程。 2． 一般來說，計算機解決一個具體問題時，需要經(jīng)過幾個步驟：首先要從具體問題抽象出一個適當(dāng)?shù)臄?shù)學(xué)模型，然后設(shè)計一個解決此數(shù)學(xué)模型的算法，最后編出程序，進行測試，調(diào)試直至得到想要的答案。對于算術(shù)表達式這個程序，主要利用棧，把運算的先后步驟進行分析并實現(xiàn)簡單的運算！為實現(xiàn)算符優(yōu)先算法，可以使用兩個棧，一個用以寄存運算符，另一個用以寄存操作數(shù)和運算結(jié)果。 3． 演示程序是以用戶于計算機的對話方式執(zhí)行，這需要一個模塊來完成使用者與計算機語言的轉(zhuǎn)化。 4． 程序執(zhí)行時的命令：

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

5、 根據(jù)要求進行轉(zhuǎn)換并求值； 輸出結(jié)果； } (2) 表達式求值模塊——實現(xiàn)具體求值。 (3) 表達式轉(zhuǎn)換模塊——實現(xiàn)轉(zhuǎn)換。 各個函數(shù)之間的調(diào)用關(guān)系 主函數(shù) 表達式轉(zhuǎn)換 表達式求值 數(shù)據(jù)輸入 輸出 輸出 棧的抽象數(shù)據(jù)類型定義 ADT SqStack{ 數(shù)據(jù)對象：D={ai| ai ∈ElemSet,i=1,2,3……，n,n≥0} 數(shù)據(jù)關(guān)系：R1={| ai-1,ai ∈D,i=1,2,3,……，n} 約定其中ai端為棧底，an端為棧頂。 操作集合： (1)void Ini

6、tStack1(SqStack1 &S1);//聲明棧建立函數(shù) (2)void InitStack2(SqStack2 &S2);//聲明棧建立函數(shù) (3)void evaluate(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);/

7、/聲明取棧頂元素函數(shù) (8)char Pop1(SqStack1 &S1);//聲明出棧函數(shù) (9)float Pop2(SqStack2 &S2);//聲明出棧函數(shù) (10)char Compare(char m,char n);//聲明比較函數(shù) (11)float Operate(float a,char rheta,float b);//聲明運算函數(shù) (12)void DispStack1(SqStack1 &S1);//從棧底到棧頂依次輸出各元素 (13)void DispStack2(SqStack2 &S2);//從棧底到棧頂依次輸出各元素 }ADT

8、SqStack 結(jié)構(gòu)分析: 棧中的數(shù)據(jù)節(jié)點是通過數(shù)組來存儲的。因為在C語言中數(shù)組是用下標從零開始的，因此我們在調(diào)用他們的數(shù)據(jù)是要特別注意。指針變量的值要么為空(NULL)，不指向任何結(jié)點；要么其值為非空，即它的值是一個結(jié)點的存儲地址。注意，當(dāng)P為空值時，則它不指向任何結(jié)點，此時不能通過P來訪問結(jié)點，否則會引起程序錯誤。如果輸入的數(shù)字不符合題目要求，則會產(chǎn)生錯誤結(jié)果。 算法的時空分析： 時間和空間性能分析：時間上，對于含n個字符的表達式，無論是對其進行合法性檢測還是對其進行入棧出棧操作n次，因此其時間復(fù)雜度為O(n)?？臻g上，由于是用數(shù)組來存儲輸入的表達式，用棧來存儲運算中的數(shù)據(jù)和運算符

9、，而棧的本質(zhì)也用到的數(shù)組，數(shù)組在定義時必須確定其大小。在不知表達式長度的情況下確定數(shù)組的長度確非易事，此時極易造成空間的浪費，因此空間性能不是很好。 四、 詳細設(shè)計 源程序 #include using namespace std; #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct //運算符棧 { char *base; char *top; int stacksize; }SqStack1; typedef struct //

10、運算數(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 &S1,char e);//聲明入棧函數(shù) void Push2(SqStack2 &S2,float e);//聲明入壓棧函數(shù) char GetTop1

11、(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);//聲明運算函數(shù) void DispStack1(SqStack1 &S1);//從棧底到棧頂依次輸出各元素 void DispStack2(SqStack2

12、&S2);//從棧底到棧頂依次輸出各元素 /*主函數(shù)*/ void main() { SqStack1 S1;//定義運算符棧 SqStack2 S2;//定義運算數(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é)束!"<

13、 /*運算符棧函數(shù)*/ void InitStack1(SqStack1 &S1)//構(gòu)造一個空棧S1 { S1.base=(char *)malloc(STACK_INIT_SIZE *sizeof(char)); if(!S1.base)cout<<"存儲分配失敗！";//存儲分配失敗 S1.top=S1.base; S1.stacksize=STACK_INIT_SIZE; } void Push1(SqStack1 &S1,char e)//入棧 { if(S1.top-S1.base>=S1.stacksize)//如果棧滿，追加存儲空間 {

14、S1.base=(char *)realloc(S1.base,(S1.stacksize+STACKINCREMENT)*sizeof(char)); if(!S1.base) cout<<"存儲分配失?。?; else { S1.top=S1.base+S1.stacksize; S1.stacksize=S1.stacksize+STACKINCREMENT; } } *S1.top=e;S1.top=S1.top+1;//將元素壓入棧中，指針上移 } char GetTop1(SqStack1 &S1)//取棧頂元素 {

15、 char e; if(S1.top==S1.base)cout<<"\n\t\t\t運算符棧已空!\n"; else e=*(S1.top-1); return e; } void DispStack1(SqStack1 &S1)//從棧底到棧頂依次輸出各元素 { char e,*p; if(S1.top==S1.base)cout<<" "; else { p=S1.base; while(p

16、ack1 &S1)//出棧 { char e; if(S1.top==S1.base)cout<<"\n\t\t\t運算符棧已空!\n"; e=*(--S1.top); return e; } /*運算數(shù)棧函數(shù)*/ void InitStack2(SqStack2 &S2)//構(gòu)造一個空棧S2 { S2.base=(float *)malloc(STACK_INIT_SIZE *sizeof(float)); if(!S2.base)cout<<"存儲分配失敗！";//存儲分配失敗 S2.top=S2.base; S2.stacksize=STACK_

17、INIT_SIZE; } void Push2(SqStack2 &S2,float e)//入棧 { if(S2.top-S2.base>=S2.stacksize)//棧滿，追加存儲空間 { S2.base=(float *)realloc(S2.base,(S2.stacksize+STACKINCREMENT)*sizeof(float)); if(!S2.base)cout<<"存儲分配失敗！"; else { S2.top=S2.base+S2.stacksize; S2.stacksize=S2.stacksize+STACK

18、INCREMENT; } } *S2.top=e;S2.top=S2.top+1;//將元素e入棧，指針上移 } void DispStack2(SqStack2 &S2)//從棧底到棧頂依次輸出各元素 { float e,*p; if(S2.top==S2.base)cout<<" "; else { p=S2.base; while(p

19、e; if(S2.top==S2.base) cout<<"\n\t\t運算數(shù)棧已空!"; else e=*(S2.top-1); return e; } float Pop2(SqStack2 &S2)//出棧 { float e; if(S2.top==S2.base)cout<<"\n\t\t運算數(shù)棧已空!"; e=*(--S2.top); return e; } /*確定如何入棧函數(shù)*/ void evaluate(SqStack1 &S1,SqStack2 &S2) { char c; float t,e; int n=0,i=1

20、,j=0,k=0,l=0; char ch[STACK_INIT_SIZE]; int s=1; int flag=0,flag2=0; float p1,p2; char ch1; Push1(S1,#);//將#入棧，作為低級運算符 cout<<"●請輸入不含變量的表達式（以#結(jié)束!）：\n "; cin>>ch; c=ch[0]; cout<<"\n●對表達式求值的操作過程如下：" <<"\n________________________________________________________________________

21、________\n" <<"步驟\t運算符棧S1\t運算數(shù)棧S2\t輸入字符\t\t主要操作"; while(c!=#||GetTop1(S1)!=#) { cout<<"\n________________________________________________________________________________\n"; cout<

22、 k--; flag=0; } if(flag2) { k+=flag2; flag2=0; } for(l=0;l

23、!(c==.)&&n>=0) { e=float(c-48); n++; if(n==1)t=e; else if(n>1)t=t*10+e; c=ch[s++]; } if(n==-1) { e=float(c-48); t=t+e/10; c=ch[s++]; } if(c==.) { n=-1; c=ch[s++]; } if((c>=0&&c<=9)||c==.) { flag2++

24、; goto as; } if(c<0||c>9) { Push2(S2,t); } cout<<"\t\tPush2(S2,"<

25、c<<")"; c=ch[s++]; break; case =://棧頂元素優(yōu)先級相等，脫括號并接收下一字符 Pop1(S1); cout<<"\t\tPop1(S1)"; c=ch[s++]; break; case >://棧頂元素優(yōu)先級高，則退棧并將運算結(jié)果入棧 p1=Pop2(S2); p2=Pop2(S2); ch1=Pop1(S1); Push2(S2,Operate(p2,ch1,p1)); cout<<"\t\tOperate("<

26、<

27、____________________________________________________________________________\n"; if(S2.top-1==S2.base)//顯示表達式最終結(jié)果 cout<<"\n●表達式的結(jié)果為："<

28、;//棧頂元素為"("、"#",此時棧頂符號優(yōu)先級低，返回"<" else return >;//否則，棧頂符號優(yōu)先級高,返回">" } else if(n==*||n==/)//輸入的符號為"*"、"/" { if(m==)||m==*||m==/)return >;//棧頂元素為")"、"*"、"/",此時棧頂符號優(yōu)先級高，返回">" else return <;//否則，棧頂符號優(yōu)先級低,返回"<" } else if(n==()return<;//輸入的符號為"(",則直接返回"<" else if(n==))//輸入的符號為")" {

29、 if(m==()return=;//棧頂元素為"(",此時優(yōu)先級同，返回"=" else return >;//否則，棧頂符號優(yōu)先級高,返回">" } else //輸入符號為其他 { if(m==#)return=;//棧頂元素為"#",此時優(yōu)先級同，返回"=" else return >;//否則，棧頂符號優(yōu)先級高,返回">" } } float Operate(float a,char theta,float b)//運算函數(shù) { float tmp=0; if (theta==+)tmp=a+b;//從運算符

30、棧取出的符號為"+"，則運算數(shù)棧的兩元素相加，并返回 else if(theta==-)tmp=a-b;//從運算符棧取出的符號為"-"，則運算數(shù)棧的兩元素相減，并返回 else if(theta==*)tmp=a*b;//從運算符棧取出的符號為"*"，則運算數(shù)棧的兩元素相乘，并返回 else if(theta==/) //從運算符棧取出的符號為"/"，則運算數(shù)棧的兩元素相除，并返回 { if(b==0) cout<<"\n表達式出錯!除數(shù)不能為0!\n"; else tmp=a/b; } return tmp; } 五、運行與測試

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

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