求助,顺序表实现约瑟夫问题
哪位高手有C++ 版的顺序表实现约瑟夫问题解法啊,
我是菜鸟,编了好久没编出,就要交了,特在此求救,希望高手赐教
谢谢了
以前用链表写的，凑或先用。。。。。。。。。。
//----------------------------------------------------------------------
//约瑟夫环问题：编号为1、2、3、……、n的n个人按顺时针方向围坐一圈，
//每个人手持一个密码（正整数）。一开始任选一个整数作为报数上限值，
//从第一个开始顺时针自1开始顺序报数，报到m时停止报数。报m的人出列，
//将他的密码作为新的m值，从它在顺时针方向上的下一个人开始重新从1报数，
//如此下去直到所有人全部出列为止。
//----------------------------------------------------------------------
#include<iostream>
#include<string>
using namespace std;
template <class T>
struct Node
{
T data;
Node<T> *next;
};
template <class T>
class LinkList
{
public:
LinkList(T a[], int n); //建立有n个元素的循环链表
~LinkList();
T Delete(int i); //在循环链表中删除第i个结点
void PrintList(); //按序号依次输出各元素
private:
Node<T> *First,*Temp; //循环链表的头指针和起点指针
};
template <class T>
LinkList<T>:: LinkList(T a[], int n)
{
First=new Node<T>; //生成头结点
Node<T> *r,*s;
r=First; //尾指针初始化
for (int i=0; i<n; i++)
{
s=new Node<T>; //为每个数组元素建立一个结点
s->data=a[i];
r->next=s; //插入到终端结点之后
r=s;
}
r->next=First; //将终端结点的指针指向头结点
Temp=First; //初始化起点指针
}
template <class T>
LinkList<T>:: ~LinkList()
{
Node<T> *p,*q;
p=First; //初始化p
while(p->next!=First) //释放每个节点
{
q=p; //暂存被释放节点
p=p->next;
delete q;
}
}
template <class T>
void LinkList<T>::PrintList()
{
Node<T> *p;
p=First->next;
while (p!=First) //循环列表结束标志
{
cout<<p->data<<'\t';
p=p->next;
}
cout<<endl;
}
template <class T>
T LinkList<T>::Delete(int i)
{
int j(1);
Node<T> *p,*q;
T temp; //暂存删掉的数据
p=Temp;
while (j<i)
{
if(p->next->next!=First) //循环到头结点时的情况
p=p->next;
else
p=First;
j++;
}
if(First!=p) //删除第一个节点的情况
{
q=p->next;
temp=q->data;
p->next=q->next;
}
else
{
q=First->next;
temp=q->data;
First->next=q->next;
}
delete q;
if(p->next!=First) //删除最后一个节点后的情况
Temp=p;
else
Temp=First;
return temp; //返回删除的数据
}
void main()
{
int iOrder[100]; //顺序
int iPsw[100]; //密码列表
cout<<"输入初始密码作为上限:\t";
int iMax,iWord,j(0);
cin>>iMax;
iMax=(iMax<=30)?iMax:30; //上限要小于30
cout<<"依次输入每个人的密码，空格间隔，输入\"99\"结束\n";
cin>>iWord;
while(iWord!=99&&j<100) //依次输入密码
{
iPsw[j]=(iWord<iMax)?iWord:iMax; //上限要小于初始密码
iOrder[j]=j+1;
j++;
cin>>iWord;
}
int psw(iMax); //初始密码
int x;
LinkList<int> a(iOrder,j); //建立循环列表对象并初始化
cout<<"原始顺序:\n";
a.PrintList();
cout<<"出列的顺序:\n";
for(int i=0;i<j;i++) //约瑟夫环
{
x=a.Delete(psw);
cout<<x<<'\t';
psw=iPsw[x-1]; //设置新密码
}
cout<<endl;
}
