C++循环链表实现约瑟夫问题
约瑟夫问题（有时也称为约瑟夫斯置换，是⼀个出现在和中的问题。在计算机的算法中，类似问题⼜称为约瑟夫环。⼜称“丢⼿绢问题”）
据说著名犹太历史学家 Jophus有过以下的故事：在罗马⼈占领乔塔帕特后，39 个犹太⼈与Jophus及他的朋友躲到⼀个洞中，39个犹太⼈决定宁愿死
也不要被敌⼈抓到，于是决定了⼀个⾃杀⽅式，41个⼈排成⼀个圆圈，由第1个⼈开始报数，每报数到第3⼈该⼈就必须⾃杀，然后再由下⼀个重新报数，直到
所有⼈都⾃杀⾝亡为⽌。然⽽Jophus 和他的朋友并不想遵从。⾸先从⼀个⼈开始，越过k-2个⼈（因为第⼀个⼈已经被越过），并杀掉第k个⼈。接着，再越
过k-1个⼈，并杀掉第k个⼈。这个过程沿着圆圈⼀直进⾏，直到最终只剩下⼀个⼈留下，这个⼈就可以继续活着。问题是，给定了和，⼀开始要站在什么地⽅
才能避免被处决？Jophus要他的朋友先假装遵从，他将朋友与⾃⼰安排在第16个与第31个位置，于是逃过了这场死亡游戏。
男生寸头
我写了⼀个循环链表来实现约瑟夫问题，其实没必要这么复杂，只需要⽤⼀个vector或者是数组即可，以下是我写的代码：
1.循环链表头⽂件：
#ifndef __CircleList_H__
#define __CircleList_H__
#include <iomanip>
#include <iostream>
#include <ctime>
#include <casrt>
using namespace std;
#define LEN 20
#define RANLEN 100
typedef int ElemType;
typedef struct Lnode
{
ElemType data; //值域
Lnode *next; //next指针
}Lnode;
class CircleList
{
private:
Lnode *head;//头指针
Lnode *curr;//当前指针
int count; //循环链表中元素个数
public:
CircleList();//构造函数，只有⼀个头结点
~CircleList(){delete head;}//析构函数
Lnode *CreateCircleList(const int& n,const int& mark);//创建循环链表,n表⽰的是循环链表中的元素个数，mark为1的时候表⽰升序，-1的时候表⽰降序，0的时候表⽰ void TraverCircleList(); //遍历整个循环链表
// void InrtNode(const ElemType& item,int pos); //向循环链表中指定位置插⼊节点
bool IsEmpty(){ return head->next == head; } //判断链表是否为空
// Lnode *Index(int pos); //返回指定位置的Lnode指针
ElemType GetElem(int pos); //返回指定位置的data值
Lnode *Next(); //返回下⼀个节点的指针
Lnode *Ret(int pos); //将curr指针指向指定的位置并返回
ElemType DeleteNext(); //删除curr指针指向的下⼀个节点
Lnode* GetCurrNode(); //返回curr指针
ElemType DeletePosNode(int pos); //删除指定位置的节点
};
#endif
2.循环链表.cpp⽂件
#include "stdafx.h"
#include "CircleList.h"
CircleList::CircleList()
{
head = new Lnode;
head->next = head;
curr = NULL;
count = 0;
}
Lnode *CircleList::CreateCircleList(const int& n,const int& mark)
{
int i,j,min;
ElemType temp;
ElemType a[LEN];
Lnode *tempNode = NULL;
srand((unsigned)time(NULL));//⽤于产⽣随机数的种⼦
count = n;
for(i = 0; i < LEN; i++ )
{
a[i] = rand()%RANLEN; //产⽣100以内的随机数，保存在a数组中，a数组的长度为LEN=20个，也即n不能超过20 cout<<a[i]<<tw(3);
if( i == LEN -1 )
cout<<endl;
}
//选择排序
for( i = 0; i < LEN-1; i++)
{
min = i;
for( j = i+1; j < LEN;j++ )
{
if( a[min] > a[j] )
min = j;
}
if( min != i )
{
temp = a[min];
a[min] = a[i];
a[i] = temp;
}
}
for( i = 0; i < LEN; i++ )
{
cout<<a[i]<<tw(3);
if( i == LEN - 1)
丁当的歌cout<<endl;
}
head->next = curr = tempNode = new Lnode;
switch(mark)
{
ca -1://表⽰降序排列
curr->data = a[0];
curr->next = head;
for(i = 1;i < n; i++ )
{
curr = new Lnode;
curr->data = a[i];
tempNode->next = curr;
tempNode = tempNode->next;
curr->next = head;
}
break;
ca 0://表⽰随机排列
curr->data = rand()%RANLEN;
curr->next = head;
for( i = 1; i < n; ++i )
for( i = 1; i < n; ++i )
{
curr = new Lnode;
curr->data = rand()%RANLEN;
tempNode->next = curr;
tempNode = tempNode->next;
curr->next = head;
}
break;
ca 1://表⽰升序排列
curr->data = a[LEN-1];
curr->next = head;
for( i = 2; i <= n; ++i )
{
curr = new Lnode;
curr->data = a[LEN-i];
tempNode->next = curr;
tempNode = tempNode->next;
curr->next = head;
}
break;
default:cerr<<"mark error!"<<endl;
}
return head;
}
void CircleList::TraverCircleList()
{
Lnode *arch = head;股骨头痛的原因
cout<<"遍历链表结果："<<endl;
while( arch->next != head )
{
arch = arch->next;
cout<<arch->data<<tw(3);
}
}
ElemType CircleList::GetElem(int pos)
{
int i = 0;
Lnode *arch = head;
for( i = 0; i < pos; i++ )
{
arch = arch->next;
}
return arch->data;
发言稿}
ElemType CircleList::DeletePosNode(int pos) {
asrt( pos > 0 );
int i = 0;
ElemType data;
Lnode *arch = head->next;
curr = head;
for( i = 1; i < pos; i++ )
{
curr = curr->next;
arch = arch->next;
}
curr->next = arch->next;
arch->next = NULL;
data = arch->data;
锡纸可以放烤箱吗
delete arch;
count--;
return data;
return data;
}
Lnode *CircleList::Next()
{
if( curr->next == head )
curr = curr->next->next;
el
curr = curr->next;
return curr;
}
Lnode *CircleList::Ret(int pos)数字7
{
int i;
curr = head;
for( i = 0; i < pos; i++ )
{
curr = curr->next;
}
return curr;
}
ElemType CircleList::DeleteNext()
{
ElemType data;
Lnode *arch = NULL;
if( curr->next != head )
{
arch = curr->next;
curr->next = curr->next->next;
data = arch->data;
arch->next = NULL;
delete arch;
}
el
王不留行的功效与作用{
arch = curr->next->next;
curr->next->next = arch->next;
data = arch->data;
arch->next = NULL;
delete arch;
}
return data;
}
Lnode* CircleList::GetCurrNode()
{
return curr;
}
3.约瑟夫函数以及主函数的.cpp⽂件
// CircleListAndJophProblem.cpp : 定义控制台应⽤程序的⼊⼝点。
//
#include "stdafx.h"
#include "CircleList.h"
wifi放大器//约瑟夫问题，n表⽰⼈数，m表⽰数多少个数,x表⽰第⼀次从哪个⼈开始数数
void JophProblem(int n,int m,int x)
{
int i,j;
CircleList cl;
cl.CreateCircleList(n,1);
cout<<"未报数之前⼈的编号顺序："<<endl;
cl.TraverCircleList();
cout<<endl;
cl.Ret(x-1);
for( i = 0; i < n-1; i++ )
{
for( j = 0; j < m-1; j++ )
cl.Next();
cout<<cl.DeleteNext()<<"元素被删除！"<<endl;
}
cout<<"最后剩下的元素为："<<cl.GetCurrNode()->data<<endl;
}
int _tmain(int argc, _TCHAR* argv[])
{
/*
CircleList cl;
cl.CreateCircleList(10,1);
cl.TraverCircleList();
cl.DeletePosNode(2);
cout<<"删除后的链表为："<<endl;
cl.TraverCircleList();
*/
JophProblem(10,3,1);
return 0;
}
如果您那么细⼼的看完代码后，发现有什么问题，希望您能够给我留⾔提出，只有不断发现不⾜，才能⼀直前进
