戳这里还有其他数据结构的题目噢

https://blog.csdn.net/qq_45724947/article/details/115625130?spm=1001.2014.3001.5501

5.分别以单向链表解决约瑟夫环问题(JosephusProblem)，比较采用三种不同存储结构解决该问题的算法时间复杂度。具体要求 与实验一的实验内容第5题类似。

 直接上代码：

单项解决约瑟夫环

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

#define TRUE        1
#define FALSE       0
#define OK          1
#define ERROR       0         //函数结果状态代码
#define INFEASIBLE -1
#define OVERFLOW   -2 

struct YueNode{
	int number;
	int password;
	struct YueNode *next;
};
struct YueNode *head,*p,*q;


int init_list(int n)//创建链表  n为总人数 
{
	head = (struct YueNode*)malloc(sizeof(struct YueNode));
	if(!head)
		return OVERFLOW;
	p = head;
	for(int i = 1;i < n;i++)
	{
		q = (struct YueNode*)malloc(sizeof(struct YueNode));
		if(!q)
			return OVERFLOW;
		p->next = q;
		p = q;
	}
	p->next = NULL;//尾结点指向 NULL 
	p = head;//将p放至头节点 
	return OK;
}

void scanf_list(int n)//输入顺序表 
{	
	head = p;//记录头节点
	printf("请输入每个同学持有密码：\n");
	for(int i = 0;i < n; i++)
	{	
		printf("第%d个同学的密码：",i+1);
		scanf("%d",&(p->password));//输入每个同学持有的密码 
		p->number = i;
		p = p->next;
	}
	printf("\n");
	p = head;//将p放至头节点
}

void print_result(int bingo,int n)//first初始报数时计数变量
{
	head = p;
	int m = 0,k = 0;//m为退出人数,k报数时计数变量
    int i = 0;//i为每次循环时计数变量
    while(m < n - 1)//还有超过1人未退出时，执行循环
    {
        if(p->password != -1) 
			k++;	
        if(k == bingo)//k=密码时，有人应该出局了
        {	
			m++;//有人退出，m++
            printf("第%d个出队编号为：%d\n",m,i+1);
            bingo = p->password;
			p->password = -1;//退出的人编号置为0
            k = 0;//一轮数数结束，k置为0
        }
        p = p->next;
		i++;//使指针下移
        if(i == n)
			{p = head;
			i = 0;}//报数到最后一个编号，将i恢复为0
    }
    while(p->password == -1) 
		{p = p->next;
		i++;}//最后剩下来的人编号不=0，寻找这一个
    printf("最后一个出队的编号为%d\n",i+1);//把编号不为0的编号输出即可
    p = head;
}

int main()
{	
	int n,k;//n为总人数，k报数时计数变量； 
	printf("请输入参加总人数：");
	scanf("%d",&n);
	printf("请输入 初始报数上限值：");
	scanf("%d",&k); 
	init_list(n);
	scanf_list(n);
	print_result(k,n);
	return 0;
	
}

环形解决约瑟夫环

#include <stdio.h>
#include <stdlib.h>//   链表完成 

#define TRUE        1
#define FALSE       0
#define OK          1
#define ERROR       0         //函数结果状态代码
#define INFEASIBLE -1
#define OVERFLOW   -2 

struct YueNode{
	int number;
	int password;
	struct YueNode *next;
};
struct YueNode *head,*p,*q;

int init_Node(int n)//创建链表 
{
	head = (struct YueNode*)malloc(sizeof(struct YueNode));//
	if(!head)
		return OVERFLOW;
	p = head;
	for(int i = 1;i < n;i++)
	{
		q = (struct YueNode*)malloc(sizeof(struct YueNode));
		if(!q)
			return OVERFLOW;
		p->next = q;
		p = q;
	}
	p->next = head;//		p为最后一个，其next连接head头节点 
	q = head;//		q指向head头节点便于赋值 
	return OK;
}

int scanf_password(int n)
{
	printf("请输入持有密码：\n");
	for(int i = 1;i <= n;i++)
	{	
		printf("第%d个:",i);
		scanf("%d",&(q->password));
		q->number = i;
		q = q->next;
	}
	q = p;//p为最后一个，q也为最后一个，遍历时可以让   第一的序号指向头节点 
	return OK;
}

int print_result(int m,int n)//m为第一次的密码值，n为人数 
{
	for(int i = 1;i <= n;i++)
	{
		for(int j = 1; j < m;j++)
		{
			q = q->next;
		}
		p = q->next;
		printf("\t第%d个出队的人是：%d\n",i,p->number);
		m = p->password;
		q->next = p->next;
		free(p);
	}
}

int main()
{
	int m,n;
	printf("\nm为第一次的参数密码，n为总人数\n");
	printf("请输入m，n的值：\n");
	scanf("%d %d",&m,&n);
	init_Node(n);
	scanf_password(n);
	printf("出队情况：\n");
	print_result(m,n);
	return 0;
}

（请不要直接复制使用。代码仅供参考，希望读者借此代码自身可以理解学习）

如果代码对您有帮助，不要忘记评论收藏噢~