作为数据结构的课程笔记,以便查阅。如有出错的地方,还请多多指正!
目录
数组的顺序存储结构矩阵的压缩存储对称矩阵三角矩阵对角矩阵稀疏矩阵定义稀疏矩阵的顺序压缩存储三元组表伪地址表示法
稀疏矩阵转置——基于三元组表按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 |