有趣的数据结构算法5——利用循环链表解决Josephus问题

「爱情、让人受尽委屈。」 2021-12-01 12:16 162阅读 0赞

### 有趣的数据结构算法5——利用循环链表解决Josephus问题 ###

*  题目复述
 *  解题思路
 *  实现代码
 *  GITHUB下载连接

本次教程主要讲述如何利用循环链表解决Josephus问题。

# 题目复述 #

据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。  
然而Josephus 和他的朋友并不想遵从，但是大家都要屎啊，朋友心里是这样想的：“你们要死关老子什么事”。  
![在这里插入图片描述][20190723145057699.jpg_pic_center]  
Josephus却是这样想的：  
![在这里插入图片描述][20190723145210330.jpg_pic_center]  
Josephus要如何安排站位才能解救自己和朋友呢？  
题目可以化简成以下模型：41个人排成一圈，按顺时针方向依次编号1，2，3…41。从编号为1的人开始顺时针"1、2、3"报数，报到3的退出。反复循环，圈子里的人将不断减少。最后剩下两个人可以免除退出。

# 解题思路 #

1.  生成长度为41的循环链表，每个节点数据由1标注到41；
2.  p结点指向表头，表头数据为1；
3.  搜索到表头后的第一个节点，此时p指向第二个人。
4.  s = p->Next，此时s指向第三个人。
5.  p->Next = s->Next，free(s)，此时第三个人被踢出链表，同时自刎。
6.  此时p进行两次Next操作，此时p指向第五个人。重复上述操作删除第六个人。
7.  重复上述操作完成筛选。

解题思路的伪代码形式如下：

//生成41位的循环链表，p指向表头
    	while (p->Next != p){
    		p = p->Next;
    		s = p->Next;	//第一轮：此时s指向第三个人；第二轮：此时s指向第六个人；
    		p->Next = s->Next;	
    		free(s);		//第一轮：第三个人自刎；第二轮：第六个人自刎；
    		p = p->Next;	//第一轮：此时p指向第四个人；第二轮：此时s指向第七个人；
    	}

# 实现代码 #

#include <stdio.h>
    #include <stdlib.h>
    
    struct Node{
        
    	int data;
    	struct Node *Next;
    };
    typedef int c;
    typedef struct Node* RoL;
    
    RoL getRol(int n){
        
    	RoL s, p;
    	RoL tail;			//指向尾节点，用于添加元素
    	int i = 1;
    	p = (RoL)malloc(sizeof(struct Node));
    	p->data = i;
    	p->Next = p;
    	tail = p;
    	while (i < n){
        
    		i++;
    		s = (RoL)malloc(sizeof(struct Node));
    		s->data = i;
    		s->Next = tail->Next;
    		tail->Next = s;			//重新指向尾节点
    		tail = s;
    	}
    	return p;					//返回头指针
    }
    
    int main(void){
        
    	RoL s, p;
    	int i = 0;
    	p = getRol(41);	//生成41位的循环链表，p指向表头
    	while (p->Next != p){
        
    		p = p->Next;	//第一轮：此时p指向第二个人；第二轮：此时p指向第五个人；
    		printf("%d->", p->Next->data);
    
    		if (15 == i){
        		//每15轮进行两次换行，结果更清晰。
    			printf("\n\n");
    			i = 0;
    		}
    
    		s = p->Next;	//第一轮：此时s指向第三个人；第二轮：此时s指向第六个人；
    		p->Next = s->Next;	
    		free(s);		//第一轮：第三个人自刎；第二轮：第六个人自刎；
    		p = p->Next;	//第一轮：此时p指向第四个人；第二轮：此时s指向第七个人；
    		i++;
    	}
    	printf("%d", p->data);
    	return 0;
    }
    }

# GITHUB下载连接 #

[https://github.com/bubbliiiing/Data-Structure-and-Algorithm][https_github.com_bubbliiiing_Data-Structure-and-Algorithm]

希望得到朋友们的喜欢。  
有问题的朋友可以提问噢。

[20190723145057699.jpg_pic_center]: /images/20211201/f00a501a84fd4d9eaa185c078ff4b8ad.png
[20190723145210330.jpg_pic_center]: /images/20211201/e80fcf7d58194253976c53a16912a2be.png
[https_github.com_bubbliiiing_Data-Structure-and-Algorithm]: https://github.com/bubbliiiing/Data-Structure-and-Algorithm