一元稀疏多項(xiàng)式計(jì)算器實(shí)驗(yàn)(報(bào)告+程序)

1、一元稀疏多項(xiàng)式計(jì)數(shù)器預(yù)習(xí)報(bào)告姓名：劉茂 學(xué)號(hào)222012315220062一、實(shí)驗(yàn)要求(1)輸入并建立多項(xiàng)式；(2)輸出多項(xiàng)式，輸出形式為整數(shù)序列：n，c1，e1，c2，e2cn，en，其中n是多項(xiàng)式的項(xiàng)數(shù)，ci，ei分別為第i項(xiàng)的系數(shù)和指數(shù)。序列按指數(shù)降序排列；(3)多項(xiàng)式a和b相加，建立多項(xiàng)式a+b；(4)多項(xiàng)式a和b相減，建立多項(xiàng)式a-b。（5）多項(xiàng)式求值；（6）多項(xiàng)式求導(dǎo)；（7）求多項(xiàng)式的乘積。二、測(cè)試數(shù)據(jù)：1、(2x+5x8-3.1x11)+(7-5x8+11x9)=(-3.1x11+11x9+2x+7);2、(6x-3-x+4.4x2-1.2x9+1.2x9)-(-6x-3+5.4

2、x2-x2+7.8x15)=(-7.8x15-1.2x9+12x-3-x);3、(1+x+x2+x3+x4+x5)+(-x3-x4)=(1+x+x2+x5);4、(x+x3)+(-x-x3)=0;5、(x+x100)+(x100+x200)=(x+2x100+x200);6、(x+x2+x3)+0=x+x2+x3.7、互換上述測(cè)試數(shù)據(jù)中的前后兩個(gè)多項(xiàng)式。三、思路分析用帶表頭結(jié)點(diǎn)的單鏈表存儲(chǔ)多項(xiàng)式。本程序要求輸入并建立多項(xiàng)式，能夠降冪顯示出多項(xiàng)式，實(shí)現(xiàn)多項(xiàng)式相加相減的計(jì)算問(wèn)題，輸出結(jié)果。采用鏈表的方式存儲(chǔ)鏈表，定義結(jié)點(diǎn)結(jié)構(gòu)體。運(yùn)用尾差法建立兩條單鏈表，以單鏈表polyn p和polyn h分別表

3、示兩個(gè)一元多項(xiàng)式a和b。為實(shí)現(xiàn)處理，設(shè)p、q分別指向單鏈表polya和polyb的當(dāng)前項(xiàng)，比較p、q結(jié)點(diǎn)的指數(shù)項(xiàng)。 若p-expnexpn，則結(jié)點(diǎn)p所指的結(jié)點(diǎn)應(yīng)是“和多項(xiàng)式”中的一項(xiàng)，令指針p后移。推薦精選 若p-expn=q-expn，則將兩個(gè)結(jié)點(diǎn)中的系數(shù)相加，當(dāng)和不為0時(shí)修改結(jié)點(diǎn)p的系數(shù)。 若p-expnq-expn，則結(jié)點(diǎn)q所指的結(jié)點(diǎn)應(yīng)是“和多項(xiàng)式”中的一項(xiàng)，將結(jié)點(diǎn)q插入在結(jié)點(diǎn)p之前，且令指針q在原來(lái)的鏈表上后移。四、實(shí)驗(yàn)程序/頭文件#include#include#include/定義多項(xiàng)式的項(xiàng)typedef struct Polynomial float coef; int expn

4、; struct Polynomial *next;*Polyn,Polynomial;void Insert(Polyn p,Polyn h) if(p-coef=0) free(p);/系數(shù)為0的話(huà)釋放結(jié)點(diǎn) else Polyn q1,q2; q1=h;q2=h-next; while(q2&p-expnexpn)/查找插入位置 q1=q2; q2=q2-next; if(q2&p-expn=q2-expn)/將指數(shù)相同相合并 q2-coef+=p-coef; free(p); if(!q2-coef)/系數(shù)為0的話(huà)釋放結(jié)點(diǎn) q1-next=q2-next; free(q2);推薦精選 e

