c語言程序?qū)嵙?xí)計(jì)劃書.doc

程序?qū)嵙?xí)報(bào)告書起止日期： 2012 年 6月 18 日 至 2012 年 6月 29日 學(xué) 號(hào)： 2011272086 .班 級(jí)： 通 信 113 .姓 名： 李 成 元 .指導(dǎo)教師： 趙金勝 刑延超 .通信與電子工程學(xué)院2012年 6月 30日1 設(shè)計(jì)時(shí)間2012.06.18-2012.06.292 設(shè)計(jì)目的1、實(shí)習(xí)目的 熟練掌握和系統(tǒng)理解C語言的基本知識(shí)點(diǎn)：數(shù)據(jù)類型、程序結(jié)構(gòu)、函數(shù)、數(shù)組、結(jié)構(gòu)體、文件等。 學(xué)會(huì)用C語言解決實(shí)際問題的方法 掌握較大型程序設(shè)計(jì)及調(diào)試的一般步驟和方法。3設(shè)計(jì)任務(wù)綜合運(yùn)用C語言程序設(shè)計(jì)課程的主要知識(shí)設(shè)計(jì)一個(gè)計(jì)算器程序，利用算符優(yōu)先關(guān)系，實(shí)現(xiàn)對算術(shù)四則混合運(yùn)算表達(dá)式的求值。輸入的形式：算術(shù)表達(dá)式，以井號(hào)“#”結(jié)束。例如2*(3+4)#； 包含的運(yùn)算符只能有+ 、- 、* 、/ 、(、 )；輸出的形式：運(yùn)算結(jié)果，例如Answer is:14；程序所能達(dá)到的功能：對算術(shù)表達(dá)式求值并輸出結(jié)果。4.1需求分析1、程序所能達(dá)到的功能：能夠處理以字符序列的形式輸入的不含變量的實(shí)數(shù)表達(dá)式，正確處理負(fù)數(shù)與小數(shù)，判斷表達(dá)式是還語法正確（包含分母不能為零的情況），正確實(shí)現(xiàn)對算術(shù)四則混合運(yùn)算表達(dá)式的求值，能夠?qū)⒂?jì)算中遇到的問題和結(jié)果以文件的形式予以存儲(chǔ)。2、輸入的形式和輸入值的范圍：以字符串的形式輸入表達(dá)式，以“#”結(jié)束。3、輸出的形式：在計(jì)算過程中遇到的問題或最終的答案將顯示在屏幕上，同時(shí)所計(jì)算的表達(dá)式的最終的結(jié)果也將保存在文件中。4、測試數(shù)據(jù)：輸入“3*(7-2)#”時(shí)，輸出“15.000000”，測試正確；輸入“!(9-2)#”時(shí)，輸出“輸入錯(cuò)誤！”，測試正確。4.2總體設(shè)計(jì)4.2.1抽象數(shù)據(jù)類型定義ADT Stack數(shù)據(jù)對象：D= |ElemSet,i=1,2,，n, n0數(shù)據(jù)對象：R1=|,i=2,，n約定端為棧頂，端為棧底。基本操作：InitStack(&S)操作結(jié)果：構(gòu)造一個(gè)空棧S。GetTop(S)初始條件：棧S已存在。操作結(jié)果：用P返回S的棧頂元素。Push(&S，ch)初始條件：棧S已存在。操作結(jié)果：插入元素ch為新的棧頂元素。Pop(&S)初始條件：棧S已存在。操作結(jié)果：刪除S的棧頂元素。In(ch)操作結(jié)果：判斷字符是否是運(yùn)算符，運(yùn)算符即返回1。Precede(c1, c2) 初始條件：c1,c2為運(yùn)算符。操作結(jié)果：判斷運(yùn)算符優(yōu)先權(quán)，返回優(yōu)先權(quán)高的。Operate(a,op,b)初始條件：a,b為整數(shù)，op為運(yùn)算符。操作結(jié)果：a與b進(jìn)行運(yùn)算，op為運(yùn)算符，返回其值。num(n)操作結(jié)果：返回操作數(shù)的長度。EvalExpr()初始條件：輸入表達(dá)式合法。操作結(jié)果：返回表達(dá)式的最終結(jié)果。ADT Stack4.2.2函數(shù)模塊說明為實(shí)現(xiàn)算符優(yōu)先算法，可以使用兩個(gè)工作棧。一個(gè)稱做OPTR，用以寄存運(yùn)算符；另一個(gè)稱做OPND，用以寄存操作數(shù)或運(yùn)算結(jié)果。算法的基本思想是：(1)首先置操作數(shù)棧為空棧，表達(dá)式起始符“#”為運(yùn)算符棧底元素(2)依次讀入表達(dá)式中每個(gè)字符，若是操作數(shù)則進(jìn)OPND棧，若是運(yùn)算符則和OPTR棧的棧頂運(yùn)算符比較優(yōu)先權(quán)后作相應(yīng)操作，直至整個(gè)表達(dá)式求值完畢（即OPTR棧的棧頂元素和當(dāng)前讀入的字符均為“#”）。4.2.3主函數(shù)流程圖4.2.4函數(shù)模塊調(diào)用關(guān)系4.2.5運(yùn)算符間的優(yōu)先關(guān)系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)用關(guān)系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(“請輸入表達(dá)式關(guān)以#結(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(“輸入錯(cuò)誤！n”);4.4測試與分析4.4.1測試加法測試，輸入正確，輸出正確，測試正確：乘法測試，輸入正確，輸出正確，測試正確：輸入表達(dá)式正確，輸出正確，測試正確：輸入表達(dá)式錯(cuò)誤，能正確判斷，測試正確：4.4.2分析內(nèi)容包括：1、調(diào)試過程中遇到的問題是如何解決的以及對設(shè)計(jì)與實(shí)現(xiàn)的回顧討論和分析:遇到的問題：調(diào)試過程中遇到了輸入非法字符不輸出“錯(cuò)誤！”的情況。解決的辦法：查ASCII碼表得知運(yùn)算符+,-,*,/,(,),#和運(yùn)算數(shù)0,1,2,3,4,5,6,7,8,9相應(yīng)的ASCII值。在主程序中加入了判斷語句，判斷輸入的是否為運(yùn)算符或運(yùn)算數(shù)。如果是，則進(jìn)行正常運(yùn)算；如果不是，則返回錯(cuò)誤。2、算法的時(shí)間復(fù)雜度和空間復(fù)雜度的分析：中綴表達(dá)式運(yùn)算時(shí)間主要用在字符串掃描和算符優(yōu)先權(quán)的比較上。把#看作運(yùn)算符，操作數(shù)與運(yùn)算符個(gè)數(shù)相同，最壞情況下優(yōu)先級(jí)比較是n/2次，即運(yùn)算順序完全是逆序的，每個(gè)字符掃描一遍是O(n)的，所以整個(gè)算法復(fù)雜度是O(n2)的。算法中用到兩個(gè)棧，分別為O(n/2)，其算法空間復(fù)雜度是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(輸入錯(cuò)誤!n);5 總結(jié)與展望通過這段時(shí)間的課程設(shè)計(jì)，本人對計(jì)算機(jī)的應(yīng)用、數(shù)據(jù)結(jié)構(gòu)的作用以及C語言的使用都有了更深的了解。當(dāng)然也遇到不少問題，也正是國為這些問題引發(fā)的思考給我?guī)砹耸斋@。從當(dāng)初不喜歡上機(jī)寫程序到現(xiàn)在能主動(dòng)寫程序，從當(dāng)初拿著程序不知從何下手到現(xiàn)在知道如何分析問題，如何用專業(yè)知識(shí)解決實(shí)際問題的轉(zhuǎn)變。我發(fā)現(xiàn)無論是專業(yè)知識(shí)還是動(dòng)手能力，自己都有很大程度的提高。在實(shí)際上機(jī)操作過程中，不僅是讓我們了解數(shù)據(jù)結(jié)構(gòu)的理論知識(shí)，更重要的