21xrx.com
2025-03-21 22:18:40 Friday
文章检索 我的文章 写文章
C++实现单链表形式的一元多项式
2023-07-13 01:17:09 深夜i     --     --
C++ 单链表 一元多项式

单链表是一种非常常见的数据结构，而在数学领域中，多项式也是一种非常重要的概念。因此，将两者结合起来，实现单链表形式的一元多项式，是一项非常有意义的任务。

在C++中，实现单链表形式的一元多项式，有以下几个步骤：

1. 定义一元多项式的项(节点)结构体

在单链表中，每个节点都需要存储数据和指向下一个节点的指针。而在一元多项式中，每个项包含系数和指数两个数据。因此，我们可以定义一个节点结构体，如下所示：

struct Term {
  double coef; // 系数
  int exp;   // 指数
  Term* next;  // 指向下一个节点的指针
};

2. 创建单链表，保存一元多项式的项

在创建单链表时，我们需要先创建一个头节点。头节点不存储任何数据，只是为了方便操作而存在。接着，我们可以逐个插入项，保证它们按照指数递减的顺序排列。具体代码如下：

Term* create_poly() {
  Term* head = new Term 0; // 创建头节点
  Term* tail = head;           // 创建尾节点指针，初始指向头节点
  double coef;
  int exp;
  std::cout << "请输入一元多项式的项，按照指数递减的顺序输入，输入0 0表示输入结束。\n";
  std::cin >> coef >> exp;        // 输入首项系数和指数
  while (exp != 0) {           // 如果输入的不是末项
    Term* t = new Term nullptr; // 创建新节点
    tail->next = t;           // 将新节点追加到尾节点后面
    tail = t;              // 更新尾节点指针
    std::cin >> coef >> exp;      // 继续输入下一项
  }
  return head;
}

3. 输出一元多项式

输出一元多项式时，我们需要对每一项进行格式化，并按照一个项一个项的顺序输出。具体代码如下：

void print_poly(Term* head) {
  Term* p = head->next;
  while (p != nullptr) {
    std::cout << p->coef;
    if (p->exp == 1)
      std::cout << "x";
     else if (p->exp != 0) {
      std::cout << "x^" << p->exp;
    }
    if (p->next != nullptr) {
      std::cout << " + ";
    }
    p = p->next;
  }
  std::cout << std::endl;
}

4. 实现一元多项式的加法

一元多项式的加法可以分为以下几个步骤：

- 遍历两个单链表，将其中相同的项合并存储在一个新的单链表中；

- 将两个单链表中剩余的项追加到新的单链表中；

- 返回新的单链表。

具体代码如下：

Term* poly_add(Term* l1, Term* l2) {
  Term* head = new Term nullptr; // 创建头节点
  Term* tail = head;           // 创建尾节点指针，初始指向头节点
  Term* p1 = l1->next;          // p1指向l1的首项
  Term* p2 = l2->next;          // p2指向l2的首项
  while (p1 != nullptr && p2 != nullptr) {
    if (p1->exp == p2->exp) {      // 如果两个项的指数相同
      double coef = p1->coef + p2->coef;
      if (coef != 0) {        // 如果系数不为0
        Term* t = new Term coef; // 创建新节点
        tail->next = t;       // 将新节点追加到尾节点后面
        tail = t;          // 更新尾节点指针
      }
      p1 = p1->next;         // p1和p2都向后移动
      p2 = p2->next;
    } else if (p1->exp > p2->exp) {   // 如果l1中的项指数大于l2中的项指数
      Term* t = new Term p1->exp; // 创建新节点
      tail->next = t;         // 将新节点追加到尾节点后面
      tail = t;            // 更新尾节点指针
      p1 = p1->next;         // p1向后移动
    } else {              // 否则，l1中的项指数小于l2中的项指数
      Term* t = new Term p2->exp; // 创建新节点
      tail->next = t;         // 将新节点追加到尾节点后面
      tail = t;            // 更新尾节点指针
      p2 = p2->next;         // p2向后移动
    }
  }
  while (p1 != nullptr) {         // 将l1中剩余的项追加到新链表中
    Term* t = new Term p1->coef;
    tail->next = t;
    tail = t;
    p1 = p1->next;
  }
  while (p2 != nullptr) {         // 将l2中剩余的项追加到新链表中
    Term* t = new Term nullptr;
    tail->next = t;
    tail = t;
    p2 = p2->next;
  }
  return head;
}

5. 测试

最后，我们可以编写测试函数，测试上述代码的正确性。具体代码如下：

int main() {
  std::cout << "请输入第一个一元多项式：\n";
  Term* l1 = create_poly();
  std::cout << "第一个一元多项式为：";
  print_poly(l1);
  std::cout << "请输入第二个一元多项式：\n";
  Term* l2 = create_poly();
  std::cout << "第二个一元多项式为：";
  print_poly(l2);
  Term* l3 = poly_add(l1, l2);
  std::cout << "两个一元多项式的和为：";
  print_poly(l3);
  return 0;
}

通过上述步骤，我们成功地实现了单链表形式的一元多项式，在进行加法等运算时也可以轻松地使用。

  
  

评论区