中南大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告

信息科學(xué)與工程學(xué)院課程設(shè)計(jì)報(bào)告書課程名稱數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)題目算術(shù)表達(dá)式求值專業(yè)班級(jí)電子信息工程1002學(xué)號(hào)0909101123姓名楊家駿指導(dǎo)教師李登2012年7月

目錄問題描述基本要求數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)軟件模塊結(jié)構(gòu)圖程序設(shè)計(jì)思想程序流程圖源程序調(diào)試分析測(cè)試數(shù)據(jù)用戶使用手冊(cè)心得體會(huì)一：?jiǎn)栴}描述從鍵盤上輸入算術(shù)表達(dá)式，包括括號(hào)，（1）判斷表達(dá)式是否是正常表達(dá)式；（2）計(jì)算出一般表達(dá)式（類似如a*b+c/d-e）的值，（3）并能實(shí)現(xiàn)一元多項(xiàng)式相加。二：基本要求(1)程序?qū)λ斎氲挠堰_(dá)式作簡(jiǎn)單的判斷，如表達(dá)式有錯(cuò)，能給出適當(dāng)?shù)奶崾?2)能處理單目運(yùn)算符：十和一。（3）已知和，并且在A(x)和B(x)中指數(shù)相差很多，求A(x)=A(x)+B(x)。要求設(shè)計(jì)存儲(chǔ)結(jié)構(gòu)表示一元多項(xiàng)式，設(shè)計(jì)算法實(shí)現(xiàn)一元多項(xiàng)式相加。三：數(shù)據(jù)結(jié)構(gòu)的分析根據(jù)本課程設(shè)計(jì)題目要求，可總體分為三個(gè)大的模塊。分別是判斷表達(dá)式正確與否（模塊1）、表達(dá)式求值設(shè)計(jì)（模塊2）、實(shí)現(xiàn)一元多項(xiàng)式相加（模塊3）。所以下面分別對(duì)三個(gè)大模塊進(jìn)行大概的各類分析。①需求分析模塊1：能夠處理以字符序列的形式輸入的不含變量的實(shí)數(shù)表達(dá)式，能夠正確處理負(fù)數(shù)與小數(shù)，能夠判斷表達(dá)式是否語法正確（即不能出現(xiàn)兩符號(hào)連續(xù)出現(xiàn)的情況，包括分母不為零的情況）。模塊2：能正確實(shí)現(xiàn)對(duì)算術(shù)四則混合運(yùn)算表達(dá)式的求值。以字符串的形式輸入表達(dá)式，以“#”結(jié)束；在計(jì)算的最終的答案將顯示在屏幕上；能夠?qū)⒂?jì)算中遇到的問題和結(jié)果以文件的形式予以存儲(chǔ)。模塊3：能夠?qū)崿F(xiàn)一元多項(xiàng)式相加，并予以存儲(chǔ)。②概要設(shè)計(jì)模塊1：數(shù)據(jù)結(jié)構(gòu)類型：#defineSTACK_INIT_SIZT100;#defineSTACKINCREMENT10typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;模塊2：數(shù)據(jù)結(jié)構(gòu)類型typedefstruct{ intdata[MAX];inttop;}SeqStack;SeqStack*OPTR,*OPND;模塊3：數(shù)據(jù)結(jié)構(gòu)類型：typedefintElemType;typedefstructCLNode{ElemTypecoef;ElemTypeexp;structCLNode*next;}CLNode,*CLinkList③詳細(xì)設(shè)計(jì)模塊1：voidmain(){SqStack_TOPTR;SqStack_NOPND;floata,b,i;chartheta,c,x;InitStack_T(&OPTR);Push_T(&OPTR,’#’);InitStack_N(&OPND);printf(“請(qǐng)輸入表達(dá)式關(guān)以’#’結(jié)尾：\n”);c=getchar();if(c==35||(c>=40&&c<=43)||c==45||(c>=47&&c<=57)){while(c!=’#’||GetTop_T(&OPTR)!=’#’){if(c>=48&&c<=57){i=(float)c-48;Push_N(&OPND,i);c=getchar();}else{switch(Precede(GetTop_T(&OPND),c)){ case’<’:Push_T(&OPTR,c);c=getchar();break;case’=’:x=Pop_T(&OPTR);c=getchar();break;case’>’:theat=Pop_T(&OPTR);b=Pop_N(&OPND);a=Pop_N(&OPND);Push_N(&OPND,Operate(a,theta,b));break;}}}printf(“結(jié)果是%f\n”,GetTop_N(&OPND));}elseprintf(“輸入錯(cuò)誤！\n”);}模塊2：voidmain(){ SeqStack*OPTR,*OPND;//定義兩個(gè)棧 intw,op,temp; inta,b,is_err; OPTR=Init_SeqStack();//初始化運(yùn)算符optr堆棧 OPND=Init_SeqStack();//初始化運(yùn)算數(shù)opnd堆棧 is_err=Push(OPTR,'#');//首先將#進(jìn)運(yùn)算符棧 system("cls"); printf("中綴表達(dá)式求值程序\n\n"); printf("使用方法：連續(xù)輸入表達(dá)式，以#號(hào)結(jié)束，最后按回車鍵。\n\n"); printf("可使用的運(yùn)算符包括：(、)、^、*、/、%、+、-\n\n"); printf("注意：運(yùn)算數(shù)為0-9十個(gè)數(shù)字。\n\n"); printf("請(qǐng)輸入表達(dá)式："); w=getchar(); while(w!='#'||GetTop(OPTR)!='#')//算符棧頂元素不是#（表達(dá)式非0，執(zhí)行語句） { if(Is_OPND(w))//w為數(shù)值，返回1，w為算符，返回0 { Push(OPND,w-'0');//數(shù)值進(jìn)opnd堆棧 w=getchar();//循環(huán) } else switch(Precede(GetTop(OPTR),w))//否則，比較optr堆棧中棧頂?shù)乃惴cgetchar()函數(shù)讀入的算符的優(yōu)先級(jí) { case-1://棧外算符優(yōu)先級(jí)高，繼續(xù)入棧 is_err=Push(OPTR,w);//入棧操作 w=getchar();//循環(huán) break; case0://??? is_err=Pop(OPTR,&temp); w=getchar(); break; case1://棧內(nèi)算符優(yōu)先級(jí)高 is_err=Pop(OPND,&b);//將棧頂?shù)脑刭x予后一個(gè)變量 is_err=Pop(OPND,&a); is_err=Pop(OPTR,&op); is_err=Push(OPND,Execute(a,op,b)); break; } } printf("結(jié)果為：%d\n",GetTop(OPND));}模塊3：voidAddpoly(PolyNode*pa,PolyNode*pb)

