1、數(shù)據(jù)結構07082018用鏈表實現(xiàn)多項式的四則運算數(shù)據(jù)結構第二次上機作業(yè)班級07082姓名丁敏學號07082018上機時間2011年3月31日報告時間：2011年4月5日實驗目的：熟練使用指針，熟悉鏈表及其操作；利用鏈表解決實際問題要求：能夠實現(xiàn)任意項有理多項式的加、減、乘、除、求模以及事運算多項式的除法注意除不盡的處理測試用例盡可能多，且說明用例的必要性用例必須包含一個自己系數(shù)為自己的學號摘要：多項式的四則運算問題是個很有趣的問題，它類似于有理數(shù)的四則運算，但又不僅僅于此.本篇課程論文重點研究了數(shù)據(jù)結構中多項式的四則運算問題。本論文的程序是通過MicrosoftVisualStudio201

2、0編譯，來解決多項式的加、減、乘、除四則運算問題，從而達到了解數(shù)據(jù)結構的實用性及程序語言對于數(shù)學問題研究的重要性的目的。07082018數(shù)據(jù)結構正文：0需求分析:0.1問題描述編寫程序來實現(xiàn)多項式的四則運算。0.2基本要求輸入多項式的系數(shù)與指數(shù)，輸入值為float型，輸出值為float型;能夠完成多項式之間的四種計算方式(+、-、*、/)。0.3函數(shù)說明typedefstructPolyNode:結構體變量，定義int型指數(shù)和float系數(shù)；PolyListCreatePolyList():創(chuàng)建多項式列表，返回頭指針；DisplayPolyList(PolyListPoly):顯示多項式；De

3、stroyPolyList(PolyListL):釋放鏈表所用存儲空間；MergePoly(PolyListPoly):將多項式合并同類項；SortPoly(PolyListPoly):將多項式按升序排列；PolyListPolyAdd(PolyListPolyA,PolyListPolyB):多項式相加，返回和多項式鏈表頭指針；PolyListPolySub(PolyListpolyA,PolyListpolyB):多項式相減，返回差多項式鏈表頭指針；PolyListPolyMutiply(PolyListPolyA,PolyListPolyB):多項式相乘，結果由Polyc返回；PolyL

4、istPolyDivide(PolyListPolyA,PolyListPolyB):多項式相除，商和余數(shù)用系數(shù)為0的結點分開。1程序執(zhí)行結果及分析：1.1執(zhí)行結果(1)* *多項式的創(chuàng)建*請輸入多項式的第1項的系數(shù)和指數(shù)(用逗號分開)：3,2請輸入多項式的第2項的系數(shù)和指數(shù)：2,0請輸入多項式的第3項的系數(shù)和指數(shù)：0,0輸入的多項式A：3.000000*xA2+2.000000*xA0請輸入多項式的第1項的系數(shù)和指數(shù)(用逗號分開)：2,2請輸入多項式的第2項的系數(shù)和指數(shù)：3,1請輸入多項式的第3項的系數(shù)和指數(shù)：0,0輸入的多項式B：2.000000*xA2+3.000000*xA1合并排序后

5、的多項式A:3.000000*xA2+2.000000*xA0合并排序后的多項式B:2.000000*xA2+3.000000*xA1* *多項式的四則運算*A+B:5.000000*xA2+3.000000*xA1+2.000000*xA0A-B:1.000000*xA2+-3.000000*xA1+2.000000*xA0A*B:6.000000*xA4+9.000000*xA3+4.000000*xA2+6.000000*xA1A/B:1.500000*xA0.-4.500000*xA1+2.000000*xA0請按任意鍵繼續(xù).* *多項式的創(chuàng)建*請輸入多項式的第1項的系數(shù)和指數(shù)（用逗號

6、分開）：1,1請輸入多項式的第2項的系數(shù)和指數(shù)：0,0輸入的多項式A:1.000000*xA1請輸入多項式的第1項的系數(shù)和指數(shù)（用逗號分開）：0,0輸入的多項式B:0合并排序后的多項式A:1.000000*xA1合并排序后的多項式B:0* *多項式的四則運算*A+B:1.000000*xA1A-B:1.000000*xA1A*B:0Error:除項為空！A/B:請按任意鍵繼續(xù).* *多項式的創(chuàng)建*請輸入多項式的第1項的系數(shù)和指數(shù)（用逗號分開）：2,3請輸入多項式的第2項的系數(shù)和指數(shù)：2/3,1（出現(xiàn)亂碼）1.2測試用例(1):，二二-二二C=A+B=30(x+y)C=AB=20(x+y)C=A

