[数据结构与算法]循环队列解决约瑟夫环问题

问题描述
编号为1、2、…按顺时针坐在一张圆桌周围，每人持有一个密码，一个人选任意正整数为报数上限m,从第一个人开始报数报到m时停止报数，这个人出列，直到所有的人都出列，游戏结束。用线性表的内容来实现这个程序。
解决问题的步骤：
第一步：建立n个节点的无头循环链表。
第二步：从链表的第一个节点开始计数，直到寻找到第m个节点第三步:输出该节点的id值，并将其password值，作为新的m值。
第三步：输出该节点的id值，并将其passward值作为新的m的值。
第四步：根据新的m值，不断从链表中删除节点，直到循环链表为空，程序结束。

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

typedef void  CLinkQueue;
typedef int ElemType;
typedef struct CLinkQueueNode
{
	CLinkQueueNode* next;
	ElemType data;
	
}CLinkQueueNode;
typedef struct TCLinkQueue
{
	CLinkQueueNode base;
	CLinkQueueNode *header;
	CLinkQueueNode *rear;
	int length;
	
}TCLinkQueue;

//创建循环队列
CLinkQueue* Init()
{
	TCLinkQueue* tmp = nullptr;
	tmp = (TCLinkQueue*)malloc(sizeof(TCLinkQueue));
	memset(tmp, 0, sizeof(TCLinkQueue));
	tmp->length = 0;
	tmp->rear = tmp->header = &tmp->base;
	if (!tmp)
		exit(-1);
	return tmp;
}


int DeQueue(CLinkQueue* q, ElemType& e);
//销毁循环队列
int Destroy(CLinkQueue* q)
{
	if (q)
	{
		ElemType e;
		TCLinkQueue* H = (TCLinkQueue*)q;
		while (H->length > 0)
			DeQueue(q, e);
		free(H);
		H->header = H->rear = nullptr;
		H->length = 0;
		q = nullptr;
		return 1;

	}
	return -1;
}

//清空循环队列
int Clear(CLinkQueue* q)
{
	if (q)
	{
		ElemType e;
		TCLinkQueue* H = (TCLinkQueue*)q;
		while (H->length > 0)
			DeQueue(q, e);
		H->header = H->rear = nullptr;
		H->length = 0;
		return 1;

	}
	return -1;
}

//返回队列的长度
int Length(CLinkQueue* q)
{
	if (q)
	{
		TCLinkQueue* H = (TCLinkQueue*)q;
		return H->length;
	}
	return -1;
}
//在队尾插入一个元素

int EnQueue(CLinkQueue* q, ElemType e)
{
	if (q!=nullptr)
	{
		TCLinkQueue* H = (TCLinkQueue*)q;
		CLinkQueueNode* elem = (CLinkQueueNode*)malloc(sizeof(CLinkQueueNode));
		memset(elem, 0, sizeof(CLinkQueueNode));
		elem->data = e;
		if (H->length == 0)
		{
			H->base.next = elem;
			H->header = elem;
			H->rear = elem;
		}
		else
		{
			elem->next = H->header;
			H->rear->next = elem;
			H->rear = elem;
			
		}
		++H->length;
		
		return 1;
	}
	return -1;
}

void GetHeader(CLinkQueue* q, ElemType& e)
{
	if (q)
	{
		TCLinkQueue* H = (TCLinkQueue*)q;
		if (H->length > 0)
		{
			e = H->header->data;
		}
	}
}
int DeQueue(CLinkQueue* q, ElemType& e)
{
	if (q)
	{
		TCLinkQueue* H = (TCLinkQueue*)q;
		if (H->length > 0)
		{
			
			CLinkQueueNode* tmp = H->header;
			e = H->header->data;
			H->header = tmp->next;
			H->base.next = H->header;
			if (tmp == H->rear)
			{
				H->header = H->header = &H->base;
			}
			free(tmp);
			--H->length;
			return 1;
		}
		
	}
	return -1;
}

void prin(ElemType e)
{
	printf("%-5d", e);
}
void Traverse(CLinkQueue* q,void (*p)(ElemType e) )
{
	if (q)
	{
		TCLinkQueue* H = (TCLinkQueue*)q;
		ElemType e;
		CLinkQueueNode* ptr = H->header;
		for (int i = 0; i < H->length; ++i)
		{
			e = ptr->data;
			p(e);
			ptr = ptr->next;
		}
		
		printf("\n");
	}
}
void Test()
{//测试队列的对不对
	CLinkQueue* q = nullptr;
	int len;
	ElemType e;
	q = Init();
	if (q)
	{
		printf("this is true\n");
		 len = Length(q);
		printf("length is %d\n", len);
	}

	//插入第一个元素
	EnQueue(q, 1);
	EnQueue(q, 2);
	len = Length(q);
	printf("length is %d\n", len);
	DeQueue(q,e);
	printf("elem e is %d\n", e);
	GetHeader(q, e);
	printf("elem e is %d\n", e);

	len = Length(q);
	printf("length is %d\n", len);
		
}
void Josephson()
{
	CLinkQueue* q = nullptr;
	q = Init();
	int pos = 1;
	int m;
	int len;
	ElemType e;
	int n;
	printf("请输入需要插入的元素个数：  ");
	scanf("%d", &n);
	while (n > 0)
	{//构建约瑟夫的循环队列的中的元素
		printf("\n请输入需要插入的元素：  ");
		scanf("%d", &e);
		
		EnQueue(q, e);
		--n;
	}
	printf("遍历循环队列得：\n");
	Traverse(q, prin);
	len = Length(q);
	printf("length is %d\n",len);
	printf("\n请输入要删除的跳跃的位数:  ");//决定将第几个人退出队列跨度，从第一个人开始
	scanf("%d", &m);
	TCLinkQueue* H = (TCLinkQueue*)q;
	CLinkQueueNode* ptr = &H->base;
	CLinkQueueNode* dl = nullptr;
	while (Length(q)>0)
	{
		
		for (int i = 1; i < m; ++i)
		{
			ptr = ptr->next;
		}
		ElemType e = ptr->next->data;
		dl = ptr->next;
		ptr->next = ptr->next->next;
		--H->length;
		free(dl);
		printf("退出队列的是第%3d   位元素：%-5d\n",pos++, e);
		
	}
	printf("测试完毕！\n");//从1-10 依次退出的是：3 -- 6 -- 9 -- 2 -- 7 -- 1 -- 8 -- 5 -- 1 -- 4 -- 0
	len = Length(q);
	printf("\nlength is %d\n", len);

}
int main()
{
	
	Josephson();//解决约瑟夫问题
	system("pause");
	return 0;

}