/*************************************************************/
/*
M个人围成一圈,从1至N开始顺序循环报数
*/
/*
每数到N的人出列,输出该数值,直至全部输出
*/
/*************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
/* 循环链表结构 */
typedef struct Node{
int data;
struct Node *next;
}*LinkList;
int CreateList(LinkList &L,int m); /* 将m个人1到m编号依次插入循环链表L中 */
int GetNode(LinkList &L,int n); /* 依次删除输出链表中符合要求的节点 */
int CreateList(LinkList &L,int m)
{
int i=1;
LinkList tmp,p;
L=(LinkList)malloc(sizeof(struct Node));
if(L==NULL)
{
printf("动态分配内存失败!");
return -1;
}
p=L;
for(i=1;i<=m;i++) /* 依次为节点分配内存,插入链表 */
{
tmp=(LinkList)malloc(sizeof(struct Node));
if(tmp==NULL)
{
printf("动态分配内存失败!");
return -1;
}
tmp->data=i;
p->next=tmp;
p=tmp;
}
p->next=L->next; /* 最后一个节点next指针指向第一个节点 */
return 0;
}
int GetNode(LinkList &L,int n)
{
LinkList p,s;
int i=0;
p=L->next;
while(p->next!=p) /* 链表中只有一个节点时终止 */
{
i++;
if(i==n-1) /* 找到报数n的节点,输出节点值并删除节点 */
{
s=p->next;
p->next=p->next->next;
printf("%d ",s->data);
i=0;
free(s);
}
p=p->next;
}
printf("%d ",p->data);
free(p);
free(L);
return 0;
}
int main()
{
int m,n;
LinkList L;
printf("Enter the total number of the person[m]:"); /* 总人数 */
scanf("%d",&m);
printf("Enter the number of get out[n]:");
scanf("%d",&n);
CreateList(L,m);
printf("The out queue is:\n");
GetNode(L,n);
printf("\n");
getch();
return 0;
}