！！！对特殊矩阵压缩存储的介绍

数据结构中，提供针对某些特殊矩阵的压缩存储结构

此处说的特殊矩阵主要分为以下二类：

1. 含有大量相同数据元素的矩阵，比如对称矩阵
2. 含有大量 0 元素的矩阵，比如稀疏矩阵、上（下）三角矩阵

针对以上两类矩阵，数据结构的压缩存储的思想是矩阵中相同数据元素（包括元素 0）只存储一个

数据结构中对称矩阵的存储

对称矩阵指的是各数据元素沿主对角线对称的矩阵

我们借助如下公式实现对下三角元素的存储（i 代表行，j 代表列）：

最终求得的 k 值即为该元素存储到数组中的位置（令此数组为 arr）

具体求法如下！！！

1. 第一行第一列的元素 1（i = 1，j = 1），k = 0，arr[0] = 1
2. 第二行第一列的元素 2（i = 2，j = 1），k = 1，arr[1] = 2
3. 第二行第二列的元素 4（i = 2，j = 2），k = 2，arr[2] = 4
4. 第三行第一列的元素 3（i = 3，j = 1），k = 3，arr[3] = 3
5. 第三行第二列的元素 5（i = 3，j = 2），k = 4，arr[4] = 5
6. 第三行第三列的元素 6（i = 3，j = 3），k = 5，arr[5] = 6

---

同理的存储上三角元素利用另一个公式：

C语言示例！！！

#include <stdio.h>

// 将对称矩阵的下三角矩阵元素存储到 arr数组中 
void appendElement(int *arr, int i, int j, int data){  // i和j分别代表元素位于几行几列 
	int index = i*(i-1)/2 + (j-1);
	arr[index] = data;
}

// 展示对称矩阵的元素
void showElement(int *arr, int m, int n){  // m和n分别代表行列数 
	int index = 0;
	for(int i = 1; i < m+1; i++){  // 行数 
		for(int j = 1; j < n+1; j++){  // 列数 
			// 计算对称矩阵的下三角部分（加上主对角线）
			if(i >= j){
				index = i*(i-1)/2 + (j-1);
				printf("%d ", arr[index]);
			}else{
				index = j*(j-1)/2 + (i-1);
				printf("%d ", arr[index]);
			}
		}
		printf("\n");
	}
} 
int main(void){
	int m, n;
	printf("请输入矩阵的行数和列数：");  // 三行三列的对称矩阵 
	scanf("%d %d", &m, &n);  // 3 3
	
	// 计算 arr数组的长度 (m*n+m)/ 2 
	int arr_length = (m*n+m)/2;  // 6
	int arr[arr_length];
	
	// 补充数组
	appendElement(arr, 1, 1, 1);
	appendElement(arr, 2, 1, 2);
	appendElement(arr, 2, 2, 4);
	appendElement(arr, 3, 1, 3);
	appendElement(arr, 3, 2, 5);
	appendElement(arr, 3, 3, 6);
	
	// 展示对称矩阵
	showElement(arr, 3, 3); 
	// outputs: 1 2 3
	//			2 4 5
	//			3 5 6
	return 0;
} 

利用三元组存储稀疏矩阵

—— 头文件

#include <stdio.h>
#define number 3

结构体声明三元组

// 结构体声明三元组节点 
typedef struct {
    int i, j;
    int data;
} triple;

结构体声明稀疏矩阵

// 结构体声明稀疏矩阵节点 
typedef struct {
    triple data[number];
    int n, m, num;
} TSMatrix;

构造增添三元组元素的函数

int index = 0; // 全局变量（记录三元组的索引值） 

// 填充三元组内容
void appendElement(TSMatrix *thisM, int i, int j, int data){
	thisM->data[index].i = i;
	thisM->data[index].j = j;
	thisM->data[index].data = data;
	index++; 
} 

构造展示稀疏矩阵的函数

// 输出存储的稀疏矩阵
void display(TSMatrix M){
    for(int i = 1; i <= M.m; i++){  // 行
        for(int j = 1;j <= M.n; j++){  // 列
            int value = 0;
            for(int k = 0; k < M.num; k++){
                if(i == M.data[k].i && j == M.data[k].j){  // 证明找到非零元素 
                    printf("%d ", M.data[k].data);  // 输出非零元素 
                    value = 1;
                    break;
                }
            }
            if(value == 0){ 
                printf("0 ");
            } 
        }
        printf("\n");
    }
}

—— 主函数

int main() {
    TSMatrix M;
    M.m = 3;  // 三行 
    M.n = 3;  // 三列  
    M.num = 3;  // 三个非零元素 
    
	// 插入三元组 
	appendElement(&M, 1, 1, 1);
	appendElement(&M, 2, 3, 5);
	appendElement(&M, 3, 1, 3);
	
	// 展示三元组 
    display(M);
    // outputs: 1 0 0
	//			0 0 5
	//			3 0 0
    return 0;
}