一元稀疏多项式算法实现

怎么用一个程序用顺序表实现一元稀疏多项式的加减法，用单链表实现乘法啊

望采纳

可以使用结构体来表示一个一元稀疏多项式的一项，并使用顺序表或单链表来存储多项式的各个项。

下面代码展示了如何使用顺序表来实现一元稀疏多项式的加法

#include <iostream>
#include <vector>

using namespace std;

struct Term {
  int coefficient;  // 系数
  int exponent;  // 指数
};

// 一元稀疏多项式类型
typedef vector<Term> Polynomial;

// 多项式加法
Polynomial operator+(const Polynomial& p1, const Polynomial& p2) {
  Polynomial result;  // 结果多项式
  int i = 0, j = 0;  // p1 和 p2 的指针
  while (i < p1.size() && j < p2.size()) {
    if (p1[i].exponent > p2[j].exponent) {
      // p1 的当前项的指数更大，将它加入结果
      result.push_back(p1[i++]);
    } else if (p1[i].exponent < p2[j].exponent) {
      // p2 的当前项的指数更大，将它加入结果
      result.push_back(p2[j++]);
    } else {
      // p1 和 p2 的当前项的指数相同，将它们的系数相加后加入结果
      result.push_back({p1[i].coefficient + p2[j].coefficient, p1[i].exponent});
      ++i;
      ++j;
    }
  }
  // 将 p1 和 p2 剩余的项加入结果
  while (i < p1.size()) result.push_back(p1[i++]);
  while (j < p2.size()) result.push_back(p2[j++]);
  return result;
}

int main() {
  Polynomial p1{{3, 5}, {2, 3}, {1, 1}};  // 3x^5 + 2x^3 + x
  Polynomial p2{{4, 5}, {3, 4}, {2, 2}, {1, 0}};  // 4x^5 + 3x^4 + 2x^2 + 1
  Polynomial p3 = p1 + p2;  // 计算 p1 + p2
  cout << "p1 = ";
  for (const auto& t : p1) {
    cout << t.coefficient << "x^" << t.exponent << " + ";
  }
  cout << endl;
  cout << "p2 = ";
  for (const auto& t : p2) {
    cout << t.coefficient << "x^" << t.exponent << " + ";
  }
  cout << endl;
  cout << "p1 + p2 = ";
  for (const auto& t : p3) {
    cout << t.coefficient << "x^" << t.exponent << " + ";
  }
  cout << endl;
  return 0;
}

输出结果

p1 = 3x^5 + 2x^3 + x^1 + 
p2 = 4x^5 + 3x^4 + 2x^2 + x^0 + 
p1 + p2 = 7x^5 + 3x^4 + 2x^3 + 2x^2 + x^1 + 

• 文章：一元稀疏多项式乘法问题 中也许有你想要的答案，请看下吧
• 除此之外, 这篇博客: 数据结构：一元多项式计算器（详解）中的 关于乘法 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

• 有了之前加法和乘法的思路，乘法就不用我说了。

  遍历A链的所有结点，遍历B链的所有结点，也就是双重循环，AXB的所有结点添加（insert）到新链中。

  因为我们规定的 insert 就是有序，不重复幂值。

  所以直接丢进去就行，不用考虑。

  void mul(LIST A, LIST B)
  {
      LIST head = (LIST)malloc(sizeof(struct node));
      head->NEXT = NULL;
      LIST i = A->NEXT;
      //if A NULL
      LIST j = B->NEXT;
      if(!i)
      {
          while(j)
          {
              insert(j->c, j->n, head);
              j = j->NEXT;
          }
          uptate(head);
          show(head);
          return;
      }
      //if B NULL
      if(!j)
      {
          while(i)
          {
              insert(i->c, i->n, head);
              i = i->NEXT;
          }
          uptate(head);
          show(head);
          return;
      }
      while(i){
          j = B->NEXT;
          while(j)
          {
              insert(i->c * j->c, i->n + j->n, head);
              j = j->NEXT;
          }
          i = i->NEXT;
      }
      uptate(head);
      show(head);
  }