// 实现方法:循环链表(包括链表的创建和结点的删除)
#include
#include
// 定义链表节点
typedef struct node
{
int data;
struct node *next;
}linklist;
// 创建循环链表(后插法)
linklist *createhrear(int t)
{
int i = 2;
linklist *head, *rear, *r;
head = (linklist *)malloc(sizeof(linklist));
head->data = 1;
rear = head;
while(i<=t)
{
r = (linklist *)malloc(sizeof(linklist));
r->data = i;
rear->next = r;
rear = r;
i++;
}
rear->next = head;
return(head);
}
// 输入:n 游戏总人数
// s 报数的起始编号
// m 报数的数值
// 输出:p 指向长度为n的数组,出圈次序保存在p指向的数组中
void circle_sort(int n, int s, int m, int *p)
{
linklist *q, *Nextq;
int i, j, k;
q = createhrear(n); // 获取链表头结点
// 寻找起始编号对应的结点
for(j=1; j q = q->next;
for(i=1; i<=n; i++)
{
// 定位报数为M的人
for(j=1; j q = q->next;
*(p+i-1) = q->data; // 记录出圈人的编号(组合成出圈次序)
// 定位报数为M的人的下一个人Nextq
Nextq = q->next;
// 定位报数为M的人的前一个人Frontq
for(k=1; k<=n-i; k++)
q = q->next;
free(q->next); // 删除出圈人所对应的结点
q->next = Nextq;
q = q->next;// 下次报数从出圈人的下一个人开始
}
}