鏈表線性結(jié)構(gòu)(多項式的加減乘除)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院實驗報告課程名稱：數(shù)據(jù)結(jié)構(gòu)與算法課程類型：必修實驗項目：線性結(jié)構(gòu)及其應(yīng)用實驗題目：多項式的加減乘除和特定值帶入實驗日期：2017/11/5班級：學(xué)號：姓名：安宏宇設(shè)計成績報告成績指導(dǎo)老師張巖一、實驗?zāi)康脑O(shè)計線性表的鏈式存儲結(jié)構(gòu)，并實現(xiàn)一元多項式的代數(shù)運算。二、實驗要求及實驗環(huán)境（1）實驗要求：以鏈表存儲一元多項式，在此基礎(chǔ)上完成對多項式的代數(shù)操作。 1.能夠輸入多項式（可以按各項的任意輸入順序，建立按指數(shù)降冪排列的多項式）和輸出多項式（按指數(shù)降冪排列）,以文件形式輸入和輸出，并顯示。 2.能夠計算多項式在某一點 x=x0 的值，其中

2、x0 是一個浮點型常量，返回結(jié)果為浮點數(shù)。 3.能夠給出計算兩個多項式加法、減法、乘法和除法運算的結(jié)果多項式，除法運算的結(jié)果包括商多項式和余數(shù)多項式。 4.要求盡量減少乘法和除法運算中間結(jié)果的空間占用和結(jié)點頻繁的分配與回收操作。（提示：利用循環(huán)鏈表結(jié)構(gòu)和可用空間表的思想，把循環(huán)鏈表表示的多項式返還給可用空間表，從而解決上述問題）。（2）實驗環(huán)境：windows下的CB;三、設(shè)計思想（本程序中的用到的所有數(shù)據(jù)類型的定義，主程序的流程圖及各程序模塊之間的調(diào)用關(guān)系）1邏輯設(shè)計:struct polynode int coef; int exp; struct polynode * link;/建立鏈

3、表typedef struct polynode poly;poly* Attch(int c,int e,poly *d);/多項式插入poly *newPoly();/新鏈表poly *padd(poly *p1,poly *p2);/多項式加法poly *pmul(poly *p1,poly *p2);/乘法poly *inputPoly();/輸入多項式poly *psub(poly *p1,poly *p2);/減poly *pdiv(poly *p1,poly *p2);/除poly *inputPoly1();double caculate(double x,poly *p);/

4、計算多項式void sortPoly(poly *p);/多項式排序void outputPoly(poly*p);/輸出多項式void delPoly(poly*p);/清空多項式 2物理設(shè)計：四、測試結(jié)果五、經(jīng)驗體會與不足不能連續(xù)輸入多個多項式函數(shù)設(shè)計不夠簡潔算法過于直接簡單加注釋后修改代碼方便六、附錄：源代碼（帶注釋）#include <stdio.h>#include <stdlib.h>struct polynode int coef; int exp; struct polynode * link;/建立新鏈表typedef struct polynode

5、poly;poly* Attch(int c,int e,poly *d);/插入鏈表poly *newPoly();/建立新鏈表poly *padd(poly *p1,poly *p2);/加法poly *pmul(poly *p1,poly *p2);/乘法poly *inputPoly();/輸入多項式poly *psub(poly *p1,poly *p2);/減法poly *pdiv(poly *p1,poly *p2);/除法poly *inputPoly1();/輸入double caculate(double x,poly *p);/計算void sortPoly(poly *

6、p);/排序void outputPoly(poly*p);/輸出多項式void delPoly(poly*p);/除法void Insert(poly *p,poly *h) if(p->coef=0) free(p); else poly *q1,*q2; q1=h;q2=h->link; while(q2&&p->exp<q2->exp) q1=q2; q2=q2->link; /*判斷兩個指數(shù)是否相等*/ if(q2&&p->exp=q2->exp) q2->coef+=p->coef; fre

7、e(p); if(!q2->coef) q1->link=q2->link; free(q2); /*相等就加系數(shù)*/ else p->link=q2; q1->link=p; /*不等就插在后面*/int main() poly *p1,*p2,*padd1,*psub1,*pmul1; p1=newPoly(); printf("第一個多項式n"); p1->link=inputPoly(); outputPoly(p1); p2=newPoly(); printf("第二個多項式n"); p2->link=

