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

1、-. z.一元稀疏多項式計數(shù)器預習報告：*茂 *0062一、實驗要求(1)輸入并建立多項式；(2)輸出多項式，輸出形式為整數(shù)序列：n，c1，e1，c2，e2，en，其中n是多項式的項數(shù)，ci，ei分別為第i項的系數(shù)和指數(shù)。序列按指數(shù)降序排列；(3)多項式a和b相加，建立多項式a+b；(4)多項式a和b相減，建立多項式a-b。5多項式求值；6多項式求導；7求多項式的乘積。二、測試數(shù)據(jù)：1、(2*+5*8-3.1*11)+(7-5*8+11*9)=(-3.1*11+11*9+2*+7);2、(6*-3-*+4.4*2-1.2*9+1.2*9)-(-6*-3+5.4*2-*2+7.8*15)=(-7

2、.8*15-1.2*9+12*-3-*);3、(1+*+*2+*3+*4+*5)+(-*3-*4)=(1+*+*2+*5);4、(*+*3)+(-*-*3)=0;5、(*+*100)+(*100+*200)=(*+2*100+*200);6、(*+*2+*3)+0=*+*2+*3.7、互換上述測試數(shù)據(jù)中的前后兩個多項式。三、思路分析用帶表頭結(jié)點的單鏈表存儲多項式。本程序要求輸入并建立多項式，能夠降冪顯示出多項式，實現(xiàn)多項式相加相減的計算問題，輸出結(jié)果。采用鏈表的方式存儲鏈表，定義結(jié)點構(gòu)造體。運用尾差法建立兩條單鏈表，以單鏈表polyn p和polyn h分別表示兩個一元多項式a和b。為實現(xiàn)處理

3、，設p、q分別指向單鏈表polya和polyb的當前項，比擬p、q結(jié)點的指數(shù)項。 假設p-e*pne*pn，則結(jié)點p所指的結(jié)點應是“和多項式中的一項，令指針p后移。 假設p-e*pn=q-e*pn，則將兩個結(jié)點中的系數(shù)相加，當和不為0時修改結(jié)點p的系數(shù)。 假設p-e*pnq-e*pn，則結(jié)點q所指的結(jié)點應是“和多項式中的一項，將結(jié)點q插入在結(jié)點p之前，且令指針q在原來的鏈表上后移。四、實驗程序/頭文件#include#include#include/定義多項式的項typedef struct Polynomial float coef; int e*pn; struct Polynomial

4、*ne*t;*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-ne*t; while(q2&p-e*pne*pn)/查找插入位置 q1=q2; q2=q2-ne*t; if(q2&p-e*pn=q2-e*pn)/將指數(shù)一樣相合并 q2-coef+=p-coef; free(p); if(!q2-coef)/系數(shù)為0的話釋放結(jié)點 q1-ne*t=q2-ne*t; free(q2); else/指數(shù)為新時將結(jié)點插入 p-ne*t=q2

5、; q1-ne*t=p;Polyn CreatePolyn(Polyn head,int m)/建立一個頭指針為head、項數(shù)為m的一元多項式 int i; Polyn p; p=head=(Polyn)malloc(sizeof(struct Polynomial); head-ne*t=NULL; for(i=0;icoef,&p-e*pn); Insert(p,head); /調(diào)用Insert函數(shù)插入結(jié)點 return head;void DestroyPolyn(Polyn p)/銷毀多項式p Polyn q1,q2; q1=p-ne*t; q2=q1-ne*t; while(q1-n

6、e*t) free(q1); q1=q2; q2=q2-ne*t;void PrintPolyn(Polyn P)Polyn q=P-ne*t; 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-e*pn=1) putchar(*); else if(q-e*pn) printf

7、(*%d,q-e*pn); else if(q-coef=1) if(!q-e*pn) putchar(1); else if(q-e*pn=1) putchar(*); else printf(*%d,q-e*pn); if(q-coef=-1) if(!q-e*pn) printf(-1); else if(q-e*pn=1) printf(-*); else printf(-*%d,q-e*pn); q=q-ne*t; flag+; printf(n);int pare(Polyn a,Polyn b) if(a&b) if(!b|a-e*pnb-e*pn) return 1; else

