dzqlist.cpp

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

	return len;
}



template<class T>
bool Chain<T>::Find(int k, T& x) const
{	// 寻找链表中的第k个元素，并将其传送至x
	//如果不存在第k个元素，则返回f a l s e，否则返回t r u e
	if (k<1) 
		return false;
	ChainNode<T> *current = first;
	int index = 1; // current的索引
	while (index < k && current!=NULL)
	{
		current = current->link;
		index++;
	}
	if (current!=NULL) 
	{
		x = current->data; 
		return true;
	}
	return false; // 不存在第k个元素
}




template<class T>
int Chain<T>::Search(const T& x) const
{	// 寻找x，如果发现x，则返回x的地址
	//如果x不在链表中，则返回0
	ChainNode<T> *current = first;
	int index = 1; // current的索引
	while (current!=NULL && current->data != x)
	{
		current = current->link;
		index++;
	}
	if (current!=NULL) return index;
	return 0;
}








template<class T>
void Chain<T>::Output(ostream& out) const
{	// 将链表元素送至输出流
	ChainNode<T> *current;
	for (current = first; current!=NULL; current = current->link)
		out << current->data << " ";
}



template <class T>
ostream& operator<<(ostream& out, const Chain<T>& x)
{
	x.Output(out);
	return out;
}



template<class T>
Chain<T>& Chain<T>::Delete(int k, T& x)
{	// 把第k个元素取至x，然后从链表中删除第k个元素
	//如果不存在第k个元素，则引发异常OutOfBounds
	if (k < 1 || NULL==first)
		throw OutOfBounds(); // 不存在第k个元素
	// p最终将指向第k个节点
	ChainNode<T> *p = first;
	// 将p移动至第k个元素，并从链表中删除该元素
	if (k == 1) // p已经指向第k个元素
	{
		if(first==last) // and only one Node.
		{
			first = first->link; // 删除之
			last=first;
		}
		else
		{
			first = first->link; // 删除之
		}
	}
	else
	{ // 用q指向第k - 1个元素
		ChainNode<T> *q = first;
		for (int index = 1; index < k - 1 && q!=NULL; index++)
			q= q->link;
		if (NULL==q || (q->link)==NULL)	
			throw OutOfBounds(); //不存在第k个元素
		p = q->link; // 存在第k个元素
		if(p==last)
			last=q;
		q->link = p->link;
	} // 从链表中删除该元素
	//保存第k个元素并释放节点p
	x= p->data;
	delete p;
	return *this;
}




template<class T>
Chain<T>& Chain<T>::Insert(int k, const T& x)
{	// 在第k个元素之后插入x
	//如果不存在第k个元素，则引发异常O u t O f B o u n d s
	// 如果没有足够的空间，则传递N o M e m异常
	if (k < 0) throw OutOfBounds();
	// p最终将指向第k个节点
	ChainNode<T> *p = first;
	//将p移动至第k个元素
	for (int index = 1; index < k && p!=NULL; index++)
		p = p->link;
	if (k > 0 && p==NULL) throw OutOfBounds(); //不存在第k个元素
	// 插入
	ChainNode<T> *y=new ChainNode<T>;
	y->data = x;
	if (k!=0) 
	{// 在p之后插入
		y->link = p->link;
		p->link = y;
	}
	else
	{// 作为第一个元素插入
		y->link = first;
		first = y;
		if(NULL==last) //original list null.
		{
			last=first;
		}
	}

	if(y->link==NULL) last=y;
	return *this;
}



template<class T>
void Chain<T>::Erase()
{ //删除链表中的所有节点
	ChainNode<T> *next;
	while (first!=NULL)
	{
		next = first->link;
		delete first;
		first = next;
	}
	last=NULL;
}



template <class T>
Chain<T>& Chain<T>::Append(const T& x)
{
	ChainNode<T> *temp=new ChainNode<T>;
	temp->data=x;
	temp->link=NULL;

	if(first!=NULL )
	{
		last->link=temp;
		last=temp;		
	}
	else
	{
		first=temp;
		last=first;
	}
	return *this;
}


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






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

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





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

	
	dest.first=src.first;
	dest.last=src.first;  //no error!!!

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

