一元n次多项式定义如下：

其中Ai​为实数，i为不小于0的整数。在完成“一元n次多项式输入输出”题目的基础上实现一元n次多项式的加法。要求用链表实现上述一元n次多项式的操作。

输入格式:

有两个一元n次多项式，例如分别为：
f(X)=3X2+ X+1
g(X)=−2X2−X-1
其中系数为实数,指数取不小于0的整数。输入分为2行，第1行为第1个一元n次多项式，第1个一元n次多项式按照第1项系数,指数 第2项系数,指数 .... 的格式输入，系数和指数以“,”分割，各项的系数和指数之间以空格分割，输入一元n次多项式不要求按指数有序排列，最后以 0,0（即系数=0,指数=0）表示结束。第2行为第2个一元n次多项式，输入格式与第1个一元n次多项式相同。对上面的两个一元n次多项式：

输入样例:

3,2 1,1 1,0 0,0
-2,2 -1,1 -1,0 0,0

输出格式:

输出分为以下3行：第1行输出第1个一元n次多项式，第2行输出第2个一元n次多项式，第3行输出两个一元n次多项式的和。输出要求一元n次多项式的高次项在前，低次项在后，即按指数由大到小排列，实数保留小数点后面1位数，一元多项式为f(X)=0时，输出为f(X)=0.0。对上面2个一元n次多项式的输出为：

输出样例:

f(X)=3.0X^2+X+1.0
g(X)=-2.0X^2-X-1.0
f(X)+g(X)=X^2

