4.一元多项式相乘

题目说明：

　　要求采用链表形式，求两个一元多项式的乘积：h3 = h1*h2。函数原型为：void multiplication( NODE * h1, NODE * h2, NODE * h3 )。

输入：

　　输入数据为两行，分别表示两个一元多项式。每个一元多项式以指数递增的顺序输入多项式各项的系数（整数）、指数（整数）。

　　例如：1+2x+x2表示为：<1,0>,<2,1>,<1,2>,

输出：

　　以指数递增的顺序输出乘积： <系数,指数>,<系数,指数>,<系数,指数>,

　　零多项式的输出格式为：<0,0>,

说明：本题目有预设代码，只要提交你编写的函数即可。

预设代码

前置代码（含注释）

#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; // 初始化指针 p 指向头节点while ((c = getchar()) != '\n') // 从标准输入读入字符，直到遇到换行符为止{if (c == '<') // 遇到左尖括号，开始解析多项式项{sum = 0; // 初始化 sum 变量为 0，用于存储系数或指数sign = 1; // 初始化 sign 变量为 1，用于存储正负号flag = 1; // 初始化 flag 变量为 1，用于标识当前解析的是系数还是指数}else if (c == '-') // 遇到减号，表示下一个解析出来的数为负数sign = -1;else if (c >= '0' && c <= '9') // 如果当前字符是数字字符{sum = sum * 10 + c - '0'; // 将当前字符转换为数字并累加到 sum 变量中}else if (c == ',') // 遇到逗号，表示当前解析的是系数，接下来将解析指数{if (flag == 1) // 如果 flag 为 1，说明上一次解析的是系数{x = sign * sum; // 将系数乘以正负号保存到变量 x 中sum = 0; // 初始化 sum 变量为 0，用于存储下一个解析出来的指数flag = 2; // 将 flag 置为 2，表示接下来要解析指数sign = 1; // 初始化 sign 变量为 1，用于存储正负号}}else if (c == '>') // 遇到右尖括号，表示本次项的解析结束{NODE* newNode = (NODE*)malloc(sizeof(NODE)); // 创建新的节点newNode->coef = x; // 设置节点的系数为之前解析出来的值 xnewNode->exp = sign * sum; // 设置节点的指数为之前解析出来的值乘以正负号newNode->next = NULL; // 将节点的指针域指向 NULLp->next = newNode; // 将新节点插入到当前链表中p = p->next; // 将指针 p 移动到下一个节点sum = 0; // 初始化 sum 变量为 0，用于存储下一个解析出来的数sign = 1; // 初始化 sign 变量为 1，用于存储正负号flag = 0; // 将 flag 置为 0，表示下一次解析的将是系数}}
}// 输出多项式函数
void output(NODE* head)
{NODE* p = head->next;while (p != NULL){printf("<%d,%d>,", p->coef, p->exp);p = p->next;}printf("\n");
}int main()
{NODE* head1, * head2, * head3;head1 = (NODE*)malloc(sizeof(NODE));input(head1); // 输入多项式 h1head2 = (NODE*)malloc(sizeof(NODE));input(head2); // 输入多项式 h2head3 = (NODE*)malloc(sizeof(NODE));head3->next = NULL;multiplication(head1, head2, head3); // 计算 h1 和 h2 的乘积，并存储在 h3 中output(head3); // 输出乘积结果return 0;
}

提交代码 （含注释）

void multiplication(NODE* h1, NODE* h2, NODE* h3)
{NODE* p1 = h1->next, * p2 = h2->next, * p3;while (p1 != NULL){p3 = h3; // 初始化p3为h3的头节点while (p2 != NULL){// 乘法运算int coef = p1->coef * p2->coef;int exp = p1->exp + p2->exp;if (coef != 0) // 仅当乘积项的系数不为0时才进行插入操作{// 查找插入位置，使链表按指数升序排列while (p3->next != NULL && p3->next->exp < exp){p3 = p3->next;}if (p3->next != NULL && p3->next->exp == exp){// 指数相同，合并多项式项的系数p3->next->coef += coef;}else{// 指数不同，插入新节点NODE* newNode = (NODE*)malloc(sizeof(NODE));newNode->coef = coef;newNode->exp = exp;newNode->next = p3->next;p3->next = newNode;}}p2 = p2->next; // 内层循环迭代至下一项}p1 = p1->next; // 外层循环迭代至下一项p2 = h2->next; // 重置p2为h2的头节点}// 删除系数为0的多项式项p3 = h3;while (p3->next != NULL){if (p3->next->coef == 0){// 系数为0，删除节点NODE* temp = p3->next;p3->next = p3->next->next;free(temp);}else{p3 = p3->next;}}// 处理结果为空的情况，插入零多项式的节点if (h3->next == NULL){NODE* newNode = (NODE*)malloc(sizeof(NODE));newNode->coef = 0;newNode->exp = 0;newNode->next = NULL;h3->next = newNode;}
}