考研数据结构之数组(5.3)——使用三元组法表示稀疏矩阵(C表示)
  xaeiTka4h8LY 2024年05月31日 38 0

使用三元组表示法来表示稀疏矩阵。

三元组数据结构是一个长度为n,表内每个元素都有3个分量的线性表,其3个分量分别为行下标和列下标。元素结构体定义如下:

/* 三元组的结构体 */
typedef struct {
	int val;// 稀疏矩阵中非零元素的值
	int i;// 稀疏矩阵中非零元素的行下标
	int j;// 稀疏矩阵中非零元素的列下标
} Trimat;

在程序中如果要定义一个含有maxterms个非零元素的稀疏矩阵,则只需写成如下代码:

Trimat trimat[maxterms+1];// maxterms是已经定义的常量

语句trimat[k].val表示取第k个非零元素的值;trimat[k].i和trimat[k].j表示取第k个非零元素在矩阵中的行下标和列下标。

下面用一个例子:给定一个稀疏矩阵A(float型),其尺寸为mxn,建立其对应的三元组存储,并通过三元组打印输出矩阵A。

具体实现代码如下:

#include<stdio.h>

#define maxterms 20
#define maxSize 20

/* 三元组的结构体 */
typedef struct {
	int val;// 稀疏矩阵中非零元素的值
	int i;// 稀疏矩阵中非零元素的行下标
	int j;// 稀疏矩阵中非零元素的列下标
} Trimat;

/* 根据稀疏矩阵建立三元组 */
/* A[][maxSize]指的是一个稀疏矩阵;m指的是稀疏矩阵的行数;n指的是稀疏矩阵的列数;trimat[maxterms+1]指的是三元组 */
void createTrimat(float A[][maxSize],int m,int n,Trimat trimat[maxterms+1]) {
	int k=1;// 计数器,记录结构体trimat数组的下标
	for(int i=0; i<m; i++) {
		for(int j=0; j<n; j++) { // 双层循环,遍历稀疏矩阵中的每个元素
			if(A[i][j]!=0) { // 判断稀疏矩阵中的非零元素
				trimat[k].val=A[i][j];// 保存非零元素的值
				trimat[k].i=i;// 保存非零元素的行下标
				trimat[k].j=j;// 保存非零元素的列下标
				k++;// 加1
			}
		}
	}
	/* 保存三元组的一些基本信息 */
	trimat[0].val=k-1;// 存放的数稀疏矩阵中非零元素的个数
	trimat[0].i=m;// 保存的是矩阵行数
	trimat[0].j=n;// 保存的是矩阵列数
}

/* 根据三元组打印出原来的稀疏矩阵 */
/* trimat[maxterms+1]指的是三元组 */
void printTrimat(Trimat trimat[maxterms+1]) {
	int m=trimat[0].i;// 稀疏矩阵的行数
	int n=trimat[0].j;// 稀疏矩阵的列数
	int k=1;// 三元组数组的下标,初始为1,因为trimat[0]保存的是三元组的一些基本信息
	for(int i=0; i<m; i++) {
		for(int j=0; j<n; j++) { // 双层循环遍历稀疏矩阵
			if(i==trimat[k].i&&j==trimat[k].j) { // 如果i和j能够匹配三元组的下标trimat[k].i和trimat[k].j
				printf("%d\t",trimat[k].val);// 如果能够配对则输出三元组的非零元素的值
				k++;// 继续遍历三元组的元素
			} else {
				printf("0\t");// 如果没有匹配则代表该处位置是0
			}
		}
		printf("\n");// 换行
	}
}

int main() {
	// 稀疏矩阵
	float A[][maxSize]= {
		{0,0,0,1},
		{0,0,3,2},
		{1,0,0,0},
		{0,2,0,0},
		{1,0,0,0}
	};
	Trimat trimat[maxSize];// 定义一个三元组
	createTrimat(A,5,4,trimat);// 调用函数创建三元组
	printTrimat(trimat);// 根据三元组打印稀疏矩阵
	return 0;
}

