【問題描述】
約瑟夫（Joseph）問題的一種描述是：編號為1，2，.....，n的n個人按順時針方向圍坐一圈，每人持有一個密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)上限值m，從第一個人開始順時針方向自1開始報數(shù)，報到m時停止報數(shù)。報m的人出列，將他的密碼作為新的m值，從他的順時針方向上的下一個人開始重新從1報數(shù)，如此下去，直至所有的人都出列為止。試設(shè)計一個程序求出列順序。

【其本要求】
利用單向循環(huán)鏈表存儲結(jié)構(gòu)模擬此過程，按照出列的順序印出各人的編號。

【測試數(shù)據(jù)】
M的初值為20；n=7，7個人密碼依次為：3，1，7，2，4，8，4，首先m的值為6（正確的出列順序應(yīng)為6，1，4，7，2，3，5）。

    #include "iostream"
using namespace std;

typedef struct LNode
{
	int num;   //表示該元素的編號
	int password;   //表示該元素的密碼
	struct LNode *next;

}LNode,*LinkList;   // 結(jié)點(diǎn)類型，指針類型

int Insert(LinkList &L,int password, int num)  //引用類型的參數(shù)
{
	LinkList p;
	if(L==NULL)   //第一個結(jié)點(diǎn)
	{
		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)  //引用類型的參數(shù)
{
	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--;    //人數(shù)減1
		p=q->next;
	}
	cout<<endl;
}
int main(void)
{
	int m,n,i,t;
	LinkList head,p=NULL;
	cout<<"請輸入人數(shù)：";         //輸入人數(shù)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;  //構(gòu)成約瑟夫環(huán)
	cout<<"出列的順序如下："<<endl;
	Joseph(head,n,m);
	system("pause");
	return 0;
}
  

運(yùn)行結(jié)果如下圖：

結(jié)構(gòu)體定義中

    typedef struct LNode
{
	int num;   
	int password;  
	struct LNode *next;
}LNode,*LinkList;   // 結(jié)點(diǎn)類型，指針類型
  

typedef 聲明，簡稱 typedef，為現(xiàn)有類型創(chuàng)建一個新的名字。
typedef struct Node
{
int data;
struct Node* next;
}LNode, *LinkList;
LNode就相當(dāng)于struct Node ，起了一個別名。
*LinkList也相當(dāng)于struct Node

也就是：

LNode 等價 struct Node
LinkList 等價 LNode* 等價 struct Node*

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

課程設(shè)計---約瑟夫環(huán)