如何使用链表和单项类c++实现多项式类

So I need to create two classes one for Monomials. The other for polynomials (built using a linked list of Monomials).

因此，我需要创建两个类，一个用于Monomials。另一个用于多项式(使用Monomials的链表构建)。

I have the function declarations done and now I need to get into the definitions, which is where I'm stuck.

我已经完成了函数声明，现在我需要进入定义，这就是我遇到的问题。

I think if I can get some direction on one function I'll be able to write the rest. Here is the direction I'm going with it, not sure if this is right. If it isn't can you point me in the right direction? Never used a the iterator thing so that's really throwing me off. Here is my header

我想如果我能得到一个函数的方向，我就能写出剩下的。这是我的方向，不确定这是否正确。如果不是，你能给我指出正确的方向吗?从来没有使用迭代器的东西，这让我很困惑。这是我的标题

#ifndef __POLYNOMIAL_H_
#define __POLYNOMIAL_H_

#include <iostream>
#include <list>
#include "Polynomial.cpp"

#define var = 'x' //varible to use in polynomial

using namespace std;

struct ZERO_T {
static const short ZERO = 0;
};
template <typename NumT>
class Monomial
{
public:
        Monomial<NumT>(NumT c = 0, int d = 0) : coeff(c), expo(d)
            { };
        NumT coefficient(void) const { return coeff; };
        int degree(void) const { return expo; };
        void assign_coefficient(const NumT c) { coeff = c; };
        void assign_degree(const int d) { expo = d; };
        bool operator==(const Monomial<NumT> & m) const
        {
            return (coeff == m.coeff && expo == m.expo);};
        bool operator!=(const Monomial<NumT> & m) const 
            {return (coeff != m.coeff || expo != m.expo);};

private:
        NumT coeff;
        int expo;
};
template <typename NumberType>
class Polynomial : public ZERO_T
{
public:
        Polynomial<NumberType>(NumberType c = 0, int d = 0)
        {
            const Monomial<NumberType> m(c, d);
            term_list.push_back(m); //creates a ZERO monomial
            number_of_terms = 1;
            highest_degree = d;
        }

        Polynomial<NumberType>(const Monomial<NumberType> & m) //type conversion constructor
        {
            term_list.push_back(m);
            number_of_terms = 1;
            highest_degree = m.degree();
        }

        ~Polynomial<NumberType>() { } // use default destructors and list's destructor

        Polynomial<NumberType>(const Polynomial<NumberType> & rhs) // copy constructor
            : term_list(rhs.term_list), number_of_terms(rhs.number_of_terms),
                highest_degree(rhs.highest_degree) { }

        const Polynomial<NumberType> & operator=(const Polynomial<NumberType> & rhs);
        //copy assignment 
        Polynomial<NumberType> operator+=(const Monomial<NumberType> &m);
        Polynomial<NumberType> operator+=(const Polynomial<NumberType> & rhs);
        const Polynomial<NumberType> operator+(const Monomial<NumberType> &m)const;
        const Polynomial<NumberType> operator+(const Polynomial<NumberType> & rhs) const;
        Polynomial<NumberType> operator*=(const Monomial<NumberType> &m);
        Polynomial<NumberType> operator*=(const Polynomial<NumberType> & rhs);
        const Polynomial<NumberType> operator*(const Monomial<NumberType>  &m) const;
        const Polynomial<NumberType> operator*(constPolynomial<NumberType> & rhs) const;
        const NumberType evaluate(NumberType x);
        bool operator==(const Polynomial<NumberType> &p) const;
        bool operator!=(const Polynomial<NumberType> &p) const;
        const int gethighestdegree();
        void read(istream & in = cin);
        void print(ostream & out = cout) const;
        //static Polynomial<NumberType> ZERO;
        private:
                list<Monomial<NumberType> > term_list;
                //sorted by decreasing degrees
                int number_of_terms;
                int highest_degree;
                void insert_in_poly(Polynomial<NumberType> & p, const Monomial<NumberType> & m);
                //helper function
                NumberType power(NumberType x, int n);
};
//template<> Polynomial<int> Polynomial<int>::ZERO = 0;
template <typename NumberType>
istream&operator>>(istream &  in, Polynomial<NumberType> & rhs);

