多項式相乘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ù)的正負號顯示合理。 對已排序且合并了同指數(shù)項的兩個多項式實現(xiàn)乘法操作，并輸出結(jié)果；結(jié)果多項式要求以動態(tài)鏈表為存儲結(jié)構(gòu)，復(fù)用原多

2、項式的結(jié)點空間；輸出結(jié)果多項式要求按指數(shù)升序排列，同指數(shù)的多項要合并，項數(shù)的正負號要求顯示合理。三概要設(shè)計主函數(shù)main()1功能模塊圖；創(chuàng)建多項式LB=creat()創(chuàng)建多項式LA=creat()調(diào)用Polysort( )排序調(diào)用print()輸出LB調(diào)用Polysort( )排序調(diào)用print()輸出LA對多項式LA,LB相乘LC=Polymul(LA,LB)調(diào)用Polysort( )排序 調(diào)用print()輸出LC2各個模塊詳細的功能描述。多項式鏈表升序排序函數(shù)Polylist Polysort(Polylist head)根據(jù)冪次的高低排序的同時并合同類項，冪次相同的系數(shù)相加存入前項，

3、釋放合并項中后者空間，若系數(shù)相加和為0則釋放兩項空間。多項式創(chuàng)建函數(shù)Polylist creat()多項式相乘函數(shù)Polylist Polymul(Polylist LA,Polylist LB)輸出函數(shù)void print(Polylist head)分三種情況：系數(shù)輸出、符號輸出、指數(shù)輸出四詳細設(shè)計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重點設(shè)計及編碼（1）多項式鏈表升序排序函數(shù)Polylist Polysort(Polylist head)Polyn

5、ode *first,*move,*p,*q; /first移動指針 move 被移動項指針p,q臨時指針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) /判斷待插入項指數(shù)是否與首項相等；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) /判斷待插入項指數(shù)是否大于第一個項的指數(shù)；head->next=move;move->next=p;else if(p->next=NULL) /判斷下一項是否為空；p->next=move;move->next=NULL;else /待插入項指數(shù)插入位置在首末項之間； q=p; /移動臨時變量指針p,qp=p->next;while(1)if(p->

7、exp=move->exp) /判斷待插入項指數(shù)是否與首項相等；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) /判斷待插入項指數(shù)是否大于當(dāng)前項的指數(shù)；q->next=move;move->next=p;break;if(p->next=NULL) /判斷下一項是否為空；p->next=move;move->next

8、=NULL;break;q=p; /移動臨時變量指針p,q；p=p->next;p=head->next; /使p,q指針重新指到初始化位置；q=head;move=first;return head; /返回頭結(jié)點；（2）多項式創(chuàng)建函數(shù)Polylist creat()Polynode *head,*p,*newnode;/head：頭指針 newnode:新結(jié)點指針 p：臨時指針變量int c,e; /ceof（系數(shù)）和exp（指數(shù)）；head=(Polynode *)malloc(sizeof(Polynode);/開辟一個新結(jié)點，并使之成為頭結(jié)點；p=head;printf(

9、"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(&

10、quot;%d %d",&c,&e);/輸入新結(jié)點的系數(shù)和指數(shù)；p->next=NULL; /為最后的結(jié)點的next賦空；head=Polysort(head); /調(diào)用Polysort排序函數(shù)對多項式鏈表進行降序排序；return head; /返回頭結(jié)點；（3）多項式相乘函數(shù)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

11、=(Polynode *)malloc(sizeof(Polynode);/開辟一個新結(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; /項之系數(shù)為LA,LB兩項系數(shù)之積；t->exp=p->exp+q->exp; /項之指數(shù)為LA,LB兩項指數(shù)之和；q=q->next;p=p->

12、;next; /p指針移動；q=LB->next; /q指針復(fù)位為LB->next；t->next=NULL; /為最后的結(jié)點的next賦空；head=Polysort(head); /調(diào)用Polysort排序函數(shù)對多項式鏈表進行降序排序；return head; /返回頭結(jié)點；（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ù)及運行結(jié)果1正常測試數(shù)據(jù)和運行結(jié)果2異常測試數(shù)據(jù)及運行結(jié)果如輸入的字符不是數(shù)字，則無法處理，如：a 2 程序無法繼續(xù)運行六調(diào)試情況，設(shè)計技巧及體會1改進方案多項式相成這個程序缺少對異常的處理，如果用戶輸入一些異常的字符程序?qū)o法繼續(xù)

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

16、include<stdlib.h>#include<malloc.h>typedef struct Polynodeint coef;/系數(shù)int exp;/指數(shù)struct Polynode *next;Polynode,*Polylist;/多項式鏈表升序排序Polylist Polysort(Polylist head)Polynode *first,*move,*p,*q; /first移動指針變量 move 被移動項指針變量p,q臨時指針變量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) /判斷待插入項指數(shù)是否與首項相等；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) /判斷待插入項指數(shù)是否

18、大于第一個項的指數(shù)；head->next=move;move->next=p;else if(p->next=NULL) /判斷下一項是否為空；p->next=move;move->next=NULL;else /待插入項指數(shù)插入位置在首末項之間； q=p; /移動臨時變量指針p,qp=p->next;while(1)if(p->exp=move->exp) /判斷待插入項指數(shù)是否與首項相等；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) /判斷待插入項指數(shù)是否大于當(dāng)前項的指數(shù)；q->next=move;move->next=p;break;if(p->next=NULL) /判斷下一項是否為空；p->next=move;move->next=NULL;break;q=p; /移動臨時變量指針p,q；p=p->next;p=head->next; /使p,q指針重新指到初始化位置；q=head;move=first;return head; /返回頭結(jié)

20、點；/多項式創(chuàng)建(頭插法)Polylist creat()Polynode *head,*p,*newnode;/head：頭指針 newnode:新結(jié)點指針 p：臨時指針變量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ù)）和exp（指數(shù)）不全為0；if(c=0)

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

22、數(shù)對多項式鏈表進行降序排序；return head; /返回頭結(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);/開辟一個新結(jié)點，并使之成為新鏈表的頭結(jié)點；t=head;while(p!=NULL)while(q!=NULL)newnode=(Polynode *)ma

23、lloc(sizeof(Polynode);/開辟一個新結(jié)點；t->next=newnode;t=t->next;t->coef=p->coef*q->coef; /項之系數(shù)為LA,LB兩項系數(shù)之積；t->exp=p->exp+q->exp; /項之指數(shù)為LA,LB兩項指數(shù)之和；q=q->next;p=p->next; /p指針移動；q=LB->next; /q指針復(fù)位為LB->next；t->next=NULL; /為最后的結(jié)點的next賦空；head=Polysort(head); /調(diào)用Polysort排序函數(shù)

24、對多項式鏈表進行降序排序；return head; /返回頭結(jié)點；/輸出函數(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