21xrx.com
2024-11-05 18:38:20 Tuesday
登录
文章检索 我的文章 写文章
[C++] 实现一元多项式相加的数据结构
2023-06-22 09:09:50 深夜i     --     --
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。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复