template <typename NumberType>  
ostream& operator<<(ostream & out, const Polynomial<NumberType> & rhs);

#include "polynomial.cpp"
#endif

How would you do the add? Here's what I have so far:

你怎么做加法?这是我目前所拥有的:

#ifndef __POLYNOMIAL_CPP_
#define __POLYNOMIAL_CPP_

#include <iostream>
#include <cmath>
#include <list>
#include "polynomial.h"
#endif

template<typename NumberType>
const Polynomial<NumberType> Polynomial<NumberType>::operator+(const Monomial<NumberType>& m) const
{
int i = 0;
term_list.sort();  //sort list in decending order
term_list.reverse();  //rearrange into ascending order
Monomial temp;      //create a temp object to hold our monomial
temp.coeff = m.coeff;   
temp.expo = m.expo;     
/////////////////experiments here/////////
list <Monomial<NumberType>>::iterator itr;
itr = p.termlist.begin();
while (itr != p.termlist.end())       //traverse termlist until we reach end
{
    if (itr.expo == temp.expo)      //if temp exponents meet current list exponent
        itr insert(i, NumberType& temp);        //insert monomial here
    else
            i++;
}

Obviously I still need to doctor it up with what if the list is empty and what if the exponent match is never found and such. But for now I just want a simple add monomial to polynomial function to use as an example to build my other functions please.

显然，我仍然需要修改它，如果列表是空的，如果没有找到指数匹配，会怎么样。但现在我只是想要一个简单的多项式函数的加单项作为例子来构建我的其他函数。

2 个解决方案

#1

After looking at your classes declarations I can see some issues and will try to mark up your existing code with comments to help you out. I will also suggest that since your classes are templates you should have 3 files to the class: ClassName.h, ClassName.inl & ClassName.cpp this will help you in the long run due to the behavior of templates. After making comments in your standing code I will then try to reconstruct your classes as they would appear in their respective files.

在查看了您的类声明之后，我可以看到一些问题，并将尝试使用注释标记现有代码，以帮助您解决问题。我还建议，由于您的类是模板，您应该有3个类文件:ClassName。h,类名。inl &名称。由于模板的行为，cpp将在长期内帮助您。在对您的代码进行评论之后，我将尝试重构您的类，因为它们将出现在各自的文件中。

This Is What You Have

这就是你所拥有的

#ifndef __POLYNOMIAL_H_
#define __POLYNOMIAL_H_

#include <iostream>
#include <list>
#include "Polynomial.cpp" // Why including *.cpp?

#define var = 'x' //varible to use in polynomial

using namespace std;

struct ZERO_T {
   static const short ZERO = 0;
};

template <typename NumT>
class Monomial {
public:
    Monomial<NumT>(NumT c = 0, int d = 0) : coeff(c), expo(d)
        { };
    NumT coefficient(void) const { return coeff; };
    int degree(void) const { return expo; };
    void assign_coefficient(const NumT c) { coeff = c; };
    void assign_degree(const int d) { expo = d; };
    bool operator==(const Monomial<NumT> & m) const
    {
        return (coeff == m.coeff && expo == m.expo);};
    bool operator!=(const Monomial<NumT> & m) const 
        {return (coeff != m.coeff || expo != m.expo);};

private:
    NumT coeff;
    int expo;
};

template <typename NumberType>
class Polynomial : public ZERO_T {
public:
    Polynomial<NumberType>(NumberType c = 0, int d = 0) {
        const Monomial<NumberType> m(c, d);
        term_list.push_back(m); //creates a ZERO monomial
        number_of_terms = 1;
        highest_degree = d;
    }

    Polynomial<NumberType>(const Monomial<NumberType> & m) //type conversion constructor {
        term_list.push_back(m);
        number_of_terms = 1;
        highest_degree = m.degree();
    }

    ~Polynomial<NumberType>() { } // use default destructors and list's destructor

    Polynomial<NumberType>(const Polynomial<NumberType> & rhs) // copy constructor
        : term_list(rhs.term_list), number_of_terms(rhs.number_of_terms),
            highest_degree(rhs.highest_degree) { }

    const Polynomial<NumberType> & operator=(const Polynomial<NumberType> & rhs);
    //copy assignment 
    Polynomial<NumberType> operator+=(const Monomial<NumberType> &m);
    Polynomial<NumberType> operator+=(const Polynomial<NumberType> & rhs);
    const Polynomial<NumberType> operator+(const Monomial<NumberType> &m)const;
    const Polynomial<NumberType> operator+(const Polynomial<NumberType> & rhs) const;
    Polynomial<NumberType> operator*=(const Monomial<NumberType> &m);
    Polynomial<NumberType> operator*=(const Polynomial<NumberType> & rhs);
    const Polynomial<NumberType> operator*(const Monomial<NumberType>  &m) const;
    const Polynomial<NumberType> operator*(constPolynomial<NumberType> & rhs) const;
    const NumberType evaluate(NumberType x);
    bool operator==(const Polynomial<NumberType> &p) const;
    bool operator!=(const Polynomial<NumberType> &p) const;
    const int gethighestdegree();
    void read( istream & in = cin );
    void print( ostream & out = cout ) const;
    //static Polynomial<NumberType> ZERO;
    private:
            list<Monomial<NumberType> > term_list;
            //sorted by decreasing degrees
            int number_of_terms;
            int highest_degree;
            void insert_in_poly(Polynomial<NumberType> & p, const Monomial<NumberType> & m);
            //helper function
            NumberType power( NumberType x, int n );
};

