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

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

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

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

4、,則將兩個結(jié)點中的系數(shù)相加，半和不為。時修改結(jié)點P的系數(shù)。若p->expn>q->expm則結(jié)點q所指的結(jié)點應是“和多項式中的-項，將結(jié)點q插入在結(jié)點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.四、概要設計1、元素類型、結(jié)點類型和指針類型：typedefstructPolynomial(floatcoef;系數(shù)intexpn;指數(shù)structPolynomial*next;*Polyn,Polynomial;2、建立一個頭指針為head.項數(shù)為m的一兀多項式，建立新結(jié)點以接收數(shù)據(jù)，調(diào)用Insert函數(shù)插入結(jié)點：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項的系數(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值，計算并返回多項式的值五、調(diào)用關(guān)系圖(圖1)六、程序代碼：#include<stdio.h>#include<stdlib.h>typedefstructPolynomialfloatcoef;intexpn;定義多項式的項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é)點ql->next=q2->next;free(q2);else指數(shù)為新時將結(jié)點插入p->next=q2;ql->next=p;PolynCreatePoIvn(Polynhead,intm)為heud>項數(shù)為m的一元多項式inti;Polynp;pAhe

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

10、t;Q2=ql->nexi;while(ql->next)銷毀多項式Pfree(ql);ql=q2；q2=q2->nexl;)voidPrinlPolyn(PolynP)Polynq=P")next;intflag=l;if(!q)項數(shù)計數(shù)器若多項式為空,putcharO);printf(',nu);return;while(q)輸出0if(q->coef>0&&flag!=l)putcharf+，)；系數(shù)大于0且不是第一項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多項式已空，但b多項式非空elsereturn1;/b多項式己空，但a多項式非空PolynAddPolyn(Polynpa,Polynpb)缸+b,返回其

13、頭指針求解并建立多項式Polynqa=pa->next;Polynqb=pb->next;Polynheadc,he,qc;hc=(Polyn)malloc(sizeof(structPolynomial);建立頭結(jié)點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)/當相力II系數(shù)為0時釋放該結(jié)點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)返回多項式的值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;求解并建立多項式a-b,將pb的系數(shù)取反恢復pb的系數(shù)輸入x值,計算并指數(shù)小于0,進行除法指數(shù)大于0,進行乘法returnsum;PolynDerivative(Polynhead)求解并建立導函數(shù)多項式,并返回其頭指針Polynq=head->next>pl,p2,hd;hd=p1=(Po1yn)ma11oc(sizeof(structPolynomial)；建立頭結(jié)點hdnext=NULL;while(q)(if(q->exp

17、n!=0)該項不是常數(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é)點q=q->next;)returnhd;)PolynMultiplyPolyn(Polynpa,Polvnpb)求解并建立多項式a*b,返回其頭指針Polynhf,pf:Polynqa=pa->next;Polynqb=pb->next;hf=(Polyn)m

18、alloc(sizeof(struetPolynomial);建立頭結(jié)點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ù)和同的項)returnhf;)voidmain()intm,n,a,x;charflag;Po

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

20、("*n)printf('z*printf(n*r)；printfC*n)；多項式操作程序*2;*rv);A:輸ill多項式aB:輸出多項式b*n)*C:輸出a的導數(shù)D:輸出b的導數(shù)*n”)；*E:代入x的值計算aF:代入x的傅計算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多項式滬);PrintPolyn(pa);break;

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