c++ - 如何使用不带幂变量的链表将 2 多项式相乘？

Question

我的老师让我用链表来做一个多项式，就像这段代码

class Node {
    public:
        int data; // only data, has no power
        Node* next;
};
class PolyList {
    private:
        Node* pHead;
     public:
        PolyList();
        ~PolyList();
         ............
}

列表由文件 input.txt 读取。示例:2 4 0 3 ---> 多项式 = ( 2x^3 + 4x^2 + 3 )

我如何实现 list1 和 list2 之间的乘以 2 多项式的方法。我在谷歌和这个网站上搜索，但只发现多项式是用包含系数变量和幂变量的数据创建的。我的多项式只有系数，我不能改变这个结构。我需要大家的帮助。非常感谢。

Answer 1

你要做的是convolution的系数。如果您可以访问 Matlab(或 Octave)，则可以尝试一下:

% Note this is Matlab, just for demonstration
p1 = [1 1];  % x + 1
p2 = [1 0];  % x
p3 = conv(p1, p2)   %x*(x + 1) => x^2 + x

% gives p3 = [1 1 0], i.e., x^2 + x

编辑:我没有给出任何关于实现这个的细节——你可能可以通过谷歌搜索找到使用链表的卷积示例。