阅读以下说明和C程序,填充函数中的空缺。
[说明]
N个游戏者围成一圈,从1~N顺序编号,游戏方式如下;从第一个人开始报数(从1到3报数),凡报到3的人退出圈子,直到剩余一个游戏者为止,该游戏者即为获胜者。
下面的函数playing(Linklist head)模拟上述游戏过程并返回获胜者的编号。其中,N个人围成的圈用一个包含N个结点的单循环链表来表示,如图1所示,游戏者的编号放在结点的数据域中。
在函数中,以删除结点来模拟游戏者退出圈子的处理。整型变量c(初值为1)用于计数,指针变量p的初始值为head(如图1所示)。游戏时,从p所指向的结点开始计数,p沿链表中的指针方向遍历结点,c的值随p的移动相应地递增。当c计数到2时,就删除p所指结点的下一个结点(因下一个结点就表示报数到3的游戏者),如图2所示,然后将c设置为0后继续游戏过程。
结点类型定义如下:
typedef struct node
int code; /*游戏者的编号*/
struct node *next;
NODE, *LinkList;
[C函数]
int P1aying(LinkList head,int n)
/*head指向含有n个结点的循环单链表的第一个结点(即编号为1的游戏者)*/
LinkList p=head,q;
int thewinner,c=1;
while(n>______)
if(c==2) /*当c等于2时,p所指向结点的后继即为将被删除的结点*/
q=p->next;
p->next=______;
printf("%d\t",q->code); /*输出退出圈子的游戏者编号*/
free(q);
/*if*/
p=______;
/*while*/
theWinner=______;
free(p);
return theWinner; /*返回最后一个游戏者(即获胜者)的编号*/
参考答案:p->code
解析:本题要求完成程序,该程序的功能是删除报号为3的结点,直到剩下一个结点为止。while语句中的n的取值范围从1到N,又因为while语句先执行中括号里的语句在判断n值,所以第一空应填n>1,while语句中的if条件语句是判断p指向的下一结点是否该删除,若当c为2时,则p指向的当前结点报号为2,p指向的下~个结点,即p->next的报号应为3,该删除,这时应该将p->next的指向c为3的结点的下一个结点,即p->next->next,再将p->next删除,所以第二空应该填p->next->next,删除p->next之后将开始新一轮的报数,根据题意,将c值重新设置为0后继续,所以第三空对c重新赋值,应该填0,此时,n个数已经删去一个数,所以n的值相应的要减少,if语句执行完后,跳出if语句,将p重新赋值,即第四空p=p->next,当从1到n都执行一遍后,会有一个人留下,即为获胜者,第五空是给获胜者编号赋值所以应该填p->code,最后返回获胜者编号,该程序执行完毕。