约瑟夫问题，就是指n个人围成一圈，每个人都有一个1~n内唯一的编号。根据游戏规则，从第s号的人开始数1,2,3..，数到第m号的那个人将被淘汰出局，然后又从第m+1个人开始数1,2,3...,如此反复，直到最后只剩下一个人的时候游戏才结束。现在根据游戏人数n,号码间隔m和起始号码s，求游戏结束时那个人的号码。
这个问题是数据结构中非常基础，也是很简单的一个问题：用一个不带附加头结点的循环链表即可实现。但是在用c++描述代码的过程中，虽然最后实现了问题的求解，但程序结束的时候却出现了内存不能read的现象，检查了一阵，仍不知道是什么原因，特将代码和结果图附上，希望能有同学加以指点。代码如下：
//CircLinkList.h
#ifndef CIRCLINKLIST_H
#define CIRCLINKLIST_H
#include<cstdlib>
//单向无附加头结点的循环链表类定义
template<class T>
struct CircLinkNode
{
T data;
CircLinkNode<T>* link;
CircLinkNode(CircLinkNode<T>* ptr=NULL):link(ptr){}
CircLinkNode(T item,CircLinkNode<T>* ptr=NULL):data(item),link(ptr){}
};
template<class T>
class CircLinkList
{
CircLinkNode<T>* first;
public:
CircLinkList(){first=new CircLinkNode<T>;first->link=first;}//默认构造函数
CircLinkList(T value){first=new CircLinkNode<T>(value);first->link=first;}//构造函数
CircLinkList(CircLinkList<T>& L);//拷贝构造函数
~CircLinkList(){makeEmpty();delete first;}
CircLinkNode<T>* getHead(){return first;}//获取头结点
int Length();//求循环链表长度
void makeEmpty();
void input(T& endTag);//创建链表
void output();//显示链表
CircLinkNode<T>* Locate(int i);//定位第i个元素
bool Insert(int i,T& x);//第i个元素后插入元素
bool Remove(int i,T& x);//删除第i个元素
bool Reverse();//逆转链表
void Creat(int n);//创建1:n的有序链表
};
#endif
/*****************************************************************/
//CircLinkList.cpp
#include"CircLinkList.h"
/*****************************************************/
//拷贝构造函数,拷贝函数有点点问题，触发了assert机制，不知为何?
template<class T>
CircLinkList<T>::CircLinkList(CircLinkList<T>& L)
{
CircLinkNode<T>* srcptr=L.getHead(),
*destptr=first;
int len=L.Length();
T value;
value=srcptr->data;
destptr->data=/*new CircLinkNode<T>*/value;//赋值第一个节点
for(int i=1;i<len;i++)
{
value=srcptr->data;
destptr=new CircLinkNode<T>(value);
if(destptr==NULL)
{
cerr<<"内存分配失败!"<<endl;
exit(1);
}
destptr=destptr->link;
srcptr=srcptr->link;
}
destptr->link=first;
}
/*****************************************************/
//求循环链表长度
template<class T>
int CircLinkList<T>::Length()
{
CircLinkNode<T>* current=first;
int count=1;
while(current->link!=first)
{
current=current->link;
count++;
}
return count;
}
/*****************************************************/
//清空结点，仅剩下头结点
template<class T>
void CircLinkList<T>::makeEmpty()
{
CircLinkNode<T>* current;
while(first->link!=first)
{
current=first->link;
first->link=current->link;
delete current;
}
}
/*****************************************************/
//创建链表
template<class T>
void CircLinkList<T>::input(T& endTag)
{
CircLinkNode<T>* newNode,*current;
makeEmpty();
current=first;
T value;
cin>>value;
if(value!=endTag)
{
//newNode=new CircLinkNode<T>(value);//此处不应该新开辟空间
first/*newNode*/->data=value;
current=/*newNode*/first;
}
cin>>value;
while(value!=endTag)
{
newNode=new CircLinkNode<T>(value);
if(newNode==NULL)
{
cerr<<"内存分配失败!"<<endl;
exit(1);
}
current->link=newNode;
current=current->link;
cin>>value;
}
current->link=first;
}
/*****************************************************/
//创建1:n的有序链表
template<class T>
void CircLinkList<T>::Creat(int n)
{
CircLinkNode<T>* newNode,*current;
makeEmpty();
current=first;
first->data=1;
current=first;
int x=2;
while(x<=n)
{
newNode=new CircLinkNode<T>(x);
if(newNode==NULL)
{
cerr<<"内存分配失败!"<<endl;
exit(1);
}
current->link=newNode;
current=current->link;
x++;
}
current->link=first;
}
/*****************************************************/
//显示链表
template<class T>
void CircLinkList<T>::output()
{
CircLinkNode<T>* current=first;
int len=Length();
for(int i=0;i<len;i++)
{
cout<<current->data<<" ";
current=current->link;
}
cout<<endl;
}
/*****************************************************/
//定位第i个元素
template<class T>
CircLinkNode<T>* CircLinkList<T>::Locate(int i)
{
int len=Length();
if(i<1 || i>len)
return NULL;
CircLinkNode<T>* current=first;
int k=1;
while(k<i)
{
current=current->link;
k++;
}
return current;
}
/*****************************************************/
//第i个元素后插入元素
template<class T>
bool CircLinkList<T>::Insert(int i,T& x)
{
CircLinkNode<T>* current=Locate(i),*newNode;
newNode=new CircLinkNode<T>(x);
if(newNode==NULL)
{
cerr<<"内存分配失败!"<<endl;
exit(1);
}
newNode->link=current->link;
current->link=newNode;
return true;
}
/*****************************************************/
//删除第i个元素
template<class T>
bool CircLinkList<T>::Remove(int i,T& x)
{
CircLinkNode<T>* current=Locate(i-1),*del;
del=current->link;
current->link=del->link;
x=del->data;
delete del;
return true;
}
/*****************************************************/
//逆转链表
template<class T>
bool CircLinkList<T>::Reverse()
{
int len=Length();
CircLinkNode<T>* rear=Locate(len);
CircLinkNode<T>* p=first,*q,*r;
q=p->link;
if(q==p)
return false;
else
{
p->link=rear;
while(q!=/*p*/first)
{
r=q->link;
q->link=p;
p=q;
q=r;
}
first/*->link*/=p;//最后一个节点就是头结点
return true;
}
}
/***************************************************************/
//Josephus.h
#ifndef JOSEPHUS_H
#define JOSEPHUS_H
#include"CircLinkList.h"
template<class T>
void Josephus(CircLinkList<T>& js,int n,int m,int s)
{
CircLinkNode<T>* current=js.Locate(s),*pre;
for(int i=0;i<n-1;i++)
{
for(int j=s;j<s+m-1;j++)
{
pre=current;
current=current->link;
}
cout<<"出列的人是: "<<current->data<<endl;
pre->link=current->link;
delete current;
current=pre->link;
}
cout<<"最后剩下: "<<current->data<<endl;
}
#endif
/***************************************************************/
//JosephusTest.h
#ifndef JOSEPHUSTEST_H
#define JOSEPHUSTEST_H
#include"CircLinkList.h"
#include"Josephus.h"
#include<iostream>
using namespace std;
void JosephusTest()
{
CircLinkList<int>js;
/********************************************
约瑟夫问题求解
*********************************************/
cout<<"输入参与游戏的总人数:"<<endl;
int n;
cin>>n;
cout<<"输入报数的间隔:"<<endl;
int m;
cin>>m;
cout<<"输入报数的起始号码:"<<endl;
int s;
cin>>s;
js.Creat(n);
cout<<"有序链表元素为: "<<endl;
js.output();
Josephus(js,n,m,s);
}
#endif
/***************************************************************/
//cllTest.h
#ifndef CLLTEST_H
#define CLLTEST_H
void cllTest()
{
CircLinkList<int>cll;
/********************************************/
int endTag=-1;
cout<<"创建单向循环链表，输入元素(-1结束)"<<endl;
cll.input(endTag);
cout<<"链表长度是: "<<cll.Length()<<endl;
cout<<"显示链表元素: "<<endl;
cll.output();
//定位元素
cout<<"输入需要定位的元素序号: "<<endl;
int index;
cin>>index;
CircLinkNode<int>* loc=cll.Locate(index);
cout<<"第"<<index<<"元素是: "<<loc->data<<endl;
//插入元素
cout<<"输入需要插入的元素: "<<endl;
int inx;
cin>>inx;
cout<<"输入需要插入的位置: "<<endl;
int ini;
cin>>ini;
cll.Insert(ini,inx);
cout<<"插入元素后的链表是: "<<endl;
cll.output();
//删除元素
cout<<"输入需要删除元素的序号: "<<endl;
int oi;
cin>>oi;
int ox;
cll.Remove(oi,ox);
cout<<"删除的元素是: "<<ox<<endl;
cout<<"删除元素后的链表是:"<<endl;
cll.output();
//逆转链表
bool reyn=cll.Reverse();
if(reyn)
cout<<"逆转成功!"<<endl;
else
cout<<"逆转失败!"<<endl;
cout<<"逆转链表后为:"<<endl;
cll.output();
}
#endif
/***************************************************************/
//main.cpp
#include"CircLinkList.h"
#include"CircLinkList.cpp"
#include"Josephus.h"
#include"JosephusTest.h"
#include"cllTest.h"
int main()
{
cout<<"***********************************************/n"
<<"************基本功能的测试*********************"<<endl;
cllTest();//基本测试
cout<<"***********************************************/n"
<<"************约瑟夫问题的测试********************"<<endl;
JosephusTest();//约瑟夫问题测试
return 0;
}
结果图如下: