循环链表解决约瑟夫问题

循环链表的存在很难想象他的应用范围到底是哪里，本文主要介绍的是通过循环链表处理解决约瑟夫问题，让大家更深刻的理解循环链表的使用和应用场景。

例题：n 个人围成一个圆圈，首先第 1 个人从 1 开始一个人一个人顺时针报数，报到第 m 个人，令其出列。然后再从下一 个人开始从 1 顺时针报数，报到第 m 个人，再令其出列，…，如此下去，求出列顺序。
假设： m = 8，n=3

最后我们得出的结果便是 ： 3 6 1 5 2 8 4 7

很明显，如果用循环链表来处理这个问题，将非常简单。大致的思路如下：

1. 生成一个有 8 个数据的循环链表
2. 无限循环遍历链表
3. 无限循环中增加for循环，每次循环 n – 1 次，每循环一次移动一次游标，将for循环完成后游标指向的数据删除
4. 依次执行，直到链表为空为止

【实现代码】

注意：需要用到上一篇文章我们编写的 CircleList.h 和 CircleList.c 文件。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "circlelist.h"

//定义结构体,存储数据
typedef struct tag_value
{
	CircleListNode header;
	int v;
}Value;

void joseph_question()
{
	int i;
	//定义结构体数组
	Value val[8];
	//创建循环链表
	CircleList* list = CircleList_Create();
	//判断链表是否创建成功
	if (list == NULL)
	{
		printf("链表创建失败\n");
		return;
	}
	//初始化结构体数组
	for (i = 0; i < sizeof(val) / sizeof(Value); ++i)
	{
		val[i].v = i+1;
		//往循环链表中插入数据
		CircleList_Insert(list, (CircleListNode*)&val[i], i);
	}
	//遍历循环链表
	printf("插入数据:\n");
	for (i = 0; i < CircleList_Length(list); ++i)
	{
		//获取游标指向的元素然后下移
		Value* pVal = (Value*)CircleList_Get(list, i);
		printf("%d\t", pVal->v);
	}

	//重置游标
	CircleList_Reset(list);
	//循环删除指定位置的元素
	printf("\n\n依次删除的节点为:\n");
	while (CircleList_Length(list) > 0)
	{
		//定义结构体指针变量,指向符合条件的元素
		Value* pVal = NULL;
		//根据条件查找指定位置的元素
		for (i = 0; i < 3-1; ++i)	//3为案例中的m
		{
			//向后移动游标
			pVal = (Value*)CircleList_Next(list);
		}
		//保存符合条件的节点
		pVal = (Value*)CircleList_Current(list);
		//打印节点信息
		printf("%d\t", pVal->v);
		//从链表中删除符合条件的节点
		CircleList_DeleteNode(list, (CircleListNode*)pVal);
	}
	printf("\n");
	//销毁循环链表
	CircleList_Destroy(list);
}

void main()
{
	joseph_question();
}