【正确答案】(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)。
【答案解析】