(15)稀疏矩阵的压缩-十字链表

2/22/2017来源:ASP.NET技巧人气:1939

  利用三元组表表示稀疏矩阵时,若矩阵的运算使非零元素的个数发生变化,就必须对三元组表进行插入、删除,也就是说必须移动三元组表中的元素,由于三元组表是顺序存储结构,所以这些操作将花费大量的时间,十字链表可以克服三元组表的上述缺点。

  在十字链表中,数组的每一行的非零元素结点构成一个带头结点的循环链表,每一列的非零元素结点也构成一个带头结点的循环链表,这种组织方法使同一非零元素结点既处在某一行的链表中,又处在某一列的链表中。因此非零元素结点中设有两个指针域:指针域down指向其同列的下一个非零元素的结点,right域指向其同行的下一个非零元素结点。除这两个域外,结点中还应设有存放该非零元素的行值、列值、元素值的域,设他们分别为row、col和e。十字链表中非零元素结点的结构如下所示:

                 

   为了使整个链表中的结点结构一致,我们规定行(列)循环链表的表头结点和表中非零元素的结点一样,也设5个域,并且均置表头结点的行域和列域为零。

   由于行表头结点不使用down域,而列表头结点不使用right域,因此,第i行的行表头结点和第i列的列表头结点可以合用一个结点,称为行列表头结点。

   由于行表头结点的数据域没有意义的,而且我们希望将行列表头结点组织在一个循环链表中,因此,使用C语言中共用体的概念,将这个域作为指针域,将各行列表头链接起来。

   我门为整个十字链表再设一个总表头结点,其row域和col域的值分别是稀疏矩阵的行数和列数,行列指针无意义,用指针域(非零元素结点的元素值域,行列表头结点相链的指针域)指向第一个列表头结点。设head为指向总表头结点的指针,因此,只要给定head指针值,便可取得稀疏矩阵的全部信息了。

               

十字链表的结构类型说明:

typedef  int ElemType;
typedef struct OLNode{
	int row, col;
	union 
	{
		struct OLNode *next;	//表头结点使用next域
		ElemType e;				//表中元素结点使用e域
	}uval;
	struct OLNode *down, *right;
}OLNode,*OLink;建立十字链表的算法分为两步:

(1)建立表头结点的循环链表。读入矩阵的行数、列数和非零元素的个数。因为行、列链表共享同一组表头结点,所以表头结点的个数应是行数、列数中的较大者。建立整个十字链表的头结点*head以及所有行、列链表的头结点,将头结点通过next域链接成循环链表。初始时每一行、列链表都是空的循环链表。

(2)依次读入非零元素的三元组表(row,col,e),生成一个结点*p,然后将其插入到第row行的行链表的正确位置上,以及第col列的列链表的正确位置上。*p的正确位置应为:在行链表上,首先查找到第row行的头结点,然后沿着结点的right域找到第一个列号大于col的结点*(q->right),而*(q->right)即为*p及结点的后继,*q即为*p结点的前驱,*p应插入到*q结点之后。如果行链表上所有结点的列号均小于col,则*p应插入到行链表的表尾。查找第col列的列链表的正确插入位置与此类似。

完整代码如下:

#include<iostream>
using namespace std;
#define  max    100
typedef  int ElemType;
typedef struct OLNode{
	int row, col;
	union 
	{
		struct OLNode *next;	//表头结点使用next域
		ElemType e;				//表中元素结点使用e域
	}uval;
	struct OLNode *down, *right;
}OLNode,*OLink;
OLink CreateCrossList() {		//建立十字链表
	int m, n, t,row,col,e, maxmn;
	OLink h[max],p,q;
	cout << "请输入行数、列数以及非零元素的个数" << endl;
	cin >> m >> n >> t;
	if (m > n) maxmn = m;
	else maxmn = n;
	OLink head = (OLNode*)malloc(sizeof(OLNode));
	head->row = m;
	head->col = n;
	h[maxmn] = head;		//h[maxmn+1]为一组指示行列表头结点的指针
	for (int i = 0; i < maxmn;i++) {	//建立表头结点的循环链表	
	    p= (OLNode*)malloc(sizeof(OLNode));
		p->row = 0; p->col = 0;
		p->down = p; p->right = p;
		h[i] = p;
		if (i == 0) head->uval.next = p;
		else h[i - 1]->uval.next = p;
	}
	p->uval.next = head;		//最后一个结点指向表头结点*head
	for (int num = 1; num <= t;num++) {
		cout << "请输入一个非零元素的三元组" << endl;
		cin >> row >> col >> e;
		p= (OLNode*)malloc(sizeof(OLNode));  //生成结点
		p->row = row;
		p->col = col;
		p->uval.e = e;
		q = h[row];
		while (q->right!=h[row] && q->right->col<col) {	//查*p在第row行的插入位置
			q = q->right;
		}
		p->right = q->right; q->right = p;  //将*p插入到第row行的循环链表中
		q = h[col];
		while (q->down != h[col] && q->down->row < row) {//查*p在第col列的插入位置

			q = q->down;
		}
		p->down = q->down; q->down = p;  //将*p插入到第col列的循环链表中
	}
	return head;
}
void PRint(OLink head) {
	OLink p = head->uval.next;
	int m = 0,n = 0;
	while (m != head->row) {
		p = p->right;
		while (n != head->col) {
			if (m == p->row && n == p->col && p->uval.e!=NULL) {
				cout << p->uval.e << " ";
				p = p->right;
			}
			else {
				cout << "0 ";
			}
			n++;
		}
		n = 0;
		m++;
		p = p->uval.next;
		cout << endl;
	}
}
void main() {
	OLink list;
	list = CreateCrossList();
	cout << "链表内容为:" << endl;
	print(list);
	system("pause");
}