循环单链表实现约瑟夫问题.cpp

来自「这个是我的大学作业哦 里面有些很经典的代码 出自清华大学的数据结构课本」· C++ 代码 · 共 106 行

 
#include <iostream>
using namespace std;
//<<<<<<<<<<<<<<<<<<<<<<<<
struct Jose{
	int code;
	Jose* next;
};

//****************************

int n , s , m;

Jose *pCur, *pivot;

bool getValue();

Jose* creatingRing();

void countBy(int m);                       

void process();
//================================================

int main(){
	if( !getValue() ){ return 1; }

	Jose* pJose = creatingRing();

	process();

	cout<<"   The Winner is->"<< pCur->code <<endl;

	delete [] pJose;

	return 0;
}
//===============================
bool getValue(){

	cout<<"Please input Number, startPosition, intervalNumber: "<<endl;

	cin>> n>> s>> m ;

	if(n >=2 && s >= 1 && m >= 1 && m <= n){ return true; }

	else
	{
    cout<<"Failed in bad Number or startPosition or intervalNumber!!"<<endl;
	return false; 
	}
}
//----------------------------------------------------
Jose* creatingRing() {

	Jose* px = new Jose[n];

	for(int i = 1; i <= n; i++)
	{
		px[i-1].next = &px[i%n];            
		px[i-1].code = i;
	}
	cout<<"There are "<< n <<" persons in total;"<<endl;

	pCur = &px[n-1];

	countBy(s);

	return px;
}
//---------------------------------------------------------------------
void countBy(int m) {

	for(int i = 0; i < m; ++i)
	{
		pivot = pCur;
		pCur = pCur->next;
	}
}
//--------------------------------------------

void process(){

	for (int i = 1; i < n; i++)
	{
		countBy(m);

	
		cout<<"  "<< pCur->code;

	
		static int line = 0;

		if(!(++line % 14))
		{
			cout<<"-------------------// #  \n";
		}

		pivot->next = pCur->next;

        delete []pCur;
		pCur = pivot;
	}
}
//-----------------------------------------------------------------