[C++] 实现一元多项式相加的数据结构 |21xrx.com

[C++] 实现一元多项式相加的数据结构

2023-06-22 09:09:50 深夜i 15 0

C++ 一元多项式相加数据结构

为实现一元多项式相加的数据结构，我们可以使用C++语言中的链表作为底层数据结构。每个链表节点表示一个项，包含两个数据成员：系数和指数。系数是一个浮点数，指数是一个整数。

首先，我们需要定义一个结构体来表示链表节点：

struct PolyNode {
  float coeff;  // 系数
  int expn;    // 指数
  PolyNode* next; // 指向下一个节点的指针
};

然后，我们可以定义一个类来封装这个数据结构：

class Polynomial {
private:
  PolyNode* head; // 指向链表头节点的指针
public:
  Polynomial();            // 构造函数
  ~Polynomial();           // 析构函数
  void insert(float coeff, int expn); // 插入一项
  friend Polynomial operator+(const Polynomial& lhs, const Polynomial& rhs); // 加法运算符重载
};

上面的代码中，构造函数和析构函数分别用于初始化和清理链表。插入函数用于向链表中插入一项。加法运算符重载函数用于将两个多项式相加。

加法运算符重载函数的实现如下：

Polynomial operator+(const Polynomial& lhs, const Polynomial& rhs) {
  Polynomial result;
  PolyNode* p1 = lhs.head->next;
  PolyNode* p2 = rhs.head->next;
  PolyNode* tail = result.head;
  while (p1 != nullptr && p2 != nullptr) {
    if (p1->expn == p2->expn) {
      float sum = p1->coeff + p2->coeff;
      if (sum != 0) {
        tail->next = new PolyNode nullptr;
        tail = tail->next;
      }
      p1 = p1->next;
      p2 = p2->next;
    } else if (p1->expn > p2->expn) {
      tail->next = new PolyNodep1->coeff;
      tail = tail->next;
      p1 = p1->next;
    } else {
      tail->next = new PolyNode p2->expn;
      tail = tail->next;
      p2 = p2->next;
    }
  }
  while (p1 != nullptr) {
    tail->next = new PolyNodep1->coeff;
    tail = tail->next;
    p1 = p1->next;
  }
  while (p2 != nullptr) {
    tail->next = new PolyNodep2->coeff;
    tail = tail->next;
    p2 = p2->next;
  }
  return result;
}

加法运算符重载函数先定义一个新的多项式对象result，并初始化其头节点的指针tail。同时定义两个指针p1，p2，分别指向被加的两个多项式的第一个节点。

然后，我们开始遍历两个多项式的链表，并将相同指数的项相加。如果相同项的系数之和不为零，则创建一个新的节点，并将其插入到新的多项式中。如果其中一个多项式的指数大于另一个，则将该项插入到新的多项式中。

最后，如果其中一个多项式遍历完了，则将另一个多项式的剩余项直接插入到新的多项式中。最后返回新的多项式result即可。

现在我们已经实现了一元多项式相加的数据结构。我们可以通过以下代码来测试它：

Polynomial p1, p2, p3;
p1.insert(2.3, 2);
p1.insert(3.4, 1);
p1.insert(-1.2, 0);
p2.insert(3.5, 3);
p2.insert(-2.4, 2);
p2.insert(5.6, 1);
p2.insert(-3.1, 0);
p3 = p1 + p2;
// 输出p3的所有项
PolyNode* p = p3.head->next;
while (p != nullptr) {
  std::cout << p->coeff << "x^" << p->expn << " + ";
  p = p->next;
}

上面的代码中，我们首先创建了两个多项式p1和p2，并将它们分别初始化为2.3x^2+3.4x-1.2和3.5x^3-2.4x^2+5.6x-3.1。然后，我们使用加法运算符将它们相加，并将结果赋值给一个新的多项式p3。

最后，我们遍历p3的所有项，并输出其系数和指数。输出结果为5.6x^3-0.1x^2+9x-4.3。

上一篇: idea打包java可执行jar包

下一篇: C++编程练习题目与解答

评论区

相似文章