数组与广义表的一章相对更为简单，第1,2节都是很熟悉的数组相关定义、实现等。因此这篇博客的讲述重点放在第3节“特殊矩阵的压缩存储”中的“稀疏矩阵”的存储以及第4节“广义表”上面。
稀疏矩阵
讲解
稀疏矩阵指的是矩阵中大多数元素为0的矩阵。这时使用传统的二维数组来存储很浪费空间，不妨单独将非零元素的 行、列和值 单独存下来放在一个表中，需要输出矩阵时再把它们还原。我们称这种存储方式为三元组表存储法。
同时为了访问方便，表中的元素按照元素的行号递增存放，同行元素按列号递增存放。这样一个双重循环就可以访问到所有元素。
本篇主要讲解的是在这种存储方式下矩阵转置的算法，即找到一种更为快速的算法使得矩阵转置（行列互换）的同时维持三元组既定的顺序。
朴素的双重循环算法不再赘述。
代码实现
// 需要引入 cstring iostream库
// 使用三元组方式线性存储的矩阵
// 适用于稀疏矩阵等0元素较多的矩阵
// 使用三元组方式线性存储的矩阵
// 适用于稀疏矩阵等0元素较多的矩阵
template <typename T>
class Matrix
{
private:
//分别表示：该矩阵的行、列数、三元组的数量、最多能存储的三元组数量
int m,n,len;
const int MAXSIZE;
// 三元组结构体的定义
// 三个值分别为该元素所在行&列，以及该元素的值
// 定义了一个dat指针，用来访问存三元组的空间
struct Triple
{
int row,col;
T value;
}*dat;
public:
// 构造函数，在初始化时就决定该矩阵的行列数以及最多的三元组个数。
Matrix(int size,int tm,int tn) : MAXSIZE(size),m(tm),n(tn)
{
// 为指针分配内存空间
dat = new Triple[MAXSIZE];
len = 0;
}
// 在矩阵中放入元素
inline void init(int row,int col)
{
T temp;
for(int i=1;i<=row;i++)
for(int j=1;j<=col;j++)
{
cin>>temp;
if(temp)
{
dat[++len].row = i;
dat[len].col = j;
dat[len].value = temp;
}
}
return;
}
// 矩阵的转置，将src矩阵中的内容转置并存入dst矩阵
// 声明友元，便于函数访问两矩阵对象的私有值
friend void Transpose(const Matrix &src, Matrix &dst)
{
// 复制源矩阵的基础参数到目标矩阵
dst.m = src.m;
dst.n = src.n;
dst.len = src.len;
// 算法的本质就是对三元组按列号递增的顺序进行重排
// cnt数组用于计算这一列有多少个元素，以便预留出足够的空间
// memset()用于初始化计数器为0
int *cnt = new int[src.n];
memset(cnt,0,src.n*sizeof(int));
// pos数组用来指明这一列的元素从什么位置开始存
int *pos = new int[src.n];
// 第一次对所有三元组进行循环，统计每一列元素个数
for(int i=1;i<=src.len;i++)
cnt[src.dat[i].col]++;
// 通过每一列元素个数来分配三元组的存放位置
// 第一列从位置1开始存，因此直接设为1
// 后面的第i列的存放位置 = 第i-1列的存放位置+第i-1列的三元组个数
pos[1]=1;
for(int i=2;i<=src.n;i++)
pos[i]=pos[i-1]+cnt[i-1];
// 开始转置过程
// 对所有三元组循环，按照列号把不同三元组放到不同位置
for(int i=1;i<=src.len;i++)
{
// now表示当前处理三元组属于哪一列
int now = src.dat[i].col;
// target存的是这一列的元素要放在哪个位置
int target = pos[now];
// 行列互换，复制值
dst.dat[target].row = src.dat[i].col;
dst.dat[target].col = src.dat[i].row;
dst.dat[target].value = src.dat[i].value;
// 这个位置已经被放了，往后推一个
pos[now]++;
}
// 清扫战场（
delete cnt;
delete pos;
return;
}
// 一个简单的输出矩阵
void output()
{
int now=1;
for(int i=1;i<=m;i++,cout<<endl)
for(int j=1;j<=n;j++)
{
if(dat[now].row == i && dat[now].col == j)
cout<<dat[now++].value<<' ';
else
cout<<"0 ";
}
cout<<endl;
return;
}
~Matrix()
{
delete[] dat;
}
};
示例
主函数如下，此时输入一个四阶矩阵，可以输出它本身和它的转置。
int main()
{
Matrix<int> m(16,4,4),n(16,4,4);
m.init(4,4);
Transpose(m,n);
m.output();
n.output();
return 0;
}