*/ --------------------------------------------------------------------------------------
*/ 出自： 编程中国 http://www.bc-cn.net
*/ 作者： josen0205 QQ：7007873
*/ 时间： 2007-10-23 编程论坛首发
*/ 声明： 尊重作者劳动，转载请保留本段文字
*/ --------------------------------------------------------------------------------------


/*************************************************************/
/* 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插入链表 */
tmp->data=i;
p->next=tmp;
p=tmp;
}
tmp->next=L->next; /* 最后一个节点next指针指向第一个节点 */
return 0;
}

int GetNode(LinkList &L,int n)
{
LinkList p,s;
int i=0;
p=L->next; /* p指向第一个节点 */
while(p->next!=p) /* 链表中只有一个节点时终止 */
{
i++;
if(i==n-1) /* 找到报数n的节点,输出节点值并删除节点,计数器i归位 */
{
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);

getch();
return 0;
}