listdata.h

这是翻阅《数据结构、算法与应用——C++语言描述》 以及在网上得到的一些资料后写出来的。起因是在项目中要用到一个链表

//////////////////////////////////////////////////////////////////////
//File:ListData.h
//Author:smoke [smoke_aT_tomydan.net]
//Description:You can get the manual(readme.txt or readme.html)
//////////////////////////////////////////////////////////////////////
#ifndef _LISTDATA_H_
#define _LISTDATA_H_

//////////////////////////////////////////////////////////////////////
//Header file
//////////////////////////////////////////////////////////////////////
#include "node.h"


template <class Type> class CListData       
{
private:
	CListData(const CListData<Type> &l);
	CNode<Type> *first, *current, *prior, *last;
	int nCount;//link list's counter
public:
	CListData();
	~CListData();
	
	//////////////////////////////////inline function//////////////////////////////////
	inline 	void Initialize();
	inline	BOOL IsEmpty();
	inline	void MakeEmpty();
	inline	int  Length() const;
	inline	Type Get();			
	inline	BOOL Put(Type const &value);
	inline	Type GetNext();				
	inline	Type Next();				
	inline	void Append(const Type &value);
	inline	BOOL InsertBefore(const Type &value);
	inline	BOOL Locate(int i);
	inline	void First();	
	inline	void End();		
	inline	BOOL IsEnd();
	inline	BOOL Remove();	
	inline	BOOL Remove(int k, Type &x);
	inline	BOOL RemoveAfter();
};

//////////////////////////////////inline function//////////////////////////////////

//////////////////////////////////////////////////////////////////////
//construct
//////////////////////////////////////////////////////////////////////
template <class Type>
CListData<Type>::CListData()
{
	first = current = last = new CNode<Type>;
	prior = NULL; 
	nCount = 0;
}

//////////////////////////////////////////////////////////////////////
//destruction
//////////////////////////////////////////////////////////////////////
template <class Type>
CListData<Type>::~CListData()
{
	delete first;
}


//////////////////////////////////////////////////////////////////////
//FunctionName:Initialize
//Parameters:NULL
//return Type:void
//Description:reset current/last and first's point and set prior to null
//////////////////////////////////////////////////////////////////////
template< class Type>
void CListData<Type>::Initialize()
{
	current = last = first;
	prior = NULL;
}

//////////////////////////////////////////////////////////////////////
//FunctionName:MakeEmpty
//Parameters:NULL
//Return Type:void
//Description:Make the link list to empty,and reset all point
//////////////////////////////////////////////////////////////////////
template <class Type>
void CListData<Type>::MakeEmpty()
{
	CNode<Type> *q;
	while (first->link != NULL)
	{
		q = first->link;
		first->link = q->link;
		delete q;
	}
	Initialize();
}

//////////////////////////////////////////////////////////////////////
//FunctionName:IsEmpty
//Parameters:NULL
//Return Value:boolean
//Description:Judgement the link list is NULL
//////////////////////////////////////////////////////////////////////
template <class Type>
BOOL CListData<Type>::IsEmpty()
{
	if (first == NULL) 
	{
		Initialize();
		return TURE;
	}
	else 
		return FALSE;
}

//////////////////////////////////////////////////////////////////////
//FunctionName:Length
//Parameters:NULL
//Return Type:int 
//Description:Get link list's length
//////////////////////////////////////////////////////////////////////
template <class Type>
int CListData<Type>::Length() const
{
	return 	nCount;
}

//////////////////////////////////////////////////////////////////////
//FunctionName:Get
//Parameters:NULL
//Return Type:Type [the type of template to sets]
//Description:Get the current node's data
//////////////////////////////////////////////////////////////////////
template <class Type>
Type CListData<Type>::Get()
{
	if (current != NULL) 
		return current -> data;
	else
		return NULL;
}

//////////////////////////////////////////////////////////////////////
//FunctionName:Put
//Parameters:Type &value
//Return Type:boolean
//Description:Move the current data's node to value
//////////////////////////////////////////////////////////////////////
template <class Type>
BOOL CListData<Type>::Put(const Type &value)
{
	if (current != NULL)
	{
		current->data = value;
		return TURE;
	}
	else 
		return FALSE;
}

//////////////////////////////////////////////////////////////////////
//FunctionName:GetNext
//Parameters:
//Return Type:Type [the type of template to sets]
//Description:Get the Next Node's data ,do not modified the current's point
//////////////////////////////////////////////////////////////////////
template <class Type>
Type CListData<Type>::GetNext()
{
	if (current->link != NULL) 
		return current->link->data;
	else 
		return NULL;
}