template<class T>
Chain<T>& Chain<T>::Emerge(Chain<T>& dest,Chain<T>& srcA,Chain<T>& srcB)
{
	//Chain A and B are sorted.Merge A and B to dest.
	//Chain A and B are empty after merged.
	//the dest is sorted via ascending.
	ChainNode<T>* pScanA=srcA.first;
	ChainNode<T>* pScanB=srcB.first;
	ChainNode<T>* pScanDest=NULL;
	
	dest.Erase();
	if(pScanA==NULL && pScanB==NULL) //both A and B are NULL.
	{
		return dest;
	}

	if(pScanA==NULL)                //only A null.
	{
		dest.first=srcB.first;
		dest.last=srcB.last;
		srcB.first=srcB.last=NULL;
		return dest;
	}

	if(pScanB==NULL)               //only B null.  
	{
		dest.first=srcA.first;
		dest.last=srcA.last;
		srcA.first=srcA.last=NULL;
		return dest;
	}

	if( (srcA.first->data) > (srcA.last->data) )  //make sure srcA ascending sort.
	{
		srcA.Reverse(srcA);
		pScanA=srcA.first;   //must reassignment.
	}
	if( (srcB.first->data) > (srcB.last->data) ) //make sure srcB ascending sort.
	{
		srcB.Reverse(srcB);
		pScanB=srcB.first;  //must reassignment.
	}

	if( (srcA.last)->data <= (srcB.first)->data )  //direct link(A->B)
	{
		dest.first=srcA.first;
		(srcA.last)->link=srcB.first;
		dest.last=srcB.last;
		srcA.first=srcA.last=NULL;
		srcB.first=srcB.last=NULL;
		return dest;
	}
	
	if( (srcB.last)->data <= (srcA.first)->data ) //direct link(B->A)
	{
		dest.first=srcB.first;
		(srcB.last)->link=srcA.first;
		dest.last=srcA.last;
		srcA.first=srcA.last=NULL;
		srcB.first=srcB.last=NULL;
		return dest;
	}


	 //Initial dest.
	if(pScanA->data <=pScanB->data)
	{
		pScanDest=pScanA;
		pScanA=pScanA->link;
	}
	else
	{
		pScanDest=pScanB;
		pScanB=pScanA->link;
	}	
	dest.first=pScanDest;
	while(pScanA!=NULL && pScanB!=NULL) //normal state.
	{
		if(pScanA->data <= pScanB->data)
		{
			pScanDest->link=pScanA;
			pScanDest=pScanA;
			pScanA=pScanA->link;
		}
		else
		{
			pScanDest->link=pScanB;
			pScanDest=pScanB;
			pScanB=pScanB->link;
		}
		
			
	}
	if(pScanA==NULL)
	{
		pScanDest->link=pScanB;
		dest.last=srcB.last;
	}
	else
	{
		pScanDest->link=pScanA;
		dest.last=srcA.last;
	}
	srcA.first=srcA.last=NULL;
	srcB.first=srcB.last=NULL;
	return dest;
}




template<class T>
void Chain<T>::Split(Chain<T>& destA, Chain<T>& destB, Chain<T>& srcC)
{
	ChainNode<T> *pA=NULL;
	ChainNode<T> *pB=NULL;
	ChainNode<T> *pScan=NULL;
	destA.Erase();
	destB.Erase();
	if(srcC.first==NULL)  //srcC empty.
		return;
	if(srcC.first==srcC.last) //srcC only one node.
	{
		destA.first=srcC.first;
		destA.last=srcC.first;
		srcC.first=srcC.last=NULL;
		return;
	}

	//equal or more than two nodes.
	pA=srcC.first;  //Initial.
	destA.first=pA;
	pB=(srcC.first)->link;
	destB.first=pB;	
	pScan=pB->link;
	bool LinkToA=true;
	while(pScan!=NULL)
	{
		if(LinkToA)      //select to A
		{
			pA->link=pScan;
			pA=pScan;
			pScan=pScan->link;
		}
		else
		{				//select to B
			pB->link=pScan;
			pB=pScan;
			pScan=pScan->link;
		}
		LinkToA=!LinkToA;
	}
	pA->link=NULL;
	pB->link=NULL;
	destA.last=pA;
	destB.last=pB;
	srcC.first=srcC.last=NULL;
}
//Chain over...........................................................................







//Chain iterator.......................................................................
template<class T>
class ChainIterator
{
	public:
		T* Initialize(const Chain<T>& c)
		{
			pLocation = c.first;
			if (pLocation!=NULL)
				return pLocation->data;
			return 0;
		}


		T* Next()
		{
			if (pLocation==NULL) 
				return 0;
			pLocation = pLocation->link;
			if (pLocation!=NULL)
				return pLocation->data;
			return 0;
		}

	private:
		ChainNode<T> *plocation;
};
//Chain iterator over.......................................................................




void OutOfBounds()
{
	cout<<"OutOfBounds!"<<endl;
	exit(0);
}


template <class T>
ostream& operator<<(ostream& out,const SigLinkedCirList<T>& c)
{
	 c.Output(out);
	 return out;
}