//template<> Polynomial<int> Polynomial<int>::ZERO = 0;
template <typename NumberType>
istream& operator>>( istream &  in, Polynomial<NumberType> & rhs );

template <typename NumberType>  
ostream& operator<<( ostream & out, const Polynomial<NumberType> & rhs );

#include "polynomial.cpp" // Why include *.cpp?
#endif

If you noticed the comment I had about Why including Polynomial.cpp? You never want to include a CPP file in another file especially a header file. If you want an implementation file that you can include at the bottom of your header file that comes after your class definition and before the #endif directive for your header file's safeguard it should be an inline file as in ClassName.inl this way any type of inline methods that are not in your ClassName.cpp file or any template functions are defined in this implementation file which is another form of a header file. Your CPP files are reserved for the compiler to build object code and the header files both H & INL are used for look ups during compilation, and linking. The use of the inline file keeps your definitions - implementations separate from your declarations!

如果你注意到我的评论关于为什么包括多项式。cpp?您永远不希望在另一个文件中包含CPP文件，特别是头文件。如果你想要一个实现文件，你可以在你的头文件的底部包括在你的类定义之后，在#endif指令为你的头文件的保护之前，它应该是一个内联文件，就像在ClassName中一样。以这种方式输入任何不在类名中的内联方法。cpp文件或任何模板函数都定义在这个实现文件中，它是头文件的另一种形式。CPP文件预留给编译器来构建对象代码，H和INL的头文件用于编译期间的查找和链接。内联文件的使用使您的定义—实现与声明分离!

I will try to simplify your classes for easier reading while separating the declarations from the definitions.

我将尽量简化类，以便在分离声明和定义的同时更容易阅读。

Monomial.h

Monomial.h

#ifndef MONOMIAL_H
#define MONOMIAL_H

template<typename NumT>
class Monomial {
private:
    NumT m_coeff;
    int  m_expo;

public:
    explicit Monomial( NumT c = 0, int d = 0 ); // Added Explicit since both parameters can be defaulted

    NumT coefficient() const;
    int  degree() const;

    void assignCoefficient( const NumT c );
    void assignDegree( const int d );

    bool operator==( const Monomial<NumT>& other ) const;
    bool operator!=( const Monomial<NumT>& other ) const;

private:
    Monomial( const Monomial& c ); // Not Implemented - Copy Constructor
    Monomial& operator=( const Monomial& c ); // Not Implemented - Assignment Operator

}; // Monomial

#include "Monomial.inl"

#endif // MONOMIAL_H

Monomial.inl

Monomial.inl

// -------------------------------------------------------------------------
// Monomial() - Constructor
template<typename NumT>
Monomial<NumT>::Monomial( NumT c, int d ) :
m_coeff( c ),
m_expo( d ) {
} // Monomial

// -------------------------------------------------------------------------
// coefficient()
template<typename NumT>
NumT Monomial<NumT>::coefficient() const {
    return m_coeff;
} // coefficient

