admin 管理员组文章数量: 1086019
2024年4月21日发(作者：digaloft)
第5章 数组和广义表
本章所讨论的多维数组和广义表是对线性表的推广，其特点是数据元素仍可被视为一个
表。要求熟悉多维数组的逻辑结构、存储结构，广义表的逻辑结构、表示形式，以及矩阵的
压缩存储的有关内容。
重点提示：
多维数组的存储方式和存取特点
特殊矩阵的存储
稀疏矩阵的存储
广义表的表示形式
5-1 重点难点指导
5-1-1 相关术语
1．特殊矩阵
要点：矩阵中非零元素或零元素的分布有一定规律的矩阵。
2．对称矩阵
要点：一种特殊矩阵；n阶方阵的元素满足性质：a
ij
=a
ji
（0≤i，j≤n-1）。
3．三角矩阵
要点：以主对角线划分，有上三角矩阵和下三角矩阵两种；主对角线以下，不包括主对
角线中的元素，均为常数c，称为上三角矩阵；主对角线以上，不包括主对角线中的元素，
均为常数c，称为下三角矩阵。
4．对角矩阵
要点：非零元素集中在以主对角线为中心的带状区域中，也称带状矩阵。
5．稀疏矩阵
要点：矩阵中非零元素的个数远小于矩阵元素总数的矩阵。
6．三元组表
要点：是稀疏矩阵的一种存储结构；将稀疏矩阵的非零元素的三元组（行、列和值）按
行优先的顺序排列；得到结点均是三元组的线性表。
7．广义表
要点：是线性表的推广；是n个元素a
1
,a
2
,…,a
n
的有限序列；其中a
i
或者是原子或者是
广义表；通常记为LS=(a
1
,a
2
,…,a
n
)，LS为广义表的名字。
5-1-2 多维数组
1．对n维数组逻辑结构的理解
n维数组可视为由n-1维数组为元素的线性结构。
举例：一个m行n列的二维数组可视为由m个一维数组为元素组成的线性结构，其中
1
每个一维数组又由n个单元素组成。
a
11
a
21
Amn
a
m1
a
12
a
1n
A
1
a
22
a
2n
A
2
a
m2
a
mnv
A
m
其中A
i
[a
i1
,a
i2
,
,a
in
]
2．数组的顺序存储方式
（1）行优先顺序——将数组元素按行向量排列，即第i＋1行紧接在第i行后面。如Amn
的存储序列为：
a
11
a
12
… a
1n
a
20
a
21
… a
2n
… a
m1
a
m2
… a
mn
第
1
行
第
2
行
…
第
m
行
（2）列优先顺序——将数组元素按列向量排列，即第i＋1列紧接在第i列后面，如Amm
的存储序列为：
a
11
a
21
… a
m1
a
12
a
22
… a
m2
… a
1n
a
2n
… a
mn
第
1
列
第
2
列
…
第
n
列
3．数组元素的存储地址（以行优先顺序计算，假设每个元素为d个单元）
（1）二维数组中a
ij
的地址
LOC(a
ij
)= LOC(a
11
)+[(i-1)*n+j-1]*d
在C（Visual C++）语言中，因数组下标从0起，故
LOC(a
ij
)=LOC(a
00
)+(i*n+j)*d
（2）三维数组中a
ijk
的地址（A
mnp
）
LOC(a
ijk
)= LOC(a
111
)+ [(i-1)*n*p+(j-1)*p+(k-1)]*d
在Visual C++语言中，因数组下标从0起，故
LOC(a
ijk
)=LOC(a
000
)+(i*n*p+j*p+k)*d
（3）对于一般的二维数组A[c
1
… d
1
,c
2
… d
2
]
LOC(a
ij
)=LOC(a
c1c2
)+[(i-c
1
)*(d
2
-c
2
+1)+j-c
2
]*d
5-1-3 特殊矩阵
矩阵在存储中常用二维数组，而对于一些特殊的矩阵，可将其按一定规律压缩存储在一
维向量中，如sa[ ]中。
1．对称矩阵
（1）特点：在n阶方阵A中有a
ij
=a
ji
（0≤i，j≤n-1）。
（2）存储：按行优先的存储顺序为：a
00
,a
10
,a
11
,a
21
,a
22
, … a
n-1 0
,a
n-1 1
… a
n-1 n-1
（3）元素的二维下标(i，j)与其在一维向量中的位置k的对应关系：
I=max(i，j)， J=min(i，j)
k=I*(I+1)/2+J
LOC(a
ij
)=LOC(sa[k])=LOC(sa[0])+k*d=LOC(sa[0]+[I*(I+1)/2+J]*d
2．三角矩阵
（1）特点：n阶方阵A中，上三角或下三角（不包括主对角线）元素均为常数c。
2
版权声明：本文标题：数据结构习题及答案与实验指导(数组和广义表)5 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1713670993a646283.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论