//兩個(gè)多項(xiàng)式相加

{

PolyNode*p,*q,*r,*temp;

//temp用來存放臨時(shí)結(jié)點(diǎn)

floatsum;

p=pa->next;

q=pb->next;

r=pa;

while(p&&q)

{

if(p->exp<q->exp)

//p指向的項(xiàng)指數(shù)小于q，尾指針指向p，且將p指向鏈表的下一結(jié)點(diǎn)

{

r=p;

p=p->next;

}

elseif(p->exp==q->exp)

//指數(shù)相等時(shí)，系數(shù)相加

{

sum=p->coef+q->coef;

if(sum!=0)

{

p->coef=sum;

r=p;

}

else

//系數(shù)相加為0

{

r->next=p->next;

free(p);

}

p=r->next;

temp=q;

q=q->next;

}

else

//q指向項(xiàng)指數(shù)小于p時(shí)，將q加入多項(xiàng)式中

{

temp=q->next;

q->next=p;

r->next=q;

r=q;

q=temp;

}

}

if(q)

r->next=q;

free(pb);

}voidPrint(PolyNode*p)

//打印多項(xiàng)式

{

inti=0;

while(p->next)

{

p=p->next;

i++;

printf("

%g*x^%d\n",p->coef,p->exp);

}

printf("一共有%d項(xiàng)\n",i);

}

voidmain()

//主函數(shù)

{

PolyNode*pa,*pb;inti;

printf("\n**********^-^歡迎光臨^-^**********\n");

printf("\n請(qǐng)輸入多項(xiàng)式a(按指數(shù)遞增順序輸入):\n");

pa=Createpoly();

Print(pa);

printf("\n請(qǐng)輸入多項(xiàng)式b(按指數(shù)遞增順序輸入):\n");

pb=Createpoly();

Print(pb);

printf("\n多項(xiàng)式相加結(jié)果是:\n");

Addpoly(pa,pb);

Print(pa);

printf("\n");

}④調(diào)試分析模塊1：未實(shí)現(xiàn)功能模塊2：模塊3： 四：軟件模塊結(jié)構(gòu)圖模塊1、2： 模塊3：主函數(shù)模塊主函數(shù)模塊初始化單鏈表初始化單鏈表建立單鏈表建立單鏈表相加多項(xiàng)式相加多項(xiàng)式五：程序設(shè)計(jì)思想模塊1：看到程序要求，頭腦里就有一定的邏輯思路和關(guān)系：先判斷括號(hào)是否對(duì)稱，然后再考慮是否有符號(hào)連續(xù)的情況。最后看是否運(yùn)算數(shù)位比符號(hào)位多1。模塊2：算術(shù)表達(dá)式中有加減乘除，以及乘方和括號(hào)等運(yùn)算關(guān)系和法則，又考慮到有運(yùn)算先后的關(guān)系。故需采用不同的存儲(chǔ)結(jié)構(gòu)來存儲(chǔ)，所以要用到OPTR和OPND兩個(gè)棧，分別用來存儲(chǔ)運(yùn)算符合運(yùn)算數(shù)，并且規(guī)定‘#’是最低運(yùn)算級(jí)，所以需用‘#’表示表達(dá)式結(jié)束。模塊3：第一眼看到要求以及多項(xiàng)式的形式，可以采用順序存儲(chǔ)結(jié)構(gòu)來實(shí)現(xiàn)，但是一般應(yīng)用中多項(xiàng)式的次數(shù)過大，難以確定鏈表的長(zhǎng)度，所以此處用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)來實(shí)現(xiàn)。開始開始Charc;SqStackOPTR,OPND;c=getchar()C!=’#’||GetTop(OPTR)!=’#’s->data[s->top]’’’’Precede(GetTop(OPTR),c)Push(OPTR,c)C=getchar()Pop(OPTR,c)Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b)ReturnGetTop(OPND)結(jié)束七：源程序#include"stdio.h"#include"stdlib.h"#include<malloc.h>#defineOK1#defineERROR0#defineOVERFLOW0#defineMAX100typedefstruct{ char*base; char*top; intstacksize;}SqStack_T;typedefstruct{ float*base; float*top; intstacksize;}SqStack_N;voidInitStack_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;}voidInitStack_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;}charGetTop_T(SqStack_T*S){ chare; if((*S).top==(*S).base)returnERROR; e=*((*S).top-1); returne;}floatGetTop_N(SqStack_N*S){ floate; if((*S).top==(*S).base)returnERROR; e=*((*S).top-1); returne;}charPush_T(SqStack_T*S,chare){ 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; returnOK;}floatPush_N(SqStack_N*S,floate){ 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; returnOK;}charPop_T(SqStack_T*S){ chare; if((*S).top==(*S).base)returnERROR; e=*(--(*S).top); returne;}floatPop_N(SqStack_N*S){ floate; if((*S).top==(*S).base)returnERROR; e=*(--(*S).top); returne;}charm[7]="+-*/()#";charn[7][7]={">><<<>>",">><<<>>",">>>><>>",">>>><>>","<<<<<=",">>>>>>","<<<<<="};charPrecede(chara,charb){ inti=0,j=0; while(m[i]!=a) i++; while(m[j]!=b) j++; return(n[i][j]);}floatOperate(floata,chartheta,floatb){ floatr; switch(theta){ case'+':r=a+b;break; case'-':r=a-b;break; case'*':r=a*b;break; case'/':if(b!=0)r=a/b; elseprintf("輸入錯(cuò)誤!"); break; } returnr;}voidmain(){ SqStack_TOPTR; SqStack_NOPND; floata,b,i; chartheta,c,x; InitStack_T(&OPTR);Push_T(&OPTR,'#'); InitStack_N(&OPND); printf("請(qǐng)輸入表達(dá)式并以'#'結(jié)尾:\n"); c=getchar(); if(c==35||(c>=40&&c<=43)||c==45||(c>=47&&c<=57)) { while(c!='#'||GetTop_T(&OPTR)!='#') { if(c>=48&&c<=57) { i=(float)c-48; Push_N(&OPND,i); c=getchar(); } else { switch(Precede(GetTop_T(&OPTR),c)) { case'<':Push_T(&OPTR,c);c=getchar();break; case'=':x=Pop_T(&OPTR);c=getchar();break; case'>':theta=Pop_T(&OPTR);b=Pop_N(&OPND);a=Pop_N(&OPND);Push_N(&OPND,Operate(a,theta,b));break; } } }printf("結(jié)果是%f\n",GetTop_N(&OPND)); } elseprintf("輸入錯(cuò)誤!\n");}} typedefstruct { intdata[MAX]; inttop; }SeqStack; SeqStack*Init_SeqStack()//初始化堆棧 { SeqStack*s; s=newSeqStack;//申請(qǐng)?？臻g if(!s) { printf("空間不足，初始化失敗！"); returnNULL;//未申請(qǐng)到足夠大的存儲(chǔ)空間，返回空指針 } else { s->top=-1;//初始化棧頂指針 printf("堆棧初始化成功!\n按回車鍵繼續(xù)..."); returns;//申請(qǐng)到棧空間，返回棧空間地址 } } intEmpty(SeqStack*s){//判空棧 if(s->top==-1) return1;//棧頂指針指向棧底，空棧 else return0; } intPush(SeqStack*s,intx){//進(jìn)棧 if(s->top==MAX-1) return0;//棧滿不能入棧，返回錯(cuò)誤代碼0 else {s->top++;//棧頂指針向上移動(dòng) s->data[s->top]=x;//將x至入新的棧頂 return1;//入棧成功，返回成功代碼1 } } intPop(SeqStack*s,int*x){//出棧 if(Empty(s)) return0;//?？詹荒艹鰲?，返回錯(cuò)誤代碼0 else {*x=s->data[s->top];//保存棧頂元素值 s->top--;//棧頂指針向下移動(dòng) return1;//返回成功代碼1 } } intGetTop(SeqStack*s)//取棧頂元素 { return(s->data[s->top]); } intIs_OPND(charx)//判斷運(yùn)算符和運(yùn)算數(shù) { inttemp; temp=1; switch(x) { case'^': case'*': case'/': case'%': case'+': case'-': case'(': case')': case'#':temp=0; } return(temp); } intPrecede(charin,charout) { intc_temp1,c_temp2; inttemp; switch(in) { case'^':c_temp1=5;break; case'*': case'/': case'%':c_temp1=4;break; case'+': case'-':c_temp1=2;break; case'(':c_temp1=0;break; case')':c_temp1=6;break; case'#':c_temp1=-1; } switch(out) { case'^':c_temp2=5;break; case'*': case'/': case'%':c_temp2=3;break; case'+': case'-':c_temp2=1;break; case'(':c_temp2=6;break; case')':c_temp2=0;break; case'#':c_temp2=-1; } if(c_temp1<c_temp2)temp=-1;//棧外算符優(yōu)先級(jí)高，入棧 if(c_temp1==c_temp2)temp=0; if(c_temp1>c_temp2)temp=1;//棧內(nèi)算符優(yōu)先級(jí)高，運(yùn)算 return(temp); } intExecute(inta,charop,intb){ ints; switch(op) { case'^':s=(int)pow(a,b);break; case'*':s=a*b;break; case'/':s=a/b;break; case'%':s=a%b;break; case'+':s=a+b;break; case'-':s=a-b;break; }return(s); } voidmain() { SeqStack*OPTR,*OPND;//定義兩個(gè)棧 intc,theta,temp; inta,b,is_err; OPTR=Init_SeqStack();//初始化運(yùn)算符optr堆棧 OPND=Init_SeqStack();//初始化運(yùn)算數(shù)opnd堆棧 is_err=Push(OPTR,'#');//首先將#進(jìn)運(yùn)算符棧 system("cls"); printf("中綴表達(dá)式求值程序\n\n"); printf("使用方法：連續(xù)輸入表達(dá)式，以#號(hào)結(jié)束，最后按回車鍵。\n\n"); printf("可使用的運(yùn)算符包括：(、)、^、*、/、%、+、-\n\n"); printf("注意：運(yùn)算數(shù)為0-9十個(gè)數(shù)字。\n\n"); printf("請(qǐng)輸入表達(dá)式："); w=getchar(); while(c!='#'||GetTop(OPTR)!='#')//算符棧頂元素不是#（表達(dá)式非0，執(zhí)行語句） { if(Is_OPND(c))//c為數(shù)值，返回1，c為算符，返回0 { Push(OPND,c-'0');//數(shù)值進(jìn)opnd堆棧 C=getchar();//循環(huán) } Else switch(Precede(GetTop(OPTR),c))//否則，比較optr堆棧中棧頂?shù)乃惴cgetchar()函數(shù)讀入的算符的優(yōu)先級(jí) { case-1://棧外算符優(yōu)先級(jí)高，繼續(xù)入棧 is_err=Push(OPTR,c);//入棧操作 c=getchar();//循環(huán) break; case0://??? is_err=Pop(OPTR,&temp); c=getchar(); break; case1://棧內(nèi)算符優(yōu)先級(jí)高 is_err=Pop(OPND,&b);//將棧頂?shù)脑刭x予后一個(gè)變量 is_err=Pop(OPND,&a); is_err=Pop(OPTR,&theta); is_err=Push(OPND,Execute(a,theta,b)); break; } } printf("結(jié)果為：%d\n",GetTop(OPND)); } typedefstructNode//多項(xiàng)式數(shù)據(jù)類型的定義 { floatcoef;//系數(shù) intexp;//指數(shù) structNode*next;//指向多項(xiàng)式的下一結(jié)點(diǎn) }PolyNode; PolyNode*Createpoly()//創(chuàng)建鏈表 { PolyNode*L,*r,*s; floatcoef; intexp; L=(PolyNode*)malloc(sizeof(PolyNode));//申請(qǐng)表頭結(jié)點(diǎn)空間 r=L;//r為尾指針 printf("coef:"); scanf("%f",&coef); printf("exp:"); scanf("%d",&exp); while(coef!=0) { s=(PolyNode*)malloc(sizeof(PolyNode));//建立項(xiàng)的結(jié)點(diǎn)，并插在鏈尾 s->coef=coef; s->exp=exp; r->next=s; r=s; printf("coef:"); scanf("%f",&coef); printf("exp:"); scanf("%d",&exp); } r->next=NULL; return(L); } voidAddpoly(PolyNode*pa,PolyNode*pb)//兩個(gè)多項(xiàng)式相加 { PolyNode*p,*q,*r,*temp;//temp用來存放臨時(shí)結(jié)點(diǎn) floatsum; p=pa->next; q=pb->next; r=pa; while(p&&q) {if(p->exp<q->exp)//p指向的項(xiàng)指數(shù)小于q，尾指針指向p，且將p指向鏈表的下一結(jié)點(diǎn) { r=p; p=p->next; } elseif(p->exp==q->exp)//指數(shù)相等時(shí)，系數(shù)相加 { sum=p->coef+q->coef; if(sum!=0) { p->coef=sum; r=p; } else//系數(shù)相加為0 { r->next=p->next; free(p); } p=r->next; temp=q; q