结构体 链表实现多项式加法

Question

问题遇到的现象和发生背景

编写一个能利用链表实现整系数多项式加法的程序。
根据提示，在右侧编辑器补充代码，利用链表实现整系数多项式的加法Node* add_poly(Node* a, Node* b)。多项式a和b用链表表示，链表定义如下：

struct Node {
int order, coeff; // 次数 和 系数
Node* nxt; // 指向后一项的指针
}

多项式a和b保证每一项系数coeff都是整数，保证每一项次数order >= 0。输入order=-1表示输入结束。保证从链表的头到尾，次数递减，详见 sample case。

结果多项式的表示和a,b的规则一样，从最高次项到最低次项，不要包含系数为0的项。但是如果结果多项式等于0（即有且仅有常数项0）则需要包含该项。计算过程中涉及的整数加法不会溢出。

测试说明
平台会对你编写的代码进行测试：

测试输入：
3 2 -1 0 0 -1
1 5 -3 2 -1 0 0 -1
输入说明：
第一个多项式为3x^2-1
第二个多项式为x^5-3x^2-1
预期输出：
1 5
-2 0
输出说明：
结果多项式为x^5-2

操作环境、软件版本等信息

Windows11 visual studio

尝试过的解决方法

部分已知代码

#include<iostream>
using namespace std;

struct Node {
  int order, coeff;
  Node *nxt;
};

Node* add_poly(Node* a, Node* b) 
{

}

int main()
{
  Node *a = nullptr, *pa = nullptr, *b = nullptr, *pb = nullptr;
  int coef, orde;
  cin >> coef >> orde;
  while (orde >= 0) {
    Node* na = new Node;
    na->order = orde;
    na->coeff = coef;
    na->nxt = nullptr;
    if (pa) pa->nxt = na;
    pa = na;
    if (a == nullptr) a = pa;
    cin >> coef >> orde;
  }
  cin >> coef >> orde;
  while (orde >= 0) {
    Node* nb = new Node;
    nb->order = orde;
    nb->coeff = coef;
    nb->nxt = nullptr;
    if (pb)  pb->nxt = nb;
    pb = nb;
    if (b == nullptr) b = pb;
    cin >> coef >> orde;
  }
  
  Node* c = add_poly(a, b);
  
  while (c) {
    cout << c->coeff << ' '<< c->order << endl;
    c = c->nxt;
  }

  //要不要补上a,b,c三个链表的删除？
  return 0;
}

我想要达到的结果

补全代码

Answer 1

代码如下，分两部分：

1. 计算多项式相加；
2. 去除coefficient为0的项；

Node* add_poly(Node* a, Node* b) 
{
    // special cases
    if(a == nullptr)      return b;   // a is empty
    else if(b == nullptr) return a;   // b is empty
    Node temp;
    Node* dummy = &temp;
    while(a != nullptr && b != nullptr)
    {
        if(a->order > b->order)
        {
            dummy->nxt = a;
            a = a->nxt;
        }
        else if(a->order < b->order)
        {
            dummy->nxt = b;
            b = b->nxt;
        }
        else
        {
            dummy->nxt = new Node{a->order, a->coeff + b->coeff, nullptr};
            a = a->nxt;
            b = b->nxt;
        }
        dummy = dummy->nxt;
    }
    if(a != nullptr)
        dummy->nxt = a;
    else if(b != nullptr)
        dummy->nxt = b;
    // get rid of node which coeff is 0
    Node* head = temp.nxt;
    Node* prev = &temp;
    while(head != nullptr)
    {
        if(head->coeff == 0)
        {
            prev->nxt = head->nxt;
            Node* p = head;
            head = head->nxt;
            delete p;
            continue;
        }
        prev = head;
        head = head->nxt;
    }
    return temp.nxt;
}

另外，你问需不需要加上删除链表的代码：
答：严格来说加上更规范，因为所有heap allocated的memory都要delete；我的答案是不需要，因为当程序结束时，所有new的memory会被系统自动回收，所以加不加都一样。