多項(xiàng)式相乘C實(shí)現(xiàn).doc

.西安郵電大學(xué)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)報(bào)告題 目： 多項(xiàng)式相乘院系名稱： 計(jì)算機(jī)學(xué)院 專業(yè)名稱： 軟件工程班 級(jí)： 學(xué)生姓名： 學(xué)號(hào)（8位）： 指導(dǎo)教師： 設(shè)計(jì)起止時(shí)間：. .一. 設(shè)計(jì)目的以動(dòng)態(tài)單鏈表為存儲(chǔ)結(jié)構(gòu)，使用排序等操作實(shí)現(xiàn)多項(xiàng)式的乘法運(yùn)算二. 設(shè)計(jì)內(nèi)容用一個(gè)單鏈表來表示一個(gè)一元多項(xiàng)式；在創(chuàng)建多項(xiàng)式的過程中，可以按指數(shù)的任意順序輸入，并且可在同一多項(xiàng)式中輸入指數(shù)相同的多個(gè)項(xiàng)；在進(jìn)行乘法操作之前，輸出參與操作的兩個(gè)多項(xiàng)式。要求輸出的多項(xiàng)式按指數(shù)升序排列，同指數(shù)的多項(xiàng)合并，項(xiàng)數(shù)的正負(fù)號(hào)顯示合理。 對(duì)已排序且合并了同指數(shù)項(xiàng)的兩個(gè)多項(xiàng)式實(shí)現(xiàn)乘法操作，并輸出結(jié)果；結(jié)果多項(xiàng)式要求以動(dòng)態(tài)鏈表為存儲(chǔ)結(jié)構(gòu)，復(fù)用原多項(xiàng)式的結(jié)點(diǎn)空間；輸出結(jié)果多項(xiàng)式要求按指數(shù)升序排列，同指數(shù)的多項(xiàng)要合并，項(xiàng)數(shù)的正負(fù)號(hào)要求顯示合理。三概要設(shè)計(jì)主函數(shù)main()1功能模塊圖；創(chuàng)建多項(xiàng)式LB=creat()創(chuàng)建多項(xiàng)式LA=creat()調(diào)用Polysort( )排序調(diào)用print()輸出LB調(diào)用Polysort( )排序調(diào)用print()輸出LA對(duì)多項(xiàng)式LA,LB相乘LC=Polymul(LA,LB)調(diào)用Polysort( )排序 調(diào)用print()輸出LC2各個(gè)模塊詳細(xì)的功能描述。多項(xiàng)式鏈表升序排序函數(shù)Polylist Polysort(Polylist head)根據(jù)冪次的高低排序的同時(shí)并合同類項(xiàng)，冪次相同的系數(shù)相加存入前項(xiàng)，釋放合并項(xiàng)中后者空間，若系數(shù)相加和為0則釋放兩項(xiàng)空間。多項(xiàng)式創(chuàng)建函數(shù)Polylist creat()多項(xiàng)式相乘函數(shù)Polylist Polymul(Polylist LA,Polylist LB)輸出函數(shù)void print(Polylist head)分三種情況：系數(shù)輸出、符號(hào)輸出、指數(shù)輸出四詳細(xì)設(shè)計(jì)1.各功能函數(shù)的數(shù)據(jù)流程圖Polysort()開始head=NULL？first=p-next; p-next=NULL; move=first; Yp-exp= =move-expp-exp= =move-exp N N yp-coef+=move-coef; free(move);p-next= =NULL yhead-next=move; move-next=p; p-coef= =0 yhead-next=move; move-next=p; q=p;p=p-next;q-next=p-next;free(p); yWhile(1)p=head-next; q=head;move=first;return head結(jié)束2重點(diǎn)設(shè)計(jì)及編碼（1）多項(xiàng)式鏈表升序排序函數(shù)Polylist Polysort(Polylist head)Polynode *first,*move,*p,*q; /first移動(dòng)指針 move 被移動(dòng)項(xiàng)指針p,q臨時(shí)指針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) /判斷待插入項(xiàng)指數(shù)是否與首項(xiàng)相等；p-coef+=move-coef; /系數(shù)相加；free(move); /釋放空間；if(p-coef=0) /若系數(shù)相加和為0；q-next=p-next;free(p); /釋放空間；else if(p-expmove-exp) /判斷待插入項(xiàng)指數(shù)是否大于第一個(gè)項(xiàng)的指數(shù)；head-next=move;move-next=p;else if(p-next=NULL) /判斷下一項(xiàng)是否為空；p-next=move;move-next=NULL;else /待插入項(xiàng)指數(shù)插入位置在首末項(xiàng)之間； q=p; /移動(dòng)臨時(shí)變量指針p,qp=p-next;while(1)if(p-exp=move-exp) /判斷待插入項(xiàng)指數(shù)是否與首項(xiàng)相等；p-coef+=move-coef;/系數(shù)相加；free(move);/釋放空間；if(p-coef=0)q-next=p-next;/若系數(shù)相加和為0；free(p);/釋放空間；break;if(p-expmove-exp) /判斷待插入項(xiàng)指數(shù)是否大于當(dāng)前項(xiàng)的指數(shù)；q-next=move;move-next=p;break;if(p-next=NULL) /判斷下一項(xiàng)是否為空；p-next=move;move-next=NULL;break;q=p; /移動(dòng)臨時(shí)變量指針p,q；p=p-next;p=head-next; /使p,q指針重新指到初始化位置；q=head;move=first;return head; /返回頭結(jié)點(diǎn)；（2）多項(xiàng)式創(chuàng)建函數(shù)Polylist creat()Polynode *head,*p,*newnode;/head：頭指針 newnode:新結(jié)點(diǎn)指針 p：臨時(shí)指針變量int c,e; /ceof（系數(shù)）和exp（指數(shù)）；head=(Polynode *)malloc(sizeof(Polynode);/開辟一個(gè)新結(jié)點(diǎn)，并使之成為頭結(jié)點(diǎn)；p=head;printf(nt請(qǐng)輸入多項(xiàng)式中元素的系數(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é)點(diǎn)；newnode=(Polynode *)malloc(sizeof(Polynode);/開辟一個(gè)新結(jié)點(diǎn)；newnode-coef=c;newnode-exp=e;p-next=newnode;p=newnode;scanf(%d %d,&c,&e);/輸入新結(jié)點(diǎn)的系數(shù)和指數(shù)；p-next=NULL; /為最后的結(jié)點(diǎn)的next賦空；head=Polysort(head); /調(diào)用Polysort排序函數(shù)對(duì)多項(xiàng)式鏈表進(jìn)行降序排序；return head; /返回頭結(jié)點(diǎn)；（3）多項(xiàng)式相乘函數(shù)Polylist Polymul(Polylist LA,Polylist LB)Polynode *head,*p,*q,*t,*newnode; /head：頭指針 newnode:新結(jié)點(diǎn)指針 p,q,t：臨時(shí)指針變量；p=LA-next;q=LB-next;head=(Polynode *)malloc(sizeof(Polynode);/開辟一個(gè)新結(jié)點(diǎn)，并使之成為新鏈表的頭結(jié)點(diǎn)；t=head;while(p!=NULL)while(q!=NULL)newnode=(Polynode *)malloc(sizeof(Polynode);/開辟一個(gè)新結(jié)點(diǎn)；t-next=newnode;t=t-next;t-coef=p-coef*q-coef; /項(xiàng)之系數(shù)為LA,LB兩項(xiàng)系數(shù)之積；t-exp=p-exp+q-exp; /項(xiàng)之指數(shù)為LA,LB兩項(xiàng)指數(shù)之和；q=q-next;p=p-next; /p指針移動(dòng)；q=LB-next; /q指針復(fù)位為LB-next；t-next=NULL; /為最后的結(jié)點(diǎn)的next賦空；head=Polysort(head); /調(diào)用Polysort排序函數(shù)對(duì)多項(xiàng)式鏈表進(jìn)行降序排序；return head; /返回頭結(jié)點(diǎn)；（4）輸出函數(shù)void print(Polylist head)Polynode *p;p=head-next;if(p=NULL) printf(0);else while(p!=NULL) /系數(shù)輸出if(p-coef=-1) printf(-);else if(p-coef!=1) printf(%d,p-coef);/符號(hào)輸出if(p-exp!=0&p-exp!=1) printf(X);else if(p-exp=1) printf(X);/指數(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-next;if(p!=NULL&p-coef0) printf(+); printf(n);五測試數(shù)據(jù)及運(yùn)行結(jié)果1正常測試數(shù)據(jù)和運(yùn)行結(jié)果2異常測試數(shù)據(jù)及運(yùn)行結(jié)果如輸入的字符不是數(shù)字，則無法處理，如：a 2 程序無法繼續(xù)運(yùn)行六調(diào)試情況，設(shè)計(jì)技巧及體會(huì)1改進(jìn)方案多項(xiàng)式相成這個(gè)程序缺少對(duì)異常的處理，如果用戶輸入一些異常的字符程序?qū)o法繼續(xù)運(yùn)行，甚至導(dǎo)致死機(jī)。改進(jìn)：加入異常處理，將各種用戶可能的輸入都包含在內(nèi)。2體會(huì)心得體會(huì)：此程序是使用鏈表完成的，一直以來比較習(xí)慣用順序表，通過這個(gè)程序加深了對(duì)鏈表的理解。程序的排序部分較為復(fù)雜，根據(jù)冪次的高低排序的同時(shí)并合了同類項(xiàng)，冪次相同的系數(shù)相加存入前項(xiàng)，釋放合并項(xiàng)中后者空間，若系數(shù)相加和為0則釋放兩項(xiàng)空間。其實(shí)想這段算法時(shí)很容易，真正實(shí)現(xiàn)卻是相當(dāng)不容易，可能是平時(shí)寫的代碼太少，真正把思想轉(zhuǎn)換成代碼困難還是比較大。七參考文獻(xiàn)C語言程序設(shè)計(jì) 王曙燕主編 科學(xué)出版社數(shù)據(jù)結(jié)構(gòu)C語言描述 耿國華 高等教育出版社數(shù)據(jù)結(jié)構(gòu) 嚴(yán)蔚敏 清華大學(xué)出版社八附錄：#include#include#includetypedef struct Polynodeint coef;/系數(shù)int exp;/指數(shù)struct Polynode *next;Polynode,*Polylist;/多項(xiàng)式鏈表升序排序Polylist Polysort(Polylist head)Polynode *first,*move,*p,*q; /first移動(dòng)指針變量 move 被移動(dòng)項(xiàng)指針變量p,q臨時(shí)指針變量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) /判斷待插入項(xiàng)指數(shù)是否與首項(xiàng)相等；p-coef+=move-coef; /系數(shù)相加；free(move); /釋放空間；if(p-coef=0) /若系數(shù)相加和為0；q-next=p-next;free(p); /釋放空間；else if(p-expmove-exp) /判斷待插入項(xiàng)指數(shù)是否大于第一個(gè)項(xiàng)的指數(shù)；head-next=move;move-next=p;else if(p-next=NULL) /判斷下一項(xiàng)是否為空；p-next=move;move-next=NULL;else /待插入項(xiàng)指數(shù)插入位置在首末項(xiàng)之間； q=p; /移動(dòng)臨時(shí)變量指針p,qp=p-next;while(1)if(p-exp=move-exp) /判斷待插入項(xiàng)指數(shù)是否與首項(xiàng)相等；p-coef+=move-coef;/系數(shù)相加；free(move);/釋放空間；if(p-coef=0)q-next=p-next;/若系數(shù)相加和為0；free(p);/釋放空間；break;if(p-expmove-exp) /判斷待插入項(xiàng)指數(shù)是否大于當(dāng)前項(xiàng)的指數(shù)；q-next=move;move-next=p;break;if(p-next=NULL) /判斷下一項(xiàng)是否為空；p-next=move;move-next=NULL;break;q=p; /移動(dòng)臨時(shí)變量指針p,q；p=p-next;p=head-next; /使p,q指針重新指到初始化位置；q=head;move=first;return head; /返回頭結(jié)點(diǎn)；/多項(xiàng)式創(chuàng)建(頭插法)Polylist creat()Polynode *head,*p,*newnode;/head：頭指針 newnode:新結(jié)點(diǎn)指針 p：臨時(shí)指針變量int c,e; /ceof（系數(shù)）和exp（指數(shù)）；head=(Polynode *)malloc(sizeof(Polynode);/開辟一個(gè)新結(jié)點(diǎn)，并使之成為頭結(jié)點(diǎn)；p=head;printf(nt請(qǐng)輸入多項(xiàng)式中元素的系數(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é)點(diǎn)；newnode=(Polynode *)malloc(sizeof(Polynode);/開辟一個(gè)新結(jié)點(diǎn)；newnode-coef=c;newnode-exp=e;p-next=newnode;p=newnode;scanf(%d %d,&c,&e);/輸入新結(jié)點(diǎn)的系數(shù)和指數(shù)；p-next=NULL; /為最后的結(jié)點(diǎn)的next賦空；head=Polysort(head); /調(diào)用Polysort排序函數(shù)對(duì)多項(xiàng)式鏈表進(jìn)行降序排序；return head; /返回頭結(jié)點(diǎn)；/多項(xiàng)式相乘Polylist Polymul(Polylist LA,Polylist LB)Polynode *head,*p,*q,*t,*newnode; /head：頭指針 newnode:新結(jié)點(diǎn)指針 p,q,t：臨時(shí)指針變量；p=LA-next;q=LB-next;head=(Polynode *)malloc(sizeof(Polynode);/開辟一個(gè)新結(jié)點(diǎn)，并使之成為新鏈表的頭結(jié)點(diǎn)；t=head;while(p!=NULL)while(q!=NULL)newnode=(Polynode *)malloc(sizeof(Polynode);/開辟一個(gè)新結(jié)點(diǎn)；t-next=newnode;t=t-next;t-coef=p-coef*q-coef; /項(xiàng)之系數(shù)為LA,LB兩項(xiàng)系數(shù)之積；t-exp=p-exp+q-exp; /項(xiàng)之指數(shù)為LA,LB兩項(xiàng)指數(shù)之和；q=q-next;p=p-next; /p指針移動(dòng)；q=LB-next; /q指針復(fù)位為LB-next；t-next=NULL; /為最后的結(jié)點(diǎn)的next賦空；head=Polysort(head); /調(diào)用Polysort排序函數(shù)對(duì)多項(xiàng)式鏈表進(jìn)行降序排序；return head; /返回頭結(jié)點(diǎn)；/輸出函數(shù)void print(Polylist head)Polynode *p;p=head-next;if(p=NULL) printf(0);else while(p!=NULL) /系數(shù)輸出if(p-coef=-1) printf(-);else if(p-coef!=1) printf(%d,p-coef);/符號(hào)輸出if(p-exp!=0&p-exp!=1) printf(X);els