第三章 3-10~3-12
3-10 如果用循环链表表示一元多项式，试编写一个函数Polynominal::Calc(x)，计算多项式在x处的值。
思路：模仿书里用单链表的方式表示一元多项式，ListNode代表多项式中的一项，类型Type实例化为Term。Term用struct定义，包括coef（系数）和exp（指数），他们都是共有数据成员，所有能够使用Term对象的函数都可以存取它们。并且把term对象声明为polynominal的私有成员。

struct Term{       //链表结点data的数据类型
   int coef;       //系数
   int exp;        //指数
   Term(int c,int e){coef=c;exp=e;}
};

class Polynominal{
//多项式按指数从小到大排列，不声明构造函数等其他函数了
public:
   Polynominal();  //构造函数，不声明了
   ~Polynominal();
   double Calc(double x);
private:
   CircList poly;  //循环链表结构，data部分数据类型为Term
};

//以下实现Cacl函数
double Polynominal::Calc(double x){
   Term current;       //当前项
   double sum=0.0;     //存放最后的结果
   int len;            //多项式的项数
   poly.First();       //当前指针指向第一项
   len=poly.Length();  //求项数
   for(int i=1;i<=len;i++){
      current=poly.getData();
      sum+=current->coef * pow(x,current->exp)
      //pow(x,y)函数，求x的y次幂函数
      poly.Next();     //下一项
   }
}


3-12 试设计一个实现下述要求的locate运算的函数。设有一个带有表头结点的双向链表L，每个结点有4个数据成员：指向前驱结点的指针prior、指向后继结点的指针next、存放数据的成员data和访问频度freq。所有结点的freq初始时都为0。每当在链表上进行一次Locate(L,x)操作时，令元素值为x的结点的访问频度freq加1，并将该结点前移，链接到与它的访问频度相等的结点后面，时的链表中所有结点保持按访问频度递减的顺序排列，以使访问频繁的结点靠近表头。

思路：Locate函数参数为双向链表L和元素值x，通过双向链表的公共操作实现该函数的功能。
声明：为双向链表结点类加入 freq域，同时在双向链表类中加入两个公共操作
int getfreq();取得当前结点的freq值,返回
addfreq(); 当前结点的freq值增加1
同时原Insert函数，加入新结点时默认将freq置为0

void Locate(DblList< Type > L,Type& x){
   if(!Find(x))
      {cout << "Not find!\n";return}
   int i;   Type tmp;
   i=getfreq();          //取得原freq值
   tmp=getData();        //该结点的值
   Remove();             //删去该结点
   while(Prior())        
/*寻找应该插入的位置，如果到了first，那么prior()返回0,current指向first*/
      if(getfreq() > i)
          return;
   Insert(tmp);         //插入
   for(int k=0;k<=i;k++)
      addfreq();         //设定freq，比原先大1
}
13:36 | Category: | 0 评论

Comments (0)

发表评论