gridmatrix.h

十字链表

template <class Elem> 
class GridMatrix
{
private:
	int row;
	int col;	
	list<HeadNode<Elem>> rowList; //using STL
	list<HeadNode<Elem>> colList;


public:
	GridMatrix(int row,int col)
	{
		this->row=row;
		this->col=col;			
	}


	int getRow()const
	{
		return row;
	}
	int getcol()const
	{
		return col;
	}

	//判断是否越界,插入删除时调用
	bool assert(int r,int c)
	{
		if(r>row||r<0||c>col||c<0)
			return false;
		return true;
	}

template <class Elem>//返回指定位置的值
bool getElement(int row,int col, Elem& item)
{
	if(!assert(row,col))return false;

	list<HeadNode<Elem>>::iterator ltrow;
	list<HeadNode<Elem>>::iterator ltcol;

	//寻找行头节点位置
	for(ltrow=rowList.begin();ltrow!=rowList.end();++ltrow)	
	{
		if(ltrow->index==row)break;	
	}
	if(ltrow==rowList.end()) 
		return false;
	
	//寻找节点位置
	DataNode<Elem>* dNodeRow;
	for(dNodeRow= ltrow->firstNode;dNodeRow->col!=col&&dNodeRow->rightNode!=NULL;dNodeRow=dNodeRow->rightNode);
	if(dNodeRow->col!=col)return false;
	
	item=dNodeRow->element;
	return true;
}



template <class Elem>
bool insertElement(int row,int col,const Elem& item)
{		
	Elem temp;
	
	DataNode<Elem>* fence;//插入位置
	DataNode<Elem>* newNode=new DataNode<Elem>(row,col,item);

	if(!assert(row,col)||getElement(row,col,temp))
		return false;//插入越界或值已存在
	
	list<HeadNode<Elem>>::iterator ltrow;//链头的迭代器
	list<HeadNode<Elem>>::iterator ltcol;
	HeadNode<Elem>a(row);
	HeadNode<Elem>b(col);

    //GridMatrix 为空时
	if(rowList.size()==0) 
		rowList.insert(rowList.begin(),a);
	if(colList.size()==0) 
		colList.insert(colList.begin(),a);

   //维护头链表
	for(ltrow=rowList.begin();(ltrow!=rowList.end ())&&(ltrow->index<row);++ltrow);//讲头指针移动插入位置
	
	if(ltrow==rowList.end ()||ltrow->index!=row) //该行尚不存在
	{	
		HeadNode<Elem> elem(row);
		ltrow=rowList.insert(ltrow,elem);		
	}

	for(ltcol=colList.begin();(ltcol!=colList.end ())&&(ltcol->index<col);++ltcol);

	if(ltcol==colList.end ()||ltcol->index!=col) 
	{	
		HeadNode<Elem> elem(col);
		ltcol=colList.insert(ltcol,elem);	
	}

	//行插入
	if(ltrow->firstNode!=NULL) 	
	{	
		for(fence=ltrow->firstNode;fence->rightNode!=NULL&&fence->col<col;fence=fence->rightNode);
		if(fence->col>col)
		{				
		 if(fence->leftNode !=NULL)//插入位置前后均有元素
		 {	
			 fence=fence->leftNode ;	
			 newNode->leftNode=fence;
			 newNode->rightNode=fence->rightNode;
			 if(fence->rightNode !=NULL)fence->rightNode ->leftNode =newNode;
			 fence->rightNode =newNode;
		 }
		 else//插入位置为头节点
		 {
			newNode->rightNode=ltrow->firstNode;			
			fence->leftNode =newNode;
			ltrow->firstNode=newNode;
		 }
		}
		else//表尾插入
		{			
			newNode->leftNode=fence;
			newNode->rightNode=fence->rightNode;
			if(fence->rightNode !=NULL)fence->rightNode ->leftNode =newNode;
			fence->rightNode =newNode;
		}			
	}
	else //作为第一个节点插入，且表为空
		ltrow->firstNode=newNode;

	//列插入，原理和行插入相同
	if(ltcol->firstNode!=NULL) 	
	{	
		for(fence=ltcol->firstNode;fence->downNode!=NULL&&fence->row<row;fence=fence->downNode);
		if(fence->row>row)
		{				
		 if(fence->upNode !=NULL)
		 {	
			 fence=fence->upNode ;	
			 newNode->upNode=fence;
			 newNode->downNode=fence->downNode;
			 if(fence->downNode !=NULL)fence->downNode ->upNode =newNode;
			 fence->downNode =newNode;
		 }
		 else
		 {
			newNode->downNode=ltcol->firstNode;
			fence->upNode =newNode;
			ltcol->firstNode=newNode;
		 }
		}
		else
		{
			
			newNode->upNode=fence;
			newNode->downNode=fence->downNode;
			if(fence->downNode !=NULL)fence->downNode ->upNode =newNode;
			fence->downNode =newNode;
		}			
	}
	else 
		ltcol->firstNode=newNode;	
	return true;
}


template <class Elem>
bool deleteElement(int row,int col)
{
	Elem temp;//只是为了使用getElement函数，无其他意义

	
	if(!assert(row,col)||!getElement(row,col,temp))return false;

	//指定位置节点不存在
	list<HeadNode<Elem>>::iterator ltrow;
	list<HeadNode<Elem>>::iterator ltcol;
	
	DataNode<Elem>* fence;
	for(ltrow=rowList.begin();(ltrow!=rowList.end ())&&(ltrow->index!=row);++ltrow);
	for(fence=ltrow->firstNode;fence->col!=col;fence=fence->rightNode);
	if(fence==ltrow->firstNode)
	{
		//如果删除节点后行空，删掉链头
		if(fence->rightNode==NULL)
		rowList.erase(ltrow);
		else
		{
			ltrow->firstNode=fence->rightNode;
		}
	}
	else 
	{
		fence->leftNode->rightNode=fence->rightNode;
		if(fence->rightNode!=NULL)
		fence->rightNode->leftNode=fence->leftNode;		
	}

	//列同理
	for(ltcol=colList.begin();(ltcol!=colList.end ())&&(ltcol->index!=col);++ltcol);
	for(fence=ltcol->firstNode;fence->row!=row;fence=fence->downNode);
	if(fence==ltcol->firstNode)
	{
		if(fence->downNode==NULL)
		colList.erase(ltcol);
		else
		{
			ltcol->firstNode=fence->downNode;
		}
	}
	else 
	{
		fence->upNode->downNode=fence->downNode;
		if(fence->downNode!=NULL)
		fence->downNode->upNode=fence->upNode;		
	}
	delete fence;	

	return true;
}















	

template <class Elem>
void  transpose()
{
	list<HeadNode<Elem>> tempList;	
	//交换头链
	tempList= rowList;
	rowList=colList;
	colList=tempList;

	int temp;
	temp = row;
	row = col;
	col = row;
	
	DataNode<Elem>* fence;
	DataNode<Elem>* tmpNode;
	list<HeadNode<Elem>>::iterator ltrow;
	list<HeadNode<Elem>>::iterator ltcol;
	for(ltrow=rowList.begin();ltrow!=rowList.end ();++ltrow)
	for(fence=ltrow->firstNode;fence!=NULL;fence=fence->rightNode)
	{	
			temp=fence->row;	
			fence->row=fence->col;
			fence->col=temp;			
		

			tmpNode=fence->upNode ;
			fence->upNode=fence->leftNode ;
			fence->leftNode=fence->upNode ;					
		}	
		
}
				

template <class Elem>
bool add(Matrix<Elem>& matrix)
{
	
	//行列不分别相等，不可相加
	if(col != matrix.getcol() ||col != this.getcol()||row!= matrix.getRow() ||col != this.getRow())
		return false;
	Elem a,b;

	for(int i=0;i<row;++i)
		for(int j=0;j<col;++j)
		{
			if(!getElement(i,j,a)&&!matrix.getElement(i,j,b)) continue;
			else if(!getElement(i,j,a)&&matrix.getElement(i,j,b))
				this.insertElement(i,j,b);
			else if(getElement(i,j,a)&&!matrix.getElement(i,j,b))
				this.insertElement(i,j,a);
			else if(getElement(i,j,a)&&matrix.getElement(i,j,b))
				this.insertElement(i,j,a+b);//a,b需支持相加
		}	
	return true;
}


template <class Elem>
void GridMatrix<Elem>::print()
{
	Elem  temp;
	for(int i=0;i<row;++i)
	{
		for(int j=0;j<col;++j)
		{
			if(getElement(i,j,temp))
				cout<<temp<<"          ";
			else cout<<0<<"          ";
		}
		cout<<endl;
	}
}




};