數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)一元稀疏多項(xiàng)式計(jì)算器報(bào)告代碼

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)設(shè)計(jì)題目：一元稀疏多項(xiàng)式計(jì)算器專業(yè)班級(jí)學(xué)號(hào)姓名指導(dǎo)教師2010年12月20H目錄一'課程題目1二、需求分析1三、測試數(shù)據(jù)2四'概要設(shè)計(jì)2五'調(diào)用關(guān)系圖3六、程序代碼3七、測試結(jié)果11八、心得體會(huì)及總結(jié)12數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)課程題目一元稀詭多項(xiàng)式計(jì)算器二、需求分析1、一元稀疏多項(xiàng)式簡單計(jì)算器的功能是：1.1 輸入并建立多項(xiàng)式；1.2 輸出多項(xiàng)式,輸出形式為整數(shù)序列:n,cl,el,c2,e2,cn,en,其中ii是多項(xiàng)式的項(xiàng)數(shù),ci和ei分別是第i項(xiàng)的系數(shù)和指數(shù)，序列按指數(shù)降序排列；1.3 求多項(xiàng)式a、b的導(dǎo)函數(shù)；1.4 計(jì)算多項(xiàng)式在x處的值；1.5 多項(xiàng)式

2、和b和加，建立多項(xiàng)認(rèn)a+b；1.6 多項(xiàng)式a和b相減,建立多項(xiàng)式a-bo2、設(shè)計(jì)思路：2.1 定義線性表的動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu)；2.2 建立多項(xiàng)式存儲(chǔ)結(jié)構(gòu)，定義指針*優(yōu)田2.3 利用鏈表實(shí)現(xiàn)隊(duì)列的構(gòu)造.每次輸入一項(xiàng)的系數(shù)和指數(shù)，町以輸出構(gòu)造的一元多項(xiàng)式2.4 演示程用以用戶和計(jì)舜機(jī)的對話方式執(zhí)行，即在計(jì)舜機(jī)終站上顯示“提示信息”Z后，由川戶化鍵盤，輸入演示程序小規(guī)運(yùn)的運(yùn)行命令；報(bào)后根據(jù)相應(yīng)的輸入數(shù)據(jù)（濾去輸入中的4法字符）建立的多項(xiàng)式以及多項(xiàng)式相加的運(yùn)行結(jié)果在屏幕上顯示。多項(xiàng)式顯示的格式為:clx*el+c2x*e2+4-cnxnen3、設(shè)計(jì)思路分析要解決多項(xiàng)式相加，必須要有多項(xiàng)式，所以必須首

3、先建立兩個(gè)多項(xiàng)式，在這電采用鏈表的方式存儲(chǔ)璉表，所以我將結(jié)點(diǎn)結(jié)構(gòu)體定義為序數(shù)coef指數(shù)expn指針域next運(yùn)川尾插法建立兩條單鏈表，以巾鏈表polynp和polynh分別表不兩個(gè)一元多項(xiàng)式a和b,a+b的求和運(yùn)算等同于單鏈表的插入問題（將單鏈表polynP中的結(jié)點(diǎn)插入到單鏈表polynh中），因此“和多項(xiàng)式”中的結(jié)點(diǎn)無須另生成。為了實(shí)現(xiàn)處理'設(shè)P、q分別指向單鏈衣polya和polyb的彳前項(xiàng)，比較hq結(jié)點(diǎn)的指數(shù)項(xiàng)，山此得到下列運(yùn)算規(guī)則：若p->expnvq->expn,則結(jié)點(diǎn)p所指的結(jié)點(diǎn)應(yīng)是和多項(xiàng)式”中的“項(xiàng)，令指針P后移。若p->expn=q->expn

