circlist.h

数据结构答案 金元平

// CircList.h: interface for the CircList class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_CIRCLIST_H__8AAAF1F0_13D5_4DC4_A464_9467B47233BF__INCLUDED_)
#define AFX_CIRCLIST_H__8AAAF1F0_13D5_4DC4_A464_9467B47233BF__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#include "ListNode.h"

template <class T> class CircListIterator;

template <class T>
class CircList  
{
	friend class CircListIterator<T>;

public:
	CircList();
	CircList(const CircList& cl);
	ListNode<T>* getNode();
	void returnNode(ListNode<T>* x);

	virtual ~CircList();
	void InsertTail(ListNode<T>* n);

private:
	ListNode<T>* last;
	static ListNode<T>* av;

};

template <class T>
ListNode<T>* CircList<T>::av = NULL;

template <class T>
CircList<T>::CircList()
{
	last = NULL;
}

template <class T>
CircList<T>::CircList(const CircList& cl)
{
	last = cl.last;
}

template <class T>
CircList<T>::~CircList()
{
	ListNode<T>* first = last->link;
	last->link = av;
	av = first;
	last = NULL;
}

template <class T>
void CircList<T>::InsertTail(ListNode<T>* n)
{
	if ( last == NULL )
	{
		last = n;
		n->link = n;
	}
	else
	{
		n->link = last->link;
		last->link = n;
		last = n;
	}
}

template <class T>
ListNode<T>* CircList<T>::getNode()
{
	ListNode<T>* x;
	if (av==NULL)
		x = new ListNode<T>;
	else
	{
		x = av;
		av = av->link;
	}
	return x;
}
	
template <class T>
void CircList<T>::returnNode(ListNode<T>* x)
{
	x->link = av;
	av = x;
}

#endif // !defined(AFX_CIRCLIST_H__8AAAF1F0_13D5_4DC4_A464_9467B47233BF__INCLUDED_)