数组：
常见的数组有一维数组和二维数组，二维数组是元素可以看成是一维数组的一维数组。对于数组主要考察元素下标计算的问题。对于一维数组较为简单，而对于二维数组的元素位置计算较为复杂，要考虑行优先和列优先两种情况。
二维数组的行优先和列优先存储：
行优先：从起始行开始一行一行地存入连续空间中
列优先：从起始列开始一列一列地存入连续空间中
矩阵的压缩存储：
矩阵的定义
- 矩阵一般用一个二维数组A[m][n]表示，表示一个m行n列的矩阵
- 其中m n 必须为常量，或者为预先定义的宏常量，如下：
1
2
3
int A[m][n];
矩阵的一般操作与实现
- 矩阵的转置：
1
2
3
4
5
6
7void transpose(int A[][maxsize],int B[][maxsize],int m,int n){
for(int i = 0; i < m ; ++i){
for(int j = 0; j < n ; ++j){
B[j][i] = A[i][j]; // 矩阵转置操作，元素关于主对角线互换位置
}
}
} - 矩阵相加:
1
2
3
4
5
6
7void addition(int A[][max],int B[][max],int C[][max],int m,int n){
for(int i = 0; i < m ; ++i){
for(int j = 0; j < n){
c[i][j] = A[i][j] + B[i][j]; //对应位置元素相加
}
}
} - 矩阵相乘：
1
2
3
4
5
6
7
8
9
10void Multiply(int A[m][n],int B[n][k],int C[m][k],int m,int n,int k){
for(int i = 0;i<m;++i){
for (int j = 0;j<k;++j){
C[i][j] = 0;
for(int h = 0;h<n;++h){
C[i][j] += A[i][h] * B[h][j];
}
}
}
}
特殊矩阵和稀疏矩阵
- 矩阵中绝大多数元素都是0的矩阵称为稀疏矩阵(国外教材)
- 相同的元素或者零元素在矩阵中的分布存在一定规律的矩阵称为特殊矩阵，反之称为稀疏矩阵(严版)
- 特殊矩阵：
a) 对称矩阵
- 矩阵中的元素满足A[i][j] = A[j][i] 的矩阵称为对称矩阵
- 如上图所示，只需要存储一半的元素就可以了，要还原出另一半只需根据A[i][j] = A[j][i]这个条件就行了。
- 将一个n×n的对称矩阵存储在一维数组中，所需的存储空间为 $ \dfrac{(1+n)·n}{2}$
- 需要保存的元素为：
- 按照行优先来存储，保存在一维数组中，如下图所示：
b)三角阵
- 上三角矩阵 为矩阵下三角部分(不包括对角线)元素全为零
- 下三角矩阵 为矩阵上三角部分(不包括对角线)元素全为零
- 三角矩阵的存储方式与对称矩阵类似，以下三角矩阵的存储为例，只需存储对角线及其以下部分的元素和其上三角中的一个元素C即可，如下图：
c)对角矩阵
- 如下图所示的对角矩阵，其特点为除了主对角线以及其上下两条带状区域的元素外，其余元素都为C ( C可以为0)：
- 下面介绍如何求出第i行带状区域内的第一个元素在一维数组中的下标，假设c存在数组的最后一位：
- 当i=1时，带状区域内的第一个元素为矩阵当中的第一个元素，其在一维数组中的下标为0；
当i>1时，第i行之前的元素个数为 $2+(i-2)×3$，则带状区域的第一个元素在一维数组中的下标为 $2+(i-2)×3$
2.稀疏矩阵稀疏矩阵中的相同元素c不像特殊矩阵中的相同元素的位置分布那么有规律可循，故必须为其设计一些特殊的存储结构
- 稀疏矩阵的顺序存储及其相关操作：
常用的稀疏矩阵顺序存储方法有三元组表示法，和伪地址表示法。
- 三元组表示法：
三元组数据结构为一个长度为n，表内每个元素都有三个分量的线性表，其三个分量分别为：“值”、“行下标”、“列下标”。
元素结构体定义如下：结构体示意图：1
2
3
4
5typedef struct Trimat{
int val; // 值
int i; // 行下标
int j; // 列下标
}；
结构题数组的定义：1
Trimat trimat[maxterms + 1]; // maxterms + 1;因为从第 1 行才开始存储元素
但是，为了方便起见，一般不用上诉结构体来定义三元组，直接申请一个二维数组就可以了：1
2
3
4
5
6
7
8
9
10int trimat[maxterms + 1][3];
// 如要求其他类型，可将int替换掉
// 需要注意的是，如果矩阵是float型的（或者其他非整型的数据类型）
// 则此时用一个数组来表示三元组应该写成如下形式：
float trimat[maxterms + 1][3];
// 这个时候若要取当前非零元素的所在位置应该这么做：
(int)trimat[k][1];
(int)trimat[k][2];
// 就是将float 型的元素造型成int型，这样就可以避免很多不必要的问题的发生
上诉定义方式中：trimat[k][0]表示原矩阵中的元素按行优先顺序的第k个元素的值
trimat[k][1]、trimat[k][2]表示第k个非零元素在矩阵中的位置。事实上，trimat此时就是一个maxterms 行 3 列的二维数组，我们规定第0行的三个元素分别用来存储原矩阵中的非零元素个数，以及矩阵的行数与列数。
示意图如下：
- 给定一个二维数组存储的矩阵，要求设计算法将其转化为三元组存储：
- 算法分析：
建立一个三元组的核心问题在于求矩阵的非零元素个数以及非零元素的值，还有其在矩阵（原数组）中的位置，故只需扫描所给矩阵的二维数组即可得到相关数据，进而建立三元组。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18// 建立三元组时，结点间的次序行按元素在矩阵中的行优先顺序排列
void creattrimat(float A[][max],int m,int n,float B[][3]){
// m,n 表示所给矩阵的规模为m×n
int k = 1;
for (int i = 0;i<m;++i){
for (int j =0;j<n;++j){ // 双重循环扫描矩阵
if (A[i][j] != 0){ // 若矩阵的[i][j] 上的元素不为零，将该元素连同其位置信息存入三元组中
B[k][0] = A[i][j];
B[k][1] = i;
B[k][2] = j;
k++; // k 指向三元组的下一个空间
}
}
}
B[0][0] = k-1; // 将矩阵的基本信息存入三元组的第0行
B[0][1] = m;
B[0][2] = n;
} - 设计算法打印出所给三元组存储的矩阵：
- 算法分析：
读取三元组的第0行，得到矩阵的相关信息
循环按行打印，若下标与三元组中的非零元素下标信息匹配则打印该非零元素，否则，打印0；1
2
3
4
5
6
7
8
9
10
11
12
13
14void print(float trimat[][3]){
int m = trimat[0][1];
int n = trimat[0][2];
int k = 1; // 非零元素从第一行开始存储
for(int i = 0;i<m;i++){ // 双重循环打印矩阵
for(int j = 0;j<n;j++){ // 循环过程中检查第[i][j]下标是否与三元组中的非零元素相同，若相同打印该非零元素，若不同打印 0 ；
if(i = (int)trimat[k][1] && j == (int)trimat[k][2]){
cout << trimat[k][0] << " ";
++k;
}
else cout << "0 " << endl;
}
}
}
- 伪地址表示法：
伪地址表示法与三元组表示法在本质上并无差别，只不过是三元组表示法的每一行用两个存储单元来存放原矩阵非零元素的位置标记，而伪地址表示法可以只用一个存储单元来存放位置标记，原因是因为对于一个$ m·n $的矩阵，伪地址表示法将元素位置下标的两个整数用一个公式映射( $ n·(i-1) +j $)到了一个整数上，同样利用该公式也可还原原i和j的值。
我们来看一个例子：
- 稀疏矩阵的链式存储及相关操作：
- 邻接表表示法：
邻接表表示法将矩阵中每一行的非零元素串联成一个单链表，链表结点中有三个分量：元素值、所在列、指针域
结点的定义如下：示意图如下：1
2
3
4
5typedef struct Listmat{
int data;
int col;
struct Listmat *next;
};
上图中最左端为一个指针数组，用来存储指向每一行非零元素单链表的头指针，数组下标为表示行标号。 - 十字链表表示法：
在稀疏矩阵的十字链表存储结构中，矩阵的每一行用一个带头结点的链表表示，每一列也用一个带头结点的链表表示，这种存储结构中的链表结点有 5 个分量：行分量、列分量、数据域、指向下方结点的指针域、指向右方结点的指针域；结构图如下：
普通结点定义：头结点定义:1
2
3
4
5
6
7typedef struct matNode{
int row;
int col;
int data;
struct matNode *down;
struct matNode *right;
};由于十字链表存储结构比较复杂，我们将通过其结构图例来深入了解它，图中附有详细的注释：1
2
3
4typedef struct CrossList{
struct matNode *rhead,*cheard; // 指向两头结点数组的指针
int m,n,k; // 矩阵行数、列数、非零结点总数
}
上图中，银灰色的结点为行头结点数组与列头结点数组，他们的定义如下：1
2
3
4
5
6
7// 其中的m n 为矩阵的行数和列数
typedef struct Rhead{ // 行头结点数组
struct matNode Rhead[m]; // 元素为matNode结点的数组
};
typedef struct Chead{ // 列头结点数组
struct matNode Chead[n];
}
- 在理解了十字链表存储结构后，我们来看一个实际的应用：
给定一个float型二维数组存储的稀疏矩阵，建立其对应的十字链表结构。
算法分析：
首先应该建立整体框架，也就是十字链表头结点以及行、列头结点数组。然后，按行优先顺序遍历矩阵数组，若发现不为零的元素，分配一个结点空间将其值存入，调整行、列头结点的指针域指向该结点，如此直到结束遍历1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54int creatCrossListmat(float A[][maxsize],int m,int n,int k,CrossList &M){
//============================================
// 搭建基本框架操作
//============================================
// 清空处理：
if (M.rhead) free(M.rhead);
if (M.chead) free(M.chead);
// 将矩阵信息存入十字链表头结点：
M.m = m;
M.n = n;
M.k = k;
// 申请行、列头结点数组空间：
if (!(M.rhead = (matNode*)malloc(sizeof(matNode)*m)))
return 0;
if (!(M.chead = (matNode*)malloc(sizeof(matNode)*n)))
return 0;
// 将行、列头结点数组的right和down指针置空：
for(int i = 0;i < m ; ++i){
M.rhead[i].right = NULL;
M.rhead[i].down = NULL;
}
for(int i = 0;i < n ;++i){
M.chead[i].right = NULL;
M.chead[i].down = NULL;
}
//===================================================
// 核心算法
//===================================================
// 建立链表的辅助指向列头结点的指针数组：
matNode *temp_r[maxsize];
for(int i = 0;i<n;++i){
temp_r[i] = &(M.chead[i]); // 引用
}
// 行优先顺序遍历矩阵数组构建十字链表：
for(int i = 0;i < m ;++i){
matNode *c = &(M.rhead[i]);
for(int j = 0;j < n;++j){
if (A[i][j] != 0){
matNode *p = (matNode*)malloc(sizeof(matNode));
p -> row = i;
p -> col = j;
p -> val = A[i][j];
p -> down = NULL;
p -> right = NULL;
// 如果某行（列）中已经连接了元素，那么就让这个元素充当该行（列）的头部，这样能使十字链表的行（列）头结点数组中的结点避免重复指向，覆盖；所以下面的代码所要做的事情很重要。
c -> right = p;
c = p;
temp_r[j] -> down = p;
temp_r[j] = p;
}
}
}
return 1;
}
广义表
- 表元素可以是原子类型的元素，也可以是广义表的一种线性表
三个重要概念：
- 广义表的长度：表中最上层元素的个数
- 广义表的深度：表中括号的最大层数，求解时应将所有的子表展开在分析
- 表头(Head)和表尾(Tail)：当表非空时，第一个元素为广义表的表头，其余元素组成广义表的表尾
两种存储结构：
- 头尾链表存储结构：
这种存储结构有两种结点，即原子结点和广义表结点。原子结点有两个域：标记域、数据域。广义表结点有三个域：标记域、头指针域、尾指针域
其中头指针指向一个原子结点或广义表结点，尾指针为空或者指向 本层中 的下一个广义表结点，而标记域用来区分广义表结点(1)与原子结点(0);
示意图入下：
- 扩展线性表结构：
该种存储结构同样有两种结点，与头尾链表存储结构不同的是这里的原子结点有三个域：标记域、数据域、尾指针域。
示意图如下：