数据结构与算法——第5章-数组和广义表-十字链表存储矩阵三元组(5.10.3)

发表于 2023-03-06 分类于开发， N-数据与算法，数据结构与算法阅读时长 ≈ 2 分钟

一概述

1 2	1.通过行标来判断位置 2.实现代码

二通过行标来判断位置

2.1 说明

1
2

由于三元组存储的是该数据元素的行标、列标和数值，所以，通过行标和列标，就能在十字链表中唯一确定一个位置。
判断方法为：在同一行中通过列标来判断位置；在同一列中通过行标来判断位置。

2.2 判断所在行的位置

首先判断该数据元素 A（例如三元组为：（i，j，k））所在行的具体位置：
1.如果 A 的列标 j 值比该行第一个非 0 元素 B 的 j 值小，
说明该数据元素在元素 B 的左侧，这时 A 就成为了该行第一个非 0 元素（也适用于当该行没有非 0 元素的情况，可以一并讨论）

2.如果 A 的列标 j 比该行第一个非 0 元素 B 的 j 值大，说明 A 在 B 的右侧，
这时，就需要遍历该行链表，找到插入位置的前一个结点，进行插入。

2.3 判断所在列的位置

对应行链表的位置确定之后，判断数据元素 A 在对应列的位置：
1. 如果 A 的行标比该列第一个非 0 元素 B 的行标 i 值还小，说明 A 在 B 的上边，这时 A 就成了该列第一个非 0 元素。
（也适用于该列没有非 0 元素的情况）

2. 反之，说明 A 在 B 的下边，这时就需要遍历该列链表，找到要插入位置的上一个数据元素，进行插入

三实现代码

//创建系数矩阵 M,采用十字链表存储表示
CrossList CreateMatrix_OL(CrossList M) {
	int m,n,t;
	int i,j,e;
	OLNode *p,*q;//定义辅助变量
	scanf("%d%d%d",&m,&n,&t); //输入矩阵的行列及非零元的数量
	//初始化矩阵的行列及非零元的数量
	M.mu=m;
	M.nu=n;
	M.tu=t;
	if(!(M.rhead=(OLink*)malloc((m+1)*sizeof(OLink)))||!(M.chead=(OLink*)malloc((n+1)*sizeof(OLink)))) {
		printf("初始化矩阵失败");
		exit(0); //初始化矩阵的行列链表
	}
	for(i=1; i<=m; i++) {
		M.rhead[i]=NULL; //初始化行
	}
	for(j=1; j<=n; j++) {
		M.chead[j]=NULL; //初始化列
	}
	for(scanf("%d%d%d",&i,&j,&e); 0!=i; scanf("%d%d%d",&i,&j,&e)) { //输入三元组 直到行为 0 结束
		if(!(p=(OLNode*)malloc(sizeof(OLNode)))) {
			printf("初始化三元组失败");
			exit(0); //动态生成 p
		}
		p->i=i;
		p->j=j;
		p->e=e; //初始化 p
		if(NULL==M.rhead[i]||M.rhead[i]->j>j) {
			p->right=M.rhead[i];
			M.rhead[i]=p;
		} else {
			for(q=M.rhead[i]; (q->right)&&q->right->j<j; q=q->right);
			p->right=q->right;
			q->right=p;
		}
		if(NULL==M.chead[j]||M.chead[j]->i>i) {
			p->down=M.chead[j];
			M.chead[j]=p;
		} else {
			for (q=M.chead[j]; (q->down)&& q->down->i<i; q=q->down);
			p->down=q->down;
			q->down=p;
		}
	}
	return M;
}

四参考

C语言中文网—十字链表实现矩阵加法

0%