C语言数据结构中约瑟夫环问题如何解决

本文小编为大家详细介绍“C语言数据结构中约瑟夫环问题如何解决”，内容详细，步骤清晰，细节处理妥当，希望这篇“C语言数据结构中约瑟夫环问题如何解决”文章能帮助大家解决疑惑，下面跟着小编的思路慢慢深入，一起来学习新知识吧。

问题描述

约瑟夫环问题的一种描述是：将编号为1，2，...n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数，报道m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。设计一个程序求出出列顺序。

基本要求

利用单向循环链表存储结构模拟此过程，按照出列的顺序印出个人的编号。

测试数据

m的初值为20；n = 7,7个人的密码依次为：3，1，7，2，4，8，4，首先m值为6（正确的出列顺序应为6，1，4，7，2，3，5）。

实现思路1

用的是数组索引。结合一点点的算法知识。

#include<stdlib.h>
#include<stdio.h>
//#用数组索引的模式 
int main(){
	int m;
	printf("请输入m的值：");
	scanf("%d",&m);
	int n;
	printf("请输入n的值:"); 
	scanf("%d",&n);
	int a[100];
	for(int i = 0;i<n;i++){
		scanf("%d",&a[i]);
	}
	int cnt = 0;
	int cnt1 = 0;
	int i = 0;
	while(1){
		if (a[i]!=0){
			cnt++;
			if(cnt==m){
				m = a[i];
				a[i] = 0;
				cnt = 0;
				printf("%d ",i+1);
				cnt1++;
			}
			if(cnt1==n){
				break;
			}
		}
		i = (++i)%n;
	} 
}

实现思路2

利用单项循环链表的方式，上干货

运用的函数：

• 创建链表

• 取得链表的下标

• 删除链表指定下标的元素

• 得到第i个元素值

数据结构的定义：

• 结构体 LNode，成员包括：原始下标，元素值

• 主函数的思路：

其中上面的函数都是参考《数据结构（C语言版）》上面。只是将创建链表的函数改成创建单向循环链表的函数。写代码主要时间消耗在主函数上。

主函数的思路：

创建一个指定大小（n）的循环链表，每一次循环得到第m个元素，记录此元素的下标，然后移动头结点到删除元素前面的结点，再把此时的头节点后面1一个结点给删除。依次遍历到n个。

#include<stdlib.h>
#include<stdio.h>
//用单项循环列表的方式 
//数据类型的定义 
typedef struct LNode{
	int data;		//定义密码值 
	int index; 		//定义数据的下标 
	struct LNode *next;
}LNode,*LinkList;
int GetElem_L(LinkList L,int i ,int &e){
	LNode* p;				//注意这里的*号 
	p = L->next;
	int j = 1;
	while(p&&j<i){
		p = p->next;
		++j;
	} 
	if(!p || j>i)
	{
		return -1;
	}
	e = p->data;
//	printf("%d ",e);
	return e;
}//GetElem_L
int GetIndex_L(LinkList L,int i ,int &e){
	LNode* p;				//注意这里的*号 
	p = L->next;
	int j = 1;
	while(p&&j<i){
		p = p->next;
		++j;
	} 
	if(!p || j>i)
	{
		return -1;
	}
	e = p->index;
//	printf("%d ",e);
	return e;
}//GetIndex_L
int ListDelete_L(LinkList &L,int i,int &e){
	LNode* p;				//注意这里的*号
	p  = L;
	int j = 0;
	while(p->next&&j<i-1){
		p = p->next;
		++j;
	}
	if(!(p->next)||j>i-1){
		return -1;
	}
	LNode* q;
	q = p->next;
	p->next = q->next;
	e = q->data;
	free(q);
	return e; 
}//ListDelete_L
void CreateList_L(LinkList &L,int n){
	L = (LinkList)malloc(sizeof(LNode));
	L->next = NULL;
	LNode* tmp = (LinkList)malloc(sizeof(LNode));
	tmp = L;
	for(int i = 0;i<n-1;++i){
		LNode* p = (LinkList)malloc(sizeof(LNode));
		scanf("%d",&p->data);
		p->index = i+1;
		p->next = tmp->next;
		tmp->next = p;
		tmp = tmp->next;
	}
	LNode* p = (LinkList)malloc(sizeof(LNode));          //注意这里的*号
	scanf("%d",&p->data);
	p->index = n;
	p->next = L->next;
	tmp->next = p;
}//创建循环链表 
int main(){
	int m;
	int cnt;
	printf("请输入m的值：");
	scanf("%d",&m);
	int n;
	printf("请输入n的值: "); 
	scanf("%d",&n);
	LNode* L;						//注意这里的*号
	CreateList_L(L,n);	
	int e = 0 ;
	int index = 0;
	for(int i = 0;i<n;i++){
		GetElem_L(L,i+1,e);
	}
	for(int i = 0;i<n;i++){
		int l = 0;
		l = GetIndex_L(L,m,index);
		printf("%d ",l);
		int tmp = GetElem_L(L,m,e);
		for(int i = 0;i<m-1;i++){		
			L = L->next;
		}
		ListDelete_L(L,1,e);
		m =  tmp;
	}
}

结果

读到这里，这篇“C语言数据结构中约瑟夫环问题如何解决”文章已经介绍完毕，想要掌握这篇文章的知识点还需要大家自己动手实践使用过才能领会，如果想了解更多相关内容的文章，欢迎关注亿速云行业资讯频道。