一元稀疏多項式計算器實驗(報告+程序)

1、一元稀疏多項式計數(shù)器預(yù)習(xí)報告姓名：劉茂 學(xué)號222012315220062一、實驗要求(1)輸入并建立多項式；(2)輸出多項式，輸出形式為整數(shù)序列：n，c1，e1，c2，e2cn，en，其中n是多項式的項數(shù)，ci，ei分別為第i項的系數(shù)和指數(shù)。序列按指數(shù)降序排列；(3)多項式a和b相加，建立多項式a+b；(4)多項式a和b相減，建立多項式a-b。（5）多項式求值；（6）多項式求導(dǎo)；（7）求多項式的乘積。二、測試數(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、互換上述測試數(shù)據(jù)中的前后兩個多項式。三、思路分析用帶表頭結(jié)點的單鏈表存儲多項式。本程序要求輸入并建立多項式，能夠降冪顯示出多項式，實現(xiàn)多項式相加相減的計算問題，輸出結(jié)果。采用鏈表的方式存儲鏈表，定義結(jié)點結(jié)構(gòu)體。運用尾差法建立兩條單鏈表，以單鏈表polyn p和polyn h分別表

3、示兩個一元多項式a和b。為實現(xiàn)處理，設(shè)p、q分別指向單鏈表polya和polyb的當(dāng)前項，比較p、q結(jié)點的指數(shù)項。 若p-expnexpn，則結(jié)點p所指的結(jié)點應(yīng)是“和多項式”中的一項，令指針p后移。推薦精選 若p-expn=q-expn，則將兩個結(jié)點中的系數(shù)相加，當(dāng)和不為0時修改結(jié)點p的系數(shù)。 若p-expnq-expn，則結(jié)點q所指的結(jié)點應(yīng)是“和多項式”中的一項，將結(jié)點q插入在結(jié)點p之前，且令指針q在原來的鏈表上后移。四、實驗程序/頭文件#include#include#include/定義多項式的項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的話釋放結(jié)點 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的話釋放結(jié)點 q1-next=q2-next; free(q2);推薦精選 e

5、lse/指數(shù)為新時將結(jié)點插入 p-next=q2; q1-next=p;Polyn CreatePolyn(Polyn head,int m)/建立一個頭指針為head、項數(shù)為m的一元多項式 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é)點 return head;void DestroyPolyn(Polyn p)/銷毀多項式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;/項數(shù)計數(shù)器 if(!q) /若多項式為空，輸出0 putchar(0); printf(n);推薦精選 return; while(q) if(q-coef0&flag!=1) putchar(+); /系數(shù)大于0且不是第一項 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多項式已空，但b多項式非空 else return 1;/b多項式已空，但a多項式非空Polyn AddPolyn(Polyn pa,Polyn pb)/求解并建立多項式a+b，返回其頭指針推薦精選 Polyn qa=pa-next; Polyn qb=pb-next; Polyn headc,hc,qc; hc=(Polyn)malloc(sizeof(struct Polynomial);/

9、建立頭結(jié)點 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時，釋放該結(jié)點 return headc;推薦精選Polyn SubtractPolyn(Polyn pa,Polyn pb)/求解并建立多項式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值，計算并返回多項式的值 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ù)多項式，并返回其頭指針 Polyn q=head-next,p1,p2,hd; hd=p1=(Polyn)malloc(sizeof(struct Polynomial)

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

13、qb=pb-next; hf=(Polyn)malloc(sizeof(struct Polynomial);/建立頭結(jié)點 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ù)相同的項 return hf;void main() int m,n,a,x;char flag;

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

15、;printf( * *n);printf( * E:代入x的值計算a F:代入x的值計算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請選擇操作：); scanf( %c,&flag);/空格符號一定要注意switch(flag) caseA: casea: printf(n 多項式a=); PrintPolyn(pa); break; caseB:caseb: p

16、rintf(n 多項式b=); PrintPolyn(pb); break; caseC: casec: pc=Derivative(pa); printf(n 多項式a的導(dǎo)函數(shù)為：a=); PrintPolyn(pc); break;推薦精選 caseD:cased: pc=Derivative(pb); printf(n 多項式b的導(dǎo)函數(shù)為：b=); PrintPolyn(pc); break; caseE:casee: printf(輸入x的值：x=); scanf(%d,&x); printf(n x=%d時，a=%dn,x,ValuePolyn(pa,x); break; caseF:casef: printf(輸入x的值：x=); scanf(%d,&x); printf(n x=%d時，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);