一元多項(xiàng)式的運(yùn)算

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

2、用一個(gè)線性表Q來表示：Q=(qm,q(m-1)，.，q1，q0)不是一般性，假設(shè)嗎嗎mnext;q=0;/記錄結(jié)點(diǎn)位置序號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é)點(diǎn)p插入到現(xiàn)有鏈表的后面，并確保多項(xiàng)式的指數(shù)expn是升序。將s節(jié)點(diǎn)插入到e所指向的鏈表。在該函數(shù)的操作中，要注意指針是如何移動的。/有序鏈表結(jié)點(diǎn)的插入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;有了上述兩個(gè)“結(jié)點(diǎn)的查找定位算法”和“有序鏈表結(jié)點(diǎn)的插入算法”，int n保存的多項(xiàng)式的項(xiàng)數(shù)，使用for語句，控制輸入多項(xiàng)式的每一項(xiàng)。當(dāng)創(chuàng)建的鏈表長度為n時(shí)，將不再提示用戶繼續(xù)輸入多項(xiàng)式的系數(shù)和指數(shù)。建立一個(gè)一元多項(xiàng)式的單鏈表的具體算法如

4、下：/多項(xiàng)式鏈表的建立void CreatPolyn(LinkList &L,int n)LinkList pa; /定義一個(gè)頭指針為pa鏈表int i,q; /i用來計(jì)輸入的項(xiàng)數(shù)，q指結(jié)點(diǎn)的位置序號DataType e; /插入的值epa=(ListNode*)malloc(sizeof(ListNode); /生成鏈表頭結(jié)點(diǎn)pa-next=NULL;for(i=1;inext;pb=Lb-next; /pa和pb分別指向兩個(gè)鏈表的開始結(jié)點(diǎn)Lc=pc=La; /用La的頭結(jié)點(diǎn)作為Lc的頭結(jié)點(diǎn)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é)點(diǎn)(4) 多項(xiàng)式鏈表的輸出void printList(LinkList L)函數(shù)功能：顯示多項(xiàng)式鏈表。在輸出項(xiàng)中使用了條件表達(dá)式，當(dāng)系數(shù)項(xiàng)為正數(shù)時(shí)，在系數(shù)前輸出一個(gè)“+”號，否則輸出一個(gè)空格，而負(fù)數(shù)的負(fù)號還照常輸出，使得輸出結(jié)果盡量與原多項(xiàng)式的表示形式類似。因此，輸出多項(xiàng)式鏈表的算法實(shí)現(xiàn)如下：/多項(xiàng)式鏈表的輸出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 /多項(xiàng)式鏈表結(jié)點(diǎn)類型定義typedef struct /在struct前使用關(guān)鍵字typedef，表示是聲明新類型float coef; /系數(shù)int expn; /指數(shù)DataType; /DataType是新類型typedef struct node /單鏈表的存儲DataType data; /數(shù)據(jù)域struct node *next; /指向下一個(gè)結(jié)點(diǎn)ListNode,*LinkList; /ListNode是結(jié)點(diǎn)的新類型，LinkList是指向ListNode類型的結(jié)點(diǎn)的指針類型/結(jié)點(diǎn)的查找定位int LocateNode(Lin

8、kList L,DataType e,int &q)ListNode *p=L-next;q=0;/記錄結(jié)點(diǎn)位置序號while(p&e.expndata.expn)p=p-next;q+;if(p=NULL|e.expn!=p-data.expn)return 0;else return 1;/有序鏈表結(jié)點(diǎn)的插入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;/多項(xiàng)式鏈表的建立void CreatPolyn(LinkList &L,int n)LinkList pa; /定義一個(gè)頭指針為pa鏈表int i,q; /i用來計(jì)輸入的項(xiàng)數(shù)，q指結(jié)點(diǎn)的位置序號DataType e; /插入的值epa=(ListNode*)malloc(sizeof(ListNode); /生成鏈表頭結(jié)點(diǎn)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);/多項(xiàng)式鏈表的相加void AddPolyn(LinkList La,LinkList Lb,LinkList &Lc) /兩個(gè)有序鏈表La和Lb表示的多項(xiàng)式相加ListNode *pa,*pb,*pc,*s;float sum;pa=La-next;pb=Lb-next;/pa和pb分別指向兩個(gè)鏈表的開始結(jié)點(diǎn)Lc=pc=La;/用La的頭結(jié)點(diǎn)作為Lc的頭結(jié)點(diǎn)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é)點(diǎn)/主控函數(shù)void main()LinkList La,Lb,Lc;int n;printf(輸入第一個(gè)多項(xiàng)式的項(xiàng)數(shù):);sca

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

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

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

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

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

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