7、B=125(x2+2xy+y2)C=A-s-B=5x+Sy(2) A=xB=/C=A+B=x3+xzC=A-B=x3xzC=AB=xlcC=A-rB=x&(3) -.：二：=：-：，.C=A+B=x2+ya+2xy+x+yC=A-B=+ya+2xy-x-yC=AB=+3x2y+3xy2+y3C=A-rB=x+y(4)輸入：A=3x+%B=x+6y輸出：-C=A-B=2x-5yC=AB=3x2+19xy+6y21.3結果分析通過三次的運行，一二兩次成功，但第三次亂碼。從第三次的運行來看由于輸入與所要求的不一樣二出現(xiàn)亂碼，故非程序的問題，所以本程序符合多項式的運算要求，是正確的。2程序的評

8、價:程序符合需求，能夠有效地運行多項式之間的運算；程序結構合理，具有層次性，易讀；程序運行界面友好，且不與別的程序相沖突由于程序會出亂碼現(xiàn)象，所以還有一定的缺陷；3總結：本文的重點是對多項式的各種關系通過編程進行處理。筆者通過通過MicrosoftVisualStudio2010編譯完成了所要求的內容。值得指出的是：本程序層次性較強，易讀，且具有較高的精度，如進一步改善，將會有很強的適用性。筆者當然也碰到許多的問題，比如算法設計上仍有很大不足，流程圖畫的不是很熟練，全局變量不會定義，main函數(shù)的順序位置等。這些問題都可以通過實踐來解決，總之，一句話熟能生巧。附錄#include<std

9、io.h>#include<stdlib.h>#include<math.h>結點定義typedefstructPolyNodeintexp;指數(shù)floatcoef;系數(shù)PolyNode*next;PolyNode,*PolyList;PolyListCreatePolyList();/創(chuàng)建多項式鏈表，返回頭指針voidDisplayPolyList(PolyListPoly);/顯示多項式voidDestroyPolyList(PolyListL);/釋放鏈表所用存儲空間voidMergePoly(PolyListPoly);/將多項式和并同類項voidSort

10、Poly(PolyListPoly);/將多項式按升序排列PolyListPolyAdd(PolyListPolyA,PolyListPolyB);/多項式相加，返回和多項式鏈表頭指針PolyListPolySub(PolyListpolyA,PolyListpolyB);/多項式相減，返回差多項式鏈表頭指針PolyListPolyMutiply(PolyListPolyA,PolyListPolyB);/多項式相乘，結果由PolyC返回PolyListPolyDivide(PolyListPolyA,PolyListPolyB);/多項式相除，結果存到PolyC中，商和余數(shù)用系數(shù)為0的結點分

11、開PolyListCreatePolyList()PolyNode*s,*rear,*head;inte;/指數(shù)floatc;/系數(shù)intn=1;計數(shù)器head=(PolyNode*)malloc(sizeof(PolyNode);rear=head;輸入多項式的系數(shù)和指數(shù)，若輸入系數(shù)為0退出printf("請輸入多項式的第%d項的系數(shù)和指數(shù)(用逗號分開)："，n+);scanf("%f,%d",&c,&e);while(fabs(c)>1e-6)s=(PolyNode*)malloc(sizeof(PolyNode);s->

12、exp=e;s->coef=c;rear->next=s;rear=s;printf("請輸入多項式的第%d項的系數(shù)和指數(shù)：",n+);scanf("%f,%d",&c,&e);)rear->next=NULL;returnhead;)計算兩個多項式(可不按順序排列)，結果存到鏈表PolyC中，并返回PolyListPolyAdd(PolyListPolyA,PolyListPolyB)PolyListPolyC;SortPoly(PolyA);SortPoly(PolyB);floatsum=0;/存儲兩項系數(shù)和Pol

