当前位置:   article > 正文

C语言循环链表实现约瑟夫环问题_c语言使用循环链表编写约瑟夫问题

c语言使用循环链表编写约瑟夫问题

问题描述

约瑟夫环问题
(1)问题描述
设有编号为1,2,…,n的n(n>0)个人围成一个圈,每个人持有一个密码m。从第一个人开始报数,报到m时停止报数,报m的人出圈,再从他的下一个人起重新报数,报到m时停止报数,报m的出圈,……,如此下去,直到所有人全部出圈为止。当任意给定n和m后,设计算法求n个人出圈的次序。
(2)基本要求
建立模型,确定存储结构。
对任意n个人,密码为m,实现约瑟夫环问题。
出圈的顺序可以依次输出,也可以用一个数组存储。
(3)设计思想
首先,设计实现约瑟夫环问题的存储结构。由于约瑟夫环问题本身具有循环性质,考虑采用循环链表,为了统一对表中任意结点的操作,循环链表不带头结点。将循环链表的结点定义为如下结构类型:
struct Node
{
int data;
Node *next;
};
其次,建立一个不带头结点的循环链表并由头指针first指示。
最后,设计约瑟夫环问题的算法。

解析过程

举个例子

在这里插入图片描述

完整代码

#include<stdio.h>
#include<stdlib.h>
//@lininig,哈尔滨工程大学
typedef struct node
{
	int data;
	struct node* next;
}Node;
//声明
void PrintJosephRing(Node* first, int m);
void JosephRing(int n, int m);
int main()
{
	int n, m;
	printf("输入n的值:n=");
	scanf("%d", &n);
	printf("输入m的值:m=");
	scanf("%d", &m);
	JosephRing(n, m);
	return 0;
}
//建立约瑟夫环循环链表
void JosephRing(int n, int m)
{
	//头指针,工作指针,尾指针
	Node* first = NULL, * p = NULL, * r = NULL;
	//创建第一个人first
	first = (Node*)malloc(sizeof(Node));
	if (!first)
	{
		printf("memory allocation failed");
		return;
	}
	first->data = 1;
	first->next = NULL;
	p = first;
	//循环创建剩下的n-1个人
	for (int i = 2; i <= n; i++)
	{
		r = (Node*)malloc(sizeof(Node));
		if (!r)
		{
			printf("memory allocation failed");
			return;
		}
		r->data = i;
		r->next = NULL;
		p->next = r;
		p = p->next;
	}
	//连接头尾,实现循环链表
	p->next = first;
	p = p->next;
	PrintJosephRing(first, m);
}
//实现出圈
void PrintJosephRing(Node* first, int m)
{
	Node* p = (Node*)malloc(sizeof(Node));
	Node* pt = (Node*)malloc(sizeof(Node));
	p = first;
	//只剩一个结点时跳出循环
	while (p->next != p)
	{
		for (int i = 1; i < m; i++)
		{
			//r存储p的值,以便后续删除出圈结点
			pt = p;
			p = p->next;
		}
		printf("%d出圈\n", p->data);
		pt->next = p->next;
		p = p->next;
	}
	printf("%d出圈\n", p->data);
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/盐析白兔/article/detail/681901
推荐阅读
相关标签
  

闽ICP备14008679号