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

1、.西安郵電大學(xué)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)報(bào)告題 目： 多項(xiàng)式相乘院系名稱： 計(jì)算機(jī)學(xué)院 專業(yè)名稱： 軟件工程班 級： 學(xué)生姓名： 學(xué)號（8位）： 指導(dǎo)教師： 設(shè)計(jì)起止時(shí)間：. .一. 設(shè)計(jì)目的以動(dòng)態(tài)單鏈表為存儲結(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ù)號顯示合理。 對已排序且合并了同指數(shù)項(xiàng)的兩個(gè)多項(xiàng)式實(shí)現(xiàn)乘法操作，并輸出結(jié)果；結(jié)果多項(xiàng)式要求以動(dòng)態(tài)鏈表為存儲結(jié)構(gòu)，復(fù)用原多

2、項(xiàng)式的結(jié)點(diǎn)空間；輸出結(jié)果多項(xiàng)式要求按指數(shù)升序排列，同指數(shù)的多項(xiàng)要合并，項(xiàng)數(shù)的正負(fù)號要求顯示合理。三概要設(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對多項(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)，

3、釋放合并項(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ù)輸出、符號輸出、指數(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+

4、=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)Polyn

5、ode *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); /釋放

6、空間；if(p->coef=0) /若系數(shù)相加和為0；q->next=p->next;free(p); /釋放空間；else if(p->exp>move->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->

7、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->exp>move->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

8、=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(

9、"nt請輸入多項(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(&

10、quot;%d %d",&c,&e);/輸入新結(jié)點(diǎn)的系數(shù)和指數(shù)；p->next=NULL; /為最后的結(jié)點(diǎn)的next賦空；head=Polysort(head); /調(diào)用Polysort排序函數(shù)對多項(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

11、=(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->

12、;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ù)對多項(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("-&

13、quot;);else if(p->coef!=1) printf("%d",p->coef);/符號輸出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->exp<0) printf("(%d)",p-&g

14、t;exp);else if(p->exp!=1&&p->exp!=0)printf("%d",p->exp); p=p->next;if(p!=NULL&&p->coef>0) 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ì)技巧及體會1改進(jìn)方案多項(xiàng)式相成這個(gè)程序缺少對異常的處理，如果用戶輸入一些異常的字符程序?qū)o法繼續(xù)

15、運(yùn)行，甚至導(dǎo)致死機(jī)。改進(jìn)：加入異常處理，將各種用戶可能的輸入都包含在內(nèi)。2體會心得體會：此程序是使用鏈表完成的，一直以來比較習(xí)慣用順序表，通過這個(gè)程序加深了對鏈表的理解。程序的排序部分較為復(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<stdio.h>#

16、include<stdlib.h>#include<malloc.h>typedef 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; /判斷鏈表是否為空；fi

17、rst=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->exp>move->exp) /判斷待插入項(xiàng)指數(shù)是否

18、大于第一個(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-

19、>next;/若系數(shù)相加和為0；free(p);/釋放空間；break;if(p->exp>move->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é)

20、點(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請輸入多項(xiàng)式中元素的系數(shù)和指數(shù):n");scanf("%d %d",&c,&e);while(c|e) /ceof（系數(shù)）和exp（指數(shù)）不全為0；if(c=0)

21、 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排序函

22、數(shù)對多項(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 *)ma

23、lloc(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ù)

24、對多項(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);/符號輸出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) prin