[C++知识库]对称矩阵的压缩

1.定义

若一个方阵A [1...n] [1...n]中的一个任意元素都有a [ i,j ] =a [ j,i ] (1<=i,j<=n),则称其为对称矩阵。

对于一个n阶方阵，可以划分为三个区域，即上三角区，主对角线，下三角区。

2.压缩原因

因为对称矩阵上三角区和下三角区对应的元素相同，如果都存储会造成空间的极大浪费，因此只需要把下三角区（或上三角区）和对角线上的元素进行存储即可。

3.实现原理

对于方阵A [1...n] [1...n]?下三角区和主对角线每行元素为（且i>=j）：

第1行：1个元素

第2行：2个元素

第3行：3个元素

......

第n行：n个元素

总元素个数为：（ n (n+1) / 2 ）?

4.代码实现

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

//对称矩阵压缩  行优先法
int* symmetricMatrix(int arr[][8],int rowlength,int collength,int &comLen) {
	comLen = (1 + rowlength) * rowlength / 2;
	int k = 0;
	int* comAdd = (int*)malloc(comLen * sizeof(int));  //开辟新数组长度
	for (int i = 0; i < rowlength; i++) {
		for (int j = 0; j < collength; j++) {
			if (i >= j) {
				comAdd[k++] = arr[i][j];
			}
		}
	}
	return comAdd;
}

//恢复压缩矩阵
void restoreMatrix(int comArr[],int rowlength,int collength,int arr[][8]) {
	int k = 0;
		for (int i = 0; i < rowlength; i++) {
			for (int j = 0; j < collength; j++) {
				if (i >= j) {
					arr[i][j] = comArr[k++];
				}
			}
		}
	for (int i = 0; i < rowlength; i++) {
		for (int j = 0; j < collength; j++) {
			if (i <j) {
				arr[j][i] = arr[i][j];
			}
		}
	}
}
int main() {
	int arr[8][8];
	int rowlength = sizeof(arr) / sizeof(arr[0]);  // 行长度
	int collength = sizeof(arr[0]) / sizeof(int);  //列长度
	int init = 0;
	int comLen;    //压缩后的长度
	int* comArr = NULL;    //接收压缩后的地址

	//初始化一个对称矩阵
	for (int i = 0; i < rowlength; i++) {
		for (int j = 0; j < collength; j++) {
			if (i >= j) {
				arr[i][j] = init++;
			}
		}
	}
	for (int i = 0; i < rowlength; i++) {
		for (int j = 0; j < collength; j++) {
			if (i < j) {
				arr[i][j] = arr[j][i];
			}
		}
	}

	//遍历输出
	printf("原数组为：\n");
	for (int i = 0; i < rowlength; i++) {
		for (int j = 0; j < collength; j++) {
			if (arr[i][j] < 10) {
				printf("%d  ", arr[i][j]);
			}
			else {
				printf("%d ", arr[i][j]);
			}
		}
		printf("\n");
	}

	//进行压缩
	comArr=symmetricMatrix(arr, rowlength , collength,comLen);
	printf("压缩后为：\n");
	for (int i = 0; i < comLen; i++) {
		printf("%d ", comArr[i]);
	}
	printf("\n");

	//进行恢复
	restoreMatrix(comArr, rowlength, collength, arr);
	printf("恢复后为：\n");
	for (int i = 0; i < rowlength; i++) {
		for (int j = 0; j < collength; j++) {
			if (arr[i][j] < 10) {
				printf("%d  ", arr[i][j]);
			}
			else {
				printf("%d ", arr[i][j]);
			}
		}
		printf("\n");
	}

	free(comArr);  //释放堆区开辟的空间
}

5.测试

?