数据结构-循环单链表之约瑟夫问题

柔情只为你懂 2022-05-25 06:46 128阅读 0赞

约瑟夫问题的由来：

据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。看来功课学得好关键时刻可以救命啊！！！ 哈哈。。。

简单实现了一个单链表以对约瑟夫问题的求解。

/*
    循环链表：循环单链表
    示例：约瑟夫环
    */
    typedef struct LNode {
    	int data;	//数据域
    	LNode *next; //指针域
    }LNode,*LinkList;

/*
    function:初始化约瑟夫环
    */
    LinkList createLinkList(int n) {
    	LNode *L = NULL;
    	LNode *s;
    	LNode *r = NULL;//尾指针
    	if (n < 1) {
    		return NULL;
    	}
    	//注释这行的目的是为了去除头结点，我们的数据节点从第一个开始
        //L = (LinkList)malloc(sizeof(LNode));//头结点
    	//r = L;
    	int j = 1;
    	int x;
    	scanf_s("%d", &x);
    	while (j<=n)
    	{
    		s = (LinkList)malloc(sizeof(LNode));
    		s->data = x;
    		if (L == NULL) {
    			//初始化第一个节点
    			L = r = s;
    		}
    		else
    		{
    			r->next = s;
    			r = s;
    		}
    		if (j == n) {
    			break;
    		}
    		j++;
    		scanf_s("%d", &x);
    	}
    	//指向第一个节点，形成闭环
    	r->next = L;
    	return L;
    }

/*
    function:依次取出满足条件的数据
    */
    void printData() {
    	LNode *p =createLinkList(10);
    	int j = 1;
    	int k = 3;//约瑟夫环约定需要处理的节点标号
    	while (p!=NULL)
    	{	
    		//p = p->next;//获取下一个节点地址
    		if (j == (k -1)) {
    			//达到约瑟夫环的条件需要移除节点的前驱节点
    			LNode *q = p->next;//需要移除的节点
    			p->next = q->next;
    			p = p->next;	//指针向前移动一个节点（从下一个节点开始）
    			printf_s("%d \t", q->data);
    			free(q);
    			j == 1;
    		}
    		else
    		{
    			j++;
    		}
    		p = p->next;//获取下一个节点地址
    	}
    }
    
    void main() {
    	printData();
    }

![70][]

以上为约瑟夫问题循环单链表的基本实现，帮助我们进一步熟悉循环单链表；我们还可以通过更高级的方式实现：递归，好吧，这就留给下次思考和实现了！

[70]: /images/20220525/04846156fb504a46a5cfda42f3845b7f.png