【数据结构】链表结构实现约瑟夫环

ゝ一世哀愁。 2023-02-17 02:57 57阅读 0赞

### 约瑟夫环问题 ###

*  什么是约瑟夫环
 *  问题来历
 *  问题解决思路
 *  代码

# 什么是约瑟夫环 #

约瑟夫问题（有时也称为约瑟夫斯置换，是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。又称“丢手绢问题”.）

# 问题来历 #

17世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事：15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。

# 问题解决思路 #

创建n个循环链表，使得最后一个链表指向首个链表的头指针。从链首开始，找到报数的人，删除结点，然后指向下一个链表，一直循环，直到链表中只剩一个结点，输出最后的结点。

# 代码 #

#include<iostream.h>  
    #include<stdlib.h>  
     
    //定义单链表存储结构
     typedef struct LNode{
          
        int data;  //数据域
        struct LNode* next;  //指针域
    }LNode,*LinkList;  
    
    void Josephus(int n, int m, int k) {
          //约瑟夫函数
    
        //声明三个指针：链首指针、p和q，初始值设置为空
    	//为什么new 出来的结构体可以赋值给指针？
    	//new运算符会返回一个指向该存储空间的地址
    	LinkList p=NULL,q=NULL,List=NULL;
    	
    	//循环建立约瑟夫环，也即循环建立含有n个结点的单链表，for循环
    	for(int i=1;i<=n;i++){
        
    		p=new LNode;
    		//判断是否分配成功
    		if(p==NULL){
        
    		cout<<"分配空间失败"<<endl;
    		exit(1);
    		}
    		p->data=i;//将数据放入链表的数据域中
    		if(List==NULL) List=p;//如果List中没有东西，那么将List指针指向第一次申请出来的空间的首节点
    		else q->next=p;//如果List中有元素，那么让q和p链起来
    		q=p;
    	}
        //让单链表的最后一个结点的next指针指向单链表的首元结点  
    	p->next=List;
    
        //从链首开始				
    	//从链首查找开始报数位置，循环结束时p指向开始报数位置（p指向第1个报数的人），for循环
    	p=List;
    	for(i=1;i<k;i++){
        
    	p=p->next;//找到开始报数的人
    	
    	}
        
    	//循环报数开始，循环结束条件为当链中只剩一个结点则报数结束，while循环
    		//从第一个报数的结点开始找报到第m个结点，循环结束时p指向第m个结点，q指向第m-1个结点，for循环
    		//从链中删除第m个结点  
    
    	while(p->next !=p){
        //如果p->的指针指向p。那么说明此链中只有一个链表
    		for(i=1;i<m;i++){
        
    		q=p;
    		p=p->next;
    		
    		}
    
    		q->next=p->next;
    		 //输出出局结点的编号  
    		cout<<p->data<<"号出局"<<endl;
    		  //释放被删除结点的空间  
    		delete p;
    		 //p指向新的出发点  
    		p=q->next;
    	
    	
    	}
    	//while循环结束  
    	//输出最后那个结点的编号  
    	cout<<"最后"<<p->data<<"号出局"<<endl;
    
    	delete p; //释放最后结点的空间 
       
    }  
    
    int main()  {
         
        int m,k,n;  
        cout<<"请输入总人数：";  
        cin>>n;  
        cout<<"请输入从第几人报数：";  
        cin>>k;  
        cout<<"请输入报至第几个人出局：";  
        cin>>m;  
        Josephus(n, m, k); 
    	return 0;
    }

![在这里插入图片描述][20200611161537147.png]

[20200611161537147.png]: https://img-blog.csdnimg.cn/20200611161537147.png