dzqlist.cpp

来自「一种基于二维链表的稀疏矩阵模半板类设计 A template Class of」· C++ 代码 · 共 951 行 · 第 1/2 页

#include "dzqList.h"

//****************************************************************************************//
//**********************************SigLinkedCirList's implementation*********************//
//****************************************************************************************//
template <class T>
SigLinkedCirList<T>::SigLinkedCirList()
{
	first=last=&HeadNode;
	HeadNode.link=first;
}




template<class T>
SigLinkedCirList<T>::SigLinkedCirList(SigLinkedCirList<T>& c)
{
	ChainNode<T>* pOldNode;
	ChainNode<T>* pNewNode;
	ChainNode<T>* pCurrent=c.first->link;
	first=&HeadNode;
	HeadNode.link=first;
	pOldNode=first;
	for(; pCurrent!=c.first; pCurrent=pCurrent->link)
	{
		pNewNode=new ChainNode<T>;
		pNewNode->data=pCurrent->data;
		pNewNode->link=first;
		pOldNode->link=pNewNode;
		pOldNode=pNewNode;
	}
	last=pOldNode;  //last.
}



template <class T>
SigLinkedCirList<T>& SigLinkedCirList<T>::operator=(const SigLinkedCirList<T>& c)
{
	if(this!=&c)
	{
		Erase();

		ChainNode<T>* pOldNode;
		ChainNode<T>* pNewNode;
		ChainNode<T>* pCurrent=c.first->link;
		
		pOldNode=first;
		for(; pCurrent!=c.first; pCurrent=pCurrent->link)
		{
			pNewNode=new ChainNode<T>;
			pNewNode->data=pCurrent->data;
			pNewNode->link=first;
			pOldNode->link=pNewNode;
			pOldNode=pNewNode;
		}
		last=pOldNode;  //last.
	}
	return *this;
}


template <class T>
SigLinkedCirList<T>::~SigLinkedCirList( )
{
	ChainNode<T> *pNext;
	pNext=first->link;
	while(pNext!=&HeadNode)
	{
		first=pNext;
		pNext=pNext->link;
		delete first;
	}
	//delete pNext;  !!!!HeadNode allocated by complier,so this instruction is not neccessary.
}


template <class T>
void SigLinkedCirList<T>::Erase()
{
	//keep HeadNode,first ,last.
	ChainNode<T> *pNext;    
	pNext=first->link;
	while(pNext!=&HeadNode)
	{
		first=pNext;
		pNext=pNext->link;
		delete first;
	}
	first=last=&HeadNode;
	first->link=first;
}



		

template <class T>
SigLinkedCirList<T>& SigLinkedCirList<T>::Append(const T& x)
{
	//Append right.
	ChainNode<T> *pNewNode=new ChainNode<T>;
	last->link=pNewNode;
	pNewNode->data=x;
	last=pNewNode;
	last->link=&HeadNode;
	return *this;
}




template<class T>
int SigLinkedCirList<T>::Length() const
{
	int len=0;
	ChainNode<T> *pScan;
	pScan=first->link;
	while(pScan!=first)
	{
		len++;
		pScan=pScan->link;
	}
	return len;
}


template <class T>
bool SigLinkedCirList<T>::Find(int k, T& x) const
{
	//find the kth Node,if exist save kth Node's data into x, and return true.
	//else return false.
	if(k<1)
		return false;
	ChainNode<T>* pScan=first->link;
	int index=1;
	while(index<k && pScan!=first)
	{
		index++;
		pScan=pScan->link;
	}
	if(pScan!=first)
	{
		x=pScan->data;
		return true;
	}
	return false;
}



template <class T>
int SigLinkedCirList<T>::Search(const T& x) const
{
	//Searching x in List,if success return index,else return 0.
	int index=1;
	ChainNode<T> *pScan=first->link;
	while(pScan!=first && pScan->data!=x)
	{
		index++;
		pScan=pScan->link;
	}
	if(pScan!=first)
	{
		return index;
	}
	return 0;
}




template <class T>
SigLinkedCirList<T>& SigLinkedCirList<T>::Delete(int k, T& x)
{
	if(k<1 || first==last)
	{
		throw OutOfBounds();
	}
	ChainNode<T> *pScan=first->link;
	ChainNode<T> *pTemp=NULL;
	int index=1;
	if(1==k)  //delete the 1st Node.
	{
		if(first->link==last) //and only one Node.
		{
			pTemp=first->link;
			first->link=first;
			last=first;
		}
		else
		{	pTemp=first->link; //more than one Node.
			first->link=pTemp->link;
		}
	}
	else
	{		
		while(pScan!=first && index<k-1)
		{
			pScan=pScan->link;
			index++;
		}
		if(pScan==first)
		{
			throw OutOfBounds();
		}
		else
		{
			pTemp=pScan->link;  //pScan->(k-1)th Node,pTemp->kth Node.
			pScan->link=pTemp->link;
			if(pTemp==last)
				last=pScan;
		}
	}
	x=pTemp->data;
	delete pTemp;
	return *this;
}




