joseph_central_issues.txt

数据结构——约瑟夫环问题C++源代码和注释 。

#include<iostream> 
using namespace std; 

//链表结点类number为这个人的编号,key为丫的密码 
struct person 
{ 
unsigned int number; 
unsigned int key; 
person *next; 
}; 

//约瑟夫环类,此类包含多个person类,并控制输入输出. 
class joseph_ring 
{ 
private: 
unsigned int n;//用于存放人数 
unsigned int m;//用于存放初始密码 
person *head;//链表的头结点 
public: 
joseph_ring(){m=0;n=0;head=NULL;}//构造函数,把成员变量赋初值 
void create();//建立环的成员函数 
void show();//运算并输出的成员函数 
}; 

void joseph_ring::create() 

{ 
//这四行应该不用解释了吧 
cout<<"请输入人数:"; 
cin>>n; 
cout<<"请输入m的初值:"; 
cin>>m; 
//定义2个临时指针 
person *p1,*p2; 
//for循环中用于初始化环 
for(int i=1;i<=n;i++) 
{ 
p1=new person;//新实例化一个"人"的对象 
p1->number=i;//给这个"人"编个号 
cout<<"请输入第 "<<i<<"个人对应密码:"; 
cin>>p1->key;//给这个"人"一密码 
//如果当前链表为空,头结点指向第一个"人" 
if(i==1) 
{ 
head=p1; 
p2=p1; 
} 
//否则,p2永远指向尾结点,新建的结点都接到p2之后 
else 
{ 
p2->next=p1; 
p2=p1; 
} 
} 
p2->next=head;//把链表连成一个循环链表(就是一个环) 
} 

void joseph_ring::show() 
{ 
person *p1,*p2,*p; 
p1=head; 

//有n个人,所以执行n次循环 
for(int i=1;i<=n;i++) 
{ 

int count=1; 
//用count定位到第m个衰人,循环后,p1指向这个衰人,p2指向这个衰人的上一个人 
while(count++<m) 
{ 
p2=p1; 
p1=p1->next; 
} 

cout<<p1->number<<"\t";//输入当前衰人的编号 
m=p1->key;//把当前衰人的密码作为指向下一个衰人所要经过的人数 
p=p1;//p指向当前这个衰人 
p2->next=p1->next;//把衰人前的人和衰人后的人连上. 
p1=p1->next;//下次从当前衰人的下一个人开始数 
delete p;//把衰人毙掉(就是释放这块内存) 
} 
cout<<endl; 
cin>>m;//这行应该是为了避免程序不出结果而写了,没什么逻辑意义. 
} 

int main() 
{ 
joseph_ring j; 
j.create(); 
j.show(); 
return 0; 
}