cirlist1.h

数据结构的一些教程....比较适于初学者

#include <iostream.h>
#include <stdlib.h>

template <class T> class CirList;	

template <class T>
class ListNode
{	
   friend class CirList<T>;
public:             //***************************************
   ListNode<T> *next;        //结点链接指针
   T data;     //结点数据
public: 
   ListNode(ListNode<T> *ptrNext=NULL);
   ListNode (const T& item, ListNode<T> *ptrNext=NULL);	   
};

//链表结点部分操作的实现
template <class T> 
ListNode<T>::ListNode(ListNode<T> *ptrNext) : next(ptrNext) {}

template <class T>
ListNode <T> ::ListNode (const T& item,ListNode<T> *ptrNext)
{
	data=item;
	next=ptrNext;
}

template <class T> class CirList
{
 protected:    //*****************************
    ListNode<T> *head;		
	int size;
	ListNode<T> *currPtr;
 public:    
	CirList(void );		//构造函数            
    ~CirList(void);	    //析构函数

   int ListSize(void) const;
   int ListEmpty(void) const;
   ListNode<T> *Index(int pos); 
   void Insert(const T&item,int pos);
   T Delete(int pos);
   T GetData(int pos);
   void ClearList(void);
   T DeleteAfter();            //删除当前结点的下一个结点
   
   bool NextEndOfList() const; //判别下一个结点是否为表尾
   ListNode<T> *Reset(int pos=0);
   ListNode<T> *Next (void);
   int EndOfList(void) const;
   T GetData(void);   //取当前结点的值
//*****************
   void Josephus1(int m);
};

//链表的公共操作
template <class T> 
CirList<T>::CirList( )
{
	head=new ListNode<T>();
    head->next=head;
	size=0;
}

template <class T> 
CirList<T>::~CirList(void)   //析构函数
{
     ClearList();  
	 delete head;
}

template <class T>
int CirList<T>::ListSize(void) const
{
	return size;
}

template <class T>
int CirList<T>::ListEmpty(void) const
{
	return size==0;
}

template <class T>
ListNode<T>* CirList<T>::Index(int pos) 
{
	if(pos<-1||pos>(size-1))
	{
		cerr<<"参数pos越界出错!"<<endl;
		exit(1);
	}
	if(pos==-1) return head;
	ListNode<T> *p=head->next;  
    int i = 0;		
    while(p!=head&&i<pos)
 	  {
		p=p->next;  
		i++; 
	 }	
     return p;				
}

template <class T> 
void CirList<T>::Insert(const T &item,int pos)
{
//将含item的新元素插入到链表pos位置
  ListNode<T> *p=Index(pos-1);
  ListNode<T> *newNode=new ListNode<T>(item,p->next);
  p->next=newNode;
  size++;
}

template <class T> 
T CirList<T>::Delete(int pos)
{
 if(size==0)
 {
	 cerr<<"链表已为空表！"<<endl;
	 exit(1);
 }
 ListNode<T> *q,*p=Index(pos-1);
 q=p->next;
 p->next=p->next->next;
 T data=q->data;
 delete q;
 size--;
 return data;
}

template <class T> 
T CirList<T>::GetData(int pos)
{
 //提取第i个结点的数据
  ListNode<T> *p=Index(pos);
 // p 指向链表第 i 个结点
  return p->data;
}

template <class T> 
void CirList<T>::ClearList(void)
{
//删去链表中除表头结点外的所有其他结点
    ListNode<T> *p,*p1;
	p=head->next;
    while(p!=head)      //注意p!=head
	{
         p1=p;
		 p=p->next;
         delete p1;        //释放它 
    }
    size=0;
    head->next=head;
}

			
template <class T> 
ListNode<T> *CirList<T>::Reset(int pos) 
{
	if(head==NULL) return NULL;
	if(pos<-1||pos>size-1)
	{
		cerr<<"参数出错!"<<endl;
		exit(1);
	}
	if(pos==-1) return head;
	if(pos==0) currPtr=head->next;
	else
	{
		currPtr=head->next;
		for(int i=0;i<pos;i++)
		{
		  currPtr=currPtr->next;
		}
	} 
	return currPtr;
}

template <class T> 
ListNode<T> *CirList<T>::Next(void)
{
	currPtr=currPtr->next;
	return currPtr;
}

template <class T> 
T CirList<T>::GetData(void)
{
	return currPtr->data;
}

template <class T> 
int CirList<T>::EndOfList(void)  const
{
	return currPtr==head;
}

template<class T>
bool CirList<T>::NextEndOfList() const
{
	return currPtr->next==head;
}

template<class T>
T CirList<T>::DeleteAfter()
{
	ListNode<T> *p=currPtr->next;
	currPtr->next=p->next;
	T data=p->data;
	delete p;
	size--;
	return data;
}

template<class T>
void CirList<T>::Josephus1(int m)
{
ListNode<T> *p,*w,*t;
int i;
w=Reset(-1);
p=w->next;  //w为p的前一个结点；
while(size>1)
{  i=1;
    while(i<m)   //1,2,…m//
   { w=p; p=p->next;   if(p!=head)  i++;  }
   t=p;    //t指向被删除结点 //
   w->next=p->next;
   p=p->next;
   delete t;
   size--;  
}
}