多項式相乘C實現(xiàn)

1、西安郵電大學(xué)數(shù)據(jù)結(jié)構(gòu)設(shè)計報告題目：多項式相乘院系名稱：計算機學(xué)院專業(yè)名稱：軟件工程班 級：_學(xué)生姓名：_學(xué)號（8位）：指導(dǎo)教師：_ 設(shè)計起止時間:設(shè)計目的以動態(tài)單鏈表為存儲結(jié)構(gòu)，使用排序等操作實現(xiàn)多項式的乘法運算二.設(shè)計內(nèi)容用一個單鏈表來表示一個一元多項式；在創(chuàng)建多項式的過程中， 可以按指數(shù)的任意順序輸入，并且可在同一多項式中輸入指數(shù)相同的多個項；在進行乘法操作之前， 輸出參與操作的兩個多項式。 要求輸出的多項式按指數(shù)升序排列，同指數(shù)的多項合并，項數(shù)的正負(fù)號顯示合理。對已排序且合并了同指數(shù)項的兩個多項式實現(xiàn)乘法操作，并輸出結(jié)果；結(jié)果多項式要求以動態(tài)鏈表為存儲結(jié)構(gòu)，復(fù)用原多項式的結(jié)點空間；輸出結(jié)

2、果多項式要求按指數(shù)升序排列，同指數(shù)的多項要合并，項數(shù)的正負(fù)號要求顯示合理。三概要設(shè)計1 功能模塊圖;2 各個模塊詳細(xì)的功能描述多項式鏈表升序排序函數(shù)Polylist Polysort(Polylist head)根據(jù)幕次的高低排序的同時并合同類項，幕次相同的系數(shù)相加存入前項，釋放合 并項中后者空間，若系數(shù)相加和為0則釋放兩項空間。多項式創(chuàng)建函數(shù)Polylist creat()多項式相乘函數(shù)Polylist Polymul(Polylist LA,Polylist LB)輸出函數(shù)void prin t(Polylist head)分三種情況：系數(shù)輸出、符號輸出、指數(shù)輸出四詳細(xì)設(shè)計1.各功能函數(shù)的

3、數(shù)據(jù)流程圖2重點設(shè)計及編碼1)多項式鏈表升序排序函數(shù)Polylist Polysort(Polylist head)Polynode *first,*move,*p,*q; /first q=head;p=head-next; if(p=NULL) return head; first=p-next;p-next=NULL; move=first;while(move!=NULL)first=first-next; if(p-exp=move-exp)p-coef+=move-coef; free(move);if(p-coef=0)q-next=p-next; free(p);else if

4、(p-expmove-exp) /移動指針 move 被移動項指針 p,q 臨時指針/判斷鏈表是否為空；/直接插入排序(鏈表排序)/判斷待插入項指數(shù)是否與首項相等；/系數(shù)相加；/釋放空間；/若系數(shù)相加和為 0；/釋放空間；判斷待插入項指數(shù)是否大于第一個項的指數(shù)；head-next=move; move-next=p;else if(p-next=NULL) p-next=move; move-next=NULL;elseq=p;p=p-next;/判斷下一項是否為空；/待插入項指數(shù)插入位置在首末項之間；/移動臨時變量指針 p,qwhile(1)if(p-exp=move-exp) /判斷待插入

5、項指數(shù)是否與首項相等； p-coef+=move-coef;/ 系數(shù)相加；free(move);/釋放空間；if(p-coef=0)q-next=p-next;/ 若系數(shù)相加和為 0； free(p); / 釋放空間；break;if(p-expmove-exp) / 判斷待插入項指數(shù)是否大于當(dāng)前項的指數(shù)； q-next=move; move-next=p; break;if(p-next=NULL)/判斷下一項是否為空；p-next=move; move-next=NULL;/移動臨時變量指針 p,q ；/使 p,q 指針重新指到初始化位置；/返回頭結(jié)點；/head：頭指針newnode:新

