问题:13个学生(姓名,成绩)围成一圈,从第一个人开始报数,1,2,3,4,...凡报到n的人出圈,
,下一个人继续从1开始报数,还是报到n的人出圈,重复上述步骤,找出最后留在圈中的学生。
提示:用链表实现
分析:
(1)构建链表
(2)统计最后留在圈中的学生
(1)构建链表
struct node
{
char name[20];
int score;
struct node *next;
};
设计一个函数(构建链表)
struct node *createlist(int n)
{
创建一个头结点;
head,p,q指向头结点
循环n次{
创建一个p节点;存放数据;q->next=p;q=p;}
q->next=NULL;
return head;
}
struct node *createlist(int n,char *xm[],int cj[])
{
int i;
struct node *head,*p,*q;
p=(struct node *)malloc(sizeof(struct node));
head=q=p;
for(i=0;i<n;i++)
{
p=(struct node *)malloc(sizeof(struct node));
strcpy(p->name,xm[i]);p->score=cj[i];
q->next=p;q=p;
}
q->next=NULL;
return head;
}
(2)统计最后留在圈中的学生
设计一个函数(统计最后留在圈中的学生)
void count(struct node *head,int n)
{
将数据节点构建一个环形;
环形遍历所有数据节点
{
报数;
当前报数到了出圈号?
如到了
{
报数计数器清0;
判断当前节点是否为首节点?如果是,则让head->next指向首节点的后继节点;
删除当前节点;
}
否则,则{报数节点指针往后平移一个节点(p,q)}
}
}
void count(struct node *head,int n)
{
int i=0;
struct node *p,*q;
p=head;q=head->next;
while (q->next!=NULL) q=q->next;
q->next=p->next;//数据节点构建成一个环形
while (p->next!=p)
{
i++;
if (i==n)
{
if (q==head->next) head->next=q->next; //让原先的第二个数据节点成为新的首节点
i=0;
p->next=q->next;
free(q);
q=p->next;
}
else
{p=q;q=q->next;}
}
}
[1]
[2]
下一页