//////////////////////////////////////////////////////////////////////
//FunctionName:Next
//(after moved current point)
//Parameters:
//Return Type:Type [the type of template to sets]
//Description:Move the current point to next and return the data
//////////////////////////////////////////////////////////////////////
template <class Type>
Type CListData<Type>::Next()
{
	if (current != NULL && current->link != NULL)
	{
		prior = current; 
		current = current->link;
		return current->data;
	}
	else
	{
		return NULL;
	}
}

//////////////////////////////////////////////////////////////////////
//FunctionName:Append
//Parameters:Type &value
//Return Type:void
//Description:Insert a node after current,do not modified the current's point
//////////////////////////////////////////////////////////////////////
template <class Type>
void CListData<Type>::Append(const Type &value)
{
	if( first == NULL )
		return;
	CNode<Type> *p = new CNode<Type>(value, current -> link);
	current->link = p;
	nCount++;
}

//////////////////////////////////////////////////////////////////////
//FunctionName:InsertBefore
//modified prior's point
//Parameters:Type &value
//Return Type:boolean
//Description:Insert a node before the current,do not modified current's pint
//////////////////////////////////////////////////////////////////////
template <class Type>
BOOL CListData<Type>::InsertBefore(const Type &value)
{
	CNode<Type> *p = new CNode<Type>(value);
	if (prior != NULL)
	{
		p->link = current;
		prior->link = p;
		prior = p;
		return TURE;
	}
	else 
		return FALSE;
}

//////////////////////////////////////////////////////////////////////
//FunctionName:Locate
//Parameters:int i
//Return Type:boolean
//Description:Moves the current to i 
//////////////////////////////////////////////////////////////////////
template <class Type>
BOOL CListData<Type>::Locate(int i)
{
	if (i <= -1 || i > nCount) 
		return FALSE;
	
	current = first->link;
	for (int j = 0; current != NULL && j < i; j++, current = current->link) 
		prior = current;
	
	if (current != NULL) 
		return TURE;
	else 
		return FALSE;
}

//////////////////////////////////////////////////////////////////////
//FunctionName:First
//Parameters:NULL
//Return Type:void
//Description:Moves the current to link list's head
//////////////////////////////////////////////////////////////////////
template <class Type>
void CListData<Type>::First()
{
	if( first == 0 )
		return;		
	current = first;
	prior = NULL;
}

//////////////////////////////////////////////////////////////////////
//FunctionName:End
//Parameters:NULL
//Return Type:void
//Description:Moves the current to link list's end
//////////////////////////////////////////////////////////////////////
template <class Type>
void CListData<Type>::End()
{
	if (last->link != NULL)
	{
		for ( ;current->link != NULL; current = current->link)
			prior = current;
		last = current;
	}
	current = last;        
}

//////////////////////////////////////////////////////////////////////
//FunctionName:End
//Parameters:NULL
//Return Type:void
//Description:Judgement the link list is end?
//////////////////////////////////////////////////////////////////////
template <class Type>
BOOL CListData<Type>::IsEnd()
{
	if( current->link == 0)
		return TRUE;
	return FALSE;
}

//////////////////////////////////////////////////////////////////////
//FunctionName:Remove
//if end of the link list sets the current to null
//Parameters:NULL
//Return Type:boolean
//Description:Delete the current node,and moves the current node to next,
//////////////////////////////////////////////////////////////////////
template <class Type>
BOOL CListData<Type>::Remove()
{
	if (current != NULL && prior != NULL)
	{
		CNode<Type> *p = current;
		prior->link = p->link;
		current = p->link;
		delete p;
		nCount--;
		return TURE;
	}
	else 
		return FALSE;
}

//////////////////////////////////////////////////////////////////////
//FunctionName:Remove
//Parameters:int k,Type &x
//Return Type:boolean
//Description:This function be invalid!!!
//////////////////////////////////////////////////////////////////////
template <class Type>
BOOL CListData<Type>::Remove(int k,Type &x)
{
	if(k <1 || !first)
	{
		throw;
		return FALSE;
	}
	
	CNode <Type> *q = first;
	for(; k > 1 && q;k--)	
		q = q->link;
	
	if(!q || !q->link)
	{
		throw;
		return FALSE;
	}
	
	CNode <Type> *p = q->link;
	q->link = p->link;
	x = p -> data;
	delete p;
	nCount--;
	
	return TRUE;
}

//////////////////////////////////////////////////////////////////////
//FunctionName:RemoveAfter
//Parameters:NULL
//Return Type:boolean
//Description:Delete the node after current,do not modify current's point
//////////////////////////////////////////////////////////////////////
template <class Type>
BOOL CListData<Type>::RemoveAfter()
{
	if (current->link != NULL && current != NULL)
	{
		CNode<Type> *p = current->link;
		current->link = p->link;
		delete p;
		return TURE;                  
	}
	else
		return FALSE;
}
//////////////////////////////////End inline function//////////////////////////////////

#endif