顺序表练习（三）：对称矩阵的压缩储存
前言
本次练习的内容是对称矩阵的压缩储存以及各种配套函数的实现，先放一下对称矩阵的定义：
对于一个方阵A，若其中的元素
满足
，则称其为对称矩阵。通俗地理解，对称矩阵就是沿着主对角线（“\”这样的是主对角线）将矩阵折叠后对应元素相同的矩阵。
对称矩阵里有近一半的元素是相同的，如果对其进行压缩储存，我们就能省下近一半的空间。
练习目标
- 实现对称矩阵的压缩储存
- 实现相应的初始化、销毁、打印矩阵等函数
- 实现对压缩后的矩阵的值的修改
结构定义
首先先定义一个结构体：
#define dimSize 5
typedef struct SymmetricMatrix
{
int *data;
int dim; //dimension -> means dim*dim matrix
SymmetricMatrix() : data(NULL), dim(-1) {}
} Mat;取别名为Mat类型，其中dim意为方阵的维度，即表示为dim*dim阶方阵。构造函数里简单地做了一下初始化，另外，我们约定矩阵以行优先形式储存，并且储存下三角的元素+主对角线上的元素。
辅助函数的实现
//创建Mat，其中数组的大小根据公式计算得出
Mat *createMat()
{
Mat *mat = new Mat;
mat->dim = dimSize;
mat->data = new int[dimSize * (dimSize + 1) / 2]{0};
return mat;
}
//销毁Mat同时以引用形式将指针置空
void destroyMat(Mat *&mat)
{
delete[] mat->data;
delete mat;
mat = NULL;
}
//获取实际的数组长度，根据公式计算得出
int getArraySize(Mat *mat)
{
int dim = mat->dim;
int sz = dim * (dim + 1) / 2;
return sz;
}
//输出数组，做了一些简单的格式处理
void printArr(Mat *mat)
{
int sz = getArraySize(mat);
cout << "SMat:[";
for (int i = 0; i < sz; i++)
{
cout << mat->data[i];
if (i != sz - 1)
cout << " ";
}
cout << "] " << sz << endl;
}
//为后面检查行列是否合法准备
bool checkIndex(Mat *mat, int col, int row)
{
int n = mat->dim;
if (col > n || row > n)
return false;
return true;
}其中值得一提的是计算数组大小的公式 dim*(dim+1)/2，看上面给的红格子示意图，如果我们将每行的红色格子数量标出来，就能得到一个1 2 3 4 5的数列，根据高中的等差数列求和公式，化简后就可以得到dim*(dim+1)/2，这就是求压缩后的矩阵的实际数组长度的公式。
实现根据数组数据初始化的函数
实现的是根据传进来的n*n大小的数组matrix来初始化压缩矩阵mat的函数，上代码：
void initMat(Mat *mat, int *matrix)
{
int n = mat->dim;
int k = 0;
for (int i = 0; i < n; i++)//行
for (int j = 0; j < i + 1; j++)//列
if (j <= i)
mat->data[k++] = matrix[j * n + i];
}参数中的matrix指针实际上是一个n*n大小的矩阵数组，这里为了方便直接使用了一维数组，其实按常规思维的话要用二维数组来表示矩阵。
这几行代码的核心思路是遍历传进来的数组，将下三角+主对角线上的元素存进数组里。其中k代表mat中数组的下标，j*n+i是用来分割数组的，因为传进来的是用一维数组储存的矩阵，j为行数i为列数。
除此之外，第二层循环的条件j < i+1是根据情况优化的，因为对于矩阵压缩而言，每行只储存和行数相同数量的元素，同时考虑到数组下标是从0开始，所以这里就写成j<i+1；循环最内层的j<=i判断是因为对于下三角元素和主对角线元素而言，他们的列号永远小于等于行号，所以就可以根据这个条件来筛选哪些元素是需要存的，哪些是可以压缩掉不存的。
实现在压缩矩阵里取值的函数
先上代码：
int getValue(Mat *mat, int col, int row) //Columns and rows are logical index (based-1)
{
if (!checkIndex(mat, col, row))
return INT_MIN;
if (col > row) //target value is located in upper triangular matrix
swap(col, row); //turn the indices into lower triangular matrix
int i = row * (row - 1) / 2 + col - 1; //logical index to physical index
return mat->data[i];
}代码中写了一些英文注释帮助理解。参数中的col和row就是要取的值的列号和行号，是从1开始的；checkIndex在上面辅助函数里有，不再赘述。重点解释一下第二个if和i的计算：
1.函数中第二个if是为了应对取上三角元素的情况（列号大于行号，即是上三角元素），因为在数组中我们没有存上三角元素，所以这里需要绕个弯，利用对称矩阵的特性（其实这就是为何能压缩的原因）将行列号互换就变成了取下三角元素，就可以直接在数组里取值。
2.i的计算其实也是和之前算数组长度的原理差不多，不过这里的参数是从1开始的行列号，所以要同时把逻辑下标转成物理下标才行。如果不用转换成物理下标的话，我们的公式应该是这样的 i = row*(row+1)/2 + col，大概的原理就是先计算当前元素上面有多少行的元素，再加上当前行的当前元素前面有多少个元素，加起来就能得到当前元素在数组的位置。但是现在我们需要转换成物理下标，所以就要把行号和列号都减1，公式就变成了i = row*(row-1)/2 + col - 1。
如果还是不能理解的话推荐自行画图并结合等差数列求和公式推导一遍。
实现打印矩阵的函数
因为有了上面实现的getValue函数，打印矩阵的函数很快就能写出来：
void printMat(Mat *mat)
{
int n = mat->dim;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
cout << getValue(mat, i, j) << " ";
cout << endl;
}
}注意getValue接收的行列号是逻辑下标，即从1开始。
实现修改矩阵元素的值的函数
根据上面的公式，我们很快就能实现这个函数：
void value(Mat *mat, int val, int col, int row)
{
if (!checkIndex(mat, col, row))
return;
if (col > row)
swap(col, row);
int i = row * (row - 1) / 2 + col - 1;
mat->data[i] = val;
}要注意的是如果我们修改一个主对角线以外的元素，会同时修改他对称的另一个元素，即修改a12会同时修改a21。
完整代码
给了main函数和测试的样例，直接运行即可。
#include <iostream>
using namespace std;
#define dimSize 5
typedef struct SymmetricMatrix
{
int *data;
int dim; //dimension -> means dim*dim matrix
SymmetricMatrix() : data(NULL), dim(-1) {}
} Mat;
Mat *createMat()
{
Mat *mat = new Mat;
mat->dim = dimSize;
mat->data = new int[dimSize * (dimSize + 1) / 2]{0};
return mat;
}
void destroyMat(Mat *&mat)
{
delete[] mat->data;
delete mat;
mat = NULL;
}
int getArraySize(Mat *mat)
{
int dim = mat->dim;
int sz = dim * (dim + 1) / 2;
return sz;
}
void printArr(Mat *mat)
{
int sz = getArraySize(mat);
cout << "SMat:[";
for (int i = 0; i < sz; i++)
{
cout << mat->data[i];
if (i != sz - 1)
cout << " ";
}
cout << "] " << sz << endl;
}
bool checkIndex(Mat *mat, int col, int row)
{
int n = mat->dim;
if (col > n || row > n)
return false;
return true;
}
void initMat(Mat *mat, int *matrix)
{
int n = mat->dim;
int k = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < i + 1; j++)
if (j <= i)
mat->data[k++] = matrix[j * n + i];
}
int getValue(Mat *mat, int col, int row) //Columns and rows are logical index (based-1)
{
if (!checkIndex(mat, col, row))
return INT_MIN;
if (col > row) //target value is located in upper triangular matrix
swap(col, row); //turn the indices into lower triangular matrix
int i = row * (row - 1) / 2 + col - 1; //logical index to physical index
return mat->data[i];
}
void value(Mat *mat, int val, int col, int row)
{
if (!checkIndex(mat, col, row))
return;
if (col > row)
swap(col, row);
int i = row * (row - 1) / 2 + col - 1;
mat->data[i] = val;
}
void printMat(Mat *mat)
{
int n = mat->dim;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
cout << getValue(mat, i, j) << " ";
cout << endl;
}
}
int main()
{
Mat *mat = createMat();
int arr[25]{
1, 2, 3, 4, 5,
2, 2, 7, 7, 5,
3, 7, 4, 2, 5,
4, 7, 2, 1, 3,
5, 5, 5, 3, 8};
initMat(mat, arr);
printArr(mat);
printMat(mat);
cout << endl;
value(mat, 99, 4, 1);
printMat(mat);
destroyMat(mat);
return 0;
}
总结
对称矩阵的压缩的实现难度比较小，重难点在于下标的计算，下标的计算公式用到了等差数列的求和公式。万丈高楼平地起，越是基础的东西越需要多打多练。