source1.cpp

循环链表的应用 循环链表的应用 很方便的实现

#include <iostream>
#include "Header1.h"
using namespace std;
const int MaxSize=20;                      //maxest number of people of the rank.

template <class Type>
Circlist<Type>::~Circlist(){               //destructor set free the room  being possessed by nodes in list
	if(LocateFirst()){                     //locate current pointer pointe to the first node
		while(Current->link!=First){   
        if(!DelCurrentNode())
			break;
		}
	}
	delete First;                           //delete header pointer
}

template <class Type>
int Circlist<Type>::GetLength() const{      //return the length of list,that is the number of nodes in the list
	int count=0;
	Current=First->link;
	while(Current!=First){
		count++;
		Current=Current->link;	
	}
	return count;
}

template <class Type>
bool Circlist<Type>::IsEmpty() const{        //judge the list being empty whether or not
	 if(First->link==First)
	     return true;
	     return false;
}

template <class Type>                         //find the code's address through given the value
CirclistNode<Type>* Circlist<Type>::Find(const Type& value){
	 Current=First->link;
	 if(Current==First)
		 return null;
	 while(Current!=First&&Current->data!=value)
	     Current=Current->link;
	 if(Current==First)
		 return null;
	 else
		 return Current;
}

template <class Type>                         //locate current pointer the specified position
bool Circlist<Type>::SetCurrent(int i){
	 if(i==0){
		 Firster();
		 return true;
	 }
	 if(LocateFirst()){
      int j=1;
	  while(Current!=First&&j<i){
           j++;
		   Current=Current->link;
	  }
	  if(Current==First&&j<i)
		   return false;
	  return true;
	 }
	 else
		 return false;
}

template <class Type>                          //insert new node to current node's next position
void Circlist<Type>::InsertNode(const Type& DataValue){
	 CirclistNode<Type>* newNodePtr=new CirclistNode<Type>(DataValue);
	 assert(newNodePtr);
	 newNodePtr->link=Current->link;
	 Current->link=newNodePtr;
}

template <class Type>
bool Circlist<Type>::DelCurrentNode(){         //delete the code which is current node's next
	 if(IsEmpty())
		return false;
	 if(Current->link==First)
		 Firster();
	 CirclistNode<Type>* temptPtr=Current->link;
     Current->link=temptPtr->link;
	 delete temptPtr;
	 return true;
}

template <class Type>
void Circlist<Type>::Firster(){                 //make current pointer pointed to the header node
     Current=First;	 
}

template <class Type>
bool Circlist<Type>::LocateFirst(){             //make current pointer pointed to first node
	 Current=First->link;
	 if(Current==First)
		 return false;
	     return true;
}

template <class Type>
bool Circlist<Type>::Next(){                    //make current pointer pointed to next node
	 Current=Current->link;
	 if(Current==First)
		 if(LocateFirst())
		    return true;
		 else
		    return false;
	 else
		    return true;
}

template <class Type>
bool Circlist<Type>::Prior(){                   //make current pointer pointed to the prior node 
	 CirclistNode<Type>* temptPtr=Current;
	 while(Current->link!=temptPtr)
		 Current=Current->link;
	 if(Current==First)
		 return false;
	 else
		 return true; 
}

template <class Type>
void Circlist<Type>::ShowAllElement(){          //show all elemenets in current list
	 if(LocateFirst()){
		 while(Current->link!=First){
		 cout<<" "<<Current->data;
		 Current=Current->link;
		 }
		 cout<<" "<<Current->data;
	 }
}

template <class Type>
void CirclJosephus_List<Type>::initalList(){    //inital the CirclJosephus_List:input the persons' ID
	                                            //and insert every person's ID to list.
	 cout<<endl<<"Please input the ID of every person:";
	 Type data[MaxSize];
	 for(int i=0;i<PeopleNumber;i++)
	 cin>>data[i];
	 int k=0;
	 for(int j=PeopleNumber-1;j>=0;j--)
		 InsertNode(data[j]);
}

template <class Type>
bool CirclJosephus_List<Type>::Run(){            //process the cycle end with returning a winner 
	 if(StartNumber<=0||Number<=0)
		 return false;
	 int start=StartNumber;
	 if(!SetCurrent(start-1))
		 return false;
	 cout<<endl<<"Start to delete people's ID:";
	 for(int i=0;i<PeopleNumber-1;i++){ 
		 for(int walk=1;walk<Number;walk++)
			 Next();
	     if((GetCurrent()->GetLink())==GetFirst())
		 cout<<" "<<GetFirst()->GetLink()->GetData();
		 else
		 cout<<" "<<(GetCurrent()->GetLink())->GetData();
         DelCurrentNode();
	 }
	 LocateFirst();
	 cout<<" "<<GetCurrent()->GetData()<<endl;
	 cout<<"The winner is:"<<GetCurrent()->GetData()<<endl;
	 return true;
}