（萌新写代码，欢迎各位大佬多多指教！）

假设我们已知多项式

   A：
讯享网             B: 

现在要求解这两个多项式的和。

第一步：用什么方式储存多项式？需要储存的数据有多项式的系数和指数，所以很自然的想到我们可以定义一个结构体数组，如下：

//定义存储多项式的数组 typedef struct { double xishu; int exp; }arr[max];

 第二步：定义一个存储多项式的线性表，如下：

讯享网//定义单链表 typedef struct dxs { double xishu; int exp; struct dxs* next; }dxs;

第三步：思考一个问题，如果我们要将这两个多项式相加，必定是要挑出相同次数的项将它们相加，次数不同的项保留。所以要比较两个多项式的次数，我们有必要将它们按照次数递减（或者递增）排序。

在线性表中，我们可以一个一个结点的比较和排序：

如图1所示，这是一个线性表，head是他的头节点，p，r 分别为两个指针。这个线性表中的第一个数据即为p的数据域，第二个数据为r的数据域。

 我们可以先打断①号和②号之间的连接，即将p的指针域赋为空，如图2所示，这样就得到了只含一个结点的有序表（即节点①）。

 然后将r赋予p，r继续为p的下一格，同时引入指针q，将头节点head赋予指针q，如图三所示。

而我们引入指针q实则是为了判断①号格和②号格的exp大小，若①的exp大于②的exp，则如图四所示。将①赋予q，后打断②③之间的连接，p，r 继续向后移位一格。

这样的操作可以一直进行下去，直到p为空。

用代码表示出来即为下面：

void sort(dxs*& head) { dxs* p = head->next, * q, * r; if (p != NULL) { r = p->next; p->next = NULL; p=r; while (p != NULL) { r = p->next; q = head; while (q->next != NULL && q->next->exp > p->exp) { q = q->next; } p->next = q->next; q->next = p; p = r; } } }

第四步：根据上述过程，我们已经得到了两个有序线性表，现在只需要实现加法运算。这就意味着我们需要新建一个线性表来存储两个多项式的和。而多项式在相加的过程中，我们要比较他们的指数，指数相同的系数相加，然后存储到和的线性表中，指数不同的直接保留到和的线性表中。

以题目为例：现在得到有序多项式A ： 

和B：

则它们的线性表如下图五：

我们创建两个指针为la和lb，它们分别指向l1和l2的第一个节点，这样我们就可以开始比较相加了。

现在lb的exp大于la的exp，所以将lb的内容直接赋予到多项式和l3的线性表中，而lb则指向下一个节点，如图六所示。

 继续比较，现在la的exp和lb的exp相等，则应当将他们的系数相加，但例子中系数相加等于0，所以不需要存入l3，而la，lb都移动到下一个节点，如图七所示。（如若系数相加不等于0，则将相加后的系数连同次数一同存入l3中）

 以此类推，你会得到最终的结果l3，即为两个多项式的和。

（这里还有一种情况，即其中一个多项式已经运算结束，而另外一个多项式还有多余的项，直接将多余的项依次存入l3中）

代码实现如下：

讯享网//将有序多项式链表相加 void add(dxs* l1, dxs* l2, dxs*& l3) { dxs* la = l1->next, * lb = l2->next, * s, * t; double c; l3 = (dxs*)malloc(sizeof(dxs)); t = l3; while (la != NULL && lb != NULL) { if (la->exp > lb->exp) { s = (dxs*)malloc(sizeof(dxs)); s->xishu = la->xishu; s->exp = la->exp; t->next = s; t = s; la = la->next; } else if (la->exp < lb->exp) { s = (dxs*)malloc(sizeof(dxs)); s->xishu = lb->xishu; s->exp = lb->exp; t->next = s; t = s; lb = lb->next; } else { c = la->xishu + lb->xishu; if (c != 0) { s = (dxs*)malloc(sizeof(dxs)); s->xishu = c; s->exp = la->exp; t->next = s; t = s; } la = la->next; lb = lb->next; } } if (lb != NULL) la = lb; while (la != NULL) { s = (dxs*)malloc(sizeof(dxs)); s->xishu = la->xishu; s->exp = la->exp; t->next = s; t = s; la = la->next; } t->next = NULL; }

 ok，现在问题已经大致解决了，附上全过程的代码：

#include <iostream> using namespace std; //定义单链表 typedef struct dxs { double xishu; int exp; struct dxs* next; }dxs; //定义存储多项式的数组 typedef struct { double xishu; int exp; }arr[20]; //根据数组中的元素创建单链表 void creat(dxs*& L, arr a, int n) { dxs* s, * r; int i; L = (dxs*)malloc(sizeof(dxs)); L->next = NULL; r = L; for (i = 0; i < n; i++) { s = (dxs*)malloc(sizeof(dxs)); s->xishu = a[i].xishu; s->exp = a[i].exp; r->next = s; r = s; } r->next = NULL; } //输出多项式 void print(dxs* l) { dxs* p=l->next; while (p != NULL) { if (p->xishu > 0) cout << "+"; if (p->exp==0) { cout << p->xishu; } else if (p->exp == 1) { cout << p->xishu << "x"; } else { cout << p->xishu << "x^" << p ->exp; } p = p->next; } } //对于多项式的链表进行指数高低的排序 void sort(dxs*& head) { dxs* p = head->next, * q, * r; if (p != NULL) { r = p->next; p->next = NULL; p=r; while (p != NULL) { r = p->next; q = head; while (q->next != NULL && q->next->exp > p->exp) { q = q->next; } p->next = q->next; q->next = p; p = r; } } } //将有序多项式链表相加 void add(dxs* l1, dxs* l2, dxs*& l3) { dxs* la = l1->next, * lb = l2->next, * s, * t; double c; l3 = (dxs*)malloc(sizeof(dxs)); t = l3; while (la != NULL && lb != NULL) { if (la->exp > lb->exp) { s = (dxs*)malloc(sizeof(dxs)); s->xishu = la->xishu; s->exp = la->exp; t->next = s; t = s; la = la->next; } else if (la->exp < lb->exp) { s = (dxs*)malloc(sizeof(dxs)); s->xishu = lb->xishu; s->exp = lb->exp; t->next = s; t = s; lb = lb->next; } else { c = la->xishu + lb->xishu; if (c != 0) { s = (dxs*)malloc(sizeof(dxs)); s->xishu = c; s->exp = la->exp; t->next = s; t = s; } la = la->next; lb = lb->next; } } if (lb != NULL) la = lb; while (la != NULL) { s = (dxs*)malloc(sizeof(dxs)); s->xishu = la->xishu; s->exp = la->exp; t->next = s; t = s; la = la->next; } t->next = NULL; } void main() { dxs* l1, * l2, * l3; arr a = { {1.2,0},{2.5,1},{3.2,3},{-2.5,5} }; arr b = { {-1.2,0},{2.5,1},{3.2,3},{2.5,5},{5.4,10} }; creat(l1, a, 4); creat(l2, b, 5); sort(l1); sort(l2); add(l1, l2, l3); print(l3); }