C ++: STL связанный список - представляющий полином

Question

Я работаю над проблемой, которая требует, чтобы я использовал класс связанного списка 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) Что касается функции добавления члена, я не уверен, как реализовать ее так, чтобы я мог определить полином и затем добавить к нему термины следующим образом:

Polynomial test(pair<3.14,0>);
Polynomial test_2(pair<2,1>);
test.add(test_2);

Главное, у меня проблемы с пониманием того, как получить доступ к терминам, хранящимся в другом объекте, и связать его с первым полиномом.

Любая помощь с благодарностью.

EDIT: код для функции 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 }         
}

Answer 1

Чтобы использовать pair в list, вы можете сделать: list<pair<double, int> > - отметить расстояние между >.Также хорошо сделать что-то вроде

typedef pair<double, int> TermCoeff;
list<TermCoeff> equation;

To sort a list:

list<TermCoeff> equation;
// insert items
equation.sort(coeff_compare);

Для pair существуют предопределенные функции компараторав заголовке <utility>.Они сравнивают элементы first, а затем элементы second, если first равен.

Для вашего второго вопроса вы должны помнить, что объект класса может получить доступ к переменным-членам объекта объекта.того же класса, даже если они частные.Если вы не оставляете пробелы в ваших коэффициентах (в конструкторе заполняете пропущенные со вторым значением пары, установленным на 0), это означает, что ваш метод добавления может выглядеть следующим образом:

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

Answer 2

Другие объяснили list<pair<double, int> > (и мне нравится предложение shelleybutterfly вывести Polynomial из списка, за исключением того, что я бы сделал его protected, а не public, чтобы внешний код не был слишком свободен для беспорядка с содержанием списка).

Но функция add немного сложна, потому что добавление двух полиномов обычно не означает их объединения или сложения их терминов. Эта операция на самом деле больше похожа на слияние - и вы скоро увидите, что списки должны быть отсортированы. (На самом деле, более естественно представлять полиномы как векторы , но я предполагаю, что это не задание.)

Я предлагаю вам сначала внедрить Polynomial::add(pair<double, int>), а затем реализовать другое (add(Polynomial &)) в терминах этого.

Я не хочу говорить об этом слишком много, так как это похоже на домашнюю работу. Этого достаточно, чтобы указать вам правильное направление?

EDIT:
Ваш новый код выглядит правильно (хотя и неэффективно), если вы исправите пару ошибок:

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.

Answer 3

Хотя можно использовать std :: pair для группировки порядка и коэффициентов, я бы порекомендовал против этого: он не очень читабелен - неясно, что означают «first» и «second», и C ++ будет неявно приводить между числовые типы - и вы не получите никакой выгоды от дополнительной функциональности пары (упорядочение).

Вместо этого создайте класс, подобный:

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 или публично производными от пары) из соображений производительности - не очень хорошая идея: встроенный конструктор, геттеры и сеттеры так же быстры, как и чтение или запись переменной напрямую, и они имеют преимущество: инкапсуляция реализации.

В этом отношении вам может потребоваться создать отдельные типы для переноса полиномиальных коэффициентов и самих показателей степени, чтобы избежать путаницы числовых типов и выполнения бессмысленных операций, например ::100100

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);
    }
[...]
};

и т.д.

Answer 4

Что касается использования пары, почему бы не использовать list<pair<double, int>> (list< pair<double, int> > для старых компиляторов)? Или вы можете даже определить отдельный класс для хранения вашей пары следующим образом:

// 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;

Answer 5

Другая возможность: вместо использования класса вы можете создать как структуру для представления термина и коэффициента; вы по-прежнему можете определять методы для него точно так же, как класс, но члены по умолчанию являются открытыми, что может иметь смысл по соображениям эффективности, особенно если вы выполняете много обработки с этими вещами. Итак, может быть:

 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.
}