#include <stdio.h>
                #include <iostream.h>

		enum Boolean { False, True };
		template <class Type> class CircList;

		template <class Type> class CircListNode {
		friend class CircList<Type>;
		public:
		   CircListNode ( Type d=0, CircListNode<Type> *next=NULL ) : data (d), link (next) { }
		private:
		   Type data;
		   CircListNode<Type> *link;
		};

		template <class Type> class CircList {
		public:
		   CircList ();
		   CircList ( Type value );						//構(gòu)造函數(shù)
		   ~CircList ( );								//析構(gòu)函數(shù)
		   int Length ( ) const;							//計算循環(huán)鏈表長度
		   Boolean IsEmpty ( ) { return first->link == first; }		//判表空否
		   Boolean Find ( const Type & value );				//在循環(huán)鏈表中尋找其值等于value的結(jié)點(diǎn)
		   Type getData ( ) { return current->data; }						//返回當(dāng)前結(jié)點(diǎn)中存放的值
		   Type getNextData () ;
		   void Firster ( ) { current = first; }					//將當(dāng)前指針置于頭結(jié)點(diǎn)
		   void First ( );							//將當(dāng)前指針指向鏈表的第一個結(jié)點(diǎn)
		   void Next ( );							//將當(dāng)前指針指到當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn)
		   void Prior ( );							//將當(dāng)前指針指到當(dāng)前結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)
		   void Insert ( const Type & value );					//插入新結(jié)點(diǎn)
		   void RemoveNext ( );
		   void Josephus ( int n, int m );								//刪除當(dāng)前結(jié)點(diǎn)
		private:
		   CircListNode<Type> *first, *current, *last;			//頭指針, 當(dāng)前指針, 尾指針
		};

		template <class Type> void CircList <Type> :: CircList () {
		    current = last = first = new CircListNode<Type> ();
		    first->link = first;
		}

		template <class Type> void CircList <Type> :: ~CircList () {
		    CircListNode<Type> *q;
		    while ( first->link != first ) {
			q = first->link;   first->link = q->link;
			delete q;
		    }
		    delete first;  current = first = last = NULL;
		}

		template <class Type> void CircList <Type> :: Next () {
		    if ( current->link == first ) current = first;
		    current = current->link;
		}

		template <class Type> Type CircList <Type> :: getNextData() {
		    if ( current->link == first ) return first->link->data;
		       else return current->link->data;
		}

		template <class Type> void CircList <Type> :: RemoveNext () {
		    CircListNode<Type> *p = current->link;
		    if ( p == last ) last = current;
		    if ( p != first ) current->link = p->link;
			else { p = first->link; first->link = p->link; }
		    delete p;
		}

		template <class Type> void CircList <Type> :: Insert (const Type & value) {
		    CircListNode<Type> *p = new CircListNode<Type> ( value, first );
		    last = last->link = p;
		}

		template <class Type> void CircList <Type> :: Josephus ( int n, int m ) {
		   for ( int i=0; i<n-1; i++ ) {		     				//循環(huán)n-1趟，讓n-1個人出列
			 for ( int j=0; j<m-1; j++ ) Next ( );	  			//讓current向后移動m-1次
			 cout << "Delete person " << getNextData ( ) << endl;
			 RemoveNext ( ); 								//刪去該結(jié)點(diǎn)，讓current指示下一結(jié)點(diǎn)
		   }
		   cout << "the winner is : " << getData () << endl;
		}