#include <stdio.h>
#include <stdlib.h>typedef struct PolynomialNode    //定义了一个名为PolynomialNode的结构体，用于表示多项式中的一项
{double coefficient;          //系数int exponent;                //指数struct PolynomialNode *next; //指针域
} PolynomialNode;PolynomialNode* createNode(double coefficient, int exponent) 
{PolynomialNode *newNode = (PolynomialNode*)malloc(sizeof(PolynomialNode));newNode->coefficient = coefficient;newNode->exponent = exponent;newNode->next = NULL;return newNode;
}void insertNode(PolynomialNode** head, double coefficient, int exponent) 
{                     //将一个新的项插入到多项式链表中PolynomialNode* newNode = createNode(coefficient, exponent);if (*head == NULL || exponent > (*head)->exponent) {newNode->next = *head;  //如果新项的指数大于当前链表头部的指数*head = newNode;        //或者链表为空，则将新项置于链表头部} else {                           //否则，遍历链表找到合适的位置插入新项PolynomialNode* current = *head;while (current->next!= NULL && current->next->exponent > exponent) {              //当前节点的下指针不为空&&当前节点的下指针的指数>当前节点的current = current->next;  //refresh当前与下一个}if (current->exponent == exponent) //如果新项的指数与链表中的某项指数相同，则合并系数{current->coefficient += coefficient;free(newNode);} else {newNode->next = current->next;current->next = newNode;}}
}void printPolynomial(PolynomialNode* head, const char* name) 
{if (head == NULL) {printf("%s=0.0\n", name);return;}PolynomialNode* current = head;int firstTerm = 1;printf("%s=", name);while (current!= NULL) {if (current->coefficient == 0) //系数为0{current = current->next;   //跳过当前项continue;}if (current->coefficient < 0)  //系数小于0{if (!firstTerm)            //不是第一项{if (current->exponent == 1) {printf("-X");} else if (current->exponent > 1) {if (current->coefficient == -1.0)  //特殊判断{printf("-X^%d", current->exponent);} else {printf("%.1fX^%d", current->coefficient, current->exponent);}} else         //是第一项{printf("%.1f", current->coefficient);}} else {if (current->exponent == 1) {printf("-X");} else if (current->exponent > 1) {if (current->coefficient == -1.0) {printf("-X^%d", current->exponent);} else {printf("%.1fX^%d", current->coefficient, current->exponent);}} else {printf("%.1f", current->coefficient);}firstTerm = 0;}} else         //系数大于0{if (!firstTerm) {if (current->exponent == 1) {printf("+X");} else if (current->exponent > 1) {if (current->coefficient == 1.0) {printf("+X^%d", current->exponent);} else {printf("+%.1fX^%d", current->coefficient, current->exponent);}} else {printf("+%.1f", current->coefficient);}} else {if (current->exponent == 1) {printf("X");} else if (current->exponent > 1) {if (current->coefficient == 1.0) {printf("X^%d", current->exponent);} else {printf("%.1fX^%d", current->coefficient, current->exponent);}} else {printf("%.1f", current->coefficient);}firstTerm = 0;}}current = current->next;}printf("\n");
}void freePolynomial(PolynomialNode* head) 
{PolynomialNode* current = head;while (current!= NULL) {PolynomialNode* next = current->next;free(current);current = next;}
}PolynomialNode* addPolynomials(PolynomialNode* poly1, PolynomialNode* poly2) 
{PolynomialNode* result = NULL;PolynomialNode* current1 = poly1;PolynomialNode* current2 = poly2;while (current1!= NULL || current2!= NULL) {             //循环会一直执行，直到两个输入链表都遍历完double coefficient;int exponent;if (current1 == NULL)      //第一个多项式链表已经遍历完{                         //从第二个多项式链表current2中取当前项的系数和指数coefficient = current2->coefficient;exponent = current2->exponent;current2 = current2->next;} else if (current2 == NULL) //第二个多项式链表已经遍历完{                         //从第一个多项式链表current1中取当前项的系数和指数coefficient = current1->coefficient;exponent = current1->exponent;current1 = current1->next;} else if (current1->exponent > current2->exponent) //第一个多项式链表中的项指数较大{                                                //取第一个多项式链表当前项的系数和指数coefficient = current1->coefficient;exponent = current1->exponent;current1 = current1->next;} else if (current1->exponent < current2->exponent) //第二个多项式链表中的项指数较大{                                                //取第二个多项式链表当前项的系数和指数coefficient = current2->coefficient;exponent = current2->exponent;current2 = current2->next;} else                         //两个多项式链表当前项的指数相同，将它们的系数相加作为新的系数{coefficient = current1->coefficient + current2->coefficient;exponent = current1->exponent;current1 = current1->next;current2 = current2->next;}if (coefficient!= 0) {insertNode(&result, coefficient, exponent);}}return result;
}int main() 
{PolynomialNode* poly1 = NULL;PolynomialNode* poly2 = NULL;double coefficient;int exponent;while (scanf("%lf,%d", &coefficient, &exponent) && coefficient!= 0 || exponent!= 0) {if (coefficient == 0 && exponent == 0) {break;}insertNode(&poly1, coefficient, exponent);}while (scanf("%lf,%d", &coefficient, &exponent) && coefficient!= 0 || exponent!= 0) {if (coefficient == 0 && exponent == 0) {break;}insertNode(&poly2, coefficient, exponent);}// 合并多项式 poly2 中的同类项PolynomialNode* tempPoly2 = poly2;while (tempPoly2!= NULL && tempPoly2->next!= NULL) {if (tempPoly2->exponent == tempPoly2->next->exponent || (tempPoly2->exponent == 1 && tempPoly2->next->exponent == 1)) {tempPoly2->coefficient += tempPoly2->next->coefficient;PolynomialNode* toFree = tempPoly2->next;tempPoly2->next = tempPoly2->next->next;free(toFree);} else {tempPoly2 = tempPoly2->next;}}printPolynomial(poly1, "f(X)");printPolynomial(poly2, "g(X)");PolynomialNode* sum = addPolynomials(poly1, poly2);printf("f(X)+g(X)");if (sum == NULL) {printf("0.0\n");} else {printPolynomial(sum, "");}freePolynomial(poly1);freePolynomial(poly2);freePolynomial(sum);return 0;
}