5、lse/指數(shù)為新時(shí)將結(jié)點(diǎn)插入 p-next=q2; q1-next=p;Polyn CreatePolyn(Polyn head,int m)/建立一個(gè)頭指針為head、項(xiàng)數(shù)為m的一元多項(xiàng)式 int i; Polyn p; p=head=(Polyn)malloc(sizeof(struct Polynomial); head-next=NULL; for(i=0;icoef,&p-expn); Insert(p,head); /調(diào)用Insert函數(shù)插入結(jié)點(diǎn) return head;void DestroyPolyn(Polyn p)/銷(xiāo)毀多項(xiàng)式p Polyn q1,q2; q1=p-next

6、; q2=q1-next; while(q1-next) free(q1); q1=q2; q2=q2-next;void PrintPolyn(Polyn P)Polyn q=P-next; int flag=1;/項(xiàng)數(shù)計(jì)數(shù)器 if(!q) /若多項(xiàng)式為空，輸出0 putchar(0); printf(n);推薦精選 return; while(q) if(q-coef0&flag!=1) putchar(+); /系數(shù)大于0且不是第一項(xiàng) if(q-coef!=1&q-coef!=-1)/系數(shù)非1或-1的普通情況 printf(%g,q-coef); if(q-expn=1) putchar

7、(X); else if(q-expn) printf(X%d,q-expn); else if(q-coef=1) if(!q-expn) putchar(1); else if(q-expn=1) putchar(X); else printf(X%d,q-expn); if(q-coef=-1) if(!q-expn) printf(-1); else if(q-expn=1) printf(-X); else printf(-X%d,q-expn); q=q-next; flag+; printf(n);int compare(Polyn a,Polyn b) if(a&b) if(!

8、b|a-expnb-expn) return 1; else if(!a|a-expnexpn) return -1; else return 0; else if(!a&b) return -1;/a多項(xiàng)式已空，但b多項(xiàng)式非空 else return 1;/b多項(xiàng)式已空，但a多項(xiàng)式非空Polyn AddPolyn(Polyn pa,Polyn pb)/求解并建立多項(xiàng)式a+b，返回其頭指針推薦精選 Polyn qa=pa-next; Polyn qb=pb-next; Polyn headc,hc,qc; hc=(Polyn)malloc(sizeof(struct Polynomial);/

9、建立頭結(jié)點(diǎn) hc-next=NULL; headc=hc; while(qa|qb) qc=(Polyn)malloc(sizeof(struct Polynomial); switch(compare(qa,qb) case 1: qc-coef=qa-coef; qc-expn=qa-expn; qa=qa-next; break; case 0: qc-coef=qa-coef+qb-coef; qc-expn=qa-expn; qa=qa-next; qb=qb-next; break; case -1: qc-coef=qb-coef; qc-expn=qb-expn; qb=qb-

10、next; break; if(qc-coef!=0) qc-next=hc-next; hc-next=qc; hc=qc; else free(qc);/當(dāng)相加系數(shù)為0時(shí)，釋放該結(jié)點(diǎn) return headc;推薦精選Polyn SubtractPolyn(Polyn pa,Polyn pb)/求解并建立多項(xiàng)式a-b，返回其頭指針 Polyn h=pb; Polyn p=pb-next; Polyn pd; while(p) /將pb的系數(shù)取反 p-coef*=-1; p=p-next; pd=AddPolyn(pa,h); for(p=h-next;p;p=p-next) /恢復(fù)pb的系

11、數(shù) p-coef*=-1; return pd;int ValuePolyn(Polyn head,int x)/輸入x值，計(jì)算并返回多項(xiàng)式的值 Polyn p; int i; int sum=0,t; for(p=head-next;p;p=p-next) t=1; for(i=p-expn;i!=0;) if(icoef*t; return sum;Polyn Derivative(Polyn head)/求解并建立導(dǎo)函數(shù)多項(xiàng)式，并返回其頭指針 Polyn q=head-next,p1,p2,hd; hd=p1=(Polyn)malloc(sizeof(struct Polynomial)

12、;/建立頭結(jié)點(diǎn) hd-next=NULL; while(q) if(q-expn!=0) /該項(xiàng)不是常數(shù)項(xiàng)時(shí) p2=(Polyn)malloc(sizeof(struct Polynomial); p2-coef=q-coef*q-expn;推薦精選 p2-expn=q-expn-1; p2-next=p1-next;/連接結(jié)點(diǎn) p1-next=p2; p1=p2; q=q-next; return hd;Polyn MultiplyPolyn(Polyn pa,Polyn pb)/求解并建立多項(xiàng)式a*b，返回其頭指針 Polyn hf,pf; Polyn qa=pa-next; Polyn

13、qb=pb-next; hf=(Polyn)malloc(sizeof(struct Polynomial);/建立頭結(jié)點(diǎn) hf-next=NULL; for(;qa;qa=qa-next) for(qb=pb-next;qb;qb=qb-next) pf=(Polyn)malloc(sizeof(struct Polynomial); pf-coef=qa-coef*qb-coef; pf-expn=qa-expn+qb-expn; Insert(pf,hf);/調(diào)用Insert函數(shù)以合并指數(shù)相同的項(xiàng) return hf;void main() int m,n,a,x;char flag;

14、Polyn pa=0,pb=0,pc;printf( 歡迎使用多項(xiàng)式操作程序nn); printf(請(qǐng)輸入a的項(xiàng)數(shù):); scanf(%d,&m); pa=CreatePolyn(pa,m);/建立多項(xiàng)式a printf(請(qǐng)輸入b的項(xiàng)數(shù):); scanf(%d,&n); pb=CreatePolyn(pb,n);/建立多項(xiàng)式b推薦精選 /輸出菜單 printf( *n); printf( * 多項(xiàng)式操作程序 *n);printf( * *n);printf( * A:輸出多項(xiàng)式 B:輸出多項(xiàng)式b *n);printf( * *n);printf( * C:輸出a的導(dǎo)數(shù) D:輸出b的導(dǎo)數(shù) *n)

15、;printf( * *n);printf( * E:代入x的值計(jì)算a F:代入x的值計(jì)算b *n);printf( * *n);printf( * G:輸出a+b H:輸出a-b *n);printf( * *n); printf( * I:輸出a*b J:退出程序 *n);printf( * *n); printf( *n);while(a) printf(n請(qǐng)選擇操作：); scanf( %c,&flag);/空格符號(hào)一定要注意switch(flag) caseA: casea: printf(n 多項(xiàng)式a=); PrintPolyn(pa); break; caseB:caseb: p

16、rintf(n 多項(xiàng)式b=); PrintPolyn(pb); break; caseC: casec: pc=Derivative(pa); printf(n 多項(xiàng)式a的導(dǎo)函數(shù)為：a=); PrintPolyn(pc); break;推薦精選 caseD:cased: pc=Derivative(pb); printf(n 多項(xiàng)式b的導(dǎo)函數(shù)為：b=); PrintPolyn(pc); break; caseE:casee: printf(輸入x的值：x=); scanf(%d,&x); printf(n x=%d時(shí)，a=%dn,x,ValuePolyn(pa,x); break; caseF:casef: printf(輸入x的值：x=); scanf(%d,&x); printf(n x=%d時(shí)，b=%dn,x,ValuePolyn(pb,x); break; caseG:caseg: pc=AddPolyn(pa,pb); printf(n a+b=); PrintPolyn(pc); break; caseH:caseh: pc=SubtractPolyn(pa,pb);