数组与广义表(一)：数组、矩阵的压缩存储 |
您所在的位置：网站首页 › 稀疏矩阵的伪地址表示法 › 数组与广义表(一)：数组、矩阵的压缩存储 |
数组与广义表(一)：数组、矩阵的压缩存储
|
作为数据结构的课程笔记，以便查阅。如有出错的地方，还请多多指正！ 目录 数组的顺序存储结构矩阵的压缩存储对称矩阵三角矩阵对角矩阵稀疏矩阵定义稀疏矩阵的顺序压缩存储三元组表伪地址表示法 稀疏矩阵转置——基于三元组表按M的列序转置快速转置 稀疏矩阵的链式压缩存储：十字链表 数组的顺序存储结构数组的顺序存储结构可随机存取任一元素 以列序为主序: FORTRAN以行序为主序：C、C++
L
O
C
(
i
,
j
)
=
L
O
C
(
0
,
0
)
+
(
b
2
×
i
＋
j
)
×
L
LOC(i,j) = LOC(0,0) + (b2×i＋j)×L
LOC(i,j)=LOC(0,0)+(b2×i＋j)×L推广到一般情况，可得到
n
n
n 维数组数据元素存储位置的映象关系
L
O
C
(
j
1
,
j
2
,
.
.
.
,
j
n
)
=
L
O
C
(
0
,
0
,
.
.
.
,
0
)
+
∑
i
=
1
n
c
i
j
i
LOC(j_1, j_2, ..., j_n ) = LOC(0,0,...,0) + \sum_{i=1}^n c_i j_i
LOC(j1,j2,...,jn)=LOC(0,0,...,0)+i=1∑nciji
其中
c
n
=
L
，
c
i
−
1
=
b
i
×
c
i
,
1
<
i
≤
n
。
其中 c_n = L，c_{i-1} = b_i \times c_i , 1 < i \leq n。
其中cn=L，ci−1=bi×ci,1 int i, j; //非零元的行、列下标
ElemType e; //非零元的值
} Triple;
//稀疏矩阵结构
#define MAXSIZE 100 //非零元最大个数
typedef struct
{
Triple data[MAXSIZE + 1]; //三元组表，data[0]未用
int mu, nu, tu; //矩阵行、列数、非零元个数
} TSMatrix;
伪地址：本元素在矩阵中（包括零元素在内）按行优先顺序的相对位置 基于三元组表的稀疏矩阵转置： 将矩阵行、列维数互换，非零元个数不变将每个三元组中的 i i i和 j j j相互调换，非零元值不变重排次序，使T.data中元素以T的行(M的列)为主序关键是如何实现重排次序
|
【本文地址】
今日新闻 |
推荐新闻 |