第3章链表 double get Expn (( const ∥返回当前项中存放的指数值 double getCoef ()()const; ∥返回当前项中存放的系数值 void Firster()i current =first; 1 ∥将当前指针置于头结点 Boolean First(; 将当前指针指向链表的第一个结点 Boolean Next ( ∥将当前指针指到当前结点的后继结点 ∥将当前指针指到当前结点的前驱结点 void Insert const double coef, double expn ) 插入新结点 void Remove ( ∥删除当前结点 double Calc( double x ) ∥多项式的值 friend Polynomial operator + Polynomial & Polynomial &) friend Polynomial operator * Polynomial & Polynomial &) 对于多项式Pa(x)=a0+a1x+ax2+ax3+…+an-xm1+anx2,可用 Horner规则将它改写求值: Pn(x)=a+(ax+(a2+(a3+…+(an-1+an*x)*X…)*x) 因为不是顺序表,必须采用递归算法实现: Value(n)=a0+ value(n-1)*x 递归求解 Value(n-1) Value(1)=an-1+ value(0) 返回求值 double Polynomal Value( Term *p, doublex)i ∥私有函数:递归求子多项式的值 if(p->link first)return p->coef else return p->coef +x' Value( p->link, x); double Polynomal Calc( double x)i ∥共有函数:递归求多项式的值 Term pc= first->link; if( pc= first )cout <<0<<endl else cout < Value( pc, x)<<endl; 但是,当多项式中许多项的系数为0时,变成稀疏多项式,如P50(x)=a+anx13+a3sx35+a0x3°, 为节省存储起见,链表中不可能保存有零系数的结点。此时,求值函数要稍加改变 #include <math. h> double Polynomal Value( Term *p, double e, double x)i ∥有函数:递归求子多项式的值。pow(x,y)是求x的y次幂的函数,它的原型在“ math h”中 if( p->link first)return p-> else return p->coef pow( x, p->expn -e)* Value(p->link, p->expn, x); double Polynomal Calc( double x)& ∥共有函数:递归求多项式的值第 3 章 链表 31 double getExpn ( ) ( ) const; //返回当前项中存放的指数值 double getCoef ( ) ( ) const; //返回当前项中存放的系数值 void Firster ( ) { current = first; } //将当前指针置于头结点 Boolean First ( ); //将当前指针指向链表的第一个结点 Boolean Next ( ); //将当前指针指到当前结点的后继结点 Boolean Prior ( ); //将当前指针指到当前结点的前驱结点 void Insert ( const double coef, double expn ); //插入新结点 void Remove ( ); //删除当前结点 double Calc ( double x ); //求多项式的值 friend Polynomial operator + ( Polynomial &, Polynomial & ); friend Polynomial operator * ( Polynomial &, Polynomial & ); }; 对于多项式 Pn(x) = a0 + a1x + a2x 2 + a3x 3 + … + an-1x n-1 + anx n，可用 Horner 规则将它改写求值： Pn(x) = a0 + (a1x + ( a2 + ( a3 + … + ( an-1 + an*x )*x … )*x )*x )*x 因为不是顺序表，必须采用递归算法实现： double Polynomal :: Value ( Term *p, double x ) { //私有函数：递归求子多项式的值 if ( p->link == first ) return p->coef; else return p->coef + x * Value ( p->link, x ); } double Polynomal :: Calc ( double x ) { //共有函数：递归求多项式的值 Term * pc = first->link; if ( pc == first ) cout << 0 << endl; else cout << Value ( pc, x ) << endl; } 但是，当多项式中许多项的系数为 0 时，变成稀疏多项式，如 P50(x) = a0 + a13x 13 + a35x 35 + a50x 50， 为节省存储起见，链表中不可能保存有零系数的结点。此时，求值函数要稍加改变： #include <math.h> double Polynomal :: Value ( Term *p, double e, double x ) { //私有函数：递归求子多项式的值。pow(x, y)是求 x 的 y 次幂的函数, 它的原型在“math.h”中 if ( p->link == first ) return p->coef; else return p->coef + pow( x, p->expn – e ) * Value ( p->link, p->expn, x ); } double Polynomal :: Calc ( double x ) { //共有函数：递归求多项式的值 Value(n) = a0 + Value(n-1)*x Value(n-1) = a1 + Value(n-2)*x …… Value(1) = an-1 + Value(0) Value(0) = an 递 归 求 解 返 回 求 值