矩阵压缩存储(对称,三角,对角,稀疏)

想写好代码的小猫头 2023-04-12 原文

1.对称矩阵

（1）下三角矩阵

利用一维数组进行储存（下面的图片参考懒猫老师《数据结构》相关课程的笔记~）

每个元素在一维数组中的存储序号=阴影部分的面积

第i行第j列的元素序号=1+2+3+4...+(i-1)+j（等差数列求和公式化，下标从0开始减1）

即 aij=i*(i-1)/2+j-1（i>=j）

（2）上三角矩阵

因为上三角矩阵其实就是将下三角矩阵的i,j进行调换得到的，同理，上三角矩阵的元素在数组中的表示可以类比：

即 aij=j*(j-1)/2+i-1（i<j）

对于这两种矩阵，如果对角线的另一侧不是0，而是一个常数定值，则表达方式是，在这个一维数组的末尾添加这个常数的值：（如图）

（3）全矩阵

通过（1）+（2），找规律可以表示在矩阵中的任意一个元素为：

2.对角矩阵

对角矩阵：所有非零元素都集中在以主对角线为中心的带状区域中，除了主对角线和它的上下方若干条对角线的元素外，所有其他元素都为零。

元素aij在一维数组中的序号

=2+3（i-2）+(j-i+2)

=2i+j-2(以零下标开始减去1)

=2i+j-3

3.稀疏矩阵

稀疏矩阵中的非零元素的分布没有规律，稀疏矩阵中包括0和非零元素，没有规律的分布

（1）顺序储存

定义三元组：（只储存非零元素的信息）

typedef struct Triple {
	int row, col; //行号，列号
	DataType item;//非零元素
} Triple;

其顺序结构储存示意图如下：

定义矩阵性质：

typedef struct Matrix {
	int num;//非零元素的个数
	int mu;//矩阵的行数
	int nm;//矩阵的列数
} Matrix;

（下面的代码实现了对一个三元组的增查，打印的等功能，后面有相应的测试用例）

完整代码：（分为功能实现包--稀疏矩阵（顺序）.h和测试功能包--稀疏矩阵测试.c）

（1）稀疏矩阵（顺序）.h

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 100
typedef int DataType;

typedef struct Triple {
	int row, col; //行号，列号
	DataType item;//非零元素
} Triple;

typedef struct Matrix {
	int num;//非零元素的个数
	int mu;//矩阵的行数
	int nm;//矩阵的列数
} Matrix;

void TripleMatrix(Triple *data) { //初始化
	for (int i = 0; i < MAX; i++) {
		data[i].row = -1;
		data[i].col = -1;
	}
}

void printTriple(Triple *data) { //打印三元组
	int i = 0;
	printf("生成的三元组为：（行，列，非零元素）\n");
	while (data[i].row != -1) {
		printf("(%d，%d，%d)\n", data[i].row, data[i].col, data[i].item);
		i++;
	}
}

void printfMatrix(Triple *data, Matrix *datasum) { //打印矩阵
	printf("矩阵为：\n");
	int matirx[datasum->mu][datasum->nm];
	for (int i = 0; i < datasum->mu; i++) { //先将矩阵初始化为全0阵
		for (int j = 0; j < datasum->nm; j++) {
			matirx[i][j] = 0;
		}
	}
	for (int k = 0; k < datasum->num; k++) { //将稀疏矩阵中的值赋进去
		matirx[data[k].row - 1][data[k].col  - 1] = data[k].item; //行列值记得减1
	}
	for (int i = 0; i < datasum->mu; i++) { //打印
		for (int j = 0; j < datasum->nm; j++) {
			if (j == datasum->nm - 1)
				printf("%-5d\n", matirx[i][j]);
			else
				printf("%-5d ", matirx[i][j]);
		}
	}
}

void setItem(Triple *data, int row, int col, DataType item) { //添加元素
	Triple *str = data;
	Triple temp, temp1;
	int flag = 1; //控制两种储存交替进行
	int type = 0; //控制最后一个插入的是新元素还是原来存在temp和temp1中的元素
	while (str->row != -1 || str->col != -1) {
		if (str->row > row || (str->row == row && str->col > col)) { //插在前面
			temp = *str;
			str->row = row;
			str->col = col;
			str->item = item;
			str++;
			while (str->row != -1) {
				if (flag == 1) {
					temp1 = *str;
					*str = temp; //temp准备存储下一个
					str++;
					flag = 2;
				} else if (flag == 2) {
					temp = *str;
					*str = temp1; //temp1准备存储下一个
					str++;
					flag = 1;
				}
			}
			if (flag == 1) //最后一个元素在temp中
				type = 1;
			else if (flag == 2) //最后一个元素在temp1中
				type = 2;
		} else if (str->row < row || str->row == row) {
			str++;
		}
	}
	//前面都没有添加进去，就添加到末尾
	//或者存入temp或temp1中的需要在最后添加进去
	if (type == 0) {
		str->col = col;
		str->row = row;
		str->item = item;
	} else if (type == 1) {
		*str = temp;
	} else if (type == 2) {
		*str = temp1;
	}
}

DataType getItem(Triple *data, int row, int col, Matrix *datasum) { //根据行号列号获取矩阵元素
	if (row > datasum->mu || col > datasum->nm)
		printf("该坐标不在矩阵内！\n");
	for (int i = 0; i < datasum->num; i++) {
		if (data[i].row == row && data[i].col == col)
			return data[i].item;
	}
	return 0;
}

（2）稀疏矩阵测试.c

#include "稀疏矩阵（顺序）.h"

main() {
	Triple data[MAX];
	TripleMatrix(data);
	Matrix datasum;
	int row, col;
	DataType item;
	printf("请输入矩阵初始的行，列和非零元个数：");
	scanf("%d %d %d", &datasum.mu, &datasum.nm, &datasum.num);
	for (int i = 0; i < datasum.num; i++) { //乱序的，不用从大到小
		printf("请依次输入行，列和非零元：");
		scanf("%d %d %d", &row, &col, &item);
		setItem(data, row, col, item);
	}
	printTriple(data);
	printfMatrix(data, &datasum);
	printf("请输入想查询的矩阵元素坐标：");
	int a, b, index;
	scanf("%d %d", &a, &b);
	index = getItem(data, a, b, &datasum);
	printf("该元素的值为：%d", index);
}

（3）测试输出

（2）十字链表