稀疏矩阵的十字链表.cpp

稀疏矩阵的十字链表算法

//	写一个算法，依次输入三元组表中的元素，建立该稀疏矩阵的十字链表。

#include<iostream.h>

//十字链表结点的类的定义
template<class Type>
class CrossLinkNode
{
	private:
		int row,col;					//元素行，列位置
		CrossLinkNode *down, *right ;	//指向同行或同列的下一个元素
	
	union v_next						//当作为头结点时，值域变成指针域，指向下一个结点		
	{
		Type value ;
		CrossLinkNode *next ;
	};
};

//类的定义
template<class Type>
class CrossLink
{
	private:
		int row,cols;				   //存放总行数，列数
		CrossLinkNode *down, *right ;  //指向同行或同列的下一个元素
	public :
		CrossLink CreatCrossLink();    //产生十字链表，返回总的头结点地址
	union v_next
	{
		Type value ;
		CrossLinkNode *next ;
	};
};

//十字链表的生成函数
template<class Type>
CrossLink<Type> CrossLink<Type> :: CreatCrossLink()
{
	CrossLinkNode *p,*q;		  //辅助指针，存放新建立的结点，并且用于插入
	CrossLinkNode *head[s+1];     //辅助数组，元素是链表的头结点
	int i,j,m,n,t;					
	int v ;
	//输入行，列数
	cin>>m;						
	cin>>n;
	cin>>t;
	
	//产生总的头结点
	CrossLink H = new * CrossLinkNode ;
	H->row = m ;
	H->col = n ;
	head [0] = H ;
	
	//判断其大小
	if (m>n) s=m;
	else s=n;
	
	for (i=0;i<s;i++)
	{
		p=new *CrossLinkNode;			//申请第i个头结点
		p->row = 0;						
		p->right = 0;
		p->right = p->down = p ;
		head[i] = p ;
		head[i-1]->v_next = p ;
	}
	head[s]->v_next.next = H;			//连接头结点，形成循环列表

	for ( k=0 ; k<t; k++ )
	{
		cin>>i;							//输入一个三元组
		cin>>j;			
		cin>>v;
		p = new *CrossLinkNode ;		//生成结点，赋值
		p->row = i;
		p->col = j;
		p->v_next.v = v;
		
		//将其插入第i列
		q = head[i];
		//寻找位置并插入
			while( q->right!=head[i] && ( q->right->col) <j )
				q = q->right ;
		p->right = q->right ; 
		q->right = p ;

		//将其插入第j列
		q = head[i];
		//寻找位置并插入
		while ( q->down!=head[j] && (q->down->row)<i )
			q = q->down ;
		p->down = q ->down;
		q->down = p ;
	}
	//返回总的头结点
	return H;
}