8、inputPoly1(); outputPoly(p2); padd1=newPoly(); pmul1=newPoly(); psub1=newPoly(); padd1->link=padd(p1,p2); printf("paddn"); outputPoly(padd1); psub1->link=psub(p1,p2); printf("psubn"); outputPoly(psub1); pmul1->link=pmul(p1,p2); printf("pmuln"); outputPoly(pmul1

9、); printf("輸入x的值！"); int x; scanf("%d",&x); x=caculate(x,p1); printf("%dn",x); pdiv(p1,p2); return 0;poly *newPoly() poly *x; x=(poly*)malloc(sizeof(poly); x->link=NULL; x->coef=0; x->exp=0; return x;poly* Attch(int c,int e,poly *d) poly *x; x=newPoly(); x-

10、>coef=c; x->exp=e; d->link=x; return x;poly *padd(poly *p1,poly *p2) poly *a, *b,*c,*d,*p; c=newPoly(); d=c; p=c; a=p1->link; b=p2->link; while(a!=NULL&&b!=NULL) if(a->exp>b->exp)/如果a的系數(shù)大于b把a先輸入 c=Attch(a->coef,a->exp,c); a=a->link; else if(a->exp<b->

11、;exp)/小于相反 c=Attch(b->coef,b->exp,c); b=b->link; else/相等 c=Attch(b->coef+a->coef,a->exp,c); a=a->link; b=b->link; /*a b比較完成開始遍歷剩下的未插入的*/ while(a!=NULL) c=Attch(a->coef,a->exp,c); a=a->link; while(b!=NULL) c=Attch(b->coef,b->exp,c); b=b->link; c->link=NULL

12、; d=d->link; p->link=NULL; delPoly(p); return d;poly *psub(poly*p1,poly*p2)/加和減思路相同，b的系數(shù)得輸入相反值 poly *a, *b,*c,*d,*p; c=newPoly(); d=c; p=c; a=p1->link; b=p2->link; while(a!=NULL&&b!=NULL) if(a->exp>b->exp) c=Attch(a->coef,a->exp,c); a=a->link; else if(a->exp&

13、lt;b->exp) c=Attch(b->coef*(-1),b->exp,c); b=b->link; else if(a->coef-b->coef)>0) c=Attch(a->coef-b->coef,a->exp,c); a=a->link; b=b->link; else a=a->link; b=b->link; while(a!=NULL) c=Attch(a->coef,a->exp,c); a=a->link; while(b!=NULL) c=Attch(b->c

14、oef*(-1),b->exp,c); b=b->link; c->link=NULL; d=d->link; p->link=NULL; delPoly(p); return d;/*乘法，先用第一個鏈表的第一個數(shù)據(jù)乘以第二個鏈表里的所有值，儲存在新的鏈表中，之后遍歷一中所有的值，最后把這些多項式加在一起。*/poly *pmul(poly*p1,poly*p2)/乘法 poly*a,*b,*c,*d,*q,*sum; int aex,aco; a=p1->link; b=p2->link; sum=newPoly(); q=sum; while(a

15、!=NULL) c=newPoly(); d=c; aco=a->coef; aex=a->exp; while(b!=NULL) c=Attch(aco*(b->coef),aex+(b->exp),c); b=b->link; b=p2->link; sum->link=padd(d,sum); a=a->link; delPoly(d); sum=sum->link; q->link=NULL; delPoly(q); sortPoly(sum); return sum;/*除法：先用鏈表一第一個的系數(shù)除以第二個鏈表的第一個系數(shù)

16、，得到的值乘以被除多項式，再用第一個多項式減。最后得到一個最大系數(shù)比被除數(shù)小的多項式。*/ poly *pdiv(poly*p1,poly*p2) poly *hf,*pf,*temp1,*temp2; poly *q1; q1=p1->link; poly *q2; q2=p2->link; hf=newPoly(); hf->link=NULL; pf=newPoly(); pf->link=NULL; temp1=newPoly(); temp1->link=NULL; temp2=newPoly(); temp2->link=NULL; temp1=

17、padd(temp1,p1); while(q1->exp>=q2->exp) temp2->link=newPoly(); temp2->link->coef=(q1->coef)/(q2->coef); temp2->link->exp=(q1->exp)-(q2->exp); Insert(temp2->link,hf); p1=psub(p1,pmul(p2,temp2); q1=p1->link; temp2->link=NULL; pf=psub(temp1,pmul(hf,p2); p2=t

18、emp1; printf("商是"); outputPoly(hf); printf("余數(shù)是"); outputPoly(pf);/*輸入：多項式的系數(shù)和指數(shù)存在p1文件中，兩個兩個讀，分別賦給多項式的系數(shù)和指數(shù)。*/poly *inputPoly() poly *q,*p; p=newPoly(); q=p; FILE *fp; if(fp=fopen("c:p1.txt","rt")=NULL) printf("nCannot open file strike any key exit!"

19、); getch(); exit(1); int a,b; while(fscanf(fp,"%d %d",&a,&b)!=-1) p->link=newPoly(); p=p->link; p->coef=a; p->exp=b; p=q; sortPoly(q); q=q->link; p->link=NULL; delPoly(p); fclose(fp); return q;poly *inputPoly1() poly *q,*p; p=newPoly(); q=p; FILE *fp; if(fp=fopen(

20、"c:p2.txt","rt")=NULL) printf("nCannot open file strike any key exit!"); getch(); exit(1); int a,b; while(fscanf(fp,"%d %d",&a,&b)!=-1) p->link=newPoly(); p=p->link; p->coef=a; p->exp=b; p=q; sortPoly(q); q=q->link; p->link=NULL; delPoly(p); fclose(fp); return q;/*輸出：讀取系數(shù)和指數(shù)，按a*xb的形式輸出*/void outputPoly(poly*p) poly*q; q=p->link; if(q!=NULL) printf("%dx%d ",q->coef,q->exp); q=q->link; else printf("0"); while(q!=NULL) if(