crosslist.cpp

数据结构中关于十字链表的实现

//////////////////////////////
//十字链表类的实现
//////////////////////////////

#include <iostream.h>
#include <stdlib.h>
#include "CrossList.h"

//十字链表构造函数--------------------------------------------------
CrossList::CrossList()
{
	m_rowNum=m_colNum=m_Count=0;
	m_colHead=NULL;
	m_rowHead=NULL;
}
CrossList::~CrossList()
{
	Destroy();
}
//销毁链表----------------------------------------------------------
void CrossList::Destroy()
{
	int num=0;
	OLNode *temp=NULL;
	for(int i=0;i<m_rowNum;i++)
	{
		for(OLNode *pG=m_rowHead[i];pG;)
		{
			temp=pG;
		    pG=pG->right;
		    delete temp;
			num++;
		}
	}
	delete []m_rowHead;
	delete []m_colHead;
	cout<<"析构了"<<num<<"个元素"<<endl;
}
//创建十字链表------------------------------------------------------
void CrossList::CreateCrossList(const int rowNum,const int colNum,int array[][100])
{
	if((m_rowHead=new OLNode*[rowNum])==NULL) exit(1);
    if((m_colHead=new OLNode*[colNum])==NULL) exit(1);
	m_rowNum=rowNum; m_colNum=colNum;
//初始化行列矢量指针为空
    OLink *t=m_rowHead;
	for(int i=0;i<rowNum;i++)
	{
		(*t)=NULL;
		t++;
	}
	t=m_colHead;
	for(int j=0;j<colNum;j++)
	{
		(*t)=NULL;
		t++;
	}
//添加非零元素------------------------------------------------------
	for(int row=0;row<rowNum;row++)
	{
		for(int col=0;col<colNum;col++)
		{
			if(array[row][col]!=0)
			{
				AddNode(row,col,array[row][col]);
			}
		}
	}
}
//添加十字链表结点--------------------------------------------------
void CrossList::AddNode(const int rowIndex,const int colIndex,const int data)
{
	OLNode *insertP;
	if((insertP=new OLNode)==NULL) exit(1);
	else if(data!=0)//非零元素，添加到链表中
	{
		insertP->row=rowIndex;
		insertP->column=colIndex;
		insertP->data=data;
		insertP->down=NULL;
		insertP->right=NULL;
		m_Count++;

	//如果行指针为空，插入，否则遍历行，插入
	if(m_rowHead[rowIndex]==NULL)
		m_rowHead[rowIndex]=insertP;
	else
	{
		for(OLNode *pG=m_rowHead[rowIndex];pG->right!=NULL;pG=pG->right){}
		pG->right=insertP;
	}//完成行插入
	if(m_colHead[colIndex]==NULL)
		m_colHead[colIndex]=insertP;
	else
	{
		for(OLNode *ptG=m_colHead[colIndex];ptG->down!=NULL;ptG=ptG->down){}
		ptG->down=insertP;
	}//完成列插入
/*cout<<"m_rowHead["<<rowIndex<<"]->row:  "<<m_rowHead[rowIndex]->row<<endl;
cout<<"m_rowHead["<<rowIndex<<"]->column:  "<<m_rowHead[rowIndex]->column<<endl;
cout<<"m_rowHead["<<rowIndex<<"]->data:  "<<m_rowHead[rowIndex]->data<<endl<<endl;
cout<<endl<<"m_colHead["<<colIndex<<"]->row:  "<<m_colHead[colIndex]->row<<endl;
cout<<"m_colHead["<<colIndex<<"]->column:  "<<m_colHead[colIndex]->column<<endl;
cout<<"m_colHead["<<colIndex<<"]->data:  "<<m_colHead[colIndex]->data<<endl;
cout<<"----------------------------------------------------------"<<endl;*/
	}
	else//零元素
		return;
}
//----------------------------------------------------------------------
OLNode* CrossList::GetOLNode(const int rowIndex,const int colIndex)
{
	OLNode *t=NULL;
	for(OLNode *pRow=m_rowHead[rowIndex];pRow;pRow=pRow->right)
	{
		if(pRow->column==colIndex)
		{
			return t=pRow;
		}
	}
	cout<<"链表中没有该结点元素!"<<endl;
	exit(1);
}
void CrossList::InsertNode(int rowIndex,int colIndex,int value)
{
	OLNode *insertP=new OLNode;
	insertP->data=value;
	insertP->row=rowIndex;
	insertP->column=colIndex;
    insertP->right=insertP->down=NULL;
//插入到行中
	OLNode *pG=NULL;
	if(m_rowHead[rowIndex]==NULL)//插入为空表时
	{
		m_rowHead[rowIndex]=insertP;		
	    m_rowHead[rowIndex]->right=NULL;
		m_Count++;
		goto INSERTCOL;
	}
	if(colIndex<m_rowHead[rowIndex]->column)//在链首插入
	{
		insertP->right=m_rowHead[rowIndex];
		m_rowHead[rowIndex]=insertP;
		m_Count++;
		goto INSERTCOL;
	}
	for(pG=m_rowHead[rowIndex];pG->right;pG=pG->right)//在链中
	{
			if(pG->column<colIndex&&colIndex<pG->right->column)
			{
				insertP->right=pG->right;
				pG->right=insertP;
				goto INSERTCOL;
			}
	}
	pG=m_rowHead[rowIndex];//在链尾
	while(pG->right)
		pG=pG->right;
	pG->right=insertP;
	m_Count++;
//插入到列中
INSERTCOL:
	if(m_colHead[colIndex]==NULL)//插入为空表时
	{
		m_colHead[colIndex]=insertP;		
	    m_colHead[colIndex]->down=NULL;
		return;
	}
	if(rowIndex<m_colHead[colIndex]->row)//在链首插入
	{
		insertP->down=m_colHead[colIndex];
		m_colHead[colIndex]=insertP;
		return;
	}

	for(pG=m_colHead[colIndex];pG->down;pG=pG->down)//在链中
	{
			if(pG->row<rowIndex&&rowIndex<pG->down->row)
			{
				insertP->down=pG->down;
				pG->down=insertP;
				return;
			}
	}
	pG=m_colHead[colIndex];//在链尾
	while(pG->down)
		pG=pG->down;
	pG->down=insertP;
}
//打印链表中元素--------------------------------------------------------
void CrossList::Print()
{
	for(int i=0;i<m_rowNum;i++)
	{
		for(OLNode *pG=m_rowHead[i];pG;pG=pG->right)
			cout<<"("<<pG->row<<","<<pG->column<<") :"
			<<pG->data<<"   ";   
		cout<<endl;
	}
/*	for(int i=0;i<m_colNum;i++)
	{
		for(OLNode *pG=m_colHead[i];pG;pG=pG->down)
			cout<<"("<<pG->row<<","<<pG->column<<") :"
			<<pG->data<<"   ";   
		cout<<endl;
	}
	*/
}