问题：设有n个人围成一个圆圈，现从第s个人开始报数，数到第m的人出列，然后从出列的下一个人重新开始报数，数到第m的人再次出列，如此反复，直到所有的人全部出列为止。对于任意给定的n、s、m，求按出列次序得到的n个人员的序列。
例：
图片就是问题简单示例，里面是每次要循环的数据，后面的S是出列的人
思路：
先创建一个链表，链表的长度就是n
从第s个节点开始循环
判断是否是第m个数
如果是第m个数，就输出并删除当前节点
循环到最后一个节点，再从第一个节点接着循环
主要代码：
void yuesefu (LinkList * head, int n, int s, int m)
{
LinkList * p, * r, * q;
int i = 1, j = n, k, l;
p = GetData_LinkList(head, s); //从第S位开始
//判断是否循环完成
while (j > 0) {
//判断是否为第m个数
if (i == m) {
i = 0;
//输出这轮出局的人
printf("%d\n", p->data);
//存储当前节点的值
k = p->data;
//删除当前节点
q = head->next;
l=1;
while (q != NULL) {
//判断当前节点得值是否等于要删除的值
if (q->data == k) {
//删除节点
DeleteNode_LinkList(head, l);
break;
}
l++;
q = q->next;
}
//从下一个节点开始循环
p = GetData_LinkList(head, l);
j--;
}else {
p = p->next;
}
//如果超出链表长度，再从第一个节点开始循环
if (p == NULL)
p = head->next;
i++;
}
}
整体代码：
#include <stdio.h>
#include <stdlib.h>
typedef int elemtype;
typedef struct node
{
elemtype data;
struct node * next;
}LinkList;
//创建链表
LinkList * Create_LinkListF(int n)
{
int i;
LinkList * head, * p;
head = (LinkList *) malloc (sizeof(LinkList));
if (head == NULL)
return head;
head->next = NULL;
for (i=1; i<=n; i++) {
p = (LinkList *) malloc (sizeof(LinkList));
if (p == NULL)
return head;
p->data = i;
p->next = head->next;
head->next = p;
}
return head;
}
//按序号查找
LinkList * GetData_LinkList (LinkList * head, int i)
{
LinkList * p;
int j = 0;
if (i <= 0)
return NULL;
p = head;
while (p->next != NULL && j<i) {
p = p->next;
j++;
}
if (i == j)
return p;
else
return NULL;
}
//删除节点
int DeleteNode_LinkList (LinkList * head, int i)
{
LinkList * p, * r;
if (i <= 0)
p = NULL;
else
if (i == 1)
p = head;
else
p = GetData_LinkList(head, i-1);
if (p == NULL) {
return 0;
}else {
r = p->next;
if (r == NULL)
return 0;
p->next = r->next;
free(r);
return 1;
}
}
void yuesefu (LinkList * head, int n, int s, int m)
{
LinkList * p, * r, * q;
int i = 1, j = n, k, l;
p = GetData_LinkList(head, s); //从第S位开始
//判断是否循环完成
while (j > 0) {
//判断是否为第m个数
if (i == m) {
i = 0;
//输出这轮出局的人
printf("%d\n", p->data);
//存储当前节点的值
k = p->data;
//删除当前节点
q = head->next;
l=1;
while (q != NULL) {
//判断当前节点得值是否等于要删除的值
if (q->data == k) {
//删除节点
DeleteNode_LinkList(head, l);
break;
}
l++;
q = q->next;
}
//从下一个节点开始循环
p = GetData_LinkList(head, l);
j--;
}else {
p = p->next;
}
//如果超出链表长度，再从第一个节点开始循环
if (p == NULL)
p = head->next;
i++;
}
}
int main (void)
{
int n, s, m;
LinkList * head;
printf("n=");
scanf("%d", &n);
printf("s=");
scanf("%d", &s);
printf("m=");
scanf("%d", &m);
head = Create_LinkListF(n);
yuesefu(head, n, s, m);
}
网友评论