矩阵的压缩存储

一、矩阵的分类

1、特殊矩阵：其矩阵值在在矩阵中分布有规律 2、稀疏矩阵：矩阵的非零值在矩阵中占比小于0.05的矩阵，即零值占比在95%以上 3、一般矩阵：不属于上面的两种矩阵

二、矩阵的存储方式

1、特殊矩阵的存储方式

1、特殊矩阵包括三角矩阵，带状矩阵 都是使用顺序存储

2、稀疏矩阵的存储方式

稀疏矩阵的存储方式有两种，其一：三元组顺序表（顺序存储）其二：十字链表（链式存储）

1、稀疏矩阵的三元组顺序表存储

3矩阵的转置

1、一般矩阵转置

2、 稀疏矩阵的一般转置

3、稀疏矩阵的快速排序

假如我们直接知道转置前的三元组数组的每个元素在转置后的三元组数组中位置，我们就可以直接转了 要想知道转置后的位置，我们必须要总结转置前的三元组数组的更详细信息。 由于转置后行列互换，所以转置后的三元组数组是按照行顺序记录的，所以我们要知道转置前矩阵的每列元素个数mun(j)，另外我们还需要知道转置前的矩阵的每一列元素的第一个非0元素在转置后的三元组数组中的位置Pos(j) 那么我们就可以根据mun(j)和Pos(j)来确定转置前的三元组数组的每个元素在转置后的三元组数组中位置 计算方法

代码

//稀疏矩阵的三元组顺序表存储表示.cpp #include<malloc.h> // malloc()等 #include<stdio.h> // EOF(=^Z或F6),NULL #include<stdlib.h> // atoi() // 函数结果状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 // #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行 typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等 typedef int Boolean; // Boolean是布尔类型,其值是TRUE或FALSE typedef int ElemType; #define MAX_SIZE 100 // 非零元个数的最大值 struct Triple { int i, j; // 行下标,列下标 ElemType e; // 非零元素值 }; struct TSMatrix { Triple data[MAX_SIZE + 1]; // 非零元三元组表，data[0]未用 int mu, nu, tu; // 矩阵的行数、列数和非零元个数 }; // 1、创建稀疏矩阵M Status CreateSMatrix(TSMatrix &M); // 2、输出稀疏矩阵M void PrintSMatrix(TSMatrix M); //3、输出完整的矩阵 void display(TSMatrix M); //4、输出完整的矩阵 void PrintSMatrix1(TSMatrix M); //5、复制矩阵T = M void CopySMatrix(TSMatrix M, TSMatrix &T); //6、求稀疏矩阵的和Q=M+N Status AddSMatrix(TSMatrix M, TSMatrix N, TSMatrix &Q); //7、求稀疏矩阵的差Q=M-N Status SubtSMatrix(TSMatrix M, TSMatrix N, TSMatrix &Q); //8、 求稀疏矩阵M的转置矩阵T，普通方法 void TransposeSMatrix(TSMatrix M, TSMatrix &T); int main() { TSMatrix M; CreateSMatrix(M); PrintSMatrix(M); display(M); } //1、创建稀疏矩阵M Status CreateSMatrix(TSMatrix &M) { int i, m, n; ElemType e; Status k; printf("请输入矩阵的行数,列数,非零元素数："); scanf_s("%d, %d, %d", &M.mu, &M.nu, &M.tu); if (M.tu > MAX_SIZE) return ERROR; M.data[0].i = 0; // 为以下比较顺序做准备 for (i = 1; i <= M.tu; i++) { do { printf("请按行序顺序输入第%d个非零元素所在的行(1～%d),列(1～%d),元素值:", i, M.mu, M.nu); scanf_s("%d,%d,%d", &m, &n, &e); k = 0; if (m<1 || m>M.mu || n<1 || n>M.nu) // 行或列超出范围 k = 1; if (m < M.data[i - 1].i || m == M.data[i - 1].i&&n <= M.data[i - 1].j) // 行或列的顺序有错,M.data[i - 1].i当前输入数据的前一个数据的行坐标 M.data[i - 1].j当前输入数据的前一个数据的列坐标 k = 1; } while (k);//输入值的行列不按顺序输入则重新输入 M.data[i].i = m; M.data[i].j = n; M.data[i].e = e; } return OK; } //2、输出稀疏矩阵M的非0值 void PrintSMatrix(TSMatrix M) { int i; printf("%d行%d列%d个非零元素。\n", M.mu, M.nu, M.tu); printf("行 列 元素值\n"); for (i = 1; i <= M.tu; i++)//按顺序输出数组中的值 printf("-M