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

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

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

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

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

5、 根據(jù)要求進行轉(zhuǎn)換并求值； 輸出結(jié)果； } (2) 表達式求值模塊——實現(xiàn)具體求值。 (3) 表達式轉(zhuǎn)換模塊——實現(xiàn)轉(zhuǎn)換。 各個函數(shù)之間的調(diào)用關系 主函數(shù) 表達式轉(zhuǎn)換 表達式求值 數(shù)據(jù)輸入 輸出 輸出 棧的抽象數(shù)據(jù)類型定義 ADT SqStack{ 數(shù)據(jù)對象：D={ai| ai ∈ElemSet,i=1,2,3……，n,n≥0} 數(shù)據(jù)關系：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é)點的存儲地址。注意，當P為空值時，則它不指向任何結(jié)點，此時不能通過P來訪問結(jié)點，否則會引起程序錯誤。如果輸入的數(shù)字不符合題目要求，則會產(chǎn)生錯誤結(jié)果。 算法的時空分析： 時間和空間性能分析：時間上，對于含n個字符的表達式，無論是對其進行合法性檢測還是對其進行入棧出棧操作n次，因此其時間復雜度為O(n)。空間上，由于是用數(shù)組來存儲輸入的表達式，用棧來存儲運算中的數(shù)據(jù)和運算符

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

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