2.39.c

部分高校使用anyview编程测试数据结构习题,此代码为数据结构题集(c语言版)严蔚敏版的课后习题答案.专门提供给在anyview上运行,全部为通告代码

◆2.39③  试对稀疏多项式Pn(x)采用存储量同多项式项
数m成正比的顺序存储结构，编写求Pn(x0)的算法（x0为
给定值），并分析你的算法的时间复杂度。

实现下列函数：
float Evaluate(SqPoly pn, float x);
/* pn.data[i].coef 存放ai，                      */
/* pn.data[i].exp存放ei (i=1,2,...,m)            */
/* 本算法计算并返回多项式的值。不判别溢出。      */
/* 入口时要求0≤e1<e2<...<em，算法内不对此再作验证*/

多项式的顺序存储结构:
typedef struct {
   int  coef;
   int  exp;
} PolyTerm;

typedef struct {
   PolyTerm *data;
   int       length;
} SqPoly;
float Evaluate(SqPoly pn, float x)
/* pn.data[i].coef 存放ai，                      */
/* pn.data[i].exp存放ei (i=1,2,...,m)            */
/* 本算法计算并返回多项式的值。不判别溢出。      */
/* 入口时要求0≤e1<e2<...<em，算法内不对此再作验证*/
{
  PolyTerm *q;
  int ex;                               //t用于记录多项式每一项系数外的部分
  float sum,t=1;                        //ex用于和每一项指数部分比较
  q=pn.data;
  sum=0;ex=0;
  while(q->coef)
  {
    while(ex<q->exp)
       {t*=x;ex++;}
    sum+=q->coef*t;
    q++;
  }
  return sum;

}