一元多項式的運算

1、-作者xxxx-日期xxxx一元多項式的運算【精品文檔】數(shù)據(jù)結(jié)構(gòu)課程設(shè)計實 驗 報 告專業(yè)班級： 學(xué) 號： 姓 名： 2011年1月1日題目：一元多項式的運算1、 題目描述一元多項式的運算在此題中實現(xiàn)加、減法的運算，而多項式的減法可以通過加法來實現(xiàn)（只需在減法運算時系數(shù)前加負號）。在數(shù)學(xué)上，一個一元n次多項式Pn(X)可按降序?qū)懗桑?Pn(X)= PnXn+ P(n-1)X(n-1)+.+ P1X+P0它由n+1個系數(shù)惟一確定，因此，在計算機里它可以用一個線性表P來表示： P=(Pn，P(n-1)，.，P1，P0)每一項的指數(shù)i隱含在其系數(shù)Pi的序號里。假設(shè)Qm(X)是一元m次多項式，同樣可以

2、用一個線性表Q來表示：Q=(qm,q(m-1)，.，q1，q0)不是一般性，假設(shè)嗎嗎mnext;q=0;/記錄結(jié)點位置序號while(p&e.expndata.expn)p=p-next;q+;if(p=NULL|e.expn!=p-data.expn)return 0;else return 1;void InsertNode(LinkList &L,DataType e,int q)函數(shù)功能：將新的節(jié)點p插入到現(xiàn)有鏈表的后面，并確保多項式的指數(shù)expn是升序。將s節(jié)點插入到e所指向的鏈表。在該函數(shù)的操作中，要注意指針是如何移動的。/有序鏈表結(jié)點的插入void InsertNode(Link

3、List &L,DataType e,int q)ListNode *s,*p;int i=0;p=L;while(p-next & inext;i+;/查找插入位置s=(ListNode*)malloc(sizeof(ListNode);s-data.coef=e.coef;s-data.expn=e.expn;s-next=p-next;p-next=s;有了上述兩個“結(jié)點的查找定位算法”和“有序鏈表結(jié)點的插入算法”，int n保存的多項式的項數(shù)，使用for語句，控制輸入多項式的每一項。當(dāng)創(chuàng)建的鏈表長度為n時，將不再提示用戶繼續(xù)輸入多項式的系數(shù)和指數(shù)。建立一個一元多項式的單鏈表的具體算法如

4、下：/多項式鏈表的建立void CreatPolyn(LinkList &L,int n)LinkList pa; /定義一個頭指針為pa鏈表int i,q; /i用來計輸入的項數(shù)，q指結(jié)點的位置序號DataType e; /插入的值epa=(ListNode*)malloc(sizeof(ListNode); /生成鏈表頭結(jié)點pa-next=NULL;for(i=1;inext;pb=Lb-next; /pa和pb分別指向兩個鏈表的開始結(jié)點Lc=pc=La; /用La的頭結(jié)點作為Lc的頭結(jié)點while (pa&pb)if(pa-data.expn pb-data.expn)pc-next=p

5、a;pc=pa;pa=pa-next;else if(pa-data.expn data.expn)pc-next=pb;pc=pb;pb=pb-next; else sum=pa-data.coef+pb-data.coef;if(fabs(sum)0) /系數(shù)和不為零pa-data.coef=sum;pc-next=pa;pc=pa;pa=pa-next;s=pb;pb=pb-next;free(s);elses=pa;pa=pa-next;free(s);s=pb;pb=pb-next;free(s);pc-next=pa?pa:pb;/插入鏈表剩余部分 free(Lb);/釋放Lb的頭

6、結(jié)點(4) 多項式鏈表的輸出void printList(LinkList L)函數(shù)功能：顯示多項式鏈表。在輸出項中使用了條件表達式，當(dāng)系數(shù)項為正數(shù)時，在系數(shù)前輸出一個“+”號，否則輸出一個空格，而負數(shù)的負號還照常輸出，使得輸出結(jié)果盡量與原多項式的表示形式類似。因此，輸出多項式鏈表的算法實現(xiàn)如下：/多項式鏈表的輸出void printList(LinkList L)ListNode *p;p=L-next;while(p)printf(%c %fx %d,(p-data.coef0? +: ),p-data.coef,p-data.expn);p=p-next;printf(n);源程序代碼：

7、#include #include #include /多項式鏈表結(jié)點類型定義typedef struct /在struct前使用關(guān)鍵字typedef，表示是聲明新類型float coef; /系數(shù)int expn; /指數(shù)DataType; /DataType是新類型typedef struct node /單鏈表的存儲DataType data; /數(shù)據(jù)域struct node *next; /指向下一個結(jié)點ListNode,*LinkList; /ListNode是結(jié)點的新類型，LinkList是指向ListNode類型的結(jié)點的指針類型/結(jié)點的查找定位int LocateNode(Lin

8、kList L,DataType e,int &q)ListNode *p=L-next;q=0;/記錄結(jié)點位置序號while(p&e.expndata.expn)p=p-next;q+;if(p=NULL|e.expn!=p-data.expn)return 0;else return 1;/有序鏈表結(jié)點的插入void InsertNode(LinkList &L,DataType e,int q)ListNode *s,*p;int i=0;p=L;while(p-next & inext;i+;s=(ListNode*)malloc(sizeof(ListNode);s-data.coe

9、f=e.coef;s-data.expn=e.expn;s-next=p-next;p-next=s;/多項式鏈表的建立void CreatPolyn(LinkList &L,int n)LinkList pa; /定義一個頭指針為pa鏈表int i,q; /i用來計輸入的項數(shù)，q指結(jié)點的位置序號DataType e; /插入的值epa=(ListNode*)malloc(sizeof(ListNode); /生成鏈表頭結(jié)點pa-next=NULL;for(i=1;inext;while(p)printf(%c %fx %d,(p-data.coef0? +: ),p-data.coef,p-

10、data.expn);p=p-next;printf(n);/多項式鏈表的相加void AddPolyn(LinkList La,LinkList Lb,LinkList &Lc) /兩個有序鏈表La和Lb表示的多項式相加ListNode *pa,*pb,*pc,*s;float sum;pa=La-next;pb=Lb-next;/pa和pb分別指向兩個鏈表的開始結(jié)點Lc=pc=La;/用La的頭結(jié)點作為Lc的頭結(jié)點while (pa&pb)if(pa-data.expn pb-data.expn)pc-next=pa;pc=pa;pa=pa-next;xpn)pc-next=pb;pc=p

11、b;pb=pb-next; else sum=pa-data.coef+pb-data.coef;if(fabs(sum)0)/系數(shù)和不為零pa-data.coef=sum;pc-next=pa;pc=pa;pa=pa-next;s=pb;pb=pb-next;free(s);elses=pa;pa=pa-next;free(s);s=pb;pb=pb-next;free(s);pc-next=pa?pa:pb;/插入鏈表剩余部分 free(Lb);/釋放Lb的頭結(jié)點/主控函數(shù)void main()LinkList La,Lb,Lc;int n;printf(輸入第一個多項式的項數(shù):);sca

12、nf(%d,&n);printf(輸入第一個多項式的每一項的系數(shù),指數(shù):n);CreatPolyn(La,n);printf(第一個多項式為:);printList(La);printf(輸入第二個多項式的項數(shù):);scanf(%d,&n);printf(輸入第二個多項式的每一項的系數(shù),指數(shù):);CreatPolyn(Lb,n);printf(第二個多項式為:); printList(Lb);AddPolyn(La,Lb,Lc);printf(n相加后的和多項式為:);printList(Lc);5、調(diào)試分析此一元多項式的運算程序，只能實現(xiàn)一元多項式的加、減法，不能實現(xiàn)一元多項式的乘法，而且若

13、想計數(shù)多個多項式的和或者差的話，必須退出界面重新開始計算。在補充程序里面，解決了程序沒有的選擇功能表的功能，及其多項式的乘法運算。6. 測試結(jié)果輸入多項式的項數(shù)，并且顯示多項式及其兩個多項式的和：補充程序：多項式運算程序具有以下基本功能：1界面輸出，提示如何輸入數(shù)據(jù)。要求先輸入多項式的項數(shù)。2創(chuàng)建多項式。接收輸入的數(shù)據(jù)，并保存到鏈表中。3顯示程序的功能表，允許使用者選擇運算類型。4顯示已經(jīng)創(chuàng)建好的多項式。5實現(xiàn)加法運算。6實現(xiàn)減法運算。7實現(xiàn)乘法運算。8清除內(nèi)存內(nèi)容，銷毀創(chuàng)建的鏈表，退出程序。該程序?qū)崿F(xiàn)了多項式的創(chuàng)建、多項式的加法、減法、乘法運算以及多項式的清除。源程序代碼：#include#

14、include/*以下函數(shù)實現(xiàn)鏈表的定義*/*該函數(shù)的功能:在計算機內(nèi)要表示一個多項式，至少以下數(shù)據(jù)信息-系數(shù)信息、指數(shù)信息和指向下一個單項式的指針。通過指針，我們就可以把多個單項式連接起來，形式一個多項式.*/typedef struct Polynomialfloat coef; /系數(shù)int expn; /指數(shù)struct Polynomial *next; /指向下一個結(jié)點*Polyn,Polynomial; /Polyn為結(jié)點指針類型/*以下函數(shù)用來實現(xiàn)鏈表的順序排列和合并相同的項 */*該函數(shù)的功能:實現(xiàn)鏈表的順序排列和合并相同的項。將新的節(jié)點p插入到現(xiàn)有鏈表的后面，并確保多項式的

15、指數(shù)expn是升序。將p節(jié)點插入到head所指向的鏈表。在該函數(shù)的操作中，要注意指針是如何移動的。*/void Insert(Polyn p,Polyn h) if(p-coef=0)free(p); /系數(shù)為0的話釋放結(jié)點else /如果系數(shù)不為0 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

16、(q2);else /指數(shù)為新時將結(jié)點插入 p-next=q2;q1-next=p;/Insert/*以下函數(shù)實現(xiàn)建立一個多項式*/*該函數(shù)功能:創(chuàng)建新的多項式鏈表。int m保存的多項式的項數(shù)，使用for語句，控制輸入多項式的每一項。當(dāng)創(chuàng)建的鏈表長度為m時，將不再提示用戶繼續(xù)輸入多項式的系數(shù)和指數(shù)。*/Polyn CreatePolyn(Polyn head,int m)/建立一個頭指針為head、項數(shù)為m的一元多項式,int m是保存的多項式的項數(shù) /在主程序初始時，先輸入的多項式中的項數(shù)m、n 在這里為m。主程序中的pa、pb在此為headint i;/定義int i計數(shù)，當(dāng)inext=

17、NULL;for(i=0;icoef,&p-expn);Insert(p,head); /調(diào)用Insert函數(shù)插入結(jié)點return head;/CreatePolyn/*以下函數(shù)實現(xiàn)多項式的銷毀*/*該函數(shù)的功能:銷毀掉創(chuàng)建的兩個鏈表，釋放內(nèi)存。以輔助退出程序*/void DestroyPolyn(Polyn p)/銷毀多項式pPolyn q1,q2;q1=p-next;q2=q1-next;while(q1-next)free(q1);q1=q2; /指針后移q2=q2-next;/*以下函數(shù)實現(xiàn)顯示輸出多項式* */*該函數(shù)的功能:顯示多項式鏈表。在該函數(shù)中較復(fù)雜的是如何控制鏈表的輸出,尤

18、其是第一項的輸出，同時還有符號的控制。在輸出第一項時要判斷是不是常數(shù)項,若是,則不要輸出字符x。*/void PrintPolyn(Polyn P) Polyn q=P-next; int flag=1;/項數(shù)計數(shù)器,flag=1表示為第一項if(!q) /若多項式為空,輸出0 putchar(0); printf(n);return; while (q)if(q-coef0&flag!=1)/系數(shù)大于0且不是第一項putchar(+); if(q-coef!=1&q-coef!=-1)/系數(shù)非1或-1的普通情況printf(%g,q-coef); if(q-expn=1) putchar(X

19、);else if(q-expn) printf(X%d,q-expn);elseif(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); elseprintf(-X%d,q-expn);q=q-next; flag+;/whileprintf(n);/PrintPolyn/*在下面的輔助乘法和加法運算*/*該函數(shù)功能：判斷兩個多項式在同一指

20、數(shù)下是否有其中一個為系數(shù)為0。用來輔助加法和乘法運算。*/int compare(Polyn a,Polyn b)/a、b兩個多項式if(a&b)/a、b多項式均非空if(!b|a-expnb-expn) /a的指數(shù)大于b的指數(shù)return 1;else if(!a|a-expnexpn) /a的指數(shù)小于b的指數(shù)return -1;else /a的指數(shù)等于b的指數(shù)return 0;else if(!a&b) return -1;/a多項式已空，但b多項式非空else return 1;/b多項式已空，但a多項式非空/compare/*以下函數(shù)實現(xiàn)加法*/*該函數(shù)功能:實現(xiàn)兩個多項式pa、pb相

21、加，并將計算結(jié)果存儲于新建立的pc中，它的原理是將指數(shù)相同的單項式相加，系數(shù)相加后為0，則pa、pb的指針都后移。在加法計算中要求pa與pb的冪次序都是升序，否則可能得到錯誤的結(jié)果。*/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);/建立頭結(jié)點hc-next=NULL;headc=hc;while(qa|qb)qc=(Polyn)malloc(siz

22、eof(struct Polynomial);/malloc()函數(shù)為其分配內(nèi)存空間switch(compare(qa,qb)case 1: /a的指數(shù)大于b的指數(shù)，a、b多項式不會實現(xiàn)相加運算qc-coef=qa-coef;qc-expn=qa-expn;qa=qa-next;break;case 0: /a的指數(shù)等于b的指數(shù)，系數(shù)和為a、b多項式的系數(shù)相加之和，指數(shù)即為其兩者相同的指數(shù) qc-coef=qa-coef+qb-coef;qc-expn=qa-expn;qa=qa-next;qb=qb-next;break; case -1: /a的指數(shù)小于b的指數(shù)，a、b多項式不會實現(xiàn)相加運

23、算qc-coef=qb-coef;qc-expn=qb-expn;qb=qb-next;break; /switchif(qc-coef!=0)qc-next=hc-next;hc-next=qc;hc=qc;else free(qc);/當(dāng)相加系數(shù)為0時，釋放該結(jié)點/whilereturn headc;/AddPolyn/*以下函數(shù)實現(xiàn)減法*/*該函數(shù)功能:實現(xiàn)兩個多項式pa、pb相減，其原理根加法類似，將指數(shù)相同的系數(shù)相減。與加法不同的是在送在減法中，創(chuàng)建了新的鏈表來存放結(jié)果，并返回該鏈表的頭指針。*/Polyn SubtractPolyn(Polyn pa,Polyn pb)/求解并建立

24、多項式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的系數(shù)p-coef*=-1;return pd;/SubtractPolyn/*以下函數(shù)實現(xiàn)乘法*/*該函數(shù)功能:實現(xiàn)兩個多項式相乘，A(X) * B(x) 。計算時運用單項式與多項式相乘的法則，然后再次運用單項式與多項式相乘的法則。*/Polyn MultiplyPolyn(Polyn pa,Polyn pb)/求解并建立多項

25、式a*b，返回其頭指針(該函數(shù)實現(xiàn)乘法)Polyn hf,pf;Polyn qa=pa-next;Polyn 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ù)相同

26、的項return hf;/MultiplyPolyn/*主函數(shù)實現(xiàn)顯示與功能選擇*/*該函數(shù)功能:main函數(shù)用來實現(xiàn)提示使用者輸入、顯示功能列表、調(diào)用其他運算函數(shù)實現(xiàn)運算功能。在main（）函數(shù)中，定義m、n用來保存兩個多項式的項數(shù)，pa、pb、pc、pd、pf定義程序所需鏈表的頭指針。在程序開始要求輸入兩個多項式的項數(shù)，隨后根據(jù)項數(shù)創(chuàng)建兩個鏈表以保存多項式，再顯示出功能列表后通過if語句來實現(xiàn)功能的選擇，從而對整個程序流程進行控制。*/int main()int m,n,flag=0;/m、n為分別為a、b兩個多項式的項數(shù)Polyn pa=0,pb=0,pc,pd,pf;/定義各式的頭指針

27、，pa與pb在使用前付初值NULL/pc頭指針?biāo)诘亩囗検接迷诩臃ㄖ凶鳛榻Y(jié)果，pd用在加法中，pf乘法中printf(*歡迎使用一元多項式運算程序*n);printf(請輸入第一個多項式a的項數(shù):);scanf(%d,&m);pa=CreatePolyn(pa,m); /建立第一個多項式aprintf(請輸入第二個多項式b的項數(shù):);scanf(%d,&n);pb=CreatePolyn(pb,n); /建立第二個多項式b/輸出菜單printf(*n);printf(請選擇您要進行的操作：nt1.輸出多項式a和bnt2.建立多項式a+bnt3.建立多項式a-bn);printf(t4.計算多項式a*b的值nt5.