我正在研究一个问题，该问题要求我使用STL链表类来表示多项式。我已经在获得类定义方面做了一个很好的开始，但是我对下一步要去哪里有点困惑(新手程序员-请原谅我潜在的无知)。
class Polynomial
{
public:
Polynomial(); //Default constructor
Polynomial(pair<double,int>); //Specified constructor
void add(Polynomial);
Polynomial multiply(Polynomial);
void print();
private:
list<int> order_terms;
list<double> coeffs;
};
我有两个问题:
1)将项和系数存储为一对似乎更优雅-但是我不确定如何使用STL列表获得工作。
2)关于add成员函数，我不确定如何实现它，这样我就可以定义一个多项式，然后像这样添加项:
Polynomial test(pair<3.14,0>);
Polynomial test_2(pair<2,1>);
test.add(test_2);
我的主要问题是理解如何访问存储在另一个对象中的术语并将其链接到第一个多项式。
任何帮助都非常感谢。
编辑:add()函数的代码-目前不工作
void Polynomial::add(const Polynomial& rhs)
{
//Perform some sort of sort here to make sure both lists are correctly sorted
//Traverse the list of terms to see if there's an existing nth order
//term in the list on the left-hand-side polynomial.
list<int>::iterator itr;
list<int>::iterator itl;
for(itr=rhs->terms.begin(); itr!=rhs->terms.end(); itr++)
{
bool match=0;
//See if there's an existing terms, if so add to it
for(itl=terms.begin(); itl!=terms.end(); itl++)
{
if(*itl->second)==*itr->second)
{
*itl->first+=*itr->first;
match = 1;
}
}
//If not, this is the first nth order term so just push it onto the list
if(!match){ terms.push_back(*itr); //Perform the sort again }
}
要在list中使用pair，您可以这样做:list<pair<double, int> > -注意>之间的空格。还可以使用
typedef pair<double, int> TermCoeff;
list<TermCoeff> equation;
对list:
list<TermCoeff> equation;
// insert items
equation.sort(coeff_compare);
在<utility>头文件中有预定义的pair比较器函数。如果first相等，则先比较first元素，然后比较second元素。
对于你的第二个问题，你应该记住，一个类的对象可以访问同一个类的对象的成员变量，即使它们是私有的。如果您没有在系数中留下任何空白(在构造函数中使用设置为0的对的第二个值填充缺失的空白)，这意味着您的add方法可以看起来像:
Polynomial& Polynomial::add(const Polynomial& rhs) {
// constructor should sort all terms and enforce that all terms are present
// lhs = current object (left hand side of operator)
// rhs = other object (right hand side of operator)
// example: lhs.add(rhs)
list<TermCoeff>::const_iterator rhs_iter = rhs.terms.begin();
list<TermCoeff>::iterator lhs_iter = terms.begin();
while(rhs_iter != rhs.terms.end()) {
if (lhs_iter != terms.end()) {
// add because we aren't at the end of current object's terms
lhs_iter->second += rhs_iter->second;
++lhs_iter;
} else {
// insert because we are at the end of current object's terms
terms.push_back(*rhs_iter);
lhs_iter = terms.end(); // keep the iterator at the end
}
++rhs_iter;
}
return *this;
}
int main (int argc, const char * argv[])
{
list<TermCoeff> first, second;
first.push_back(TermCoeff(0, 0.0)); // empty
first.push_back(TermCoeff(1, 5.0));
first.push_back(TermCoeff(2, 5.0));
second.push_back(TermCoeff(0, 6.0));
second.push_back(TermCoeff(1, 0.0)); // empty
second.push_back(TermCoeff(2, 8.0));
second.push_back(TermCoeff(3, 9.0));
Polynomial first_eq(first);
Polynomial second_eq(second);
first_eq.add(second_eq);
first_eq.print();
return 0;
}
注意，我返回了对当前对象的引用。这是在加法方法中做的一件好事，因为这样你就可以链式添加了:
first.add(second).add(third);
或
first.add(second.add(third));
其他人已经解释了list<pair<double, int> >(我喜欢shelleybutterfly从列表中派生Polynomial的建议，但我将使其成为protected，而不是public，以便外部代码不会太自由地混淆列表的内容)。
但是add函数有点棘手，因为添加两个多项式通常并不意味着将它们连接起来或将它们的项相加。这个操作实际上更像是合并——您很快就会看到必须对列表进行排序。(事实上，将多项式表示为向量更自然，但我想这不是赋值。)
我建议你先实现Polynomial::add(pair<double, int>)，然后再实现另一个(add(Polynomial &))。
我不想详细说明，因为这看起来像是家庭作业。这足以给你指明正确的方向吗?
编辑:
如果您修复了几个错误，您的新代码看起来是正确的(尽管效率低下):
void Polynomial::add(const Polynomial& rhs)
{
// Don't forget to implement the sorting routine.
// The iterators must be of the correct type. And itr must be const,
// since you have declared rhs to be a const reference. The compiler
// will not allow you to have an iterator with the power to alter
// a const thing.
list<pair<double,int> >::const_iterator itr;
list<pair<double,int> >::iterator itl;
for(itr=rhs->terms.begin(); itr!=rhs->terms.end(); itr++)
{
bool match=false;
for(itl=terms.begin(); itl!=terms.end(); itl++)
{
// You have an extra parenthesis here, and too much dereferencing.
if(itl->second == itr->second)
{
itl->first+=itr->first;
match = true;
}
}
if(!match)
{ terms.push_back(*itr); //Perform the sort again
} // Be careful not to catch the closing brace in a comment
}
}
一旦它开始工作，你就可以想办法让它更干净、更高效。例如，如果您在正确的位置insert新术语，则列表将始终以正确的顺序排列，并且不需要sort例程。
至于使用pair，为什么不使用list<pair<double, int>> (list< pair<double, int> >用于较旧的编译器)?或者你甚至可以定义一个单独的类来保存你的pair，像这样:
// example is implemented inline, you could always pull it out to
// your source file; although it's even possible that you could
// do everything inline if you want to allow just including a
// header but not having to link a separate file.
class CoeffAndTerm : public pair<double,int>
{
public:
// if you need it you should put extra functions here to
// provide abstractions:
double getTotalValue()
{
return first * second;
}
}
，然后使用
list<CoeffAndTerm> Polynomial;
作为变量，甚至
// same stuff goes for this class RE: the inline function definitions
class Polynomial : public list<CoeffAndTerm>
{
public:
// same goes here for the abstraction stuff maybe things
// like in your current Polynomial class; assuming some
// functions here ...
Polynomial Multiply(Polynomial other)
{
Polynomial Result = new Polynomial();
for (int i=0; i < size(); ++i)
{
Result.addCoeffAndTerm(
new CoeffAndTerm(
other.first * first,
other.second * second
);
}
return Result;
}
}
所以你得到的多项式是列表本身的一个衍生。不确定多项式的确切用法，所以我很难说哪个更有意义，但我更喜欢这种方式作为这种类型的一般规则;似乎多项式"是一个"系数和项的列表，它不只是"有"一个。:)我知道这是有争议的，这取决于你代码的实际使用。
对于操作，您可以执行引用返回，就像在其他示例之一中一样，但我已经在不修改现有值的情况下实现了乘法，您也可以为加法，减法等执行乘法，因此，假设第一，第二，第三等是其他多项式
Polynomial Result = First.Multiply(Second).Add(Third).Subtract(Fourth);
你也可以实现复制构造函数，operator =, operator +, operator *, operator /然后做一些看起来像普通数学的事情:
Polynomial Result = First * Second + Third - Fourth;
虽然可以使用std::pair对术语order和coefficient进行分组，但我不建议这样做:它不是很好读- 'first'和'second'的含义并不清楚，而且c++将隐式地在数字类型之间进行强制转换-并且您不会从pair(排序)的附加功能中获得任何好处。
相反，创建一个类:
class Term {
double coeff_;
int exp_;
public:
Term(double coeff, int exp): coeff_(coeff), exp_(exp) {}
double coefficient() const { return coeff; }
int exponent() const { return exp; }
[...]
};
class Polynomial {
std::list<Term> terms;
[...]
出于性能原因使字段公开(例如使用struct或public派生自pair)并不是一个好主意:内联构造函数、getter和setter与直接读取或写入变量一样快，它们具有封装实现的优点。
对于这种情况，您可能需要创建单独的类型来包装多项式系数和指数本身，以避免混淆数字类型，并执行无意义的操作，例如:class Coefficient {
double val;
public:
explicit Coefficient(double value): val(value) {}
double getValue() { return val; }
double operator*(double rhs) { return val*rhs; }
Coefficient operator+(const Coefficient& rhs) {
return Coefficient(val+rhs.val);
}
[...]
};
等。
另一种可能性:不使用类，您可以创建一个struct来表示项和系数;你仍然可以在它上面定义方法，就像类一样，但是成员默认是公共的，出于效率考虑，这是有意义的，特别是当你用这些东西做很多处理的时候。所以,也许:
struct CoeffAndTerm
{
int Term;
double Coeff;
private CoeffAndTerm(int parTerm, double parCoeff)
{
Term = parTerm;
Coeff = parCoeff;
}
public static CoeffAndTerm Make(int parTerm, double parCoeff)
{
return new CoeffAndTerm(parTerm, parCoeff);
}
// etc. and otherwise you can just do things as given in the example
// with the classes deriving from list<pair<int, double>>, e.g.,
// silly example again
public double getTotalValue()
{
return first * second;
}
}
，同样适用于第一个示例，再次提供比该示例更直接的访问，但仍然允许将抽象方法直接放在对象
上。struct Polynomial : public list<CoeffAndTerm>
{
list<CoeffAndTerm> CoefficientsAndTerms;
Polynomial Multiply(Polynomial other)
{
Polynomial Result = new Polynomial();
for (int i=0; i < size(); ++i)
{
Result.addCoeffAndTerm(
new CoeffAndTerm(
other.first * first,
other.second * second
);
}
return Result;
}
// etc.
}