链表经典问题——猴子选大王

本文主要是介绍链表经典问题——猴子选大王，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

n只猴子要选大王，选举方法如下：所有猴子按 1，2 ……… n 编号并按照顺序围成一圈，从第 1个猴子起，由1开始报数，报到m时，该猴子就跳出圈外，下一只猴子再次由1开始报数，如此循环，直到圈内剩下一只猴子时，这只猴子就是大王。

#include<malloc.h>
#include<iostream>
using namespace std;
typedef struct snode
{int data;struct snode *next;
}lnode;
void houzi(int n,int k)
{lnode *p,*lq,*head,*s,*pre;		//p：当前结点。 head ：头结点 。pre：当前结点前一个结点。head=(lnode *)malloc(sizeof(lnode));head->next=head;head->data=0;p=head;p->data=1;p->next=p;for(int i=2;i<=n;i++){lq=(lnode *)malloc(sizeof(lnode));lq->data=i;lq->next=p->next;p->next=lq;p=p->next;}p=head;pre=head;while(n!=1){for(int i=1;i<k;i++){p=p->next;cout<<p->data<<" ";}cout<<endl<<p->data<<"出局"<<endl;while(pre->next!=p)				//确定删除结点的前一个节点，以便删除。pre=pre->next;pre->next=p->next;s=p;p=p->next;free(s);n--;}cout<<"最后的结点为："<<p->data<<endl;
}
int main()
{houzi(8,3);
}








约瑟夫问题。

解决方法：建立一个有n个节点，没有头结点的循环链表，确定第一个报数人的位置。不断从链表中删除节点，直到链表为空。
还需要搞定的：单链表反转，对单链表遍历一次求中间值。先记下。

这篇关于链表经典问题——猴子选大王的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---