首页 > 代码库 > 数据结构与算法分析 3.7 - 多项式乘法链表实现

数据结构与算法分析 3.7 - 多项式乘法链表实现

技术分享

思路

        <1>对于p(x)中的每一个因式,与q(x)中每一个因式相乘的结果,保存于另外的链表中;

        <2>对于保存结果的链表排序,并去重,即去除系数相同的因式结点,但系数相加 

代码

#include <list>using namespace std;struct Node{    int coefficient = 0;    int exponent = 0;};bool compfn(const Node &lhs, const Node &rhs) { return lhs.exponent > rhs.exponent; }list<Node> MultiplyPolynomial(list<Node> &polyFirst, list<Node> &polySecond){    list<Node> polyProd;    for (auto i = polyFirst.cbegin( ); i != polyFirst.cend( ); ++ i)    {        for (auto j = polySecond.cbegin( ); j != polySecond.cend( ); ++ j)        {            Node prod;            prod.coefficient = i->coefficient * j->coefficient;            prod.exponent = i->exponent + j->exponent;            polyProd.push_back(prod);        }    }    polyProd.sort(compfn);    if (polyProd.size() > 1)    {        auto i = polyProd.begin( );        while (i != polyProd.end())        {            auto j = i;            if (++ j != polyProd.end() && i->exponent == j->exponent)            {                i->coefficient += j->coefficient;                polyProd.erase(j);            }            else                ++i;        }    }    return polyProd;}

 

数据结构与算法分析 3.7 - 多项式乘法链表实现