一元稀疏多项式算法实现

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

望采纳

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

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

#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);
    }