文档库

最新最全的文档下载
当前位置:文档库 > 约瑟夫环实现

约瑟夫环实现

#include
#include

using namespace std;

//struct LinkNode
struct LinkNode
{
int Student_ID;
int Student_Code;
LinkNode *next;
};

//class Josphus
class Josphus
{
public:
Josphus();
~Josphus();
void Clear();
bool IsEmpty(){return len<=0;}
bool Append(const int);
bool Delete(int&,int&,int);
void Play();
void Traverse(void(*visit)(const int,const int));
int Length()const {return len;}
void Create();

private:
int len;
LinkNode *p_head;
};

//Josphus();
Josphus::Josphus()
{
len = 0;
p_head = new LinkNode;
p_head->next = NULL;
}

//~Josphus();
Josphus::~Josphus()
{
Clear();
delete p_head;
cout<<"Cleared!"<}

//Clear();
void Josphus::Clear()
{
if(IsEmpty())
return ;
LinkNode *p = p_head->next;
LinkNode *q;
while(len)
{
q = p->next;
delete p;
p = q;
len--;
}
p_head->next = NULL;
return ;
}

//Delete(int&,int&,int);
bool Josphus::Delete(int &s_id,int &s_code,int i)
{
if(IsEmpty())
return false;
int n;
LinkNode *p = p_head->next;
LinkNode *q = p->next;
if(len == 1)
{
s_id = p->Student_ID;
s_code = p->Student_Code;
delete p;
p_head->next = NULL;
len = 0;
return true;
}
if(i % len == 1)
{
LinkNode *r = p_head->next;
for(int j = 1; j < len;j++)
r = r->next;
r->next = q;
s_id = p->Student_ID;
s_code = p->Student_Code;
delete p;
p_head->next = q;
}
else
{
n = (i-1) % len;
for(int j = 1 ; j < n ; j++ )
{
p = p->next;
q = q->next;
}
p->next = q->next;
s_id = q->Student_ID;
s_code = q->Student_Code;
delete q;
p_head->next = p->next;
}
--len;
return true;
}

//Append()
bool Josphus::Append(const int s_code)
{
LinkNode *p = p_head->next;
LinkNode *q = new LinkNode;
q->Student_ID = Length()+1;
q->Student_Code = s_code;
if(IsEmpty())
{
p_head->next = q;
q->next = q;
++len;
return true;
}
for(int i = 1;ip = p->next;
p->next = q;
q->next = p_head->next;
++len;
return true;
}

//Print();
void Print(const int s_id,const int s_code)
{
cout<<"Student's ID = "<int n;
cin>>n;
int s_id;
int s_code;
while(!IsEmpty())
{
Delete(s_id,s_code,n);
cout<<"Student's ID id:"<n = s_code;
}
}

//Create()
void Josphus::Create()
{
int n;
int max;
cout<<"Please input the max number to limit:"<cin>>max;
cout<<"Please input the number of students you want:"<cin>>n;
while(n>max)
{
cout

约瑟夫环实现

(共2页)