johnseph.cpp

约瑟夫环程序

#include<stdlib.h>
#include<iostream.h>

//构件链表数据结构
typedef struct Node
{
	int Num;											//约瑟夫环成员所在的位置
	int Pwd;											//约瑟夫环成员的密码
	struct Node *Next;									//链表的下一成员的指针
}ListNode;
typedef ListNode *LinkList;

//建立约瑟夫环成员的循环链表
LinkList BuildYSFCircle(int _Member)
{
	LinkList Head;										//Head为头节点的指针
	LinkList Prev;										//Prev为当前指针的前一指针
	LinkList Now;										//Now为当前指针
	Head = (LinkList)malloc(sizeof(ListNode));			//分配Head内存空间
    Prev = Head;
    for(int i = 1;i < _Member;i++)
	{
		Now = (LinkList)malloc(sizeof(ListNode));
		Prev -> Next= Now;
		Prev = Now;
	}
	Now -> Next = Head;									//头指针与尾指针相连建立循环链表
	Now = Head;
	Prev = Head;
	return (Head);										//返回链表斗指针
}

//输出各人的编号
void PrintYSFCircle(int _Member,LinkList _Head,int _Count)
{
	LinkList Prev;										//Prev为当前指针的前一指针
	LinkList Now;										//Now为当前指针
	Prev = _Head;
	for(int i = 1;i <= _Member;i++)
	{
		for(int a = 1;a < _Count;a++)					//按密码获取当前节点
		{
			 Prev = Prev -> Next;
		}
		Now = Prev -> Next;								
		_Count = Now -> Pwd;							//获取访问的当前节点的密码
		cout<<Now -> Num;								//打印访问的当前节点
		Prev -> Next = Now -> Next;						//删除访问的当前节点
		free(Now);										//释放访问的当前节点空间
		Now = Prev; 
	}
}

//输入个人的密码
void InputYSFCirclePwd(int _Member,LinkList _Head)
{
	int Pwd;											//约瑟夫环成员的密码
	LinkList Next;										//定义约瑟夫环头当前下一指针
	Next = _Head;										//初始化约瑟夫环头当前下一指针
    cout<<"请输入约瑟夫环成员的密码:"<<endl;			//输出控制台信息
    for(int i = 1;i <= _Member;i++)						//输入约瑟夫环成员的密码
	{
		cin>>Pwd;
		Next ->Num = i;
		Next -> Pwd = Pwd;
		Next = Next -> Next;
	}
	Next = _Head;
}

void main()
{
	int Count;											//第一次报数的间隔
	int Member;											//约瑟夫环成员的个数
	LinkList YSFhead;									//定义约瑟夫环头指针
	YSFhead = (LinkList)malloc(sizeof(ListNode));		//分配指针内存空间
	cout<<"请输入约瑟夫环成员的个数:"<<endl;			//输出控制台信息
	cin>>Member;										//从控制台获得约瑟夫环成员的个数
	cout<<"请输入约瑟夫环第一次报数的间隔:"<<endl;		//输出控制台信息
    cin>>Count;											//从控制台获得约瑟夫环第一次报数的间隔
	YSFhead = BuildYSFCircle(Member);					//建立约瑟夫环成员的循环链表
	InputYSFCirclePwd(Member,YSFhead);					////从控制台获得约瑟夫环成员的密码
	cout<<"输出的位置排列为："<<endl;					//输出控制台信息
	PrintYSFCircle(Member,YSFhead,Count);				//打印约瑟夫环成员排列的位置
	cout<<endl;
}