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

Question

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

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

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

最少的代码:

#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

P 8
0 2
5 -3
12 5
2 6
5 7
3 -4
2 9
2 2

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是错误的，您应该返回一个具有新值的新对象，而不是更改操作数。

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

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

错误似乎在 AddOneTerm 中你在哪里做比较错误。您的循环将在 第一个 位置插入新术语，其中 (term.deg >= it->deg)但它应该是 last 正确的位置。

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

您对迭代器的使用也非常困惑:

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