6、結(jié)點指針 p:臨時指針變量break; q=p; p=p-next;p=head-next;q=head; move=first; return head;2)多項式創(chuàng)建函數(shù)Polylist creat()Polynode *head,*p,*newnode;int c,e;/ceof (系數(shù))和 exp (指數(shù))；head=(Polynode *)malloc(sizeof(Polynode);/ 開辟一個新結(jié)點，并使之成為頭結(jié)點； p=head;printf(nt 請輸入多項式中元素的系數(shù)和指數(shù) :n);scanf(%d %d,&c,&e);while(c|e)/ceof (系數(shù))和 ex

7、p (指數(shù))不全為 0;if(c=0)scanf(%d %d,&c,&e);continue;/若 c 為 0，不開辟新結(jié)點；newnode=(Polynode *)malloc(sizeof(Polynode);/ 開辟一個新結(jié)點； newnode-coef=c;newnode-exp=e;p-next=newnode;p=newnode;scanf(%d %d,&c,&e);/ 輸入新結(jié)點的系數(shù)和指數(shù)；p-next=NULL;/為最后的結(jié)點的 next 賦空；head=Polysort(head);/調(diào)用 Polysort 排序函數(shù)對多項式鏈表進行降序排序；return head;/返回頭

8、結(jié)點；( 3 )多項式相乘函數(shù)Polylist Polymul(Polylist LA,Polylist LB)Poly node *head,*p,*q,*t,* new node; /head :頭指針 newn ode:新結(jié)點指針 p,q,t :臨時指針 變量；p=LA-next;q=LB-next;head=(Polynode *)malloc(sizeof(Polynode);/ 開辟一個新結(jié)點， 并使之成為新鏈表的頭結(jié) t=head;while(p!=NULL)while(q!=NULL)newnode=(Polynode *)malloc(sizeof(Polynode);/ 開

9、辟一個新結(jié)點；t-next=newnode; t=t-next; t-coef=p-coef*q-coef; t-exp=p-exp+q-exp; q=q-next;p=p-next;q=LB-next;t-next=NULL;head=Polysort(head);降序排序；return head;(4)輸出函數(shù)void print(Polylist head)Polynode *p;p=head-next;if(p=NULL)printf(0);elsewhile(p!=NULL)/系數(shù)輸出if(p-coef=-1) printf(-);else if(p-coef!=1)printf(%

10、d,p-coef);/符號輸出 if(p-exp!=0&p-exp!=1) prin tf(XA);else if(p-exp=1)printf(X);/項之系數(shù)為 LA,LB 兩項系數(shù)之積；/項之指數(shù)為 LA,LB 兩項指數(shù)之和；/p 指針移動；/q 指針復(fù)位為 LB-next ；/ 為最后的結(jié)點的 next 賦空；/ 調(diào)用 Polysort 排序函數(shù)對多項式鏈表進行/返回頭結(jié)點；/指數(shù)輸出if(p-exp=0&(p-coef=-1|p-coef=1)printf(1);if(p-expexp);else if(p-exp!=1&p-exp!=0)printf(%d,p-exp);p=p-n

11、ext;if(p!=NULL&p-coef0)printf(+);prin tf(n);五測試數(shù)據(jù)及運行結(jié)果1 正常測試數(shù)據(jù)和運行結(jié)果請輸入一元多項式仏諳輸入一元多頂式矩請輸入多項式中元素的系數(shù)和指數(shù)=-2 13 02 30 0 3-2X*2X*3請輸人一元多項式請輸入多項代中元索的系刪啪數(shù)：1 -1戸3* 1” e兩參負(fù)式相乘結(jié)果LC； 3X-1)-2*1BX-1BK2-6K3+16X4-4X62 異常測試數(shù)據(jù)及運行結(jié)果如輸入的字符不是數(shù)字，則無法處理, 如：a2程序無法繼續(xù)運行六調(diào)試情況，設(shè)計技巧及體會1 改進方案多項式相成這個程序缺少對異常的處理，如果用戶輸入一些異常的字符程序?qū)o法繼續(xù)

12、運 行，甚至導(dǎo)致死機。改進：加入異常處理，將各種用戶可能的輸入都包含在內(nèi)。2體會心得體會：此程序是使用鏈表完成的，一直以來比較習(xí)慣用順序表，通過這個程序加深了對 鏈表的理解。程序的排序部分較為復(fù)雜，根據(jù)幕次的高低排序的同時并合了同類項，幕次相同的系數(shù)相加存入前項，釋放合并項中后者空間，若系數(shù)相加和為0則釋放兩項空間。其實 想這段算法時很容易， 真正實現(xiàn)卻是相當(dāng)不容易，可能是平時寫的代碼太少， 真正把思想轉(zhuǎn)換成代碼困難還是比較大。七參考文獻(xiàn)C 語言程序設(shè)計王曙燕主編 科學(xué)出版社數(shù)據(jù)結(jié)構(gòu) C 語言描述 耿國華 高等教育出版社 數(shù)據(jù)結(jié)構(gòu) 嚴(yán)蔚敏 清華大學(xué)出版社八附錄：#include#include

13、#include typedef struct Polynodeint coef;/ 系數(shù) int exp;/ 指數(shù) struct Polynode *next;Polynode,*Polylist;/ 多項式鏈表升序排序Polylist Polysort(Polylist head) Polynode *first,*move,*p,*q; /first 臨時指針變量q=head;p=head-next;if(p=NULL) return head; / first=p-next;p-next=NULL;move=first; while(move!=NULL) / first=first-

14、next; if(p-exp=move-exp) / p-coef+=move-coef; / free(move); / if(p-coef=0) /q-next=p-next; free(p); /else if(p-expmove-exp) /移動指針變量 move 被移動項指針變量 判斷鏈表是否為空； 直接插入排序（鏈表排序） 判斷待插入項指數(shù)是否與首項相等；系數(shù)相加；釋放空間；若系數(shù)相加和為 0；釋放空間；判斷待插入項指數(shù)是否大于第一個項的指數(shù)；p,qhead-next=move;move-next=p;判斷下一項是否為空；else if(p-next=NULL) /p-next=m

15、ove; move-next=NULL; else/ 待插入項指數(shù)插入位置在首末項之間；q=p; p=p-next; while(1)/移動臨時變量指針 p,qif(p-exp=move-exp) / 判斷待插入項指數(shù)是否與首項相等；p-coef+=move-coef;/ free(move);if(p-coef=0)q-next=p-next;/ free(p);break;/系數(shù)相加； 釋放空間；若系數(shù)相加和為 0； 釋放空間； if(p-expmove-exp) /判斷待插入項指數(shù)是否大于當(dāng)前項的指數(shù)；q-next=move; move-next=p; break;if(p-next=N

16、ULL) /判斷下一項是否為空；p-next=move; move-next=NULL; break; q=p; p=p-next;/移動臨時變量指針 p,q ； p=head-next; q=head; move=first; return head;/使 p,q 指針重新指到初始化位置；/返回頭結(jié)點；/ 多項式創(chuàng)建 (頭插法 ) Polylist creat()Polynode *head,*p,*newnode; /head：頭指針 newnode: 新結(jié)點指針 p ：臨時指針變點；八、，int c,e;/ceof（系數(shù)）和exp （指數(shù)）;head=(Polynode *)malloc

17、(sizeof(Polynode);/開辟一個新結(jié)點，并使之成為頭結(jié)p=head;printf(nt 請輸入多項式中元素的系數(shù)和指數(shù) :n);scanf(%d %d,&c,&e);while(c|e)/ceof(系數(shù))和 exp (指數(shù))不全為 0;if(c=0)scanf(%d %d,&c,&e);continue;/ 若 c 為 0，不開辟新結(jié)點；newnode=(Polynode *)malloc(sizeof(Polynode);/開辟一個新結(jié)點；newnode-coef=c;newnode-exp=e;p-next=newnode;p=newnode;scanf(%d %d,&c,&

18、e);/ 輸入新結(jié)點的系數(shù)和指數(shù)； p-next=NULL;/head=Polysort(head);/進行降序排序；return head;/為最后的結(jié)點的 next 賦空； 調(diào)用 Polysort 排序函數(shù)對多項式鏈表返回頭結(jié)點；/ 多項式相乘Polylist Polymul(Polylist LA,Polylist LB)Polynode *head,*p,*q,*t,*newnode; /head：頭指針 newnode: 新結(jié)點指針 p,q,t臨時指針變量；p=LA-next;q=LB-next;head=(Polynode *)malloc(sizeof(Polynode);/開辟

19、一個新結(jié)點， 并使之成為新鏈表的頭結(jié)點；t=head;while(p!=NULL)while(q!=NULL)newnode=(Polynode *)malloc(sizeof(Polynode);/開辟一個新結(jié)點；t-next=newnode;t=t-next;t-coef=p-coef*q-coef;/t-exp=p-exp+q-exp;/q=q-next;項之系數(shù)為 LA,LB 兩項系數(shù)之積； 項之指數(shù)為 LA,LB 兩項指數(shù)之和；p=p-next;/pq=LB-next;/qt-next=NULL;/head=Polysort(head);/進行降序排序；指針移動；指針復(fù)位為 LB-next ；為最后的結(jié)點的 next 賦空； 調(diào)用 Polysort 排序函數(shù)對多項式鏈表/ 輸出函