C/C++经典约瑟夫环问题——带头结点的单向循环链表

本程序是采用带头结点的单向循环链表写成的，当指针指到要出列的结点时，先输出结点的序列号，再删除之，直到所有结点都出列完

#include
using namespace std;
int total_num ;
int t=1;

typedef struct Node
{
	int num;                    //序列号
	int key;                    //密码
    Node   * next;              //指针域 
}Node*link;

typedef struct
{
	link Head;                  
	int length;                 //未出列的人数
}josephu;


void creat（josephu &L）
{
	L.Head=new Node;
	L.Head->next=L.Head;
	link p;
	L.Head->num=0;              //头结点定义为第0个人，表示不存在
	L.length=total_num;         //表示当前总人数
	for（int i=total_num;i>0;i--）
	{
		p=new Node;
		p->num=i;               //表示它是第i个人
		p->next=L.Head->next;
		L.Head->next=p;
	}
}


void get_key（josephu &L）      
{   link p;
	p=L.Head->next;
	char choice;  cout<<“每次是否使用同一密码，是就输入y！“<	cin>>choice;
	if（choice==‘y‘）
	{
		int key;  cout<<“请输入密码:“<		cin>>key;
		for（int i=0;i		{
			p->key=key;
			p=p->next;
		}
	}
	else
	for（int i=0;i	{  
		cout<<“请输入第“<num<<“的密码:“<		cout<<“                   “;
		cin>>p->key;               
		p=p->next;
	}
}
	
void deal_josephu（josephu L）
{
	link pq;
	q=L.Head;
	p=L.Head->next;
	while（L.length>0）
	{
		int k=p->key;
		for（int i=2;i<=k;）
		{
			p=p->next;
			if（p!=L.Head）
			{++i;}
			q=q->next;
		}


		if（p!=L.Head）
		{   
			cout<<“第“<num<			q->next=p->next;
			p=p->next;
			t++;
			L.length--;
		}
		if（p==L.Head）
		{
			p=p->next;
			q=q->next;
		}
	}
}

int main（）
{   
	cout<<“请输入环的总人数:“<	cin>>total_num;
	josephu L;
    creat（L）;		
    get_key（L）;
	deal_josephu（L）;
	return 0;
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       1713  2009-03-20 13:42  Josephu‘s link.cpp

----------- ---------  ---------- -----  ----

                 1713                    1