课程设计---约瑟夫环

题目：约瑟夫环

【问题描述】
约瑟夫（Joseph）问题的一种描述是：编号为1，2，.....，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始顺时针方向自1开始报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有的人都出列为止。试设计一个程序求出列顺序。

【其本要求】
利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。

【测试数据】
M的初值为20；n=7，7个人密码依次为：3，1，7，2，4，8，4，首先m的值为6（正确的出列顺序应为6，1，4，7，2，3，5）。

#include "iostream"
using namespace std;

typedef struct LNode
{
	int num;   //表示该元素的编号
	int password;   //表示该元素的密码
	struct LNode *next;

}LNode,*LinkList;   // 结点类型，指针类型

int Insert(LinkList &L,int password, int num)  //引用类型的参数
{
	LinkList p;
	if(L==NULL)   //第一个结点
	{
		p=(LinkList)malloc(sizeof(LNode));
		if(!p)
		{
			cout<<"分配空间失败！"<<endl;
			return -1;
		}
		p->num=num;
		p->password=password;
		L=p;
	}
	else
	{
		p=(LinkList)malloc(sizeof(LNode));
		if(!p)
		{
			cout<<"分配空间失败！"<<endl;
			return -1;
		}
		p->num=num;
		p->password=password;
		L->next=p;
		p->next=NULL;
		L=p;
	}
	return 0;
}
void Joseph(LinkList &L,int k,int m)  //引用类型的参数
{
	int i;
	LinkList p,q;
	p=q=L;
	while(q->next!=L)
		q=q->next;
	while(k>0)
	{
		for(i=1;i<m;i++)
		{
			q=q->next;
			p=p->next;
		}
		q->next=p->next;
		cout<<p->num<<"  ";
		m=p->password;  //更新m的值
		free(p);
		k--;    //人数减1
		p=q->next;
	}
	cout<<endl;
}
int main(void)
{
	int m,n,i,t;
	LinkList head,p=NULL;
	cout<<"请输入人数：";         //输入人数n
	cin>>n;
	cout<<"请输入初始密码：";     //输入初始密码m
	cin>>m;
	cout<<"请输入大家手中的密码："<<endl;
	for(i=1;i<=n;i++)
	{
		cin>>t;
		if(Insert(p,t,i)==-1)
			return 0;
		if(i==1)
			head=p;
	}
	p->next=head;  //构成约瑟夫环
	cout<<"出列的顺序如下："<<endl;
	Joseph(head,n,m);
	system("pause");
	return 0;
}

运行结果如下图：

结构体定义中

typedef struct LNode
{
	int num;   
	int password;  
	struct LNode *next;
}LNode,*LinkList;   // 结点类型，指针类型

typedef 声明，简称 typedef，为现有类型创建一个新的名字。
typedef struct Node
{
int data;
struct Node* next;
}LNode, *LinkList;
LNode就相当于struct Node ，起了一个别名。
*LinkList也相当于struct Node

也就是：

LNode 等价 struct Node
LinkList 等价 LNode* 等价 struct Node*

LNode a;等价 struct Node a;
LinkList p;等价 LNode* p;等价 struct Node* p;