18、其是第一項(xiàng)的輸出，同時(shí)還有符號的控制。在輸出第一項(xiàng)時(shí)要判斷是不是常數(shù)項(xiàng),若是,則不要輸出字符x。*/void PrintPolyn(Polyn P) Polyn q=P-next; int flag=1;/項(xiàng)數(shù)計(jì)數(shù)器,flag=1表示為第一項(xiàng)if(!q) /若多項(xiàng)式為空,輸出0 putchar(0); printf(n);return; while (q)if(q-coef0&flag!=1)/系數(shù)大于0且不是第一項(xiàng)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/*在下面的輔助乘法和加法運(yùn)算*/*該函數(shù)功能：判斷兩個(gè)多項(xiàng)式在同一指

20、數(shù)下是否有其中一個(gè)為系數(shù)為0。用來輔助加法和乘法運(yùn)算。*/int compare(Polyn a,Polyn b)/a、b兩個(gè)多項(xiàng)式if(a&b)/a、b多項(xiàng)式均非空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多項(xiàng)式已空，但b多項(xiàng)式非空else return 1;/b多項(xiàng)式已空，但a多項(xiàng)式非空/compare/*以下函數(shù)實(shí)現(xiàn)加法*/*該函數(shù)功能:實(shí)現(xiàn)兩個(gè)多項(xiàng)式pa、pb相

21、加，并將計(jì)算結(jié)果存儲于新建立的pc中，它的原理是將指數(shù)相同的單項(xiàng)式相加，系數(shù)相加后為0，則pa、pb的指針都后移。在加法計(jì)算中要求pa與pb的冪次序都是升序，否則可能得到錯(cuò)誤的結(jié)果。*/Polyn AddPolyn(Polyn pa,Polyn pb)/求解并建立多項(xiàng)式a+b，返回其頭指針Polyn qa=pa-next;Polyn qb=pb-next;Polyn headc,hc,qc;hc=(Polyn)malloc(sizeof(struct Polynomial);/建立頭結(jié)點(diǎn)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àng)式不會實(shí)現(xiàn)相加運(yùn)算qc-coef=qa-coef;qc-expn=qa-expn;qa=qa-next;break;case 0: /a的指數(shù)等于b的指數(shù)，系數(shù)和為a、b多項(xiàng)式的系數(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àng)式不會實(shí)現(xiàn)相加運(yù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時(shí)，釋放該結(jié)點(diǎn)/whilereturn headc;/AddPolyn/*以下函數(shù)實(shí)現(xiàn)減法*/*該函數(shù)功能:實(shí)現(xiàn)兩個(gè)多項(xiàng)式pa、pb相減，其原理根加法類似，將指數(shù)相同的系數(shù)相減。與加法不同的是在送在減法中，創(chuàng)建了新的鏈表來存放結(jié)果，并返回該鏈表的頭指針。*/Polyn SubtractPolyn(Polyn pa,Polyn pb)/求解并建立

24、多項(xiàng)式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ù)實(shí)現(xiàn)乘法*/*該函數(shù)功能:實(shí)現(xiàn)兩個(gè)多項(xiàng)式相乘，A(X) * B(x) 。計(jì)算時(shí)運(yùn)用單項(xiàng)式與多項(xiàng)式相乘的法則，然后再次運(yùn)用單項(xiàng)式與多項(xiàng)式相乘的法則。*/Polyn MultiplyPolyn(Polyn pa,Polyn pb)/求解并建立多項(xiàng)

25、式a*b，返回其頭指針(該函數(shù)實(shí)現(xiàn)乘法)Polyn hf,pf;Polyn qa=pa-next;Polyn qb=pb-next;hf=(Polyn)malloc(sizeof(struct Polynomial);/建立頭結(jié)點(diǎn)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、的項(xiàng)return hf;/MultiplyPolyn/*主函數(shù)實(shí)現(xiàn)顯示與功能選擇*/*該函數(shù)功能:main函數(shù)用來實(shí)現(xiàn)提示使用者輸入、顯示功能列表、調(diào)用其他運(yùn)算函數(shù)實(shí)現(xiàn)運(yùn)算功能。在main（）函數(shù)中，定義m、n用來保存兩個(gè)多項(xiàng)式的項(xiàng)數(shù)，pa、pb、pc、pd、pf定義程序所需鏈表的頭指針。在程序開始要求輸入兩個(gè)多項(xiàng)式的項(xiàng)數(shù)，隨后根據(jù)項(xiàng)數(shù)創(chuàng)建兩個(gè)鏈表以保存多項(xiàng)式，再顯示出功能列表后通過if語句來實(shí)現(xiàn)功能的選擇，從而對整個(gè)程序流程進(jìn)行控制。*/int main()int m,n,flag=0;/m、n為分別為a、b兩個(gè)多項(xiàng)式的項(xiàng)數(shù)Polyn pa=0,pb=0,pc,pd,pf;/定義各式的頭指針

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