数据结构循环链表的应用：约瑟夫环问题

墨蓝 2022-09-19 01:29 162阅读 0赞

#include <stdio.h>
    #include <stdlib.h>
    #include <iostream.h>
    
    #define OK          1
    #define ERROR       0
    #define OVERFLOW    -2
    
    typedef int ElemType;
    
    typedef struct LNode
    {
    	ElemType data;
    	struct LNode *next;
    }LNode, *LinkList;
    
    void Create_LinkList(LinkList &L, int n)
    {
    	int i = 2;
    	LinkList pCur = NULL,pPrev;
    	L = (LinkList)malloc(sizeof(LNode));
    	if (!L)
    	{
    		exit(OVERFLOW);
    	}
    	L->data = 1;
    	L->next = NULL;
    	pPrev = L;
    	while (--n > 0)
    	{
    		pCur = (LinkList)malloc(sizeof(LNode));
    		if (!pCur)
    		{
    			exit(OVERFLOW);
    		}
    		pCur->data = i;
    		pPrev->next = pCur;
    		pPrev = pCur;
    		i++;
    	}
    	pCur->next = L;
    }
    
    void KickFromRing(LinkList &L, int n)
    {
    	LinkList pCur,pPrev;
    	int i = 1;
    	pCur = pPrev = L;
    	while (1)
    	{
    		if (i == n)
    		{
    			printf("%d\n",pCur->data);
    			pPrev->next = pCur->next;
    			free(pCur);
    			pCur = pPrev->next;
    			i = 1;
    		}
    		pPrev = pCur;
    		pCur = pCur->next;
    		if (pCur == pPrev)
    		{
    			printf("%d\n",pCur->data);
    			free(pCur);
    			break;
    		}
    		i++;
    	}
    }
    
    
    
    
    int main()
    {
    	int m,n;
    	scanf("%d%d",&m,&n);
    	LinkList L;
    	Create_LinkList(L,m);
    	KickFromRing(L,n);
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，162人围观）

还没有评论，来说两句吧...

相关阅读

相关循环链表的一个案例-约瑟夫环

/ Josephus.c Created on: 2019年7月25日 Author: Administra

╰+哭是因爲堅強的太久メ/ 2023年10月09日 12:50/ 0 赞/ 25 阅读

相关数据结构约瑟夫环问题，链表环的问题。

一.约瑟夫环问题使用单链表解决约瑟夫环问题，基本思想：设置一个计数器count和工作指针p和q，当计数器累加到m时，删除结点p。为了能够让计数器从1开始计数，将采

﹏ヽ暗。殇╰゛Y/ 2023年10月03日 02:21/ 0 赞/ 19 阅读

相关约瑟夫问题——循环链表

think: 1顺序建立循环链表+循环链表中的符合题意的元素结点的删除 2注意只有一个人玩死亡游戏的情况 [sdut原题链接][sdut] 约瑟夫问题 Time

秒速五厘米/ 2022年09月28日 11:46/ 0 赞/ 192 阅读

相关数据结构循环链表的应用：约瑟夫环问题

include <stdio.h> include <stdlib.h> include <iostream.h> defin

墨蓝/ 2022年09月19日 01:29/ 0 赞/ 163 阅读

相关【数据结构】循环单链表约瑟夫回环问题

include<stdio.h> include<stdlib.h> typedef struct data {

电玩女神/ 2022年08月25日 01:52/ 0 赞/ 184 阅读

相关单循环链表--约瑟夫环

include <stdio.h> include <stdlib.h> //单链表类型定义 typedef struct node

男娘i/ 2022年06月17日 07:23/ 0 赞/ 226 阅读

相关约瑟夫环-(数组、循环链表、数学)

约瑟夫环（[约瑟夫问题][Link 1]）是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他

╰+哭是因爲堅強的太久メ/ 2022年05月08日 05:24/ 0 赞/ 240 阅读

相关循环链表解决约瑟夫环问题

　　约瑟夫环问题可以简单的使用数组的方式实现，但是现在我使用循环链表的方法来实现，因为上午看到一道面试题规定使用循环链表解决约瑟夫环问题。　　什么是约瑟夫环？　　“约瑟

Love The Way You Lie/ 2022年04月10日 08:22/ 0 赞/ 228 阅读

相关【数据结构】单向循环链表应用-约瑟夫环

编号1,2,...n的n个人按顺时针方向围坐在一圈,每人持有一个密码.一开始任选一个正整数作为报数上限值m,从第一个开始按顺时针方向自1开始顺序报数,报到m时停止报数.报m的人

落日映苍穹つ/ 2022年03月07日 05:40/ 0 赞/ 224 阅读

相关 C++数据结构--循环链表的应用--解决约瑟夫问题

解决问题过程图解 ![20130731102002984][] 实现代码： //n个竞争者，每隔m个竞争者就淘汰一个 //返回值为胜

偏执的太偏执、/ 2021年12月01日 15:46/ 0 赞/ 227 阅读