c語言程序?qū)嵙曈媱潟?doc

程序?qū)嵙晥蟾鏁鹬谷掌冢?2012 年 6月 18 日 至 2012 年 6月 29日 學 號： 2011272086 .班 級： 通 信 113 .姓 名： 李 成 元 .指導教師： 趙金勝 刑延超 .通信與電子工程學院2012年 6月 30日1 設計時間2012.06.18-2012.06.292 設計目的1、實習目的 熟練掌握和系統(tǒng)理解C語言的基本知識點：數(shù)據(jù)類型、程序結(jié)構(gòu)、函數(shù)、數(shù)組、結(jié)構(gòu)體、文件等。 學會用C語言解決實際問題的方法 掌握較大型程序設計及調(diào)試的一般步驟和方法。3設計任務綜合運用C語言程序設計課程的主要知識設計一個計算器程序，利用算符優(yōu)先關系，實現(xiàn)對算術(shù)四則混合運算表達式的求值。輸入的形式：算術(shù)表達式，以井號“#”結(jié)束。例如2*(3+4)#； 包含的運算符只能有+ 、- 、* 、/ 、(、 )；輸出的形式：運算結(jié)果，例如Answer is:14；程序所能達到的功能：對算術(shù)表達式求值并輸出結(jié)果。4.1需求分析1、程序所能達到的功能：能夠處理以字符序列的形式輸入的不含變量的實數(shù)表達式，正確處理負數(shù)與小數(shù)，判斷表達式是還語法正確（包含分母不能為零的情況），正確實現(xiàn)對算術(shù)四則混合運算表達式的求值，能夠?qū)⒂嬎阒杏龅降膯栴}和結(jié)果以文件的形式予以存儲。2、輸入的形式和輸入值的范圍：以字符串的形式輸入表達式，以“#”結(jié)束。3、輸出的形式：在計算過程中遇到的問題或最終的答案將顯示在屏幕上，同時所計算的表達式的最終的結(jié)果也將保存在文件中。4、測試數(shù)據(jù)：輸入“3*(7-2)#”時，輸出“15.000000”，測試正確；輸入“!(9-2)#”時，輸出“輸入錯誤！”，測試正確。4.2總體設計4.2.1抽象數(shù)據(jù)類型定義ADT Stack數(shù)據(jù)對象：D= |ElemSet,i=1,2,，n, n0數(shù)據(jù)對象：R1=|,i=2,，n約定端為棧頂，端為棧底?；静僮鳎篒nitStack(&S)操作結(jié)果：構(gòu)造一個空棧S。GetTop(S)初始條件：棧S已存在。操作結(jié)果：用P返回S的棧頂元素。Push(&S，ch)初始條件：棧S已存在。操作結(jié)果：插入元素ch為新的棧頂元素。Pop(&S)初始條件：棧S已存在。操作結(jié)果：刪除S的棧頂元素。In(ch)操作結(jié)果：判斷字符是否是運算符，運算符即返回1。Precede(c1, c2) 初始條件：c1,c2為運算符。操作結(jié)果：判斷運算符優(yōu)先權(quán)，返回優(yōu)先權(quán)高的。Operate(a,op,b)初始條件：a,b為整數(shù)，op為運算符。操作結(jié)果：a與b進行運算，op為運算符，返回其值。num(n)操作結(jié)果：返回操作數(shù)的長度。EvalExpr()初始條件：輸入表達式合法。操作結(jié)果：返回表達式的最終結(jié)果。ADT Stack4.2.2函數(shù)模塊說明為實現(xiàn)算符優(yōu)先算法，可以使用兩個工作棧。一個稱做OPTR，用以寄存運算符；另一個稱做OPND，用以寄存操作數(shù)或運算結(jié)果。算法的基本思想是：(1)首先置操作數(shù)棧為空棧，表達式起始符“#”為運算符棧底元素(2)依次讀入表達式中每個字符，若是操作數(shù)則進OPND棧，若是運算符則和OPTR棧的棧頂運算符比較優(yōu)先權(quán)后作相應操作，直至整個表達式求值完畢（即OPTR棧的棧頂元素和當前讀入的字符均為“#”）。4.2.3主函數(shù)流程圖4.2.4函數(shù)模塊調(diào)用關系4.2.5運算符間的優(yōu)先關系1 2+-*/()#+-*/(#=S.stacksize) S.base=(SElemType*)realloc(S.base,(S.StackSize+STACKINCREMENT)*sizeof (SElemType); if(!S.base) exit(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize += STACKINCREMENT;*S.top+ =e;return OK;Status Pop(SqStack &S,SElemType &e)if(S.top = S.base) return ERROR;e = * -S.top;return OK;OperandType EvaluateExpession()InitStack(OPTR); Push(OPTR,#);InitStack(OPND); c = getchar();while(c!#|GetTop(OPTR)!=#) if(!In(c,OP)Push(OPND,c); c = getchar();) else switch(Precede(GetTop(OPTR),c) case:Pop(OPTR,theta); Pop(OPND,b); Pop(OPND,a); Push(OPND,Operate(a,theta,b); break; 4.3.2函數(shù)調(diào)用關系4.3.3主要模塊的算法描述void main()SqStack_T OPTR;SqStack_N OPND;float a,b,i; char theta,c,x;InitStack_T(&OPTR);Push_T(&OPTR,#);InitStack_N(&OPND);printf(“請輸入表達式關以#結(jié)尾：n”);c=getchar();if(c=35|(c=40&c=47&c=48&c=57) i=(float)c-48; Push_N(&OPND,i); c=getchar(); else switch(Precede(GetTop_T(&OPND),c) case:theat=Pop_T(&OPTR);b=Pop_N(&OPND);a=Pop_N(&OPND);Push_N(&OPND,Operate(a,theta,b);break; printf(“結(jié)果是%fn”,GetTop_N(&OPND);else printf(“輸入錯誤！n”);4.4測試與分析4.4.1測試加法測試，輸入正確，輸出正確，測試正確：乘法測試，輸入正確，輸出正確，測試正確：輸入表達式正確，輸出正確，測試正確：輸入表達式錯誤，能正確判斷，測試正確：4.4.2分析內(nèi)容包括：1、調(diào)試過程中遇到的問題是如何解決的以及對設計與實現(xiàn)的回顧討論和分析:遇到的問題：調(diào)試過程中遇到了輸入非法字符不輸出“錯誤！”的情況。解決的辦法：查ASCII碼表得知運算符+,-,*,/,(,),#和運算數(shù)0,1,2,3,4,5,6,7,8,9相應的ASCII值。在主程序中加入了判斷語句，判斷輸入的是否為運算符或運算數(shù)。如果是，則進行正常運算；如果不是，則返回錯誤。2、算法的時間復雜度和空間復雜度的分析：中綴表達式運算時間主要用在字符串掃描和算符優(yōu)先權(quán)的比較上。把#看作運算符，操作數(shù)與運算符個數(shù)相同，最壞情況下優(yōu)先級比較是n/2次，即運算順序完全是逆序的，每個字符掃描一遍是O(n)的，所以整個算法復雜度是O(n2)的。算法中用到兩個棧，分別為O(n/2)，其算法空間復雜度是O(n)。4.5附錄源程序#include stdio.h#include stdlib.h#define OK 1#define ERROR 0#define OVERFLOW 0#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef structchar *base;char *top;int stacksize;SqStack_T;typedef structfloat *base;float *top;int stacksize;SqStack_N;void InitStack_T(SqStack_T *S)(*S).base=(char *)malloc(STACK_INIT_SIZE*sizeof(char);if(!(*S).base) exit(OVERFLOW);(*S).top=(*S).base;(*S).stacksize=STACK_INIT_SIZE;void InitStack_N(SqStack_N *S)(*S).base=(float *)malloc(STACK_INIT_SIZE*sizeof(float);if(!(*S).base) exit(OVERFLOW);(*S).top=(*S).base;(*S).stacksize=STACK_INIT_SIZE;char GetTop_T(SqStack_T *S)char e;if(*S).top=(*S).base) return ERROR;e=*(*S).top-1);return e;float GetTop_N(SqStack_N *S)float e;if(*S).top=(*S).base) return ERROR;e=*(*S).top-1);return e;char Push_T(SqStack_T *S,char e)if(*S).top-(*S).base=(*S).stacksize)(*S).base=(char*)realloc(*S).base,(*S).stacksize+STACKINCREMENT)*sizeof(char);if(!(*S).base) exit(OVERFLOW);(*S).top=(*S).base+(*S).stacksize;(*S).stacksize+=STACKINCREMENT;*(*S).top)+=e;return OK;float Push_N(SqStack_N *S,float e)if(*S).top-(*S).base=(*S).stacksize)(*S).base=(float*)realloc(*S).base,(*S).stacksize+STACKINCREMENT)*sizeof(float);if(!(*S).base) exit(OVERFLOW);(*S).top=(*S).base+(*S).stacksize;(*S).stacksize+=STACKINCREMENT;*(*S).top)+=e;return OK;char Pop_T(SqStack_T *S)char e;if(*S).top=(*S).base) return ERROR;e=*(-(*S).top);return e;float Pop_N(SqStack_N *S)float e;if(*S).top=(*S).base) return ERROR;e=*(-(*S).top);return e;char m7=+-*/()#;char n77=, ,=40&c=47&c=48&c=57)i=(float)c-48;Push_N(&OPND,i);c=getchar();elseswitch(Precede(GetTop_T(&OPTR),c)case:theta=Pop_T(&OPTR);b=Pop_N(&OPND);a=Pop_N(&OPND);Push_N(&OPND,Operate(a,theta,b);break;printf(結(jié)果是%fn,GetTop_N(&OPND);else printf(輸入錯誤!n);5 總結(jié)與展望通過這段時間的課程設計，本人對計算機的應用、數(shù)據(jù)結(jié)構(gòu)的作用以及C語言的使用都有了更深的了解。當然也遇到不少問題，也正是國為這些問題引發(fā)的思考給我?guī)砹耸斋@。從當初不喜歡上機寫程序到現(xiàn)在能主動寫程序，從當初拿著程序不知從何下手到現(xiàn)在知道如何分析問題，如何用專業(yè)知識解決實際問題的轉(zhuǎn)變。我發(fā)現(xiàn)無論是專業(yè)知識還是動手能力，自己都有很大程度的提高。在實際上機操作過程中，不僅是讓我們了解數(shù)據(jù)結(jié)構(gòu)的理論知識，更重要的