问答题 请设计一个算法,求出循环表中结点的个数。
【正确答案】(1)数据结构
   采用不带头结点的循环链表。
   struct Node;
   typedef struct Node*PNode;
   struct Node{
   DataType info;
   PNode link;
   });
   typedef struct Node*LinkList;
   (2)思路
   遍历整个循环链表,同时计数即可。
   (3)算法
   1)错误算法
   int count(LinkList clist){
       int count;
       PNode p,q;
       p=clist;
       q=p->link;
       if(clist==NuLL)return 0;    /*如果是空表*/
       count=1;
       while(q!=p){
           q=q->link;
           count++;
       }
       return count;
   }
   错误:如果clist是一个空表,那么第5行的语句“q=p->link;”是非法的。
   分析:应把第6行语句提前1行或2行,一定要放在语句“q=p->link;”之前。
   缺点:增加局部变量p。
   分析:这样做没有必要,因为p的初值置为clist,在程序中并没有对p做其他修改,所以程序中不需要引入p而直接使用clist即可。
   2)正确算法
   int count(LinkList clist){
       int count;
       PNode q;
       ff(clist==NULL)returri 0;    /*如果是空表*/
       q=clist->link;
       count=1;
       while(q!=clist){
           q=q->link;
           count++;
       }
       relturn count;
   }
   (4)代价分析
   该算法访问循环链表中每个结点各一次,时间代价为O(n)。
【答案解析】