数据结构 —— 约瑟夫环

前两天有一个同学问了我一道约瑟夫环的问题，给他做完之后发现自己也学到不少，在这里写一篇文章记录一下。

问题描述：

约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，每报数到第 M个人该人就被拉出去杀掉，
剩下的人仍在围成一圈。然后再由下一个重新报数，直到最后剩下一个，其余人都将被杀掉。

约瑟夫环运作如下：

1. 一群人围在一起坐成环状（如： N）

2. 从某个编号开始报数（如： K）

3. 数到某个数（如：M）的时候，此人出列，下一个人重新报数

4. 一直循环，直到所有人出列，约瑟夫环结束

例如 N = 6，M = 5，被杀掉的顺序是：5，4，6，2，3，1

步骤分析：

1、使用 CreateList 函数建立循环链表（表示围成一圈的人），队列长度由参数N指定（元素编号为1~N，表示每个人的编号），该函数返回循环队列的第一个元素的指针。

2、设置 now 指针指向第一个元素（表示当前报数的人，从第一个人开始报数）。

3、设置 i 的值为1（表示当前报道的数，默认从1开始报数）。

4、判断当前队列是否为空（如果为空表示所有人均已经出局，程序结束，如果不为空则执行以下循环）。

5、判断这个人报的数是否为 m 。

6、如果是，表示这个人出局，保存这个人的下一个人（因为这个人会被删除，无法得到下一个人），调用 DelItem 函数删除节点（该函数会返回被删除节点的序号），输出被删除节点的序号，设置报数重新开始，设置当前人为下一个人。

7、如果不是就报数 +1，继续下一个人。

程序框图：

伪代码实现（类C代码）：

// 初始化循环队列
list = CreateList(N);
    
// 当前指向队列头
now = list;

// 从第一个数开始报数，当队列不空
i = 1;
while(!is_empty(list))
{
    // 如果这个人报到M，出局
    if(i == M)
    {
        // 这个人的下一个人
        next = now->next;
        // 调用函数删除这个人人
        num = DelItem(list,now);
        // 输出被删除人的序号
        printf("%d\n",num);
        // 从1开始再次报数
        i = 1;
        now = next;
    }
    else
    {
        // 报数+1
        i++;
        //下一个人
    	now = now->next;
    }
    
}

C语言实现（VS2017）：

#include <stdio.h>
#include <stdlib.h>

// 节点
typedef struct node
{
	int num;                      // 节点的序号
	struct node* next;            // 下一个节点的指针
}NODE,*LIST;

LIST CreateList(int);                 // 建立循环链表
int is_empty(LIST);                   // 判断循环链表是否为空
int DelItem(LIST*,NODE*);             // 删除元素

int main(void)
{
	// n为人数，m为报到几的出局，可以使用scanf()函数获取，这里没有这么写
	// i为当前报道的数，num为出局的序号
	int m = 3, n = 41, i = 0, num = 0;

	LIST list = NULL;
	NODE* now = NULL;
	NODE* next = NULL;

	// 初始化循环队列
	list = CreateList(n);

	// 当前指向队列头
	now = list;

	// 从第一个数开始报数，当队列不空
	i = 1;
	while (!is_empty(list))
	{
		// 如果这个人报到M，出局
		if (i == m)
		{
			// 这个人的下一个人
			next = now->next;

			// 调用函数删除这个人
			num = DelItem(&list, now);

			// 输出被删除人的序号
			printf("%d\n", num);

			// 从1开始再次报数
			i = 1;
			now = next;
		}
		else
		{
			// 报数+1
			i++;

			//下一个人
			now = now->next;
		}
	}
	// 等待输入，vs2017需要这句暂停程序
	getchar();
	return 0;
}


// 建立循环链表
LIST CreateList(int n)
{
	if (n == 0)
	{
		return NULL;
	}
	else
	{
		// 当前的节点值
		int i = 1;

		// 循环链表
		LIST list = NULL;

		// 两个工作节点
		NODE* p = NULL;
		NODE* q = NULL;

		// 生成第一个节点
		p = (node*)malloc(sizeof(node));
		p->num = i;
		list = p;
		 
		// 当前节点个数小于总个数
		while(i < n)
		{
			// 节点序号+1
			i++;

			// 生成新节点
			q = (NODE*)malloc(sizeof(NODE));

			// 把新节点插入链表
			q->num = i;
			q->next = NULL;
			p->next = q;
			p = q;
		}

		// 设置链表为循环链表
		p->next = list;
		return list;
	}
}


// 判断是否是空队列
int is_empty(LIST list)
{
	return list == NULL;
}


//删除元素
int DelItem(LIST* plist, NODE* now)
{
	if (is_empty(*plist))
	{
		return 0;
	}
	else if((*plist)->next == *plist)  //如果是最后一个元素
	{
		int num = 0;
		num = (*plist)->num;
		free((*plist)->next);
		*plist = NULL;
		return num;
	}
	else
	{
		if ((*plist) == now)  // 要删除表头元素
		{
			(*plist) = (*plist)->next;  // 设置下一个元素为表头元素
		}

		// 工作节点
		NODE *p = (*plist);
		NODE *temp = NULL;

		int num = 0;
		// 查找要删除节点的前一个节点
		while (p->next != now)
		{
			p = p->next;
		}

		// 删除节点
		temp = p->next;
		p->next = temp->next;
		num = temp->num;
		free(temp);
		return num;
	}
}