c++ - (有效地)动态存储多项式

Question

我想要完成的是使用数组存储未知大小的多项式。我在互联网上看到的是使用一个数组，每个单元格都包含系数，度数是单元格编号，但这不是有效的，因为如果我们有一个多项式，如:6x^14+x+5。这意味着我们将从 1 到 13 的所有单元格都为零。我已经看过一些带有 vector 和链表的解决方案，但是有没有其他方法可以有效地解决这个问题，而无需使用 (std::vectors 或 std::列表)?

Answer 1

除非有令人信服的理由不这样做(这是一项要求您使用 C 样式数组的编程任务)，否则您应该使用标准库中的 std::vector。图书馆存在的原因是:让您的生活更轻松。在您的程序上下文中，开销可能微不足道。

您提到将多项式(例如 4*x^5 + x - 1)存储在 std::vector 中，索引代表幂(例如 [-1 , 1, 0, 0, 0, 4]) 效率低下。这是事实，但除非您存储次数大于 1000 的多项式，否则这种浪费完全可以忽略不计。对于次数高但系数很少的“稀疏”多项式，您可以考虑使用成对 vector ，每对的第一个值存储功率，第二个值存储系数。