8、 if(!a|a-e*pne*pn) 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-ne*t; Polyn qb=pb-ne*t; Polyn headc,hc,qc; hc=(Polyn)malloc(sizeof(struct Polynomial);/建立頭結(jié)點 hc-ne*t=NULL; headc=hc; whil

9、e(qa|qb) qc=(Polyn)malloc(sizeof(struct Polynomial); switch(pare(qa,qb) case 1: qc-coef=qa-coef; qc-e*pn=qa-e*pn; qa=qa-ne*t; break; case 0: qc-coef=qa-coef+qb-coef; qc-e*pn=qa-e*pn; qa=qa-ne*t; qb=qb-ne*t; break; case -1: qc-coef=qb-coef; qc-e*pn=qb-e*pn; qb=qb-ne*t; break; if(qc-coef!=0) qc-ne*t=h

10、c-ne*t; hc-ne*t=qc; hc=qc; else free(qc);/當相加系數(shù)為0時，釋放該結(jié)點 return headc;Polyn SubtractPolyn(Polyn pa,Polyn pb)/求解并建立多項式a-b，返回其頭指針 Polyn h=pb; Polyn p=pb-ne*t; Polyn pd; while(p) /將pb的系數(shù)取反 p-coef*=-1; p=p-ne*t; pd=AddPolyn(pa,h); for(p=h-ne*t;p;p=p-ne*t) /恢復pb的系數(shù) p-coef*=-1; return pd;int ValuePolyn(Po

11、lyn head,int *)/輸入*值，計算并返回多項式的值 Polyn p; int i; int sum=0,t; for(p=head-ne*t;p;p=p-ne*t) t=1; for(i=p-e*pn;i!=0;) if(icoef*t; return sum;Polyn Derivative(Polyn head)/求解并建立導函數(shù)多項式，并返回其頭指針 Polyn q=head-ne*t,p1,p2,hd; hd=p1=(Polyn)malloc(sizeof(struct Polynomial);/建立頭結(jié)點 hd-ne*t=NULL; while(q) if(q-e*pn!

12、=0) /該項不是常數(shù)項時 p2=(Polyn)malloc(sizeof(struct Polynomial); p2-coef=q-coef*q-e*pn; p2-e*pn=q-e*pn-1; p2-ne*t=p1-ne*t;/連接結(jié)點 p1-ne*t=p2; p1=p2; q=q-ne*t; return hd;Polyn MultiplyPolyn(Polyn pa,Polyn pb)/求解并建立多項式a*b，返回其頭指針 Polyn hf,pf; Polyn qa=pa-ne*t; Polyn qb=pb-ne*t; hf=(Polyn)malloc(sizeof(struct Po

13、lynomial);/建立頭結(jié)點 hf-ne*t=NULL; for(;qa;qa=qa-ne*t) for(qb=pb-ne*t;qb;qb=qb-ne*t) pf=(Polyn)malloc(sizeof(struct Polynomial); pf-coef=qa-coef*qb-coef; pf-e*pn=qa-e*pn+qb-e*pn; Insert(pf,hf);/調(diào)用Insert函數(shù)以合并指數(shù)一樣的項 return hf;void main() int m,n,a,*;char flag; Polyn pa=0,pb=0,pc;printf( 歡送使用多項式操作程序nn); pr

14、intf(請輸入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的導數(shù) D:輸出b的導數(shù) *n);printf( * *n);printf( * E:代入*的值計算a F:代入*的值計算b *n

15、);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: printf(n 多項式b=); PrintPolyn(pb); break; caseC: cas

16、ec: pc=Derivative(pa); printf(n 多項式a的導函數(shù)為：a=); PrintPolyn(pc); break; caseD:cased: pc=Derivative(pb); printf(n 多項式b的導函數(shù)為：b=); PrintPolyn(pc); break; caseE:casee: printf(輸入*的值：*=); scanf(%d,&*); printf(n *=%d時，a=%dn,*,ValuePolyn(pa,*); break; caseF:casef: printf(輸入*的值：*=); scanf(%d,&*); printf(n *=%d時，b=%dn,*,ValuePolyn(pb,*); break; caseG:caseg: pc=AddPolyn(pa,pb); printf(n a+b=); PrintPolyn(pc); break; caseH:c