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

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

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

3、圖(1)多項式鏈表升序排序函數(shù) PolylistPolysort(Polylisthead) Polynode*first,*move,*p,*q;/first移動指針 move被移動項指針 p,q臨時指針q=head; p=head->next; if(p=NULL)returnhead;/判斷鏈表是否為空；first=p->next; p->next=NULL; move=first; while(move!=NULL)/直接插入排序(鏈表排序) first=first->next; if(p->exp=move->exp)/判斷待插入項指數(shù)是否與首項相

4、等； p->coef+=move->coef;系數(shù)相加;free(move);/ 釋放空間；if(p->coef=0)/ 若系數(shù)相加和為0; q->next=p->next; free(p); /釋放空間； elseif(p->exp>move->exp)/判斷待插入項指數(shù)是否大于第一個項的指數(shù)；head->next=move; move->next=p; elseif(p->next=NULL)/判斷下一項是否為空； p->next=move;move->next=NULL;else/待插入項指數(shù)插入位置在首末項之

5、間； q=p;/移動臨時變量指針 p,qp=p->next; while if(p->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; i

6、f(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; returnhead;/ 返回頭結(jié)點； (2)多項式創(chuàng)建函數(shù) Polylistcreat() Polynode*head,*p,*newnode;/head :頭指針newnode:新結(jié)點指針 p：臨時指針變量intc,e;/ceof(系數(shù))和 exp (指數(shù))；head=(P

7、olynode*)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) scanf("%d%d",&c,&e);continue;/ 若 c 為 0,不開辟新結(jié)點； newnode=(Polynode*)malloc(sizeof(Polynode);/開辟個新結(jié)點；newnode

8、->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ù)對多項式鏈表進行降序排序； returnhead; / 返回頭結(jié)點； (3)多項式相乘函數(shù) PolylistPolymul(PolylistLA,PolylistLB) Polynode*head,*p,*q,*t,*newnod

9、e;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*)malloc(sizeof(Polynode);/開辟個新結(jié)點；t->next=newnode; t=t->next; t->coef=p->coef*q->coef;/項之系數(shù)為LA,

10、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ù)對多項式鏈表進行降序排序； returnhead;/返回頭結(jié)點； (4)輸出函數(shù) voidprint(Polylisthead) Polynode*p;p=head->next;if(p=NU

11、LL)printf("0");elsewhile(p!=NULL)/系數(shù)輸出if(p->coef=-1)printf("-");elseif(p->coef!=1)printf("%d",p->coef);/符號輸出if(p->exp!=0&&p->exp!=1)printf("XA");elseif(p->exp=1)printf("X");/指數(shù)輸出if(p->exp=0&&(p->coef=-1|p->c

12、oef=1)printf("1");if(p->exp<0)printf("(%d)",p->exp);elseif(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ù)字，

13、則無法處理，如：a2程序無法繼續(xù)運行六.調(diào)試情況，設(shè)計技巧及體會1 .改進方案多項式相成這個程序缺少對異常的處理，如果用戶輸入一些異常的字符程序?qū)o法繼續(xù)運 行，甚至導(dǎo)致死機。改進：加入異常處理，將各種用戶可能的輸入都包含在內(nèi)。2 .體會心得體會：此程序是使用鏈表完成的，一直以來比較習(xí)慣用順序表，通過這個程序加深了對 鏈表的理解。程序的排序部分較為復(fù)雜，根據(jù)哥次的高低排序的同時并合了同類項，哥次相同的系數(shù)相加存入前項，釋放合并項中后者空間，若系數(shù)相加和為。則釋放兩項空間。其實 想這段算法時很容易，真正實現(xiàn)卻是相當(dāng)不容易，可能是平時寫的代碼太少，真正把思想轉(zhuǎn)換成代碼困難還是比較大。七.參考文獻C

14、語言程序設(shè)計王曙燕主編科學(xué)出版社數(shù)據(jù)結(jié)構(gòu)一一C語言描述耿國華高等教育出版社 數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏清華大學(xué)出版社八.附錄：#include<stdio.h>#include<stdlib.h> #include<malloc.h> typedefstructPolynode intcoef;/ 系數(shù) intexp;/ 指數(shù) structPolynode*next; Polynode,*Polylist; /多項式鏈表升序排序 PolylistPolysort(Polylisthead) Polynode*first,*move,*p,*q;/first移動指針變量m

15、ove被移動項指針變量 p,q臨時指針變量 q=head; p=head->next; if(p=NULL)returnhead;/判斷鏈表是否為空；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);/ 釋放空間；if(p->coef=0)/若系數(shù)相加和為0;

16、q->next=p->next;free(p)；/釋放空間;elseif(p->exp>move->exp)/判斷待插入項指數(shù)是否大于第一個項的指數(shù);head->next=move;move->next=p;elseif(p->next=NULL)/判斷下一項是否為空;p->next=move;move->next=NULL; else/待插入項指數(shù)插入位置在首末項之間;q=p;p=p->next; while(1) /移動臨時變量指針p,qif(p->exp=move->exp)/判斷待插入項指數(shù)是否與首項相等;p

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

18、動臨時變量指針p,q ;p=head->next; 使p,q指針重新指到初始化位置;q=head;move=first;returnhead;/返回頭結(jié)點；/多項式創(chuàng)建(頭插法)Polylistcreat() Polynode*head,*p,*newnode; /head :頭指針 newnode:新結(jié)點指針 p：臨時指針變量 intc,e;/ceof(系數(shù))和 exp (指數(shù))；head=(Polynode*)malloc(sizeof(Polynode);/開辟一個新結(jié)點，并使之成為頭結(jié)點；p=head; printf("nt請輸入多項式中元素的系數(shù)和指數(shù)：n"

19、);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,&

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

21、olynode);/開辟一個新結(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->next;/p 指針移動； q=LB->n

22、ext;/q 指針復(fù)位為 LB->next ; t->next=NULL;/ 為最后的結(jié)點的 next賦空； head=Polysort(head);/ 調(diào)用Polysort 排序函數(shù)對多項式鏈表進行降序排序；returnhead;/返回頭結(jié)點;/輸出函數(shù)voidprint(Polylisthead)Polynode*p;p=head->next;if(p=NULL) printf("0"); else while(p!=NULL) /系數(shù)輸出 if(p->coef=-1) printf("-");elseif(p->coef!=1) printf(&q