// -------------------------------------------------------------------------
// degree()
template<typename NumT>
int Monomial<NumT>::degree() const {
    return m_expo;
} // degree

// -------------------------------------------------------------------------
// assignCoefficient()
template<typename NumT>
void Monomial<NumT>::assignCoefficient( const NumT c ) {
    m_coeff = c;
} // assignCoefficient

// -------------------------------------------------------------------------
// assignDegree()
template<typename NumT>
void Monomial<NumT>::assignDegree( const int d ) {
    m_expo = d; 
} // assignDegree

// -------------------------------------------------------------------------
// operator==()
template<typename NumT>
bool Monomial<NumT>::operator==( const Monomial<NumT>& other ) const {
    return ( m_coeff == other.m_coeff && m_expo == other.m_expo );
} // operator==

// -------------------------------------------------------------------------
// operator!=()
template<typename NumT>
bool Monomial<NumT>::operator!= ( const Monomial<NumT>& other ) const {
    return ( m_coeff != other.m_coeff || m_expo != other.m_expo );
} // operator!=

Monomial.cpp

Monomial.cpp

#include "Monomial.h"

Polynomial.h

Polynomial.h

#ifndef POLYNOMIAL_H
#define POLYNOMIAL_H

#include <iostream>
#include <list>

#include "Monomial.h"

#define var = 'x'

struct ZERO_T {
    static const short ZERO = 0;
};

template<typename NumberType>
class Polynomial : public ZERO_T {
    friend std::istream& operator>>( std::istream& in, const Polynomial<NumberType>& poly );
    friend std::ostream& operator<<( std::ostream& out, const Polynomial<NumberType>& poly );
private:
    list<Nomomial<NumberType>> m_lTerms;

    int m_iNumTerms;
    int m_iHighestDegree;

public:
    // Constructors & Destructors
    explicit Polynomial( NumberType c = 0, int d = 0 );
    Polynomial( const Monomial<NumberType>& m );
    Polynomial( const Polynomial<NumberType& rhs );
    // ~Polynomial(); // Default Okay

    // Assignment Operator
    const Polynomial<NumberType>& operator=( const Polynomial<NumberType>& rhs );

    // Comparison Operators
    bool operator==( const Polynomial<NumberType>& p ) const;
    bool operator!=( const Polynomial<NumberType>& p ) const;
    bool operator<(  const Polynomial<NumberType>& p ) const;
    bool operator<=( const Polynomial<NumberType>& p ) const;
    bool operator>(  const Polynomial<NumberType>& p ) const;
    bool operator>=( const Polynomial<NumberType>& p ) const;

    // Numerical Operators
    Polynomial<NumberType>& operator+=( const Monomial<NumberType>& m );
    Polynomial<NumberType>& operator+=( const Polynomial<NumberType>& rhs );
    Polynomial<NumberType>  operator+(  const Monomial<NumberType>& m ) const;
    Polynomial<NumberType>  operator+(  const Polynomial<NumberType>& rhs ) const;
    Polynomial<NumberType>& operator*=( const Monomial<NumberType>& m );
    Polynomial<NumberType>& operator*=( const Polynomial<NumberType>& rhs );
    Polynomial<NumberType>  operator*(  const Monomial<NumberType>& m ) const;
    Polynomial<NumberType>  operator*(  const Polynomial<NumberType& rhs ) const;

    // Public Member Functions
    int getHighestDegree() const;

    void read( std::istream& in = cin );
    void print( std::ostream& out = cout ) const;

private:
    void insertInPoly( Polynomial<NumberType>& p; const Monomial<NumberType>& m );
    NumberType power( NumberType x, int n );

}; // Polynomial

#include "Polynomial.inl"

#endif // POLYNOMIAL_H

Polynomial.inl

Polynomial.inl

// -------------------------------------------------------------------------
// Polynomial()

// To save some time all of this class's implementations should be in here
// where template<typename T> needs to be defined, just as I did within 
// Monomial.inl

Polynomial.cpp

Polynomial.cpp

#include "Polynomial.h"

