约瑟夫环

约瑟夫环（约瑟夫问题）：

已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。
输出出列的顺序。

思考

其实这个问题可以用01数组+while循环取模来实现，代码实现非常简单。
然而老师要求要用链表来写，啊~我以前只写过前向星，这里贴出前向星的解析，所以遇到这样的指针啊什么内存啊什么的东西就非常让人摸不到头脑，于是一边百度一边写。
这里我设置了一个head和一个tail代表队列的首尾。

  1. malloc()这个函数的返回值是void，所以为了避免出错，要强制类型转换一下，比如我这个指针的类型是struct Node，所以在这里：

    1
    p = (struct Node *)malloc(sizeof(struct Node));

  2. 指针分配内存后就不用让它=NULL了。C++也是~

  3. 至于VS怎么建立C工程文件，右侧解决方案资源管理器中右键cpp文件重命名为c后缀就好啦。
  4. VS对c编译很严格，现在define都不管用了，也只有用#pragma warning(disable:4996)来忽略警告了。
  5. VS中编译c文件使用预编译头会报错，调试 –> 属性 –> C/C++ –> 预编译头 –> 不使用预编译头。

贴上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#pragma warning(disable:4996)
#include "stdafx.h"
#include <stdio.h>
#include <malloc.h>
#define Size 1000
struct Node
{
	int data;
	struct Node *next;
};
struct Node *head;
struct Node *tail;
void jose(int n, int m, int k)
{
	int i;
	struct Node *p;
	p = (struct Node *)malloc(sizeof(struct Node));
	p->data = 1;
	head = tail = p;
	for (i = 2; i <= n; i++)
	{
		p = (struct Node *)malloc(sizeof(struct Node));
		p->data = i;
		tail->next = p;
		tail = p;
	}
	tail->next = head;
	struct Node *node;
	p = head;
	while (p->data != k) p = p->next;
	while (p->next != p)     //当仅剩一个节点时
	{
		for (i = 2; i < m; i++) p = p->next;
		node = p->next;
		printf("%d ", node->data);
		p->next = node->next;
		free(node);
		p = p->next;
	}
	printf("%d ", p->data);
	free(p);
	printf("\n");
}
int main()
{
	int n, m, k;
	while (scanf("%d%d%d", &n, &m, &k) != EOF) jose(n, m, k);
    return 0;
}



以下是改进的双向链表写法，其实也没有什么不一样，就是变得可以任意左右方向都可以数。
具体的操作是，每次有人出列后人数n都会减1，即有可能出现m>n的情况，所以每次人出列后都使m对n取模，这样首先保证m是小于n的。然后每次出列操作之前都对m进行判断，如果m小于n的一半就顺序数，否则就倒着数。
注意：因为正着数时起始报数的人本身会报一个数，但是倒着数的时候他是不报数的，所以正着数是从2开始数，枚举到要出局的人的上一位，倒着数就从1开始数，数到要出局的人的下一位。
这里我特判了m==1的情况，如果要删除自身，就把p置于p的前驱就好啦，后面的删除步骤是一样的。



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#pragma warning(disable:4996)
#include "stdafx.h"
#include <stdio.h>
#include <malloc.h>
#define Size 1000
struct Node
{
	int data;
	struct Node *next;
	struct Node *pre;
};
struct Node *head;
struct Node *tail;
void jose(int n, int m, int k)
{
	int i;
	struct Node *p;
	p = (struct Node *)malloc(sizeof(struct Node));
	p->data = 1;
	head = tail = p;
	for (i = 2; i <= n; i++)
	{
		p = (struct Node *)malloc(sizeof(struct Node));
		p->data = i;
		tail->next = p;
		p->pre = tail;
		tail = p;
	}
	tail->next = head;
	head->pre = tail;
	struct Node *node;
	p = head;
	while (p->data != k) p = p->next;
	while (p->next != p)
	{
		m = (m - 1) % n + 1;   //保证 m < n 且 m != 0
		if (m <= (n + 1) / 2)
		{
			if (m == 1) p = p->pre;
			else for (i = 2; i < m; i++) p = p->next;
			node = p->next;
			node->next->pre = p;
			p->next = node->next;
			p = p->next;
		}
		else
		{
			for (i = 1; i < n - m + 1; i++) p = p->pre;
			node = p->pre;
			node->pre->next = p;
			p->pre = node->pre;
			p = p->pre;
		}
		printf("%d ", node->data);
		free(node);
		n--;
	}
	printf("%d ", p->data);
	free(p);
	printf("\n");
}
int main()
{
	int n, m, k;
	while (scanf("%d%d%d", &n, &m, &k) && n && m && k) jose(n, m, k);
    return 0;
}

文章目录
  1. 1. 约瑟夫环（约瑟夫问题）：
  2. 2. 思考
|