七、一元多项式相乘
七、一元多項式相乘
題目描述
要求采用鏈表形式，求兩個一元多項式的乘積：h3 = h1*h2。函數原型為：void multiplication( NODE * h1, NODE * h2, NODE * h3 )。
輸入：
輸入數據為兩行，分別表示兩個一元多項式。每個一元多項式以指數遞增的順序輸入多項式各項的系數（整數）、指數（整數）。
例如：1+2x+x2表示為：<1,0>,<2,1>,<1,2>,
輸出：
以指數遞增的順序輸出乘積： <系數,指數>,<系數,指數>,<系數,指數>,
零多項式的輸出格式為：<0,0>,
說明：本題目有預設代碼，只要提交你編寫的函數即可。
預設代碼：
/* PRESET CODE BEGIN - NEVER TOUCH CODE BELOW */#include <stdio.h> #include <stdlib.h>typedef struct node { int coef, exp;struct node *next; } NODE;void multiplication( NODE *, NODE * , NODE * ); void input( NODE * ); void output( NODE * );void input( NODE * head ) { int flag, sign, sum, x;char c;NODE * p = head;while ( (c=getchar()) !='\n' ){if ( c == '<' ){ sum = 0;sign = 1;flag = 1;}else if ( c =='-' )sign = -1;else if( c >='0'&& c <='9' ){ sum = sum*10 + c - '0';}else if ( c == ',' ){ if ( flag == 1 ){ x = sign * sum;sum = 0;flag = 2;sign = 1;}}else if ( c == '>' ){ p->next = ( NODE * ) malloc( sizeof(NODE) );p->next->coef = x;p->next->exp = sign * sum;p = p->next;p->next = NULL;flag = 0;}} }void output( NODE * head ) {while ( head->next != NULL ){ head = head->next;printf("<%d,%d>,", head->coef, head->exp );}printf("\n"); }int main() { NODE * head1, * head2, * head3;head1 = ( NODE * ) malloc( sizeof(NODE) );input( head1 );head2 = ( NODE * ) malloc( sizeof(NODE) );input( head2 );head3 = ( NODE * ) malloc( sizeof(NODE) );head3->next = NULL;multiplication( head1, head2, head3 );output( head3 );return 0; }/************************************** void multiplication( NODE *, NODE * , NODE * ) {This function is wating for you. } ***************************************//* PRESET CODE END - NEVER TOUCH CODE ABOVE */| 測試用例 1 | <1,0>,<2,1>,<1,2>, <1,0>,<1,1>, | <1,0>,< 3,1>,< 3,2>,<1,3>, | 1秒 | 1024KB | 0 |
| 測試用例 2 | <0,0>, <1,20>,<-8,40>, | <0,0>, | 1秒 | 1024KB | 0 |
| 測試用例 3 | <1,20>,<-8,40>, <0,0>, | <0,0>, | 1秒 | 1024KB | 0 |
| 測試用例 4 | <-1,0>,<1,1>, <1,0>,<1,1>, | <-1,0>,<1,2>, | 1秒 | 1024KB | 0 |
| 測試用例 5 | <5,0>,<10,1>, <2,0>,< 3,1>,<4,2>,<5,3>, | <10,0>,<35,1>,<50,2>,<65,3>,<50,4>, | 1秒 | 1024KB | 0 |
解題思路
乘法和加法不一樣，乘法必須對多項式中的每一項都進行相乘。
因為題目要以指數遞增的順序輸出乘積，在運算時還需要調整多項式之間的位置。
用三個指針 p1、p2、p3，p1用于建立第一個結點，p3記錄上一次的結點位置，幫助p2尋找指數對應位置的結點
對該結點的后一個結點進行判斷：
- 如果該結點后續為空，建立新結點
- 若后續不為空，則比較對應指數
- 指數相等則合并節點（若系數為空則刪除該結點）
- 指數較大則建立新結點插入
最后，不要忘了為零多項式建立結點進行輸出。
上機代碼
void multiplication(NODE *head1, NODE *head2, NODE *head3) {// 初始化NODE *p1, *p2, *p3;p1 = p2 = p3 = head3;NODE *h1 = head1->next, *h2 = head2->next;int coef = 0, exp = 0;//分項相乘相加while(h1 != NULL){while(h2 != NULL){coef = h1->coef * h2->coef;//處理系數if (coef == 0)//系數為0直接進入下一次{h2 = h2->next;continue;}exp = h1->exp + h2->exp;//處理指數if (p1->next == NULL)//創建第一個節點{NODE *s = (NODE*)malloc(sizeof(NODE));s->coef = coef;s->exp = exp;s->next = NULL;p1->next = s;}else{//找到指數對應位置的結點if(p3->next != NULL && exp > p3->next->exp)//指數大{p2 = p3;while(p2->next != NULL && exp > p2->next->exp){p2 = p2->next;p3 = p2;}}else//指數小{while(p2->next != NULL && exp > p2->next->exp){p2 = p2->next;p3 = p2;}}NODE *temp = p2->next;if(p2->next == NULL)//若該結點后為空，建立新結點{NODE *s = (NODE*)malloc(sizeof(NODE));s->coef = coef;s->exp = exp;s->next = NULL;p2->next = s;}else if(temp->exp == exp)//指數相等則合并節點{temp->coef += coef;if(temp->coef == 0)//值為0，則刪除節點{NODE *dele = temp->next;p2->next = dele;free(temp);}}else if(temp->exp > exp)//指數大則插入新結點{NODE *s = (NODE*)malloc(sizeof(NODE));s->coef = coef;s->exp = exp;p2->next = s;s->next = temp;}}//下一項h2 = h2->next;p2 = head3;}//一輪循環結束，h2從頭開始乘以下一項h2 = head2->next;h1 = h1->next;}//處理零多項式的情況if(head3->next == NULL){NODE *s = (NODE*)malloc(sizeof(NODE));s->coef = 0;s->exp = 0;s->next = NULL;head3->next = s;}return; } 《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀總結