4、,則將兩個(gè)結(jié)點(diǎn)中的系數(shù)相加，半和不為。時(shí)修改結(jié)點(diǎn)P的系數(shù)。若p->expn>q->expm則結(jié)點(diǎn)q所指的結(jié)點(diǎn)應(yīng)是“和多項(xiàng)式中的-項(xiàng)，將結(jié)點(diǎn)q插入在結(jié)點(diǎn)PZ前，且令指針q在原來的鏈農(nóng)上后移。三、測試數(shù)據(jù)：1、(2x+5x8-31x41)+(7-5x8+llx'9)=(-3.lxll+Ux'9+2x+7);2、(6x-3x+4.4x21.2x9+1.2x9)-(-6x-3十5.4x2-x2十7.8x15)=(-7.8x”15l.2x“9+12x-3-x);3、(l+x+x*2+x*3+x°4+x5)+(_x*3-x4)=(l+x+x*2+x*5);4、(

5、x+x'3)+(-x-x*3)=0;5、(x+x”100)+(x*100+xA200)二(x+2x*100+x*200);6、(x+x”2+x"3)+0=x+x”2+x”3.四、概要設(shè)計(jì)1、元素類型、結(jié)點(diǎn)類型和指針類型：typedefstructPolynomial(floatcoef;系數(shù)intexpn;指數(shù)structPolynomial*next;*Polyn,Polynomial;2、建立一個(gè)頭指針為head.項(xiàng)數(shù)為m的一兀多項(xiàng)式，建立新結(jié)點(diǎn)以接收數(shù)據(jù)，調(diào)用Insert函數(shù)插入結(jié)點(diǎn)：PolynCreatePolyn(Polynhead,intm)inti;Polynp

6、;p=liead=(Polyn)malloc(sizeof(structPolynomial);head->next=NULL;for(i=0;ivm;i+)(p=(Polyn)malloc(sizeof(structPolynomial);printfC請輸入第d項(xiàng)的系數(shù)與指數(shù)："，i十1);scanf(u%f%d：&p->coef,&p->expn);Insert(p,head);)returnhead:)3、主函數(shù)和其他函數(shù)：voidmainO(intm,n,a,x;charflag;Polynpa=0,pb=0,pc;)floatValueP

7、olyn(Polynhead,intx)輸入x值，計(jì)算并返回多項(xiàng)式的值五、調(diào)用關(guān)系圖(圖1)六、程序代碼：#include<stdio.h>#include<stdlib.h>typedefstructPolynomialfloatcoef;intexpn;定義多項(xiàng)式的項(xiàng)structPolynomial*next;*Polyn,Polynomial;系數(shù)voidInsert(Polvnp,Polvn指數(shù)h)if(p->coef=0)free(p);elsePolvnql,q2;qi=h；系豹為o的話奢放結(jié)占q2=h->next;while(q2&&a

8、mp;p->expn<q2-expn)查找插入位置ql=q2;q2=q2->next;)if(q2&&p->expr)=q2->expn)將指數(shù)相同相合并q2->coef+二p->coef;free(p);if(!q2->coef)系數(shù)為0的話禪放結(jié)點(diǎn)ql->next=q2->next;free(q2);else指數(shù)為新時(shí)將結(jié)點(diǎn)插入p->next=q2;ql->next=p;PolynCreatePoIvn(Polynhead,intm)為heud>項(xiàng)數(shù)為m的一元多項(xiàng)式inti;Polynp;pAhe

9、ud31(Pulvn)malloc(sizeof(structPolynomial);head->next=XULL;for(i=0;i<m;i+)建立一個(gè)頭指針p=(Polyn)malloc(sizeof(structPolynomial);收數(shù)據(jù)printf(請輸入第d項(xiàng)的系數(shù)-與指數(shù):,i+1);scanf("%f&p->coef,&p->expn);Insert(p,head);數(shù)插入結(jié)點(diǎn)建立新結(jié)點(diǎn)以接調(diào)HJInsert函returnhead;)voidDestroyPolyn(Polynp)Polynql,q2;ql=p>nex

10、t;Q2=ql->nexi;while(ql->next)銷毀多項(xiàng)式Pfree(ql);ql=q2；q2=q2->nexl;)voidPrinlPolyn(PolynP)Polynq=P")next;intflag=l;if(!q)項(xiàng)數(shù)計(jì)數(shù)器若多項(xiàng)式為空,putcharO);printf(',nu);return;while(q)輸出0if(q->coef>0&&flag!=l)putcharf+，)；系數(shù)大于0且不是第一項(xiàng)if(q->coef!=l&&q->coef!=-1)1系數(shù)非1或T的普通情況p

11、rintfC*%g*,q->coef);if(q->expn=l)putchar('X')；elseif(q->expn)prititf("X%cT,q->expn);)else(if(q->coef=l)，,if(!q->expn)putchar1');elseif(q->expn=l)pulchar(?X');elseprintfq->expn);)ir(q->coef=-l)(if(!q->expn)printf(uTn);elseif(q->expn=l)prinlf(u-XH)

12、;elseprintfC-X%dH,q->expn):)q=q-)next;flag+;)printf(nnn);)inicompare(PolynatPolynb)iifGiMb)(if(!bl1a->expn>b->expn)return1;elseif(!cdIa->expn<b->expn)returnT;elsereturn0;)elseif(!a&&b)return-1;a多項(xiàng)式已空，但b多項(xiàng)式非空elsereturn1;/b多項(xiàng)式己空，但a多項(xiàng)式非空PolynAddPolyn(Polynpa,Polynpb)缸+b,返回其

