qq_58991159 2022-12-14 21:06 采纳率: 33.3%
浏览 84
已结题

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

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

编写一个能利用链表实现整系数多项式加法的程序。
根据提示,在右侧编辑器补充代码,利用链表实现整系数多项式的加法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;
}

我想要达到的结果

补全代码



  • 写回答

1条回答 默认 最新

  • 婉瑄|Vivian_ 2022-12-14 21:59
    关注

    代码如下,分两部分:

    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会被系统自动回收,所以加不加都一样。

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论 编辑记录

报告相同问题?

问题事件

  • 系统已结题 12月23日
  • 已采纳回答 12月15日
  • 创建了问题 12月14日

悬赏问题

  • ¥15 CMAKE+VS2019+QT5.15.2组合进行二次编译
  • ¥15 nginx 配置静态html访问 ,后台登录时页面始终被重定向到登录页,无法访问到后台的静态html页
  • ¥20 自动登录的j2ee程序编译
  • ¥15 fluent模拟静态气体扩散
  • ¥15 java根据模板,生成word文档,需要带目录
  • ¥15 广告联盟的兜底广告是什么意思
  • ¥15 如何证明高斯噪声的包络公式
  • ¥150 寻找王者荣耀开发作者,合作或者解答
  • ¥15 关于cpci总线的几个问题,别用人工智能回答
  • ¥15 乳腺癌数据集 相关矩阵 特征选择