控制台打印结果如下:

考研数据结构之数组(5.3)——使用三元组法表示稀疏矩阵(C表示)

为了简便起见,可以不使用上述结构体定义的方法来定义三元组,直接申请一个二维数组即可。

如:

int trimat[maxterms+1][3];

trimat[k][0]表示原矩阵中的元素按行优先排序的第k个非零元素的值;trimat[k][1]、trimat[k][2]表示第k个非零元素在矩阵中的位置。可以看出此时trimat就是一个maxterms行3列的二维数组。规定第0行的三个元素分别来存储非零元素的个数、行数和列数。例如:trimat[0][0]为原矩阵中的非零元素个数,trimat[0][1]和trimat[0][2]为矩阵行数和列数。

所以实现代码如下:

#include<stdio.h>

#define maxterms 20
#define maxSize 20

/* 通过稀疏矩阵来建立三元组B */
/* A[][maxSize]指的是稀疏矩阵;m指的是稀疏矩阵的行数;n指的是稀疏矩阵的列数;B[][3]指的是三元组 */
void createtrimat(float A[][maxSize],int m,int n,float B[][3]) {
	int k=1;// 三元组的行下标,初始为1,因为0要存储稀疏矩阵的基本信息
	for(int i=0; i<m; i++) {
		for(int j=0; j<n; j++) {// 循环遍历稀疏矩阵的所有元素
			if(A[i][j]!=0) {// 判断稀疏矩阵中的非零元素,如果是非零元素
				B[k][0]=A[i][j];// 将非零元素保存在B[k][0]
				B[k][1]=i;// 将非零元素的行下标保存在B[k][1]
				B[k][2]=j;// 将非零元素的列下标保存在B[k][2]
				k++;
			}
		}
	}
	/* 保存稀疏矩阵的基本信息 */
	B[0][0]=k-1;// 专门用B[0][0]来保存稀疏矩阵中非零元素的个数
	B[0][1]=m;// 专门用B[0][1]来保存稀疏矩阵的行数
	B[0][2]=n;// 专门用B[0][2]来保存稀疏矩阵的列数

}

/* 通过三元组打印稀疏矩阵A */
/* B[][3]指的是三元组 */
void print(float B[][3]) {
	int k=1;// 计数器,记录三元组行下标的位置,从1开始,0表示的是稀疏矩阵的基本信息
	for(int i=0; i<B[0][1]; i++) {
		for(int j=0; j<B[0][2]; j++) {// 循环遍历稀疏矩阵的行和列
			if(i==(int)B[k][1]&&j==(int)B[k][2]) {// 判断i和j是否与三元组中的行下标和列下标是否配对
				printf("%1.f\t",B[k][0]);// 如果配对则输出稀疏矩阵的非零元素
				k++;// 计数器加1,下一行
			} else {// 如果不能配对,则是零元素
				printf("0\t");// 输出零即可
			}
		}
		printf("\n");// 换行
	}
}

int main() {
	// 稀疏矩阵
	float A[][maxSize]= {
		{0,0,0,1},
		{0,0,3,2},
		{1,0,0,0},
		{0,2,0,0},
		{1,0,0,0}
	};
	float trimat[maxterms][3];// 定义一个三元组
	createtrimat(A,5,4,trimat);// 调用函数创建三元组
	print(trimat);// 根据三元组打印稀疏矩阵
	return 0;
}

结果一样

考研数据结构之数组(5.3)——使用三元组法表示稀疏矩阵(C表示)

【版权声明】本文内容来自摩杜云社区用户原创、第三方投稿、转载,内容版权归原作者所有。本网站的目的在于传递更多信息,不拥有版权,亦不承担相应法律责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@moduyun.com

  1. 分享:
最后一次编辑于 2024年05月31日 0

暂无评论

推荐阅读
  xaeiTka4h8LY   2024年04月26日   47   0   0 split数组字符串
xaeiTka4h8LY