clistmz.cpp

数据结构中的双链表问题

//CListMZ.cpp

#include "CListMZ.H"
#include "iostream.h"

///////////////////////////////////////////////////////////////////////

//模板类_CListNote的定义
//构造函数
template<class T>
_CListNote<T>::_CListNote(_CListNote<T> * up,_CListNote<T> * donw)
{
	Down=donw;
	Up=up;
}

template<class T>
_CListNote<T>::_CListNote(T & data,_CListNote<T> * up,_CListNote<T> * donw)
{
	Down=donw;
	Up=up;
	Data=data;
}
//类 _CListNote的定义结束


///////////////////////////////////////////////////////////////////////

//模板类CListMZ的定义
//构造函数
template<class T>
CListMZ<T>::CListMZ()
{
    Set();
}

template<class T>
CListMZ<T>::CListMZ(int n)
{
	Set();
	Create(n);
}

template<class T>
CListMZ<T>::CListMZ(int n,T & data)
{
    Set();
    Create(n,data);
}

template<class T>
CListMZ<T>::CListMZ(CListMZ<T> & list)
{
	Set();
    Create(list);
}

//创建函数
template<class T>
bool CListMZ<T>::Create(int n)
{
	_CListNote<T> *p;
	if(!IsEmpty())
		return 0;
	if(n>0)
	{
		if(m_nLength)
			DestroyList();
		p=m_pHead=m_pPoint=NewElem();
        if(!p)
			return 0;
		m_nLength=1;
		for(int i=1;i<n;i++)
		{
			p->Down=NewElem(p);
			if(!p->Down)
				return 0;
			m_nLength++;
			p=p->Down;
		}
		m_nPosition=0;
	    return 1;
	}
	return 0;
}

template<class T>
bool CListMZ<T>::Create(int n,T & data)
{
    _CListNote<T> *p;
    if(!IsEmpty())
		return 0;
	if(n>0)
	{
		if(m_nLength)
			DestroyList();
		p=m_pHead=m_pPoint=NewElem(data);
		if(!p)
			return 0;
		m_nLength=1;
		for(int i=1;i<n;i++)
		{
			p->Down=NewElem(data,p);
			if(!p->Down)
				return 0;
			m_nLength++;
			p=p->Down;
		}
		m_nPosition=0;
		return 1;
	}
    return 0;
}

template<class T>
bool CListMZ<T>::Create(CListMZ<T> &list)
{
   	if(list.IsEmpty())
	{	
		Set();
		return 1;
	}
	if(!IsEmpty())
		return 0;
	if(m_nLength)
		DestroyList();
	
	_CListNote<T> *p;
	T data;

	list.MoveToHead();
	list.GetAt(0,data);

	p=m_pHead=m_pPoint=NewElem(data);
	if(!p)
		return 0;
	m_nLength=1;
	for(int i=1;i<list.m_nLength;i++)
	{
		list.GetAt(i,data);	
	    p->Down=NewElem(data,p);
        if(!p->Down)
			return 0;
		m_nLength++;
	  	p=p->Down;
	}
	m_nPosition=0;
	return 1;
}

//析构函数
template<class T>
CListMZ<T>::~CListMZ()
{
   DestroyList();
}

//操作函数
template<class T>
void CListMZ<T>::DestroyList()
{
	_CListNote<T> * p1,* p2;
	p1=m_pHead;
	while(p1!=NULL)
	{
		p2=p1->Down;
		delete p1;
		p1=p2;
	}
	Set();
}

template<class T>
int CListMZ<T>::GetLength() const
{
	return m_nLength;
}

template<class T>
bool CListMZ<T>::GetAt(int n,T & data) 
{
    if(!MoveToPosition(n))
		return 0;
 	data=m_pPoint->Data;
	return 1;
}

template<class T>
bool CListMZ<T>::IsEmpty() const
{
	return m_nLength?0:1;
}

template<class T>
bool CListMZ<T>::SetAt(int n,const T & data)
{
    if(!MoveToPosition(n))
		return 0;
	m_pPoint->Data=data;
	return 1;
}