13、yNode*pa,*pb,*rear,*s;PolyC=(PolyNode*)malloc(sizeof(PolyNode);pa=PolyA->next;pb=PolyB->next;rear=PolyC;rear->next=NULL;while(pa&&pb)if(pa->exp=pb->exp)sum=pa->coef+pb->coef;if(fabs(sum)>1e-6)如果兩兩系數(shù)不為0,則將兩項和存入s中，并插入PolyC尾部s=(PolyNode*)malloc(sizeof(PolyNode);s->coe

14、f=sum;s->exp=pa->exp;rear->next=s;rear=s;)/pa,pb指針后移pa=pa->next;pb=pb->next;)elseif(pa->exp>pb->exp)右pa指數(shù)大于pb指數(shù)，將pa結點副本插入到PolyC尾部while(pa)s=(PolyNodes=(PolyNode*)malloc(sizeof(PolyNode);s->coef=pa->coef;s->exp=pa->exp;rear->next=s;rear=s;*)malloc(sizeof(PolyNod

15、e);s->coef=pa->coef;s->exp=pa->exp;rear->next=s;pa=pa->next;rear=s;pa=pa->next;else若pb指數(shù)大于pa指數(shù)將pb結點副本插入到PolyC尾部s=(PolyNode*)malloc(sizeof(PolyNode);s->coef=pb->coef;s->exp=pb->exp;rear->next=s;pb=pb->next;rear=s;while(pb)s=(PolyNode*)malloc(sizeof(PolyNode);s-&

16、gt;coef=pb->coef;s->exp=pb->exp;rear->next=s;pb=pb->next;rear=s;rear->next=NULL;returnPolyC;)voidDestroyPolyList(PolyListL)(PolyNode*p,*temp;p=L;while(p!=NULL)temp=p;p=p->next;free(temp);)將多項式和并同類項voidMergePoly(PolyListPoly)PolyNode*p,*q,*rear,*pre,*temp;rear=Poly;p=Poly->nex

17、t;while(rear->next!=NULL)q=p->next;pre=p;temp=p;while(q)if(p->exp=q->exp)p->coef+=q->coef;if(fabs(p->coef)>1e-6)pre->next=q->next;temp=q;q=temp->next;free(temp);else/兩項系數(shù)和為0,釋放結點p和qrear->next=p->next;temp=p;p=temp->next;free(temp);pre->next=q->next;tem

18、p=q;q=temp->next;free(temp);)elsepre=q;q=q->next;指數(shù)不等，指針q后移與p指數(shù)相同的節(jié)點合并完畢，或者沒有找到，p后移rear=p;p=rear->next;rear->next=NULL;將多項式按升序排列voidSortPoly(PolyListPoly)PolyListrear,p,temp,prior;if(!Poly->next)return;若多項式為空，返回rear=Poly;intexp;/記錄當前啊搜索項中的最小指while(rear->next!=NULL)exp=rear->next

19、->exp;p=rear->next;prior=rear;temp=prior->next;while(p!=NULL)if(p->exp>exp)exp=p->exp;temp=p;p=temp->next;elsep=p->next;MergePoly(Poly);if(rear->next->next=NULL)return;/p為最后一個元素且指數(shù)最小，提前返回)while(prior->next!=temp)prior=prior->next;prior->next=temp->next;temp-

20、>next=rear->next;rear->next=temp;rear=rear->next;)多項式相減，返回差多項式鏈表頭指針PolyListPolySub(PolyListPolyA,PolyListPolyB)PolyListPolyC;SortPoly(PolyA);SortPoly(PolyB);floatsum=0;/存儲兩項系數(shù)差PolyNode*pa,*pb,*rear,*s;PolyC=(PolyNode*)malloc(sizeof(PolyNode);pa=PolyA->next;pb=PolyB->next;rear=PolyC

21、;rear->next=NULL;while(pa&&pb)if(pa->exp=pb->exp)sum=pa->coef-pb->coef;if(fabs(sum)>1e-6)如果兩兩系數(shù)不為0,則將兩項和存入s中，并插入PolyC尾部s=(PolyNode*)malloc(sizeof(PolyNode);s->coef=sum;s->exp=pa->exp;rear->next=s;rear=s;)/pa,pb指針后移pa=pa->next;pb=pb->next;)elseif(pa->exp

22、>pb->exp)若pa指數(shù)大于pb指數(shù)，將pa結點副本插入到PolyC尾部(s=(PolyNode*)malloc(sizeof(PolyNode);s->coef=pa->coef;s->exp=pa->exp;rear->next=s;rear=s;pa=pa->next;)else若pb指數(shù)大于pa指數(shù),將pb結點副本插入到PolyC尾部(s=(PolyNode*)malloc(sizeof(PolyNode);s->coef=-pb->coef;s->exp=pb->exp;rear->next=s;pb=

23、pb->next;rear=s;)while(pa)(s=(PolyNode*)malloc(sizeof(PolyNode);s->coef=pa->coef;s->exp=pa->exp;rear->next=s;pa=pa->next;rear=s;)while(pb)(s=(PolyNode*)malloc(sizeof(PolyNode);s->coef=-pb->coef;s->exp=pb->exp;rear->next=s;pb=pb->next;rear=s;)rear->next=NULL;

24、returnPolyC;)輸出多項式voidDisplayPolyList(PolyListPoly)(if(Poly=NULL)printf("n");return;PolyNode*p=Poly->next;if(p=NULL)printf("0n");return;/如果鏈表為空提前退出while(p->next!=NULL)if(fabs(p->coef)>1e-6)if(fabs(p->next->coef)>1e-6)printf("%f*xA%d+",p->coef,p-&

25、gt;exp);elseprintf("%f*xA%d",p->coef,p->exp);elseprintf(".");/輸出分割點p=p->next;if(fabs(p->coef)>1e-6)printf("%f*xA%d",p->coef,p->exp);printf("n");多項式相乘，結果由PolyC返回PolyListPolyMutiply(PolyListPolyA,PolyListPolyB)PolyListPolyC;PolyNode*pa,*pb,*

26、pc_pre,*pc,*s;if(PolyA=NULL|PolyB=NULL)returnNULL;若某一個多項式為空，返回PolyC=(PolyNode*)malloc(sizeof(PolyNode);pc=PolyC;pc->next=NULL;if(PolyA->next=NULL|PolyB->next=NULL)returnPolyC;SortPoly(PolyA);SortPoly(PolyB);pa=PolyA->next;pb=PolyB->next;s=(PolyNode*)malloc(sizeof(PolyNode);s->coef=

27、pa->coef*pb->coef;s->exp=pa->exp+pb->exp;if(pc->next=NULL)(pc->next=s;pc=s;pc->next=NULL;)直接插入第一個結點while(pa)(pb=PolyB->next;while(pb)(兩項對應相乘，結果存入到s中pc=PolyC->next;if(pa=PolyA->next&&pb=PolyB->next)/避免重復插入第一個結點(pb=pb->next;if(pb=NULL)break;)s=(PolyNode*)

28、malloc(sizeof(PolyNode);s->coef=pa->coef*pb->coef;s->exp=pa->exp+pb->exp;/查找s合適的插入位置，使得插入后PolyC仍為升序排列while(pc&&pc->exp>s->exp)pc_pre=pc;pc=pc_pre->next;if(pc=NULL)pc_pre->next=s;s->next=NULL;pb=pb->next;elseif(pc->exp<s->exp)pc_pre->next=s;s

29、->next=pc;pb=pb->next;elseif(s->exp=pc->exp)pc->coef+=s->coef;free(s);if(fabs(pc->coef)<1e-6)pc_pre->next=pc->next;free(pc);pb=pb->next;pa=pa->next;returnPolyC;多項式相除，結果存到PolyC中，商和余數(shù)用系數(shù)為0的結點分開PolyListPolyDivide(PolyListPolyA,PolyListPolyB)if(!PolyA|!PolyB)returnNUL

30、L;if(PolyB->next=NULL)printf("Error:除項為空！n");returnNULL;PolyListPolyTI,PolyT2,pt,s,PolyC,p,s_pre;PolyC=(PolyList)malloc(sizeof(PolyNode);PolyC->next=NULL;if(PolyA->next=NULL)returnPolyC;p=PolyA->next;PolyTI=(PolyList)malloc(sizeof(PolyNode);pt=PolyTI;de);s_pre=(PolyList)malloc(

31、sizeof(PolyNowhile(p)將PollyA復制到PolyT中(s=(PolyList)malloc(sizeof(PolyNode);s->coef=p->coef;s->exp=p->exp;pt->next=s;pt=s;p=p->next;pt->next=NULL;將商存入到PolyC中p=PolyC;while(PolyT1->next&&PolyT1->next->exp>=PolyB->next->exp)(s=(PolyList)malloc(sizeof(PolyNode);s_pre->next=s;s->next=NULL;s->coef=PolyT1->next->coef/PolyB->next->coef;s->exp=PolyT1->next->exp-PolyB->next->exp;p->next=s;p=s;PolyT2=(PolyList)malloc(sizeof(PolyNode);PolyT2=PolySub(PolyT1,PolyMutiply(PolyB,s_pre);DestroyPolyList(PolyT1);PolyT1