利用顺序表实现约瑟夫问题

/* 语言:C++ */
cpp源文件:
--------------
#include "SeqList.h" //顺序表类
void display(int n,int s,int d)
{
SeqList ring1(n); //声明并初始化顺序表ring1
ring1.create(n); //顺序表ring1中添加n个自然数
cout<<"ring:\t";
ring1.output();
int i,j,k;
i=s-1; //从第s个开始计数
k=n;
while(k>1) //n-1个人依次出环
{
j=0;
while(j {
i=i%n+1; //将顺序表看成环形
if(ring1.get(i)!=0) //不能以ring1.table[i]形式访问SeqList类中的private变量table
j++; //计数
}
cout<<"out : "< ring1.set(i,0); //第i个人出环,设置第i个位置为空
k--;
cout<<"ring:\t";
ring1.output();
}
i=1;
while(i<=n && ring1.get(i)==0) //寻找最后一个人
i++;
cout<<"The final person is "<}

void main(void)
{
display(5,1,2);
}
/*
程序运行结果：
ring: 1 2 3 4 5
out : 2 ring: 1 0 3 4 5
out : 4 ring: 1 0 3 0 5
out : 1 ring: 0 0 3 0 5
out : 5 ring: 0 0 3 0 0
The final person is 3
*/
/* seqlist.h 头文件*/
#include
class SeqList //顺序表类
{
private:
int *table; //指向数组的指针
int size; //顺序表的数组容量
int len; //顺序表的实际长度
public:
SeqList(int n=0); //构造函数
~SeqList(void); //析构函数
bool isEmpty()const; //判断顺序表是否为空
bool isFull()const; //判断顺序表是否已满
int length()const; //返回顺序表的实际长度
int get(int i)const; //返回第i个数据元素值
bool set(int i,int k); //设置第i个数据元素值为k
bool insert(int i,int k); //插入k值作为第i个数据元素
bool insert(int k); //将k值添加到顺序表最后,函数重载
int search(int k); //返回k值首次出现的位置
bool remove(int k); //删除k值首次出现的数据元素
void output(); //按实际长度输出顺序表的数据元素
bool create(int n); //顺序表中添加n个自然数
};

SeqList::SeqList(int n) //构造函数,初始化顺序表
{
table=new int[n]; //为顺序表分配n个存储单元
size=n;
len=0; //此时顺序表实际长度为0
}
SeqList::~SeqList(void) //析构函数，撤销顺序表对象
{
delete []table;
}
bool SeqList::isEmpty()const //判断顺序表是否为空
{
return len==0;
}
bool SeqList::isFull()const //判断顺序表是否已满
{
return len>=size;
}
int SeqList::length()const //返回顺序表的实际长度
{
return len;
}
int SeqList::get(int i)const //返回第i个数据元素值
{
if(i>0 && i<=len)
return table[i-1];
else
return -1;
}
bool SeqList::set(int i,int k) //设置第i个数据元素值为k
{
if(i>0 && i<=len+1)
{
table[i-1]=k;
return true;
}
else
return false;
}

bool SeqList::insert(int i,int k) //插入k值作为第i个数据元素
{
if(!isFull())
{
if(i<=0) i=1;
if(i>len) i=len+1;
for(int j=len-1;j>=i-1;j--) //向后移动元素
table[j+1]=table[j];
table[i-1]=k; //插入元素
len++; //长度加1
return true; //插入成功
}
else
{
cerr<<"顺序表已满，无法插入"< return false; //插入失败
}
}

bool SeqList::insert(int k) //将k值添加到顺序表最后,函数重载
{
return insert(length()+1,k);
}

int SeqList::search(int k) //查找，返回k值首次出现的位置
{ //未找到时，返回0
int i=1;
while(i<=length() && get(i)!=k)
i++;
if(i<=length())
return i;
else
return 0;
}
bool SeqList::remove(int k) //删除k值首次出现的数据元素
{
if (!isEmpty())
{
int i=search(k); //第i个结点
for(int j=i;j set(j,get(j+1)); //即table[j]=table[j+1];
len--; //长度减1
return true;
}
else
{
cout<<"顺序表为空，无法删除值！\n";
return false;
}
}

void SeqList::output() //按实际长度输出顺序表的数据元素
{
for(int i=1;i<=length();i++)
cout< cout<<"\n";
}

bool SeqList::create(int n) //顺序表中添加n个自然数
{
if(n<=size)
{
int i=0;
while(i i++;
return true;
}
else
return false;
}