一、引言

主要思路：相同指数的项系数相加，其余部分进行拷贝。

二、多项式加法运算

采用不带头结点的单向链表，按照指数递减的顺序排列各项。

/* c语言实现 */

strct PolyNode{
  int coef;  // 系数
  int expon;  // 指数
  struct PolyNode *link; // 指向下一个结点的指针
};
typedef struct PolyNode *Polynomial;
Polynomial P1, P2;

2.1 算法思路

两个指针P1和P2分别指向这两个多项式第一个结点，不断循环：

P1->expon == P2->expon：系数相加，若结果不为0，则作为结果多项式对应项的系数。同时，P1和P2都分别指向下一项；
P1->expon > P2->expon：将P1的当前项存入结果多项式，并使P1指向下一项；
P1->expon < P2->expon：将P2的当前项存入结果多项式，并使P2指向下一项；

当某一多项式处理完时，将另一个多项式的所有结点依次复制到结果多项式中去。

/* c语言实现 */

Polynomial PolyAdd(Polynomial P1, Polynomian P2)
{
  Polynomial front, rear, temp;
  int sum;
  rear = (Polynomial)malloc(sizeof(struct PolyNode)); // 为方便表头插入，先产生一个临时空节点作为结果多项式链表头
  front = rear; // 由front记录结果多项式链表头结点
  while (P1 && P2) // 当两个多项式都有非零项待处理时
    switch(Compare(P1->expon, P2->expon)){
        case1: // P1中的数据项指数较大
        	Attach(P1->coef, P1->expon, &rear);
        	P1 = P1->link;
        	break;
        case-1: // P2中的数据项指数较大
        	Attach(P2->coef, P2->expon, &rear);
        	P2 = P2->link;
        	break;
     		case 0: // 两项数据项指数相等
        	sum = P1->coef + P2->coef;
        	if (sum) Attach(sum, P1->expon, &rear); // 判断系数和是否为0
        	P1 = P1->link;
        	P2 = P2->link;
        	break;  
    }
  // 讲未处理完的另一个多项式的所有节点一次复制到结果多项式中去
  for (; P1; P1 = P1->link) Attach(P1->coef, P1->expon, &rear);
  for (; P2; P2 = P2->link) Attach(P2->coef, P2->expon, &rear);
  rear->link = NULL;
  temp = front;
  front = front->link; // 令front指向结果多项式第一个非零项
  free(temp); // 释放临时空表头结点
  return front;
}

/* c语言实现 */

void Attach(int c, int e, Polynomial *pRear)
{
  /* 由于在本函数中需要改变当前结果表达式尾项指针的值，
  所以由函数传递进来的是结点指针的地址，*pRear指向尾项 */
  Polynomial P;
  
  P = (Polynomial)malloc(siezeof(struct PolyNode)); // 申请新结点
  P->coef = c; // 对新结点赋值
  P->expon = e;
  P-Llink = NULL;
  // 将P指向的新结点插入到当前结果表达式尾项的后面
  (*pRear)->link=P;
   *pRear = P; // 修改pRear值
}

def adds(l1, l2):  # l1,l2为链表,且不为空
    p1 = l1.head
    p2 = l2.head
    addRes = []
    while (p1 is not None) and (p2 is not None):  # 当p1和p2都部位空时，进行运算
        tmp1_exp = p1.get_data()[1]  # 获取p1指针处节点的指数
        tmp2_exp = p2.get_data()[1]  # 获取p2指针处节点的指数

        # 当指数相同时，系数相加，指数不变
        if tmp1_exp == tmp2_exp:
            addRes.append([p1.get_data()[0] + p2.get_data()[0], p1.get_data()[1]])
            p1 = p1.next  # 指针指向下一个节点
            p2 = p2.next

        # 当指数不相同时，选择较大的指数项存到结果中
        if tmp1_exp > tmp2_exp:
            addRes.append([p1.get_data()[0], p1.get_data()[1]])
            p1 = p1.next
        if tmp1_exp < tmp2_exp:
            addRes.append([p2.get_data()[0], p2.get_data()[1]])
            p2 = p2.next

    # 对于链表中剩余的节点添加到结果中
    while p1 is not None:
        addRes.append([p1.get_data()[0], p1.get_data()[1]])
        p1 = p1.next
    while p2 is not None:
        addRes.append([p2.get_data()[0], p2.get_data()[1]])
        p2 = p2.next

    # 此时的addRes结果
    # addRes [[5, 20], [-4, 4], [-5, 2], [9, 1], [-2, 0]]
    # 列表中每一项代表一各指数项，其中第一个元素代表系数，第二个元素代表指数。如[5，20]：5x^20

    # 以下是对addRes进行变形处理
    res1 = []
    for item in addRes:
        if item[0] != 0:  # 如果指数为0，即存在抵消情况，此时不应该输出
            res1.append(item[0])
            res1.append(item[1])
    if len(res1) == 0:  # 如果结果为0,需要输出：0  0
        return [0, 0]

    # 此时的输出结果变为
    # [5,20,-4,4,-5,2,9,1,-2,0]
    return res1