template <class T>
SigLinkedCirList<T>& SigLinkedCirList<T>::Insert(int k, const T& x)
{
	//insert the node which contain data x after the kth node.
	ChainNode<T> *pTemp;
	if(k<0)
		throw OutOfBounds();
	if(first==last)   //the original list is null.
	{
		if(k!=0)
			throw OutOfBounds();
		else    //the original list is null, and insert node as first node.
		{
			pTemp=new ChainNode<T>;
			pTemp->data=x;
			pTemp->link=first;
			first->link=pTemp;
			last=pTemp;
		}
		return *this;
	}

	if(k==0) //original list not null and insert node as first node.
	{
		pTemp=new ChainNode<T>;
		pTemp->data=x;
		pTemp->link=first->link;
		first->link=pTemp;
		return *this;
	}


	ChainNode<T> *pScan=first->link;  //common state.
	int index=1;
	for(; index<k && pScan!=first; index++,pScan=pScan->link);
	if(pScan==first)
	{
		throw OutOfBounds();
	}
	else
	{
		pTemp=new ChainNode<T>;
		pTemp->data=x;
		pTemp->link=pScan->link;
		pScan->link=pTemp;
		if(pScan==last)
			last=pTemp;
	}
	return *this;
}



template <class T>
SigLinkedCirList<T>& SigLinkedCirList<T>::AppendLeft(const T& x)
{
	
	ChainNode<T> *pTemp=new ChainNode<T>;
	pTemp->data=x;
	pTemp->link=first->link;
	first->link=pTemp;
	if(first==last)
		last=pTemp;
	return *this;
}




		

template<class T>
SigLinkedCirList<T>& SigLinkedCirList<T>::Reverse()
{
	ChainNode<T> *pScan;
	ChainNode<T> *pTemp;
	ChainNode<T> *pTracer;
	if(first==last  || first->link==last) //empty or only one node.
		return *this;

	
	pTracer=first->link;
	pScan=first->link->link;
	while(pScan!=first)
	{
		pTemp=pScan;
		pScan=pScan->link;
		pTemp->link=pTracer;
		pTracer=pTemp;
	}
	last=first->link;
	last->link=first;
	first->link=pTracer;
	
	return *this;
}






template<class T>
SigLinkedCirList<T>& SigLinkedCirList<T>::Reverse(SigLinkedCirList<T>& dest,SigLinkedCirList<T>& src)
{
	//Without delete any memory in src.(just change pointers' content).
	//and without allocate any memory.
	dest.Erase();
	ChainNode<T> *pTemp;
	ChainNode<T> *pScanSrc;
	ChainNode<T> *pScanDest;
	if(src.first==src.last)  //src empty.
		return dest;

	
	pScanDest=src.first->link;
	dest.last=src.first->link;  //no error!!!

	pTemp=src.first->link;
	pScanSrc=src.first->link;
	while(pScanSrc!=src.first)
	{
		pTemp=pScanSrc;
		pScanSrc=pScanSrc->link;
		pTemp->link=pScanDest;
		pScanDest=pTemp;
	}
	src.last=src.first;
	src.first->link=src.first;
	dest.last->link=dest.first;
	dest.first->link=pTemp;
	return dest;
}




template<class T>
void SigLinkedCirList<T>::Output(ostream& out) const
{
	ChainNode<T> *pScan;
	pScan=first->link;
	while(pScan!=first)
	{
		out<<pScan->data<<"  ";
		pScan=pScan->link;
	}
}




//***********************************************************************************//
//****************************Above are SigLinkedCirList's implementation************//
//***********************************************************************************//





//Chain's implementation.
template<class T>
Chain<T>::Chain(Chain<T>& c)
{
	ChainNode<T>* pOldNode;
	ChainNode<T>* pNewNode;
	ChainNode<T>* pCurrent=c.first;
	if(c.first!=NULL)
	{
		pOldNode=new ChainNode<T>;
		first=pOldNode;   //first
		pOldNode->data=pCurrent->data;
		pOldNode->link=NULL;
		pCurrent=pCurrent->link;
		for(; pCurrent!=NULL; pCurrent=pCurrent->link)
		{
			pNewNode=new ChainNode<T>;
			pNewNode->data=pCurrent->data;
			pNewNode->link=NULL;
			pOldNode->link=pNewNode;
			pOldNode=pNewNode;
		}
		last=pOldNode;  //last.
	}
	else
	{
		first=last=NULL;
	}
}


template<class T>
Chain<T>& Chain<T>::operator=(const Chain<T>& c)
{
	if(this!=&c)  //avoid assigment by oneself.
	{
		Erase();
		ChainNode<T>* pOldNode;
		ChainNode<T>* pNewNode;
		ChainNode<T>* pCurrent=c.first;
		if(c.first!=NULL)
		{
			pOldNode=new ChainNode<T>;
			first=pOldNode;   //first
			pOldNode->data=pCurrent->data;
			pOldNode->link=NULL;
			pCurrent=pCurrent->link;
			for(; pCurrent!=NULL; pCurrent=pCurrent->link)
			{
				pNewNode=new ChainNode<T>;
				pNewNode->data=pCurrent->data;
				pNewNode->link=NULL;
				pOldNode->link=pNewNode;
				pOldNode=pNewNode;
			}
			last=pOldNode;  //last.
		}
		else
		{
			first=last=NULL;
		}
	}
	return *this;
}




template<class T>
Chain<T>:: ~Chain( )
{// 链表的析构函数，用于删除链表中的所有节点
	ChainNode<T> *next; // 下一个节点
	while (first!=NULL)
	{		
		next = first->link;
		delete first;
		first = next;
	}
	cout<<"delete!"<<endl;
}



template<class T>
int Chain<T>::Length() const
{
	ChainNode<T> *current = first;
	int len = 0;
	while (current!=NULL)
	{
		len++;
		current = current->link;
	}