稀疏矩阵、矩阵压缩、稀疏矩阵的快速转置、十字链表
前几期期链接：
- 【数据结构】栈与队列的概念和基本操作代码实现
- 【数据结构】树与二叉树的概念与基本操作代码实现
1.数组
k维数组的定义：
k
维数组
D
＝
{
a
j
1
,
j
2
,
.
.
.
,
j
k
}
k维数组D＝\{ a_{j_1, j_2, ..., j_k} \}
k维数组D＝{aj1,j2,...,jk}
k
>
0
称为数组的维数，
b
i
是数组第
i
维的长度，
j
i
是数组元素第
i
维的下标
k>0称为数组的维数，b_i是数组第i维的长度，j_i是数组元素第 i维的下标
k>0称为数组的维数，bi是数组第i维的长度，ji是数组元素第i维的下标
a
j
1
,
j
2
,
.
.
.
,
j
k
属于
E
l
e
m
S
e
t
(
元素的性质相同
)
，
Y
i
=
0
,
.
.
.
,
b
i
−
1
(
i
=
1
,
2
,
…
,
k
)
a_{j_1, j_2, ..., j_k}属于ElemSet(元素的性质相同)，Y_{i}=0, ..., b_i -1 ( i=1, 2, …, k)
aj1,j2,...,jk属于ElemSet(元素的性质相同)，Yi=0,...,bi−1(i=1,2,…,k)
-
数组可以看作是一种特殊的线性表，即线性表数据元素本身又是一个线性表
-
数组特点
数组结构固定，每一维的大小不可变
数据元素同构(元素性质相同) -
数组运算
给定一组下标，存取、修改相应的数据元素，一般不做插入、删除操作。
2.数组的顺序表示和实现
二维数组有两种顺序映象的方式
-
以行序为主序:从数组的第一行开始依次存放每一行的数组元素;存放第i行时，从第一列开始顺次存放
特点：有地址计算公式，可以随机访问
二维数组任意元素的存储地址：
L o c ( a i j ) = L o c ( a 11 ) + [ ( i − 1 ) n + ( j − 1 ) ] ∗ L Loc( a_{ij})=Loc(a_{11})+[(i-1)n+(j-1)]*L Loc(aij)=Loc(a11)+[(i−1)n+(j−1)]∗L
L o c ( a 11 ) 称为基地址或基址 Loc(a_{11})称为基地址或基址 Loc(a11)称为基地址或基址
-
以列序为主序:
二维数组任意元素的存储地址：
L o c ( a i j ) = L o c ( a 11 ) + [ ( j − 1 ) m + ( i − 1 ) ] ∗ L Loc( a_{ij})=Loc(a_{11})+[(j-1)m+(i-1)]*L Loc(aij)=Loc(a11)+[(j−1)m+(i−1)]∗L
L o c ( a 11 ) 称为基地址或基址 Loc(a_{11})称为基地址或基址 Loc(a11)称为基地址或基址
可将二维数组的行为主序和列为主序的存储方式推广到一般情况，可得到 n 维数组数据元素存储位置的映象关系
3.特殊矩阵的压缩存储
宗旨：为值相同的矩阵元素只分配一个空间，对零元不分配存储空间.
(1) 特殊矩阵：非零元在矩阵中的分布有一定规则
- 上（下）三角矩阵
- 对称矩阵
- 对角矩阵
(2.)稀疏阵：零元多，分布无规律
（1）. 上三角矩阵—列为主序压缩存储
存储方式：列为主序压缩存储和行为主序压缩存储，存储空间是一维的，将二维数组以一维方式存储。
特点：均可以随机访问数组元素。
上三角矩阵—列为主序压缩存储–数组sa[M]
(1)下三角为0时：
当i≤j时，aij为非0元，存放地址Loc(aij)的计算公式：
L
o
c
(
a
i
j
)
=
L
o
c
(
a
11
)
+
(
(
j
−
1
)
⋅
j
2
+
i
−
1
)
⋅
L
,
(
c
o
n
d
i
t
i
o
n
:
i
≤
j
)
Loc(a_{ij})= Loc(a_{11})+(\frac{(j-1)\cdot j}{2}+i-1)\cdot L , (condition:i≤j )
Loc(aij)=Loc(a11)+(2(j−1)⋅j+i−1)⋅L,(condition:i≤j)
一维存储空间用一维数组sa[M]表示， Loc(aij)计算公式（a11存于sa[0],地址为0 ）：
L
o
c
(
a
i
j
)
=
0
+
(
(
j
−
1
)
⋅
j
2
+
i
−
1
)
⋅
1
,
(
c
o
n
d
i
t
i
o
n
:
i
≤
j
)
Loc(a_{ij})= 0+(\frac{(j-1)\cdot j}{2}+i-1)\cdot 1, (condition:i≤j )
Loc(aij)=0+(2(j−1)⋅j+i−1)⋅1,(condition:i≤j)
数组sa的大小:
M
=
(
n
+
1
)
⋅
n
2
M=\frac{(n+1)\cdot n}{2}
M=2(n+1)⋅n
aij(i≤j)存于下标为k的一维数组元素中:
L
o
c
(
a
i
j
)
=
k
=
(
j
−
1
)
⋅
j
2
+
i
−
1
Loc(aij)=k=\frac{(j-1)\cdot j}{2}+i-1
Loc(aij)=k=2(j−1)⋅j+i−1
(2)下三角为常数时：
常数的存放的位置为：
(
n
+
1
)
⋅
n
2
\frac{(n+1)\cdot n}{2}
2(n+1)⋅n
数组sa的大小:
M
=
(
n
+
1
)
⋅
n
2
+
1
M=\frac{(n+1)\cdot n}{2}+1
M=2(n+1)⋅n+1
（2）. 下三角矩阵—行为主序压缩存储
存储方式：列为主序压缩存储和行为主序压缩存储，存储空间是一维的，将二维数组以一维方式存储。
行为主序压缩存储：从第一行开始依次存放每一行的“非0（C）元”
特点：均可以随机访问数组元素。
下三角矩阵—行为主序压缩存储–数组sa[M]
(1)上三角为0时：
当 j≤i时，aij为非0元，存放地址Loc(aij)的计算公式：
L
o
c
(
a
i
j
)
=
L
o
c
(
a
11
)
+
(
(
i
−
1
)
⋅
i
2
+
j
−
1
)
⋅
L
,
(
c
o
n
d
i
t
i
o
n
:
j
≤
i
)
Loc(a_{ij})= Loc(a_{11})+(\frac{(i-1)\cdot i}{2}+j-1)\cdot L , (condition:j≤i )
Loc(aij)=Loc(a11)+(2(i−1)⋅i+j−1)⋅L,(condition:j≤i)
一维存储空间用一维数组sa[M]表示， Loc(aij)计算公式（a11存于sa[0],地址为0 ）：
L
o
c
(
a
i
j
)
=
0
+
(
(
i
−
1
)
⋅
i
2
+
j
−
1
)
⋅
1
,
(
c
o
n
d
i
t
i
o
n
:
j
≤
i
)
Loc(a_{ij})= 0+(\frac{(i-1)\cdot i}{2}+j-1)\cdot 1, (condition:j≤i )
Loc(aij)=0+(2(i−1)⋅i+j−1)⋅1,(condition:j≤i)
数组sa的大小:
M
=
(
n
+
1
)
⋅
n
2
M=\frac{(n+1)\cdot n}{2}
M=2(n+1)⋅n
aij(i≤j)存于下标为k的一维数组元素中:
L
o
c
(
a
i
j
)
=
k
=
(
i
−
1
)
⋅
i
2
+
j
−
1
Loc(aij)=k=\frac{(i-1)\cdot i}{2}+j-1
Loc(aij)=k=2(i−1)⋅i+j−1
上三角为常数时：
常数的存放的位置为：
(
n
+
1
)
⋅
n
2
\frac{(n+1)\cdot n}{2}
2(n+1)⋅n
数组sa的大小:
M
=
(
n
+
1
)
⋅
n
2
+
1
M=\frac{(n+1)\cdot n}{2}+1
M=2(n+1)⋅n+1
（3）. 对称矩阵
存放方式：只存上三角阵或只存下三角阵都可以
地址计算公式 : 参考上三角和下三角矩阵的地址计算公式
（4）. 对角矩阵
对角矩阵 –2d+1对角阵：主对角线和主对角线上面d条对角线、主对角线下面d条对角线上的数据元素分布不规律，非0（C）.
2d+1 对角阵特点：**第一行和最后一行每行有d+1个数据元素**，余下每行**最多**2d+1个数据元素
压缩存储方法：第一行和最后一行每行存 d+1 个数据元素，余下每行存 2d+1 个数据元素
2d+1-对角阵行为主序压缩存储地址计算公式：
矩阵元素下标从0开始的地址计算公式：
L
o
c
(
a
i
j
)
=
L
o
c
(
a
00
)
+
(
2
d
+
1
)
∗
i
−
d
+
j
−
(
i
−
d
)
=
L
o
c
(
a
00
)
+
(
2
d
+
1
)
∗
i
+
j
−
i
Loc(a_{ij})=Loc(a_{00})+(2d+1)*i-d+j-(i-d) =Loc(a_{00})+(2d+1)*i+j-i
Loc(aij)=Loc(a00)+(2d+1)∗i−d+j−(i−d)=Loc(a00)+(2d+1)∗i+j−i
0
≤
i
,
j
<
n
,
∣
i
−
j
∣
≤
d
0≤i,j<n, |i-j|≤d
0≤i,j<n,∣i−j∣≤d
§矩阵元素下标从1开始的地址计算公式：
L
o
c
(
a
i
j
)
=
L
o
c
(
a
11
)
+
(
2
d
+
1
)
∗
(
i
−
1
)
−
d
+
j
−
i
+
d
=
L
o
c
(
a
11
)
+
(
2
d
+
1
)
∗
(
i
−
1
)
+
j
−
i
Loc(a_{ij})=Loc(a_{11})+(2d+1)*(i-1)-d+j-i+d= Loc(a_{11})+(2d+1)*(i-1)+j-i
Loc(aij)=Loc(a11)+(2d+1)∗(i−1)−d+j−i+d=Loc(a11)+(2d+1)∗(i−1)+j−i
1
≤
i
,
j
≤
n
,
∣
i
−
j
∣
≤
d
1≤i,j≤n, |i-j|≤d
1≤i,j≤n,∣i−j∣≤d
4. 稀疏矩阵
稀疏矩阵: 矩阵元素零元多，在矩阵中随机出现
假设 m行 n列的矩阵含 t个非零元素,则稀疏因子：
δ
=
t
m
⋅
n
δ =\frac{t}{m\cdot n}
δ=m⋅nt
通常认为 δ ≤ 0.05 的矩阵为稀疏矩阵。
压缩存储原则：只存储每个非零元的行、列下标及其值和矩阵的行列维数
常规存储方法缺点:
(1) 零值元素占了很大空间;
(2) 计算中进行了很多和零值的运算，遇除法，还需判别除数是否为零。
解决问题的原则:
(1) 尽可能少存或不存零值元素；
(2) 尽可能减少没有实际意义的运算；
(3) 操作方便。 即：尽可能快地找到与下标值(i,j)对应的元素，尽可能快地找到同一行或同一列的非零值元。
5. 稀疏矩阵的压缩
稀疏矩阵的压缩存储方法:
1. 三元组顺序表
2. 行逻辑联接的顺序表
3. 十字链表
（1）. 三元组顺序表
三元表结构：
//三元表结构：
typedef struct{
int i, j; //非零元的行、列下标
int e; //非零元的值
} Triple;
//稀疏矩阵的结构
#define MAXSIZE 100 //非零元最大个数
typedef struct{
Triple data[MAXSIZE + 1]; //三元组表，data[0]未用
int mu, nu, tu; //矩阵行、列数、非零元个数
} TSMatrix;
特点：
有序的双下标法行序有序存储便于进行依行顺序处理的矩阵运算若需存取某一行中的非零元，需**从头开始查找**。
压缩存储后，元素aij的存储位置与其下标无关，而取决于之前的非零元个数
非零元以行为主序顺序存放
（2）. 行逻辑联接的顺序表
#define MAXRC 500
//行逻辑联接的顺序表
typedef struct {
Triple data[MAXSIZE + 1];
int rpos[MAXRC + 1]; // 每一行非0元存放的起始位置
int mu, nu, tu;
} RLSMatrix; // 行逻辑链接顺序表类型
（3）. 十字链表
用三元组表存储稀疏矩阵，在单纯的存储和做类似转置之类的运算时可以节约存储空间，且运算速度较快;
但当进行矩阵相加等运算时，稀疏矩阵的非零元位置和个数都会发生变化。使用三元组表必然会引起数组元素的大量移动。
- 采用链表存放稀疏矩阵的非0元
- 将稀疏矩阵每行的非0元按照列升序的顺序放在一个单链表中
- 将稀疏矩阵每列的非0元按照行升序的顺序放在一个单链表中
即：
稀疏矩阵的每个非0元即位于一个行单链表，也同时位于一个列单链表用一维数组保存每行非0元的单链表的头指针用一维数组保存每列非0元的单链表的头指针
十字链表 ：每个非零元用含有五个域的结点表示（非零元的所在行、列、值，及同行、同列的下一个非零元）
//十字链表
typedef struct OLNode{
int row, col; //非零元所在行、列
int val; //非零元的值
struct OLNode*right, *down;//同行、同列的下一个非零元
}OLNode,* OLink;
typedef struct{
OLink rhead[M],chead[N]; //行、列指针数组
int mu, nu, tu; //行、列数及非零元个数
}CrossList;
6. 稀疏矩阵的转置（普通转置 和 快速转置）
解决思路：
- 将矩阵行、列维数互换，非零元个数不变
- 将每个三元组中的i和j相互调换，非零元值不变
- 重排次序，使T.data中元素以T的行(M的列)为主序
方法一（普通转置）复杂度为O(T.mu×T.nu)
按矩阵T中三元组表T.data的次序依次在矩阵M的三元组表M.data中找到相应三元组进行转置
为找到M.data中第i列所有非零元素，需对M.data扫描一遍
由于M.data以M行序为主序，所以得到的恰是T.data中应有的顺序文章来源：https://www.toymoban.com/news/detail-845747.html
//复杂度为O(T.mu×T.nu)
Status TransposeSMatrix(TSMatrix M, TSMatrix &T){
int col, p, k;
T.mu=M.nu;
T.nu=M.mu;
T.tu=M.tu;
if(T.tu){ //有非零元，转置
k=1;//k为T.data表下标
for(col=1;col<=M.nu;col++)//查找M每一列的非零元
for( p=1;p<=M.tu;p++)//扫描M的所有非零元
if( M.data[p].j==col ){
T.data[k].i=M.data[p].j;
T.data[k].j=M.data[p].i;
T.data[k].e=M.data[p].e;
k++;
}
return OK;
}
return ERROR;
}
//T(n)=O(M.nu×M.tu)
//若M.tu与M.mu×M.nu同数量级则 T(n)=O(M.mu×M.nu^2)
方法二：快速转置 复杂度O(S.nu+S.tu)
//复杂度O(S.nu+S.tu)
//若S.tu与S.mu×S.nu同数量级则 T(n)=O(S.mu×S.nu)
void TransPose_F(TSMatrix S,TSMatrix &Transpose_S){
//S为原来矩阵
//Transpose_S为转置后矩阵
Transpose_S.mu=S.nu;
Transpose_S.nu=S.mu;
Transpose_S.tu=S.tu;
if(S.tu){
//判断是否为空
int col;//列
int num[MAXSIZE]={0};// 记录原三元组中列号为 col 的项的数目。 辅助数组
int cpot[MAXSIZE]={0};// 记录原三元组中列号为 col 的项在新三元组中的首位置。 辅助数组
//扫描第一次 记录元素矩阵S中列数为j的个数
for(int i=1;i<=S.tu;i++){
//记录元素矩阵S中列数为j的个数
num[S.data[i].j]++;
}
cpot[1]=1;//初始化第一个元素的地址
//扫描第二次 记录原三元组中列号为 col 的项在新三元组中的首位置
for(col=2;col<=S.nu;col++){
//列号为 col 的项在新三元组中的首位置
cpot[col]=cpot[col-1]+num[col-1];
}
//扫描第三次 转置
for(int t=1;t<=S.tu;t++){
col=S.data[t].j;//列数
int s=cpot[col];//地址 下标
Transpose_S.data[s].e=S.data[t].e;
Transpose_S.data[s].i=S.data[t].j;
Transpose_S.data[s].j=S.data[t].i;
cpot[col]++;//下标 后移
}
}
}
感谢阅读！
前几期期链接：文章来源地址https://www.toymoban.com/news/detail-845747.html
- 【数据结构】栈与队列的概念和基本操作代码实现
- 【数据结构】树与二叉树的概念与基本操作代码实现
到了这里，关于【数据结构】数组（稀疏矩阵、特殊矩阵压缩、矩阵存储、稀疏矩阵的快速转置、十字链表）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