13、頭指針求解并建立多項(xiàng)式Polynqa=pa->next;Polynqb=pb->next;Polynheadc,he,qc;hc=(Polyn)malloc(sizeof(structPolynomial);建立頭結(jié)點(diǎn)hc->next=XLLL;headc=hc;while(qaqb)qc=(Polyn)malloc(sizeof(structPolynomial);switch(compare(qa,qb)case1:qc->coef=qa->coef;qc->expn=qa->expn;qa=qa->next;break;case0:qc-&

14、gt;coef=qci->coefAclb->coef;qc->expn=qa->expn;qd二qti->nexl;qb=qb->next;break:case-1:qc->coef=qb->coof;qc->expn=qb->expn;qb二qb->nexl;break;if(qc->coef!=0)qc->next=hc->next;hc->next=qc;he二qc;elsefree(qc)/當(dāng)相力II系數(shù)為0時(shí)釋放該結(jié)點(diǎn)returnheadc:)Polvn SubtractPolyn(Polyn

15、 pa, Polvn pb) 返 回其頭指針Polyn h=pb;Polyn p=pb->nexl:Polyn pd;whi le(p)(p->coef*=-l;p=p->next:)pdAzWdPulynCpa, h);for (p=h->next;p;p=p->nexl) p->coef*=-l; return pd;)float ValuePolyn(PoIyn head, int x)返回多項(xiàng)式的值Polyn p;int i, t;float sum 二 0;for (p=head->next;p;p=p->next)t=l；for (i

16、=p->expn;i!=0;)(if(i<0) (t./=x;i+;) elsei* 二 x；i；)sum+=p->coef*t;求解并建立多項(xiàng)式a-b,將pb的系數(shù)取反恢復(fù)pb的系數(shù)輸入x值,計(jì)算并指數(shù)小于0,進(jìn)行除法指數(shù)大于0,進(jìn)行乘法returnsum;PolynDerivative(Polynhead)求解并建立導(dǎo)函數(shù)多項(xiàng)式,并返回其頭指針Polynq=head->next>pl,p2,hd;hd=p1=(Po1yn)ma11oc(sizeof(structPolynomial)；建立頭結(jié)點(diǎn)hdnext=NULL;while(q)(if(q->exp

17、n!=0)該項(xiàng)不是常數(shù)項(xiàng)時(shí)p2=(Polyn)malloc(sizeof(structPolynoffliul);p2->coel-q->coef*q->expn;p2->expn=q->expn-l;p2->next二pl-next;p»next=p2;pl=p2;連接結(jié)點(diǎn)q=q->next;)returnhd;)PolynMultiplyPolyn(Polynpa,Polvnpb)求解并建立多項(xiàng)式a*b,返回其頭指針Polynhf,pf:Polynqa=pa->next;Polynqb=pb->next;hf=(Polyn)m

18、alloc(sizeof(struetPolynomial);建立頭結(jié)點(diǎn)hf->next=NULL;for(;qa;qa=qa->nexl)for(qb=pb->next;qb;qb=qb>next)pf=(Polyn)malloc(sizeof(structPolynomial);pf->coef=qa->coef*qb->coef;pf->expn二qai->expn+qb-)expn;Insert(pf,hf);調(diào)用Insert函數(shù)以合并指數(shù)和同的項(xiàng))returnhf;)voidmain()intm,n,a,x;charflag;Po

19、lynpa=0,pb=0,pc;printfCnn)；printf*班*nn);printfC*rT);printfC歡迎使川多項(xiàng)式操作程序rT);prinlf(八請輸入e的項(xiàng)數(shù):“)；scanf(n%dn,&m);pa=CreatePolyn(pa,m);建立多項(xiàng)式apriritf®輸入b的項(xiàng)數(shù)：”);scanf(n%dn,&n);pb=(,reatePolvn(pbtn);建立多項(xiàng)式b輸出菜單printfCprintf(u*printf(/z*printf(*printf('，*n”)；printff*printfC*n”)；printf(“*printf

20、("*n)printf('z*printf(n*r)；printfC*n)；多項(xiàng)式操作程序*2;*rv);A:輸ill多項(xiàng)式aB:輸出多項(xiàng)式b*n)*C:輸出a的導(dǎo)數(shù)D:輸出b的導(dǎo)數(shù)*n”)；*E:代入x的值計(jì)算aF:代入x的傅計(jì)算b*lv);*G:輸出a+bH:輸出u-b*n”)；*I:輸出a*bJ：退出程序printfC*n)；prinlfC*門”)；while(a)printfCni#選擇操作：)；scanfC%c：&flag);switch(flag)caseA:case'ci:printf(z，n多項(xiàng)式滬);PrintPolyn(pa);break;

21、)case。B':case*:(printf(nn多項(xiàng)式b=H);PrintPolyn(pb);break;case,C：case*c':(pc=Derivative(pa);printfCXn多項(xiàng)式a的導(dǎo)函數(shù)為：PrintPolyn(pc);break;)case"D:cased':(pc=Derivative(pb);printfCn多項(xiàng)式b的導(dǎo)函數(shù)為：PrintPolyn(pc);break;)case1E':case，:(printf(*輸入x的值:x=");scanf&x);printf('zna=%<3fnn,x,ValuePolyn(pa,x);break;)case*F