数据结构之“Ordered List and Sorted List”（四）

本文主要是介绍数据结构之“Ordered List and Sorted List”（四），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

        本文主要介绍“Ordered List”的一种应用——“多项式求导”。（点击打开链接）

一、名字介绍

        本文的数学公式比较多，我就不在博客中编公式了，在此简单列一下几个高数名词。

        polynomial    ——  多项式

        coefficient     ——  系数

        exponent       ——  指数

        derivative      —— 导数

        differentiation —— 微分

二、数学理论

        利用“Ordered List”进行多项式求导，它在数学上，首先要将多项式表示为“系数-指数对”序列，即“An alternative representation for such a polynomial consists of a sequence of ordered pairs”。然后在观察原始多项式和求导后的多项式“系数-指数对”序列的变化，寻找规律。原文如下：

方法就是：

1，丢弃指数为零的项；

2，对于其他项，将其系数修改为“系数与指数的乘积”，再将其指数减一，如此即可。

三、编程实现

1，“系数-指数对”抽象为“Term”；

2，多项式继承自“ListAsLinkedList”。

#pragma once
#include "ListAsLinkedList.h"// the oredered pair
class Term : public Object
{
public:Term(double, unsigned int);void Put(std::ostream &)const;void Differentiate();protected:int CompareTo(Object const &) const;private:double coefficient;unsigned int exponent;
};class Polynomial : public ListAsLinkedList
{
public:void Differentiate();
};class DifferentiatingVisitor : public Visitor
{
public:void Visit(Object & object){Term & term = dynamic_cast<Term&> (object);term.Differentiate();}
};

实现

#include "stdafx.h"
#include "PolynomialDifferentiate.h"Term::Term(double _coefficient, unsigned int _exponent): coefficient(_coefficient), exponent(_exponent)
{
}void Term::Put(std::ostream & s) const
{s << typeid(*this).name() << " {";s << coefficient << "," << exponent;s << " }";
}void Term::Differentiate()
{if (exponent > 0){coefficient *= exponent;--exponent;}elsecoefficient = 0;
}int Term::CompareTo(Object const & object) const
{Term const & term = dynamic_cast<Term const &> (object);if (exponent == term.exponent)return ::Compare(coefficient, term.coefficient);elsereturn exponent - term.exponent;
}void Polynomial::Differentiate()
{DifferentiatingVisitor visitor;Accept(visitor);Object & zeroTerm = Find(Term(0, 0));if (!zeroTerm.IsNull()){Withdraw(zeroTerm);//delete & zeroTerm;}
}

四、测试

    // test for Polynomial Differentiate{Polynomial polynomial;Term pArray[] = { Term(5,0), Term(32,1), Term(4,2), Term(56,3), Term(16,4), Term(45,5) };for (unsigned int i = 0; i < 5; ++i)polynomial.Insert(pArray[i]);polynomial.Differentiate();polynomial.Put(std::cout);polynomial.RescindOwnership();}

这篇关于数据结构之“Ordered List and Sorted List”（四）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---