根据度数对多项式项进行排序

Question

我有这段关于多项式乘法的代码。我没有遇到任何错误，只是我想要的是根据度（从低度到高）对术语进行排序。如果我在 //commented 部分的 operator* 中添加条件，它将被打印太多次。我想知道我是否可以使用 m_Polynomial.sort()？如果是如何？如果没有，我还可以使用哪些其他方法？

因为它既用于打印多项式又用于打印它们的乘法结果，如果它可以添加到打印函数中就更好了。

此外，如果可以将多项式的打印样式更改为所需格式（以添加相同次数项的系数）

最小代码：

#include <iostream>
#include <fstream>
#include <string>
#include <list>
#include <vector>
using namespace std;


typedef struct Node
{
    double  cof;      // coefficient 
    int     deg;      // degree
} Node;

class CPolynomial
{
public:
    CPolynomial();
    CPolynomial(const string& file);
    ~CPolynomial();
    CPolynomial operator*(const CPolynomial &right);
    CPolynomial& operator=(const CPolynomial &right);
    void Print() const;

private:
    void ReadFromFile(string file);

private:
    list<Node> m_Polynomial;
};



int main()
{
    CPolynomial p1("P3.txt");
    CPolynomial p2("P4.txt");
    CPolynomial p3;
    p1.Print();
    p2.Print();

    p3 = p1*p2;
    p3.Print();

    system("pause");
    return 0;
}

CPolynomial::CPolynomial()
{
    Node term;
    term.cof = 0;
    term.deg = 0;
    m_Polynomial.push_back(term);
}

CPolynomial::~CPolynomial()
{
    m_Polynomial.clear();
}

CPolynomial::CPolynomial(const string& file)
{
    ReadFromFile(file);
}

CPolynomial CPolynomial:: operator*(const CPolynomial &right)
{
    CPolynomial result;
    result.m_Polynomial = m_Polynomial;

    for (list<Node>::iterator itr = result.m_Polynomial.begin(); itr != result.m_Polynomial.end(); ++itr)
    {
        itr->cof = 0;
        itr->deg = 0;
    }

    Node term;
    Node termR;
    Node temp;

    for (list<Node>::const_iterator it = m_Polynomial.begin(); it != m_Polynomial.end(); ++it)
    {
        for (list<Node>::const_iterator itR = right.m_Polynomial.begin(); itR != right.m_Polynomial.end(); ++itR)
        {
            term = *it;
            termR = *itR;

            temp.cof = termR.cof* term.cof;
            temp.deg = termR.deg + term.deg;

            for (list<Node>::iterator itr = result.m_Polynomial.begin(); itr != result.m_Polynomial.end(); ++itr)
            {
                if (temp.deg == itr->deg)
                {
                    temp.cof += itr->cof;
                    itr->cof = 0;
                }
            // if(temp.deg < it->deg)
            //result.m_Polynomial.insert(it, temp);
            }
            result.m_Polynomial.push_back(temp);
        }
    }
    return result;
}

CPolynomial& CPolynomial:: operator=(const CPolynomial &right)
{

    this->m_Polynomial = right.m_Polynomial;
    return *this;
}

void CPolynomial::Print() const
{
    list<Node>::const_iterator it;

    for (it = m_Polynomial.begin(); it != m_Polynomial.end(); it++)
    {
        if (it->cof == 0)
        {
            ;
        }
        else
        {
            if (it->cof > 0)
            {
                if (it != m_Polynomial.begin()) // if 'it' is not the first term, '+' is not necessary
                    cout << "+";
            }
            cout << it->cof;
            if (it->deg != 0)
                cout << "x^" << it->deg;
        }
    }
    cout << endl;
}

void CPolynomial::ReadFromFile(string file)
{
    Node term;
    fstream MyFile;
    string p;
    int num;

    MyFile.open(file);

    if (!MyFile.is_open())
    {
        cerr << "Unable to open input file" << endl;
        exit(EXIT_FAILURE);
    }
    else
    {
        MyFile >> p >> num;

        std::list<Node>::iterator it = m_Polynomial.begin();

        for (int i = 0; i < num; i++)
        {
            MyFile >> term.deg >> term.cof;

            m_Polynomial.push_back(term);
        }
        MyFile.close();
    }

}

P1.txt

P4.txt

P 2
1 4
4 -3

输出

2-3^5+5x^12+6x^2+7x^5-4x^3+9x^2+2x^2         (P1)
4x^1-3x^4                                    (P2)
8x^1+20x^13-15x^16_12x^9-22x^4+12x^7+68x^3    (P1*P2)

期望的输出：

2+17x^2-4x^3+4x^5+5x^12
4x^1-3x^4 
8x^1+68x^3-22x^4+12x^7_12x^9+20x^13-15x^16

Answer 1

你的运算符修改了它的左操作数，为什么？

如果你说p3 = p1 * p2;那么修改p1是错误的，你应该return一个具有新值的新对象，而不是改变操作数。

一个解决方案是提供 operator*= 作为改变其左操作数的成员函数，然后将 operator* 定义为非成员函数：

CPolynomial operator*(const CPolynomial& lhs, const CPolynomial& rhs)
{
  CPolynomial result = lhs;
  result *= rhs;
  return result;
}

错误似乎出现在 AddOneTerm 中，您在其中进行了错误的比较。您的循环将在 (term.deg >= it->deg) 的 first 位置插入新术语，但它应该是 last 的位置。

此外，您应该在 ReadFromFile 中使用 AddOneTerm(term) 而不是 m_Polynomial.push_back(term) 以确保条款的顺序正确。

您对迭代器的使用也很混乱：

        std::list<Node>::iterator next_it;
        next_it = ++it;

现在 next_it 和 it 都递增了，所以它们都是下一个学期。为什么？

我建议更简单一些：

void CPolynomial::AddOneTerm(Node term)
{
    auto it = m_Polynomial.begin();
    while (it != m_Polynomial.end() && it->deg < term.deg)
    {
        ++it;
    }

    if (it != m_Polynomial.end() && term.deg == it->deg)
    {
        it->cof += term.cof;
    }
    else
    {
        m_Polynomial.insert(it, term);
    }
}

您还可以为 Node 个对象定义比较运算符：

bool operator<(const Node& l, const Node& r)
{
    return l.deg < r.deg;
}

现在您可以轻松地对 list<Node> 结构进行排序，并且可以使用 lower_bound 在 AddOneTerm 中找到正确的位置：

void CPolynomial::AddOneTerm(Node term)
{
    auto it = std::lower_bound(m_Polynomial.begin(), m_Polynomial.end(), term);

    if (it != m_Polynomial.end() && term.deg == it->deg)
    {
        it->cof += term.cof;
    }
    else
    {
        m_Polynomial.insert(it, term);
    }
}

根据度数对多项式项进行排序

Sorting polynomial terms based on degrees

c++

class

linked-list

polynomial-math