特殊矩阵（对称矩阵）的压缩存储和解压缩
参考书目：严蔚敏《数据结构》P95-96
一、背景
矩阵在工程计算中经常使用，对于一些特殊矩阵，比如对称矩阵，稀疏矩阵……有时为了节省空间，可以对这类矩阵进行压缩存储。这里只讨论对称矩阵，上（下）三角矩阵和对角矩阵，掌握其他类似对称矩阵就很容易了
二、压缩原则
为多个值相同的元素只分配一个存储空间，对零元素不分配空间。
三、对称矩阵的压缩
性质：
0<=i,j<=n-1（在 程序中 数组下标是从 0 开始的)
举例：
压缩：以行序为主序存储下三角（包括对角线）元素
推导如下：
①为书上的方法
②自己想的一种，在压缩 对角矩阵 时会多节省一点空间
四、程序实现 4阶 对称矩阵压缩
4阶矩阵压缩（后面会总结 n阶 ）
#include <iostream>using namespace std;//原始矩阵 int a[4][4]={{0,4,5,6},{4,1,7,8},{5,7,2,9},{6,8,9,3}}; //压缩矩阵 int Sa1[10];int Sa2[10];//通过压缩矩阵复原 原矩阵 int a1[4][4] = {0}; void Printa(){for(int i=0; i<4; i++){for(int j=0; j<4; j++)cout << a[i][j] << "\t";cout << endl;}cout << endl;} void MatrixCompression1()//矩阵压缩 1{for(int i=0; i<4; i++){for(int j=0; j<=i; j++){int k = i*(i+1)/2+j;Sa1[k] = a[i][j];}}}void MatrixCompression2()//矩阵压缩 2{for(int i=0; i<4; i++){for(int j=0; j<=i; j++){int m = i-j;int k = 4*m-m*(m-1)/2+j;Sa2[k] = a[i][j]; }}}int main(){cout << "原始矩阵：" << endl;Printa(); MatrixCompression1();cout << "第一种压缩方式："; cout << "Sa1 = ";for(int i=0; i<10; i++)cout << Sa1[i] << " "; cout << endl;MatrixCompression2();cout << "第二种压缩方式："; cout << "Sa2 = ";for(int i=0; i<10; i++)cout << Sa2[i] << " "; return 0;}
运行结果：
五、解压缩
压缩容易，解压难，不聪明的小脑袋瓜子想了一节课，发现直接从公式出发就好了
其实都可以用暴力法穷举出来，第一种方式我优化了一下，为 O(n2)；第二种方式为 O(n4)，n 表示阶数
void MatrixRecovery1()//矩阵复原1{int i=3,j,k; for(k=9; k>=0; k--){j = k-(i+1)*i/2;if(j>=0){a1[i][j] = a1[j][i] = Sa1[k]; }else{i--;j = k-(i+1)*i/2;a1[i][j] = Sa1[k];}}}
void MatrixRecovery2()//矩阵复原2{int i,j,k,m; for(k=0; k<10; k++){for(i=0; i<4; i++)for(j=0; j<=i; j++){m = i-j;if(k==4*m-m*(m-1)/2+j){a2[i][j] = a2[j][i] = Sa2[k];break;}}}}
六、全部代码和运行结果
#include <iostream>#include <iostream>using namespace std;//原始矩阵 int a[4][4]={{0,4,5,6},{4,1,7,8},{5,7,2,9},{6,8,9,3}}; //压缩矩阵 int Sa1[10];int Sa2[10];//通过压缩矩阵 解压缩回 原矩阵 int a1[4][4] = {0}; int a2[4][4] = {0}; void PrintArray(int a[][4]){for(int i=0; i<4; i++){for(int j=0; j<4; j++)cout << a[i][j] << "\t";cout << endl;}cout << endl;} void MatrixCompression1()//矩阵压缩 1{for(int i=0; i<4; i++){for(int j=0; j<=i; j++){int k = i*(i+1)/2+j;Sa1[k] = a[i][j];}}}void MatrixCompression2()//矩阵压缩 2{for(int i=0; i<4; i++){for(int j=0; j<=i; j++){int m = i-j;int k = 4*m-m*(m-1)/2+j;Sa2[k] = a[i][j]; }}}void MatrixRecovery1()//矩阵复原1{int i=3,j,k; for(k=9; k>=0; k--){j = k-(i+1)*i/2;if(j>=0){a1[i][j] = a1[j][i] = Sa1[k]; }else{i--;j = k-(i+1)*i/2;a1[i][j] = Sa1[k];}}} void MatrixRecovery2()//矩阵复原2{int i,j,k,m; for(k=0; k<10; k++){for(i=0; i<4; i++)for(j=0; j<=i; j++){m = i-j;if(k==4*m-m*(m-1)/2+j){a2[i][j] = a2[j][i] = Sa2[k];break;}}}} int main(){cout << "原始矩阵 a ：" << endl;PrintArray(a); cout << endl;MatrixCompression1();cout << "第一种压缩方式："; cout << "Sa1 = ";for(int i=0; i<10; i++)cout << Sa1[i] << " "; cout << endl;MatrixCompression2();cout << "第二种压缩方式："; cout << "Sa2 = ";for(int i=0; i<10; i++)cout << Sa2[i] << " "; cout << endl;cout << endl;MatrixRecovery1();cout << "第一种压缩方式的解压缩 a1 ：" << endl; PrintArray(a1);MatrixRecovery2();cout << "第二种压缩方式的解压缩 a2 ：" << endl; PrintArray(a2); return 0;}
运行结果：
七、n阶
改改参数就好了
#include <iostream>using namespace std;const int RECORD = 20;//阶数//原始矩阵 int a[RECORD][RECORD]={0}; //压缩矩阵 int Sa1[RECORD*(RECORD+1)/2];int Sa2[RECORD*(RECORD+1)/2];//通过压缩矩阵 解压缩回 原矩阵 int a1[RECORD][RECORD] = {0}; int a2[RECORD][RECORD] = {0}; void Inita(){int cnt = 0;for(int i=0; i<RECORD; i++)for(int j=0; j<=i; j++){a[i][j] = a[j][i] = cnt;cnt++;} } void PrintArray(int a[][RECORD]){for(int i=0; i<RECORD; i++){for(int j=0; j<RECORD; j++)cout << a[i][j] << "\t";cout << endl;}cout << endl;} void MatrixCompression1()//矩阵压缩 1{for(int i=0; i<RECORD; i++){for(int j=0; j<=i; j++){int k = i*(i+1)/2+j;Sa1[k] = a[i][j];}}}void MatrixCompression2()//矩阵压缩 2{for(int i=0; i<RECORD; i++){for(int j=0; j<=i; j++){int m = i-j;int k = RECORD*m-m*(m-1)/2+j;Sa2[k] = a[i][j]; }}}void MatrixRecovery1()//矩阵复原1{int i=RECORD-1,j,k; for(k=RECORD*(RECORD+1)/2-1; k>=0; k--){j = k-(i+1)*i/2;if(j>=0){a1[i][j] = a1[j][i] = Sa1[k]; }else{i--;j = k-(i+1)*i/2;a1[i][j] = Sa1[k];}}} void MatrixRecovery2()//矩阵复原2{int i,j,k,m; for(k=0; k<RECORD*(RECORD+1)/2; k++){for(i=0; i<RECORD; i++)for(j=0; j<=i; j++){m = i-j;if(k==RECORD*m-m*(m-1)/2+j){a2[i][j] = a2[j][i] = Sa2[k];break;}}}} int main(){//初始化 原始矩阵 aInita();cout << "原始矩阵 a" << "(" << RECORD << "阶)" <<"：" << endl;PrintArray(a); cout << endl;MatrixCompression1();cout << "第一种压缩方式："; cout << "Sa1 = ";for(int i=0; i<RECORD*(RECORD+1)/2; i++)cout << Sa1[i] << " "; cout << endl;MatrixCompression2();cout << "第二种压缩方式："; cout << "Sa2 = ";for(int i=0; i<RECORD*(RECORD+1)/2; i++)cout << Sa2[i] << " "; cout << endl;cout << endl;MatrixRecovery1();cout << "第一种压缩方式的解压缩 a1 ：" << endl; PrintArray(a1);MatrixRecovery2();cout << "第二种压缩方式的解压缩 a2 ：" << endl; PrintArray(a2); return 0;}
各阶数所花时间：
阶数越高，运行成本越高。