template<class T>
bool CListMZ<T>::Delete(int n)
{
	if(!MoveToPosition(n))
		return 0;
	if(n==0)
		if(m_nLength==1)
		{
			m_pHead=NULL;
			m_nPosition=-1;
		}
		else
		{
			m_pHead=m_pPoint->Down;
		    m_pPoint->Down->Up=NULL;
			m_nPosition=0;
		}
	else if(n==m_nLength-1)
	{
		m_pPoint->Up->Down=NULL;
		m_nPosition=0;
	}
	else
	{
		m_pPoint->Up->Down=m_pPoint->Down;
		m_pPoint->Down->Up=m_pPoint->Up;
		m_nPosition=0;
	}
	delete m_pPoint;
	m_nLength--;
	m_pPoint=m_pHead;
	return 1;
}

template<class T>
bool CListMZ<T>::Find(const T & data,int & n)
{
    MoveToHead();
	for(int i=0;i<m_nLength;i++)
		if(m_pPoint->Data==data)
		{
			n=i;
			return 1;
        } 
		else
			MoveToDown();
	n=-1;
	return 0;
}

template<class T>
bool CListMZ<T>::Insert(int n,T & data)
{
	if(!MoveToPosition(n))
		return 0;
    _CListNote<T> * p=NewElem(data,m_pPoint->Up,m_pPoint);
	if(!p)
		return 0;
	if(n==0)
		m_pHead=p;
	else 
		m_pPoint->Up->Down=p;
	m_pPoint->Up=p;
	m_nLength++;
	m_pPoint=p;
	return 1;
}

template<class T>
bool CListMZ<T>::Add(T & data)
{
    _CListNote<T> * p=NewElem(data);
	if(!p)
		return 0;
	if(m_nLength==0)
	{
		m_pHead=p;
	}
	else
	{
		MoveToPosition(m_nLength-1);
		p->Up=m_pPoint;
		m_pPoint->Down=p;
	}
	m_nLength++;
	m_pPoint=p;
	m_nPosition++;
	return 1;
}
template<class T>
void CListMZ<T>::Display()
{
	if(!IsEmpty())
	{
		_CListNote<T> * p=m_pHead;
		while(p)
		{
			cout<<p->Data<<' ';
			p=p->Down;
		}
	}
	else
		cout<<"表是空的";
	cout<<endl;
}

template<class T>
T & CListMZ<T>::operator [] (int n)
{
    if(!MoveToPosition(n))
		return *(new T);
	return m_pPoint->Data;
}

template<class T>
void CListMZ<T>::MoveToHead()
{
	m_pPoint=m_pHead;
	m_nPosition=0;
}

template<class T>
bool CListMZ<T>::MoveToPosition(int n)
{
	if(!Check(n))
		return 0;
	while(n>m_nPosition)
		MoveToDown();
	while(n<m_nPosition)
		MoveToUp();
	return 1;
}

template<class T>
bool CListMZ<T>::MoveToDown()
{
	if(m_nPosition>=m_nLength-1)
		return 0;
	m_pPoint=m_pPoint->Down;
	m_nPosition++;
	return 1;
}

template<class T>
bool CListMZ<T>::MoveToUp()
{
	if(m_nPosition<=0)
		return 0;
	m_pPoint=m_pPoint->Up;
	m_nPosition--;
	return 1;
}

template<class T>
void CListMZ<T>::Set()
{
	m_pHead=NULL;
	m_pPoint=NULL;
	m_nLength=0;
	m_nPosition=-1;
}

template<class T>
_CListNote<T> * CListMZ<T>::NewElem(T & data,_CListNote<T> * up,_CListNote<T> * Down)
{
	return (new _CListNote<T>(data,up,Down));
}

template<class T>
_CListNote<T> * CListMZ<T>::NewElem(_CListNote<T> * up,_CListNote<T> * Down)
{
	return (new _CListNote<T>(up,Down));
}

template<class T>
bool CListMZ<T>::Check(int n)
{
	if(n<0||n>=m_nLength)
		return 0;
	return 1;
}