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

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

2、 數(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)等方面，加深對(duì)課程基本內(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)先法對(duì)算術(shù)表達(dá)式求值的過程。深入了解棧和隊(duì)列的特性，以便在解決實(shí)際問題中靈活運(yùn)用它們，同時(shí)加深對(duì)這種結(jié)構(gòu)的理解和認(rèn)識(shí)。 二、 系統(tǒng)分析 1． 以字符列的形式從終端輸入語法正確的、不含變量的整數(shù)表達(dá)式。利用已知的算符

3、優(yōu)先關(guān)系，實(shí)現(xiàn)對(duì)算術(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)行測(cè)試，調(diào)試直至得到想要的答案。對(duì)于算術(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． 演示程序是以用戶于計(jì)算機(jī)的對(duì)話方式執(zhí)行，這需要一個(gè)模塊來完成使用者與計(jì)算機(jī)語言的轉(zhuǎn)化。 4． 程序執(zhí)行時(shí)的命令：

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

5、 根據(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ù)對(duì)象：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);//聲明運(yùn)算函數(shù) (12)void DispStack1(SqStack1 &S1);//從棧底到棧頂依次輸出各元素 (13)void DispStack2(SqStack2 &S2);//從棧底到棧頂依次輸出各元素 }ADT

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

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

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

12、&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é)束!"<

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

14、S1.base=(char *)realloc(S1.base,(S1.stacksize+STACKINCREMENT)*sizeof(char)); if(!S1.base) cout<<"存儲(chǔ)分配失?。?; 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運(yùn)算符棧已空!\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運(yùn)算符棧已空!\n"; e=*(--S1.top); return e; } /*運(yùn)算數(shù)棧函數(shù)*/ void InitStack2(SqStack2 &S2)//構(gòu)造一個(gè)空棧S2 { S2.base=(float *)malloc(STACK_INIT_SIZE *sizeof(float)); if(!S2.base)cout<<"存儲(chǔ)分配失敗！";//存儲(chǔ)分配失敗 S2.top=S2.base; S2.stacksize=STACK_

17、INIT_SIZE; } void Push2(SqStack2 &S2,float e)//入棧 { if(S2.top-S2.base>=S2.stacksize)//棧滿，追加存儲(chǔ)空間 { S2.base=(float *)realloc(S2.base,(S2.stacksize+STACKINCREMENT)*sizeof(float)); if(!S2.base)cout<<"存儲(chǔ)分配失??！"; 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運(yùn)算數(shù)棧已空!"; else e=*(S2.top-1); return e; } float Pop2(SqStack2 &S2)//出棧 { float e; if(S2.top==S2.base)cout<<"\n\t\t運(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

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,#);//將#入棧，作為低級(jí)運(yùn)算符 cout<<"●請(qǐng)輸入不含變量的表達(dá)式（以#結(jié)束!）：\n "; cin>>ch; c=ch[0]; cout<<"\n●對(duì)表達(dá)式求值的操作過程如下：" <<"\n________________________________________________________________________

21、________\n" <<"步驟\t運(yùn)算符棧S1\t運(yùn)算數(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)先級(jí)相等，脫括號(hào)并接收下一字符 Pop1(S1); cout<<"\t\tPop1(S1)"; c=ch[s++]; break; case >://棧頂元素優(yōu)先級(jí)高，則退棧并將運(yùn)算結(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)//顯示表達(dá)式最終結(jié)果 cout<<"\n●表達(dá)式的結(jié)果為："<

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

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

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

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

32、取編寫出更優(yōu)良的程序來。 讓我對(duì)數(shù)據(jù)結(jié)構(gòu)有了更進(jìn)一步的認(rèn)識(shí)和了解，也讓我知道，要想學(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)對(duì)一些看似簡單的東西掌握不夠熟練，比如由于函數(shù)的調(diào)用參數(shù)問題不熟而造成了調(diào)試的困難。對(duì)于語法的掌握也欠缺成熟，需要進(jìn)一步掌握。 (3)棧的結(jié)構(gòu)理解不夠清晰，造成了設(shè)計(jì)程序時(shí)理不清頭緒，需要對(duì)數(shù)據(jù)結(jié)構(gòu)有更深層次的理解。 13