This style of layout separates the declarations from the definitions making the code easier to read and allowing it to be modular. This way a person or user who is using your classes doesn't have to worry about how these functions work they only need to see the declaration of what they return and what parameters they accept with a basic description of what kind of tasks the functions / methods perform. I also removed some lines of code that were not needed in the Monomial class since they were only being used by the Polynomial class #includes, #defines & structure and moved them into the Polynomial class where they are needed.

这种布局将声明与定义分离开来，使代码更容易阅读，并允许代码模块化。这样，使用类的人或用户就不必担心这些函数是如何工作的，他们只需要通过函数/方法执行的任务的基本描述来查看返回的内容和接受的参数的声明。我还删除了一些单项类中不需要的代码行，因为它们只被多项式类#include、#define和structure使用，并将它们移动到需要它们的多项式类中。

Now as to your question about how to do a specific task that you showed in your question such as how to do add I can give you some advice based off of what you already have shown.

至于你的问题，关于如何完成你的问题，比如如何添加，我可以根据你已经展示的内容给你一些建议。

If you are creating a stack variable of type Monomial called temp you need to use the template brackets for the variable as such:

如果您正在创建一个称为temp的单项类型的堆栈变量，那么您需要为变量使用模板括号，如下所示:

Monomial<NumberType> temp; // You did define Monomial as a template type.

I see that you are setting both the coefficient & exponent of your passed in parameter of a Monomial<> type, it could be helpful to define the assignment operator in your Monomial class. You may want to also add other operators to your Monomial Class as well +, +=, *, *=, etc.

我看到您正在设置一个单项<>类型的传入参数的系数和指数，在您的单项类中定义赋值运算符可能会有帮助。您可能还想在单项类中添加其他操作符，例如+、+=、*、*=等。

As for your implementation of adding two monomials that have equivalent exponents you are on the right track, you already have your comparison operators for you to see if they are equal or not, then when two Monomials: A & B can be added you need to add the two and store the answer in a temporary container and removed the two that you added together from the list, continue this process until no more terms can be added. Then take all of your temporarily stored terms and repopulate your class's list.

至于你实现等效的增加两个单项指数你在正确的轨道上,你已经有你的比较运算符,看看他们是平等的,当两个单项:A和B可以添加您需要添加两个答案并存储在一个临时容器和从列表中删除了两个你加在一起,继续这个过程,直到没有更多的可以添加。然后获取所有临时存储的术语并重新填充类的列表。

You have to remember that the numerical operators in your Polynomial are for adding & multiplying two Polynomials together. If you are trying to add two Monomials together then this is where you will need the operator in your Monomial class.

你必须记住多项式中的数值运算符是用来把两个多项式相加或相乘的。如果你想把两个单因子相加，那么这就是你在单项类中需要运算符的地方。

#2

Why I don't like answering questions like this: In order to answer it you wind up doing half of someone's homework. Maybe they learn, maybe they don't, but lemme tell ya something. Cut and paste may get you through a class, but it leave you serving coffee and selling phones in real life.

为什么我不喜欢回答这样的问题:为了回答这个问题，你不得不做别人一半的家庭作业。也许他们会学习，也许他们不会，但让我告诉你一些事情。剪切和粘贴可能会让你通过一堂课，但它会让你在现实生活中提供咖啡和卖手机。

I'm not even trying to optimize this code. The polynomial += polynomial operator is the worst way to do it. It is also the fastest to write.

我甚至没有优化这段代码。多项式+=多项式算子是最糟糕的方法。它也是写得最快的。

OK. The Monomial class is largely the same. I add two methods and a friend function.

好的。单项类基本相同。我添加了两个方法和一个friend函数。

Monomial& operator+=(const Monomial & toadd)
{
    if (expo != toadd.expo)
    {
        throw "Mismatched exponents";
    }
    coeff += toadd.coeff;
    return *this;
}

Pretty simple. If the coefficients don't match, blow up. Otherwise add the coefficients and return a reference to the modified object.

很简单。如果系数不匹配，就爆炸。否则，添加系数并返回修改后对象的引用。

I start with += because + is += called with a local copy

我以+=开头，因为+是用本地副本调用的+=

Monomial operator+(const Monomial & toadd) const
{
    return Monomial(*this) += toadd;
}

