《數(shù)據(jù)結構與算法》課程設計-表達式的相關函數(shù)庫實現(xiàn)

數(shù)據(jù)結構與算法課程設計成果報告表達式的相關函數(shù)庫實現(xiàn)學生學號： 學生姓名： 學 院： 計算機學院 專業(yè)班級： 1341 專業(yè)課程： 數(shù)據(jù)結構與算法 指導教師： 2014 年 12 月 29 日題 目表達式的相關函數(shù)庫實現(xiàn)考核項目考核內容得分平時考核（30分）出勤情況、態(tài)度、效率；知識掌握情況、基本操作技能、知識應用能力、獲取知識能力系統(tǒng)設計（20分）分析系統(tǒng)的功能模塊編程調試（20分）實現(xiàn)系統(tǒng)的各個功能模塊，并完成調試回答問題（15分）回答老師針對課程設計提出的問題課程設計報告撰寫（10分）嚴格按照規(guī)范要求完成課程設計報告源代碼（5分）按照規(guī)范要求完成課程設計源代碼的排版總 評 成 績指導教師評語： 日期： 年 月 日目 錄1 課程設計目標與任務11.1課程設計目標11.2課程設計任務12 分析與設計22.1 題目需求分析22.2 存儲結構設計22.3 算法描述22.4 程序流程圖22.5 測試程序說明23 程序清單34 測試44.1 測試數(shù)據(jù)44.2 測試結果分析45 總結5參考文獻7附 錄81 課程設計目標與任務1.1 課程設計目標數(shù)據(jù)結構課程設計是在學完數(shù)據(jù)結構課程之后的實踐教學環(huán)節(jié)。該實踐教學是軟件設計的綜合訓練,包括問題分析，總體結構設計用戶界面設計，程序設計基本技能和技巧。要求學生在設計中逐步提高程序設計能力培養(yǎng)科學的軟件工作方法學生通過數(shù)據(jù)結構課程設計各方面得到鍛煉：（1）能根據(jù)實際問題的具體情況結合數(shù)據(jù)結構課程中的基本理論和基本算法，正確分析出數(shù)據(jù)的邏輯結構，合理地選擇相應的存儲結構，并能設計出解決問題的有效算法；（2）通過上機實習,驗證自己設計的算法的正確性，學會有效利用基本調試方法，迅速找出程序代碼中的錯誤并且修改；（3）培養(yǎng)算法分析能力，分析所設計算法的時間復雜度和空間復雜度，進一步提高程序設計水平；（4）盡可能借助語言環(huán)境實現(xiàn)圖形顯示功能，以便將抽象的數(shù)據(jù)結構以圖形方式顯示出來，將復雜的運行過程以動態(tài)方式顯示出來，獲得算法的直觀感受。1.2 課程設計任務設計一個表達式求值的程序。該程序必須可以接受包含（，），+， -，*，/，%，和（求冪運算符ab=a）的中綴表達式并求出結果。如果表達式正確則輸出表達式的結果如果表達式非法則輸出錯誤信息。2 分析與設計2.1 題目需求分析利用棧設計一個程序，該程序能夠用于表達式求值，程序能夠處理以字符序列的形式輸入的不含變量的實數(shù)表達式，能正確處理負數(shù)與小數(shù)，判斷表達式是否語法正確，包含分母不能為零的情況。正確實現(xiàn)對算術四則混合運算表達式的求值，將計算中遇到的問題和結果予以輸出。2.2 存儲結構設計在計算機中，算術表達式的計算往往是通過使用棧來實現(xiàn)的。所以，求值程序的最主要的數(shù)據(jù)結構就是棧。本程序就是使用棧來存儲輸入表達式的操作符和操作數(shù)。輸入的表達式是由操作數(shù)和運算符以及改變運算次序的圓括號連接而成的式子。任何一個表達式都是由操作數(shù)(OPTR)、運算符(OPND)和界限(delimiter)組成的。實現(xiàn)運算符優(yōu)先算法時需要使用兩個工作棧，一個為OPTR，用以存放運算符，另一個為OPND，用以存放操作數(shù)或運算的中間結果。首先初始化操作數(shù)棧OPTR和運算符棧OPND，并將表達式起始符“”壓入運算符棧，依次讀入表達式中的每個字符,若是操作數(shù)則直接進入操作數(shù)棧OPTR，若是運算符，則與運算符棧OPND的棧頂運算符進行優(yōu)先權比較，并做如下處理： (1) 若棧頂運算符的優(yōu)先級低于剛讀入的運算符，則讓剛讀入的運算符進OPTR棧。 (2) 若棧頂運算符的優(yōu)先級高于剛讀入的運算符，則將棧頂運算符退棧,同時接收下一個運算符，最后將運算結果推入OPND棧。 (3) 若棧頂運算符的優(yōu)先級與剛讀入的運算符的優(yōu)先級相同，說明左右括號相遇，只需將棧頂運算符“左括號”退棧即可。當輸入完一個完整的表達式之后（沒有遇到最后一個是運算符輸入時）程序結束。2.3 算法描述 （1）首先是創(chuàng)建了一個運算符優(yōu)先級表，用于比較運算符，然后創(chuàng)建兩個棧，再設計3個指針，用于指向結點。然后是計算函數(shù)Operate的設計，它也是利用棧來實現(xiàn)運算。利用創(chuàng)建的兩個棧直接對表達式進行計算。分別構建一個char類型和一個double類型的棧函數(shù)。（2）在main函數(shù)中讓用戶進行輸入，將用戶輸入的字符串進行循環(huán)、判斷，并將判斷后的字符串傳遞到新的數(shù)組中，循環(huán)結束后，再將數(shù)組傳遞給中綴表達式轉后綴表達式函數(shù)。（3）在Operate()函數(shù)中先創(chuàng)建一個數(shù)字棧和一個符號棧，對表達式進行循環(huán)，直到元素為0。在循環(huán)中如果元素為數(shù)字，將元素賦給新的數(shù)組s，再判斷下一個元素，若是則利用函數(shù)將數(shù)組中的字符串轉換成double類型的數(shù)字，然后數(shù)字進棧，清空數(shù)組s；否則，繼續(xù)判斷。若元素不為數(shù)字，則先看棧頂，如果棧為空或棧頂元素為（或者棧頂元素為+或并且現(xiàn)有元素為*、/或%又或是現(xiàn)有元素為，則現(xiàn)有元素進棧；否則，再對現(xiàn)有元素進行判斷：如果現(xiàn)有元素為），運算符出棧直到（出棧；否則，運算符出棧直到?？栈蛘邨ｍ斣氐膬?yōu)先級低于現(xiàn)有運算符，現(xiàn)有運算符才進棧。每當有一個運算符出棧，就從數(shù)棧中取兩個數(shù)與運算符一起傳遞給Operate()函數(shù),并將函數(shù)的返回值壓入棧中。循環(huán)結束后，將棧中的運算符全部依次輸出，每當有一個運算符出棧，就從數(shù)棧中取兩個數(shù)與運算符一起傳遞給Operate()函數(shù),并將函數(shù)的返回值壓入棧中，最后輸出數(shù)字棧中的數(shù)字成為表達式的最終結果，再銷毀棧。（4）Operate()函數(shù)是利用switch語句對傳入進來的運算符進行判斷，并將傳入的兩個數(shù)進行相應的運算，并返回運算結果。（5）各模塊的主要功能*Push(SC *s,char c)：把字符壓棧*Push(SF *s,float f)：把數(shù)值壓棧*Pop(SC *s)：把字符退棧*Pop(SF *s)：把數(shù)值退棧Operate(a,theta,b)：根據(jù)theta對a和b進行+ 、- 、* 、/ 、操作In(Test,*TestOp)：若Test為運算符則返回true，否則返回falseReturnOpOrd(op,*TestOp)：若Test為運算符，則返回此運算符在數(shù)組中的下標precede(Aop,Bop)：根據(jù)運算符優(yōu)先級表返回Aop與Bop之間的優(yōu)先級EvaluateExpression(*MyExpression)：用算符優(yōu)先法對算術表達式求值2.4 程序流程圖程序流程圖1-12.5 測試程序說明1.一般來說，計算機解決一個具體問題時，需要經過幾個步驟：首先要從具體問題抽象出一個適當?shù)臄?shù)學模型，然后設計一個解決此數(shù)學模型的算法，最后編出程序，進行測試，調試直至得到想要的答案。對于算術表達式這個程序，主要利用棧，把運算的先后步驟進行分析并實現(xiàn)簡單的運算！為實現(xiàn)算符優(yōu)先算法，可以使用兩個棧，一個用以寄存運算符，另一個用以寄存操作數(shù)和運算結果。2.演示程序是以用戶于計算機的對話方式執(zhí)行，這需要一個模塊來完成使用者與計算機語言的轉化。 3.程序塊的功能介紹：（1）棧的抽象數(shù)據(jù)類型定義：ADT Stack數(shù)據(jù)對象：D=ai|aiElemSet,i=1,2,n,n0數(shù)據(jù)關系：R1=|ai-1,aiD,i=2,n約定an端為棧頂，ai端為棧底（）基本操作：Push(&S,e)初始條件：棧S已存在操作結果：插入元素e為新的棧頂元素Pop(&S,&e)初始條件：棧S已存在且非空操作結果：刪除S的棧頂元素，并用e返回其值ADT Stack3 程序清單#includestdio.h#includestdlib.h #includestring.h #includemath.h#define true 1 #define false 0 #define OPSETSIZE 8 typedef int Status; unsigned char Prior88 = / 運算符優(yōu)先級表 / + - * / ( ) # /*+*/, /*(*/,=, , , /*#*/, ,=, ; typedef struct StackChar char c; struct StackChar *next; SC; /StackChar類型的結點SCtypedef struct StackFloat float f; struct StackFloat *next; SF; /StackFloat類型的結點SFSC *Push(SC *s,char c) /SC類型的指針Push，返回p SC *p=(SC*)malloc(sizeof(SC); p-c=c; p-next=s; return p; SF *Push(SF *s,float f) /SF類型的指針Push，返回p SF *p=(SF*)malloc(sizeof(SF); p-f=f; p-next=s; return p; SC *Pop(SC *s) /SC類型的指針Pop SC *q=s; s=s-next; free(q); return s; SF *Pop(SF *s) /SF類型的指針Pop SF *q=s; s=s-next; free(q); return s; float Operate(float a,unsigned char theta, float b) /計算函數(shù)Operate switch(theta) case +: return a+b; case -: return a-b; case *: return a*b; case /: return a/b; case : return pow(a,b); default : return 0; char OPSETOPSETSIZE=+,-,*,/,(,),#,; Status In(char Test,char *TestOp) int Find=false; for (int i=0; i OPSETSIZE; i+) if(Test = TestOpi) Find= true; return Find; Status ReturnOpOrd(char op,char *TestOp) for(int i=0; ic!=#) if (!In(*c, OPSET) Dr0=*c; strcat(TempData,Dr); /字符串連接函數(shù) c+; if (In(*c, OPSET) Data=atof(TempData); /字符串轉換函數(shù)(double) OPND=Push(OPND, Data); strcpy(TempData,0); else / 不是運算符則進棧 switch (precede(OPTR-c, *c) case : / 退棧并將運算結果入棧 theta=OPTR-c;OPTR=Pop(OPTR); b=OPND-f;OPND=Pop(OPND); a=OPND-f;OPND=Pop(OPND); OPND=Push(OPND, Operate(a, theta, b); break; /switch /while return OPND-f; /EvaluateExpression int main(void) char s128; puts(請輸入表達式:); gets(s); puts(該表達式的值為:); printf(%sb=%gn,s,EvaluateExpression(s); system(pause); return 0;4 測試4.1 測試數(shù)據(jù)下面執(zhí)行加法運算：1+1測試結果圖-1下面執(zhí)行減法運算：10-9測試結果圖1-2下面執(zhí)行乘法運算：5*2測試結果圖1-3下面執(zhí)行除法運算：8/4測試結果圖1-4下面執(zhí)行混合運算：(2+2)*3_2)/5測試結果圖1-54.2 測試結果分析程序經過測試之后，主要的功能可以實現(xiàn)，可以完成實驗的要求，并仿照教科書的例子在求值中運算符棧、運算數(shù)棧、輸入字符和主要操作的變化過程進行四則混合運算。但是也存在一些小問題，就是在計算完一個表達式之后，不可以直接進行下一運算，必須再一次啟動程序進行計算。但它的優(yōu)點是，用戶輸入方便，沒有過多的輸入要求，直接輸入想計算的表達式即可，沒有過多的格式要求。以字符列的形式從終端輸入語法正確的、不含變量的整數(shù)表達式。利用已知的運算符優(yōu)先關系，實現(xiàn)對算術四則混合運算表達式的求值。5 總結 一周的課程設計即將結束了，在這次的課程設計中不僅檢驗了我所學習的知識，也培養(yǎng)了我如何去把握一件事情，如何去做一件事情，又如何完成一件事情。在設計過程中，與同學分工設計，和同學們相互探討，相互學習，相互監(jiān)督。學會了合作，學會了運籌帷幄，學會了寬容，學會了理解，也學會了做人與處世。由于本人的設計能力有限，在設計過程中難免出現(xiàn)錯誤，懇請老師多多指教,我十分樂意接受您的批評與指正，我將十分感謝。參考文獻1朱福喜.Java語言程序設計（第二版）.科學出版社2陳國君等.Java程序設計基礎（第二版）.清華大學出版社3Deitel.Java大學基礎教程（第六版）.電子工業(yè)出版社4MaryCampione.Java語言導學（第四版）.機械工業(yè)出版社5Y.DanielLiang.Java語言程序設計基礎篇（第六版）.機械工業(yè)出版社6KathySierra.HeadFirstJava（第二版）.東南大學出版社#includestdio.h #includestdlib.h #includestring.h #includemath.h #define true 1 #define false 0 #define OPSETSIZE 8 typedef int Status; unsigned char Prior88 = / 運算符優(yōu)先級表 / + - * / ( ) # /*+*/, /*(*/,=, , , /*#*/, ,=, ; typedef struct StackChar char c; struct StackChar *next; SC; /StackChar類型的結點SC typedef struct StackFloat float f; struct StackFloat *next; SF; /StackFloat類型的結點SF SC *Push(SC *s,char c) /SC類型的指針Push，返回p SC *p=(SC*)malloc(sizeof(SC); p-c=c; p-next=s; return p; SF *Push(SF *s,float f) /SF類型的指針Push，返回p SF *p=(SF*)malloc(sizeof(SF); p-f=f; p-next=s; return p; SC *Pop(SC *s) /SC類型的指針Pop SC *q=s; s=s-next; free(q); return s; SF *Pop(SF *s) /SF類型的指針Pop SF *q=s; s=s-next; free(q); return s; float Operate(float a,unsigned char theta, float b) /計算函數(shù)Operate switch(theta) case +: return a+b; case -: return a-b; case *: return a*b; case /: return a/b; case : return pow(a,b); default : return 0; char OPSETOPSETSIZE=+,-,*,/,(,),#,;