joseph_linklist.cpp

约瑟夫环的c++程序实现

/*
一、需求分析
1、	本程序利用单向循环链表模拟了约瑟夫（Joseph）问题；
2、	本程序采用人机对话方式完成整个问题，按照提示输入参加的人数（n），每个人的密码（steps），
	以及第一次的报数次数（m）；然后对该人按照输入的顺序进行标号，当程序执行完输出出列人的
	编号。

二、调试过程
	刚开始使用了模板来写，但是后来一想没有这个必要就省去了，在用malloc（）函数进行动态分配
	时，由于初次使用出现了一些写法上的问题，但是不够成什么问题，在调试过程中没有出现什么错
	误；
	
三、测试结果

屏幕输出如下：
The program will be quit if you the number of player if zero!!!!!!!!!!
Input the number of player (n):7
Input the code of every one:3 1 7 2 4 8 4
Input the initial steps(m):6
The order of people out is:6 1 4 7 2 3 5

Input the number of player (n):7
Input the code of every one:3 1 7 2 4 8 4
Input the initial steps(m):6
The order of people out is:6 1 4 7 2 3 5

Input the number of player (n):7
Input the code of every one:3 2 6 5 3 2 1
Input the initial steps(m):12
The order of people out is:5 1 4 6 2 7 3

Input the number of player (n):1
Input the code of every one:1
Input the initial steps(m):1
The order of people out is:1

Input the number of player (n):1
Input the code of every one:1
Input the initial steps(m):123
The order of people out is:1

Input the number of player (n):0
Press any key to continue
*/


/*******************************************************************************/
/*****************************main program**************************************/
/*******************************************************************************/


struct ListNode
{
	int data;
	int steps;
	ListNode *link;
};


#include<iostream>

using namespace std;

int main()
{
	int n,m;
	cout<<"The program will be quit if you the number of player if zero!!!!!!!!!!\n";
	while( 1)
	{
		ListNode *Joseph = (ListNode *) malloc (sizeof(ListNode));
		cout<<"Input the number of player (n):";
		cin>>n;
		if( !n )
			return 1;
		cout<<"Input the code of every one:";
		cin>>Joseph->steps;
		Joseph->data = 1;
		Joseph->link = Joseph;
		for( int i=1; i<n; i++ )
		{ 
			ListNode *temp = (ListNode *) malloc (sizeof(ListNode));
			cin>>temp->steps;
			temp->data = i+1;
			temp->link = Joseph->link;
			Joseph->link = temp;
			Joseph = Joseph->link;
		}

		ListNode *temp = Joseph;
		Joseph = Joseph->link;//go to back the first of the List;

		cout<<"Input the initial steps(m):";
		cin>>m;

		cout<<"The order of people out is:";

		while(Joseph->link != Joseph)
		{
			int i(1);

			while( i<m )
			{
				temp = Joseph;
				Joseph = Joseph->link;
				i++;
			}

			cout<<Joseph->data<<' ';
			m = Joseph->steps;
			temp->link = Joseph->link;
			free(Joseph);
			Joseph = temp->link;

		}

		cout<<Joseph->data<<endl<<endl;
		free(Joseph); 
	}
	return 1;
}
//*****************************************************//
/*
一、需求分析
1、	本程序利用单向循环链表模拟了约瑟夫（Joseph）问题；
2、	本程序采用人机对话方式完成整个问题，按照提示输入参加的人数（n），每个人的密码（steps），
	以及第一次的报数次数（m）；然后对该人按照输入的顺序进行标号，当程序执行完输出出列人的
	编号。

二、调试过程
	刚开始使用了模板来写，但是后来一想没有这个必要就省去了，在用malloc（）函数进行动态分配
	时，由于初次使用出现了一些写法上的问题，但是不够成什么问题，在调试过程中没有出现什么错
	误；
	
三、测试结果
屏幕输出如下：
The program will be quit if you the number of player if zero!!!!!!!!!!
Input the number of player (n):7
Input the code of every one:3 1 7 2 4 8 4
Input the initial steps(m):6
The order of people out is:6 1 4 7 2 3 5

Input the number of player (n):7
Input the code of every one:3 1 7 2 4 8 4
Input the initial steps(m):6
The order of people out is:6 1 4 7 2 3 5

Input the number of player (n):7
Input the code of every one:3 2 6 5 3 2 1
Input the initial steps(m):12
The order of people out is:5 1 4 6 2 7 3

Input the number of player (n):1
Input the code of every one:1
Input the initial steps(m):1
The order of people out is:1

Input the number of player (n):1
Input the code of every one:1
Input the initial steps(m):123
The order of people out is:1

Input the number of player (n):0
Press any key to continue
	*/