I toyed with passing in non const non reference toadd because somebody's getting copied, but wimped out and went for the familiar. I don't play games with the return because it is a trivial object to copy and any constructor logic will probably be elided if the compiler sees a need.

因为有人被复制了，所以我就把不需要引用的东西给传了进去，但我就偷偷溜了出去，去找熟悉的东西。我不玩返回的游戏，因为要复制的对象很简单，如果编译器看到需要，任何构造函数逻辑都可能被省略。

friend std::ostream& operator<<(std::ostream & out,
                                const Monomial<NumT> & rhs)
{
    out << rhs.coeff << '^' << rhs.expo;
    return out;
}

And a standard << override to test the results.

和一个标准<< override来测试结果。

The Polynomial class I write entirely inside the class. There is usually nothing to be gained from spinning off the implementation of a template and this is no exception.

我写的多项式类完全在类里面。通常从分离模板的实现中没有任何收获，这也不例外。

Polynomial & operator+=(const Monomial<NumberType> &m)
{
    auto found = std::find_if(term_list.begin(),
                              term_list.end(),
                              [&m] (const Monomial<NumberType> &mono)
                              {
                                  return mono.degree() == m.degree();
                              } );
    if (found != term_list.end())
    {
        *found += m;
    }
    else
    {
        term_list.push_back(m);
        highest_degree = std::max(m.degree(), highest_degree);
        number_of_terms++; // pointless variable. Should always equal term_list.size()
    }
    return *this;
}

I got rid of the sorting. There's not much point to sorting and resorting every time. Sorting every time is an O(n) that you're probably going to have to do anyway since Polynomial is built around std::list. Sort when the list is modified or don't sort at all. Anyway, I used std::find_if, which may have some container and ordering optimizations baked in, to do the look-up if the container is changed in the future.

我去掉了排序。没有太多的时间去整理和使用。每次排序都是O(n)因为多项式是围绕std::list构建的，所以你可能不得不这么做。当列表被修改或根本不排序时进行排序。无论如何，我使用了std::find_if，它可能包含一些容器和排序优化，以便在将来容器发生更改时进行查找。

Polynomial & operator+=(const Polynomial & rhs)
{
    for (auto & mono: rhs.term_list)
    {
        *this += mono;
    }
    return *this;
}

This is the laziest, stupidest way I could add two polynomials. Every monomial in rhs is added to this. Since polynomial + monomial inserts exponents that aren't there and adds to those that are, all monomials will be represented in the result. I'm pretty sure the time complexity can be reduced from O(n^2) to O(n) with some care and attention.

这是我能加两个多项式中最懒，最愚蠢的方法。rhs中的每一个单项都加到这里。由于多项式+单项插入的指数不存在并且增加了那些，所有的单项式都将在结果中表示。我很确定时间复杂度可以从O(n ^ 2)降低到O(n)和一些关心和关注。

const Polynomial operator+(const Monomial<NumberType> &m) const
{
    return Polynomial (*this) += m;
}

const Polynomial operator+(const Polynomial & rhs) const
{
    return  Polynomial (*this) += rhs;
}

Same as last time the operator + simply copies and calls +=.

与上次相同，操作符+只是复制并调用+=。

friend std::ostream& operator<<(std::ostream & out,
                                const Polynomial<NumberType> & rhs)
{
    if (!rhs.term_list.empty())
    {
        auto mono = rhs.term_list.begin();
        out << *mono;
        for (++mono; mono != rhs.term_list.end();++mono)
        {
            out << " + " << *mono;
        }
    }
    else
    {
        out << "empty";
    }
    return out;
}

And again a << overload for easy testing.

还有一个 <重载，便于测试。< p>

Finally some test code to make sure I'm not totally on crack.

最后是一些测试代码，以确保我没有完全处于崩溃状态。

#include <iostream>
#include "Polynomial.h"
using namespace std;

int main()
{
    Polynomial<int> p;

    p += Monomial<int>(100,0);
    p += Monomial<int>(1,1);
    p += Monomial<int>(0,2);
    p += Monomial<int>(1,3)+Monomial<int>(1,3);
    p += Monomial<int>(5,4);
    cout << p<<endl;

    auto p2 = p+ Monomial<int>(3,3);
    cout << p2 << endl;
    cout << p+p2<< endl;
}