第 5章 多维数组与广义表
5.1 数组的存储结构与寻址
5.2 特殊矩阵的压缩存储方式
5.3 广义表
5.4 本章小结
5.1 数组的存储结构与寻址
看待 N维数组的两种不同角度：
1.多维数组是 线性表 。 N维数组是一
个一维的大数组，而该数组的每个数据
元素则是一个 N-1维数组。
2.多维数组是线性表的 扩展, N维数组
的每个元素同时受 N个线性关系的约束。
?对于 数组与线性表的关系 的两种不同理解，可
图示如下，以 三维数组 array[5][3][4]为例,
array[0]
array[1]
array[2]
array[1][0] array[1][1]
( a ) 数组a r r a y [ 3 ] [ 2 ] 是包含
三个元素的一维数组
( b ) 数组元素a r r a y [ 1 ]
本身又是一个包含两
个元素的数组
array[2][1][0]
array[2][1][2]
array[2][1][1]
array[2][0][3]
array[2][2][3]
array[0][1][3] array[1][1][3]
array[3][1][3]
array[4][1][3]
array[2][1][3]
( c ) 三维数组元素a r r a y [ 2 ] [ 1 ] [ 3 ] 同时受三个线性关系的约束
图5, 1 数组元素与线性表的关系
数组的寻址操作：
根据所给的下标定位相应的元素。
方法：
根据一定的 映射规则, 将多维数组的
,多维, 结构映射到计算机中, 一维, 的物
理存储单元中去。
映射规则：
1,行主序（主要）
2,列主序
以二维数组 arr[2][3]为例：
arr[0][0] arr[0][1] arr[0][2] arr[1][0] arr[1][1] arr[1][2]
arr[0][0] arr[1][0] arr[0][1] arr[1][1] arr[0][2] arr[1][2]
arr[0][0] arr[0][1] arr[0][2]
arr[1][0] arr[1][1] arr[1][2]
? ?
? ? ?
数组a r r 的第1 行 数组a r r 的第2 行
数组a r r 的第1 列 数组a r r 的第2 列 数组a r r 的第3 列
( a ) 数组a r r 的逻辑结构
(b) 以行序为主序进行存储
(c) 以列序为主序进行存储
图 5, 2 数组a r r [ 2 ] [ 3 ] 的
逻辑结构及两种存储方式
? 以行序为主序（按行存储）的方法,
,左, 下标优先
? 以列序为主序（按列存储）的方法,
,右, 下标优先
?对于 N（ N≥1 ）维数组，假定数组第 k
（ 1≤ k≤N ）维下标 ik取值的下限为 bk，
上限为 tk，维宽 wk=tk-bk+1。任意一个元
素 array[i1][i2]…[i N]，其维内偏移 sk=ik-bk。
在按行或按列排列的情况下，该元素所
在空间的首地址为：
?按行排列：
Loc(i1,i2,…,iN)=Loc(b1,b2,…,bN)+(s1w2w3… w N
+s2w3w4… wN+… +sN-1wN+sN)*c
?按列排列：
Loc(i1,i2,…,iN)=Loc(b1,b2,…,bN)+(s1+w1s2+… +
w1w2… wN-2sN-1+w1w2… wN-1sN)*c
5.2 特殊矩阵的压缩存储方式
? 矩阵的存储问题：
普通矩阵：二维数组
特殊矩阵：采用二维数组相对低效，
需要采用特殊方法。
5.2.1 对称矩阵（下 /上三角矩阵）的
压缩存储
? 对称矩阵,
矩阵 AN× N，其元素 ai,j满足特性：
ai,j=aj,i（ 1≤ i≤N, 1≤ j≤N ）
?存储方式,
使用一维数组对下三角矩阵或上三角
矩阵进行存储。
矩阵元素 ai,j对应的存储空间的地址：
Loc(ai,j) = Loc(0,0) + (+ j-1)*c (i≥j)；
Loc(ai,j) = Loc(aj,i) (i<j)
数组首地址
一个矩阵元素所
占的空间数
? 上 /下三角矩阵,
位于主对角线下 /上方的所有元素都
为零。
?存储方式,
与对称矩阵存储方式类似。
?注意,
实际工程中可能有这样的, 下 /上三角矩阵,,
其主对角线上 /下方的所有元素是非零常数，对于
这样的, 下 /上三角矩阵,,我们只要多开辟一个
空间，将此常数存入即可。
? 对角矩阵：
所有的非零元素都集中在以主对角
线为中心的带状区域内。
?存储方式,
按照某种原则将其压缩在一维数组
中进行存储。
以 三对角矩阵为例,
a
1,1
a
1,2
0 ? 0 0
a
2,1
a
2,2
a
2,3
? 0 0
0 a
3,2
a
3,3
? 0 0
? ? ? ? ? ?
0 0 0 ? a
N-1,N-1
a
N-1,N
0 0 0 ? a
N,N-1
a
N,N
主上对角线
主对角线
主下对角线
图5, 4 三对角矩阵
三条对角线上的元素 ai,j对应的元素存储首地址
Loc(ai,j)为：
Loc(ai,j) = Loc(0,0) + (2(i-1)+j-1)*c (i = j+1或 i = j或
i= j-1)
数组首地址
一个矩阵元素所占的空间数
5.2.2 稀疏矩阵的三元组顺序表存储方式
? 稀疏矩阵：
含有“较多”零元素,通常指零元素
数目占整个矩阵元素数目的 95％或者更
高的矩阵。
? 存储方式,
压缩存储：对于每一个非零元，我们都用
一个三元组（元素值，元素所处的行号，元素所
处的列号）把它的全部属性表示出来。
“三元组顺序表,
10000
00020
00000
40300 row col val
1 3 3
1 5 4
3 2 2
4 5 1
( a ) 矩阵M ( b ) 三元组序列
图5, 5 矩阵及其对应的三元组序列
三元组按照连续存储的方
式构成一个线性表
除此之外，还需保存：
原矩阵的行数、列数
非零元的数量
矩阵加减法、乘法的实现思路：
预先开设足够大的一组空间, 将计算结
果暂存其中, 最后在处理完运算之后, 再按
照三元组的实际个数将其导入目标数组中 。
矩阵转置运算的实现思路：
每一个三元组自身, 只要将其行列下标
值互换即可 ；
保证新的三元组序列的次序是合法的 。
矩阵转置的算法：
方法 1,选择三元组时，按照列号的下标
从小到大进行。
效率分析,如果矩阵 CM× N的非零元个数
为 T，则时间效率为 O(N*T)。
方法 2,在选择三元组时仍旧按照原来的顺
序，但是在把该处理过的三元组放到目标序列
时，借助, 工具, 直接定位 ----快速转置法
效率分析,如果矩阵 CM× N的非零元个数
为 T，则时间效率为 O(T)。
?5.2.3 稀疏矩阵的十字链表存储方式
00015
00270
80012
row col val
rightdown
r o w, 非零元素行号
c o l, 非零元素列号
v a l, 非零元素的值
d o w n, 非零元素列链表的后继指针
r i g h t, 非零元素行链表的后继指针
( a ) 十字链表中节点的结构
( c ) 稀疏矩阵M
3 × 4
1 1 12 1 4 8
∧∧
2 2 27
∧∧
3 1 15
∧∧
count
rows
cols
colHead
rowHead
r o w s, 矩阵行数
c o l s, 矩阵列数
c o u n t, 非零元素个数
colHead:各 个列链表头指针形成的数组
rowHead:各 个行链表头指针形成的数组
( b ) 十字链表结构
4
3
4
∧
∧ ∧
( d ) 矩阵M
3 × 4
对应的十字链表
图5, 7 稀疏矩阵与十字链表
使用, 二维, 的链表把稀疏矩阵的非
零元素串起来，一个非零元素对应的节
点就会处在横向链表与纵向链表的交叉
处。即, 十字链表, （ Orthogonal
List）。
优点：
链表的插入 /删除比数组的插入 /
删除更快捷。
5.3 广义表
广义表 （ Generalized Lists） 是线性
表的推广, 有时也称为列表 （ Lists） 。
当线性表中的元素类型不一致 （ 即
某些元素是原子类型的数据, 而另一些
元素却是原子类型构成的一个线性表 ）
时, 会使元素之间在原有线性关系的基
础上, 加入层次关系的新特性 。
5.3.1 广义表的定义、特性与基本操作
广义表的定义,
可以把含有 n（ n≥ 0） 个元素, 名称为
L的广义表记为：
L =（ ε 1,ε 2,…,ε n）
ε i为广义表的元素，它可以是一个
广义表，也可以是单个元素
其他术语：
? n=0，则该广义表为 空表 。
? n>0时，
对于广义表的每个元素，如果其类型仍
为广义表，那么可以称这个元素为广义表
L的, 子表, 。
如果其类型只是单个元素，那么可以称
其为广义表 L的, 原子, 。
第一个元素为广义表 L的, 表头,,而
其余元素组成的表被称为广义表 L的, 表
尾, 。
示例：
? L1=（ ）, L1是一个 空表, 表长度为 0；
? L2=（ a）, L2中只包含 1个元素：原子 a,L2
表长度为 1；
? L3=（（ ））, L3中只包含 1个元素：空表,
L3表长度为 1；
习惯上用大写字母表示广义表的名称，
用小写字母表示原子。
? L4=（ a,（ b,c,d））, L4包含 2个元
素, 一个是原子 a,一个是子表 （ b,c，
d）, 子表表长为 3,L4表表长为 2；
? L5=（ L1,L2,L4）, L5包含 3个元素,
三个元素都是列表 。 将子表的值带入后,
我们可以得到 L5=（（ ）, （ a）, （ a，
（ b,c,d））） ；
? L6=（ a,L6）, L6只包含 2个元素, 但由
于 L6是包含自己的 递归表, 所以 L6相当于
是一个无限的列表,L6=（ a,（ a,（ a，
（ a,… ）））） 。
广义表的基本操作：
? 对广义表 L执行取表头的操作：
getHead(L)
? 对广义表 L执行表尾的操作：
getTail(L)
广义表的基本特性：线性表
广义表兼具线性与层次双重
关系特性。
广义表的扩展特性,嵌套
广义表的元素可以是子表，而子表
的元素又可以是子表,…
L5
aa
b c d
L1 L2 L4
(b,c,d)
图5.8 广义表的层次结构
嵌套特性使得广义
表具有层次结构
5.3.2 广义表的存储结构与广义表的
递归算法
? 广义表的存储结构
链式存储结构
方法一, 每个节点仍由两部分构成：
指针域和数据域。
为了标明该节点是原子还是列表，在数
据域中加一个分量，存储节点的类型。
－－－－ 扩展线性链表
a ∧ ∧
1
0
∧a0
1 ∧
b0 d0 ∧c0
head
1 ∧
tag next
data.ptr
tag next
data.val
( a ) 元素类型是原子 ( b ) 元素类型是列表
( c ) 广义表
(a,(b,c,d))
图5, 9 扩展线性链表的存储方式
示例,广义表 (a,(b,c,d))的结构
方法二, 列表类型的广义表元素分成
表头和表尾两个指针域；
为了标明该节点是原子还是列表，在数
据域中加一个分量，存储节点的类型。
－－－－ 头尾链表
示例,广义表 (a,(b,c,d))的结构
e ∧
1
0
∧a0
1
b0 d0c0
head
1 ∧
tag ptr.tp
ptr.hp
tag
val
( a ) 元素类型是原子 ( b ) 元素类型是列表
( c ) 广义表
(a,(b,c,d))
图5, 1 0 头尾链表的存储方式
1 ∧
1 1 ∧
广义表的递归算法
? 思路一：
对于原子类型的数据，直接操作；对
于列表型的数据，将其分解成表头与表尾
两部分，再分别进行递归调用。（ 分而治
之 ）
? 思路二：
对于原子型数据，直接操作；对于列
表型数据，可以把列表中各项看成是并列
的，依次对各项进行递归处理。
借用字符串来存储广义表的, 逻
辑, 表示形式；
以, 分治, 思想为基础递归将各
项广义表信息填入具体存储结构。
根据广义表的, 逻辑, 表示
形式完成广义表的, 物理, 构造：
5.4 本章小结
?基本内容：
1,数组与线性表的关系
2,行主序寻址与列主序寻址
3,特殊矩阵的存储策略
4,兼具线性关系与层次关系的复杂
结构：广义表
? 基本要求：
了解数组的两种存储表示方法, 并掌握数组在
以行为主的存储结构中的 地址计算 方法 。
掌握对特殊矩阵进行 压缩存储 时的 下标变换公
式 。
了解 稀疏矩阵 的两种压缩存储方法的特点和适
用范围, 领会以 三元组 表示稀疏矩阵时进行矩阵
运算采用的处理方法 。
掌握 广义表 的结构特点及其存储表示方法, 熟
练掌握任意一种结构的链表, 学会 对非空广义表
进行分解 的两种分析方法：即可将一个非空广义
表分解为表头和表尾两部分或者分解为 n个子表 。
学会利用分治法的算法设计思想编制递归算
法的方法 。
5.1 数组的存储结构与寻址
5.2 特殊矩阵的压缩存储方式
5.3 广义表
5.4 本章小结
5.1 数组的存储结构与寻址
看待 N维数组的两种不同角度：
1.多维数组是 线性表 。 N维数组是一
个一维的大数组，而该数组的每个数据
元素则是一个 N-1维数组。
2.多维数组是线性表的 扩展, N维数组
的每个元素同时受 N个线性关系的约束。
?对于 数组与线性表的关系 的两种不同理解，可
图示如下，以 三维数组 array[5][3][4]为例,
array[0]
array[1]
array[2]
array[1][0] array[1][1]
( a ) 数组a r r a y [ 3 ] [ 2 ] 是包含
三个元素的一维数组
( b ) 数组元素a r r a y [ 1 ]
本身又是一个包含两
个元素的数组
array[2][1][0]
array[2][1][2]
array[2][1][1]
array[2][0][3]
array[2][2][3]
array[0][1][3] array[1][1][3]
array[3][1][3]
array[4][1][3]
array[2][1][3]
( c ) 三维数组元素a r r a y [ 2 ] [ 1 ] [ 3 ] 同时受三个线性关系的约束
图5, 1 数组元素与线性表的关系
数组的寻址操作：
根据所给的下标定位相应的元素。
方法：
根据一定的 映射规则, 将多维数组的
,多维, 结构映射到计算机中, 一维, 的物
理存储单元中去。
映射规则：
1,行主序（主要）
2,列主序
以二维数组 arr[2][3]为例：
arr[0][0] arr[0][1] arr[0][2] arr[1][0] arr[1][1] arr[1][2]
arr[0][0] arr[1][0] arr[0][1] arr[1][1] arr[0][2] arr[1][2]
arr[0][0] arr[0][1] arr[0][2]
arr[1][0] arr[1][1] arr[1][2]
? ?
? ? ?
数组a r r 的第1 行 数组a r r 的第2 行
数组a r r 的第1 列 数组a r r 的第2 列 数组a r r 的第3 列
( a ) 数组a r r 的逻辑结构
(b) 以行序为主序进行存储
(c) 以列序为主序进行存储
图 5, 2 数组a r r [ 2 ] [ 3 ] 的
逻辑结构及两种存储方式
? 以行序为主序（按行存储）的方法,
,左, 下标优先
? 以列序为主序（按列存储）的方法,
,右, 下标优先
?对于 N（ N≥1 ）维数组，假定数组第 k
（ 1≤ k≤N ）维下标 ik取值的下限为 bk，
上限为 tk，维宽 wk=tk-bk+1。任意一个元
素 array[i1][i2]…[i N]，其维内偏移 sk=ik-bk。
在按行或按列排列的情况下，该元素所
在空间的首地址为：
?按行排列：
Loc(i1,i2,…,iN)=Loc(b1,b2,…,bN)+(s1w2w3… w N
+s2w3w4… wN+… +sN-1wN+sN)*c
?按列排列：
Loc(i1,i2,…,iN)=Loc(b1,b2,…,bN)+(s1+w1s2+… +
w1w2… wN-2sN-1+w1w2… wN-1sN)*c
5.2 特殊矩阵的压缩存储方式
? 矩阵的存储问题：
普通矩阵：二维数组
特殊矩阵：采用二维数组相对低效，
需要采用特殊方法。
5.2.1 对称矩阵（下 /上三角矩阵）的
压缩存储
? 对称矩阵,
矩阵 AN× N，其元素 ai,j满足特性：
ai,j=aj,i（ 1≤ i≤N, 1≤ j≤N ）
?存储方式,
使用一维数组对下三角矩阵或上三角
矩阵进行存储。
矩阵元素 ai,j对应的存储空间的地址：
Loc(ai,j) = Loc(0,0) + (+ j-1)*c (i≥j)；
Loc(ai,j) = Loc(aj,i) (i<j)
数组首地址
一个矩阵元素所
占的空间数
? 上 /下三角矩阵,
位于主对角线下 /上方的所有元素都
为零。
?存储方式,
与对称矩阵存储方式类似。
?注意,
实际工程中可能有这样的, 下 /上三角矩阵,,
其主对角线上 /下方的所有元素是非零常数，对于
这样的, 下 /上三角矩阵,,我们只要多开辟一个
空间，将此常数存入即可。
? 对角矩阵：
所有的非零元素都集中在以主对角
线为中心的带状区域内。
?存储方式,
按照某种原则将其压缩在一维数组
中进行存储。
以 三对角矩阵为例,
a
1,1
a
1,2
0 ? 0 0
a
2,1
a
2,2
a
2,3
? 0 0
0 a
3,2
a
3,3
? 0 0
? ? ? ? ? ?
0 0 0 ? a
N-1,N-1
a
N-1,N
0 0 0 ? a
N,N-1
a
N,N
主上对角线
主对角线
主下对角线
图5, 4 三对角矩阵
三条对角线上的元素 ai,j对应的元素存储首地址
Loc(ai,j)为：
Loc(ai,j) = Loc(0,0) + (2(i-1)+j-1)*c (i = j+1或 i = j或
i= j-1)
数组首地址
一个矩阵元素所占的空间数
5.2.2 稀疏矩阵的三元组顺序表存储方式
? 稀疏矩阵：
含有“较多”零元素,通常指零元素
数目占整个矩阵元素数目的 95％或者更
高的矩阵。
? 存储方式,
压缩存储：对于每一个非零元，我们都用
一个三元组（元素值，元素所处的行号，元素所
处的列号）把它的全部属性表示出来。
“三元组顺序表,
10000
00020
00000
40300 row col val
1 3 3
1 5 4
3 2 2
4 5 1
( a ) 矩阵M ( b ) 三元组序列
图5, 5 矩阵及其对应的三元组序列
三元组按照连续存储的方
式构成一个线性表
除此之外，还需保存：
原矩阵的行数、列数
非零元的数量
矩阵加减法、乘法的实现思路：
预先开设足够大的一组空间, 将计算结
果暂存其中, 最后在处理完运算之后, 再按
照三元组的实际个数将其导入目标数组中 。
矩阵转置运算的实现思路：
每一个三元组自身, 只要将其行列下标
值互换即可 ；
保证新的三元组序列的次序是合法的 。
矩阵转置的算法：
方法 1,选择三元组时，按照列号的下标
从小到大进行。
效率分析,如果矩阵 CM× N的非零元个数
为 T，则时间效率为 O(N*T)。
方法 2,在选择三元组时仍旧按照原来的顺
序，但是在把该处理过的三元组放到目标序列
时，借助, 工具, 直接定位 ----快速转置法
效率分析,如果矩阵 CM× N的非零元个数
为 T，则时间效率为 O(T)。
?5.2.3 稀疏矩阵的十字链表存储方式
00015
00270
80012
row col val
rightdown
r o w, 非零元素行号
c o l, 非零元素列号
v a l, 非零元素的值
d o w n, 非零元素列链表的后继指针
r i g h t, 非零元素行链表的后继指针
( a ) 十字链表中节点的结构
( c ) 稀疏矩阵M
3 × 4
1 1 12 1 4 8
∧∧
2 2 27
∧∧
3 1 15
∧∧
count
rows
cols
colHead
rowHead
r o w s, 矩阵行数
c o l s, 矩阵列数
c o u n t, 非零元素个数
colHead:各 个列链表头指针形成的数组
rowHead:各 个行链表头指针形成的数组
( b ) 十字链表结构
4
3
4
∧
∧ ∧
( d ) 矩阵M
3 × 4
对应的十字链表
图5, 7 稀疏矩阵与十字链表
使用, 二维, 的链表把稀疏矩阵的非
零元素串起来，一个非零元素对应的节
点就会处在横向链表与纵向链表的交叉
处。即, 十字链表, （ Orthogonal
List）。
优点：
链表的插入 /删除比数组的插入 /
删除更快捷。
5.3 广义表
广义表 （ Generalized Lists） 是线性
表的推广, 有时也称为列表 （ Lists） 。
当线性表中的元素类型不一致 （ 即
某些元素是原子类型的数据, 而另一些
元素却是原子类型构成的一个线性表 ）
时, 会使元素之间在原有线性关系的基
础上, 加入层次关系的新特性 。
5.3.1 广义表的定义、特性与基本操作
广义表的定义,
可以把含有 n（ n≥ 0） 个元素, 名称为
L的广义表记为：
L =（ ε 1,ε 2,…,ε n）
ε i为广义表的元素，它可以是一个
广义表，也可以是单个元素
其他术语：
? n=0，则该广义表为 空表 。
? n>0时，
对于广义表的每个元素，如果其类型仍
为广义表，那么可以称这个元素为广义表
L的, 子表, 。
如果其类型只是单个元素，那么可以称
其为广义表 L的, 原子, 。
第一个元素为广义表 L的, 表头,,而
其余元素组成的表被称为广义表 L的, 表
尾, 。
示例：
? L1=（ ）, L1是一个 空表, 表长度为 0；
? L2=（ a）, L2中只包含 1个元素：原子 a,L2
表长度为 1；
? L3=（（ ））, L3中只包含 1个元素：空表,
L3表长度为 1；
习惯上用大写字母表示广义表的名称，
用小写字母表示原子。
? L4=（ a,（ b,c,d））, L4包含 2个元
素, 一个是原子 a,一个是子表 （ b,c，
d）, 子表表长为 3,L4表表长为 2；
? L5=（ L1,L2,L4）, L5包含 3个元素,
三个元素都是列表 。 将子表的值带入后,
我们可以得到 L5=（（ ）, （ a）, （ a，
（ b,c,d））） ；
? L6=（ a,L6）, L6只包含 2个元素, 但由
于 L6是包含自己的 递归表, 所以 L6相当于
是一个无限的列表,L6=（ a,（ a,（ a，
（ a,… ）））） 。
广义表的基本操作：
? 对广义表 L执行取表头的操作：
getHead(L)
? 对广义表 L执行表尾的操作：
getTail(L)
广义表的基本特性：线性表
广义表兼具线性与层次双重
关系特性。
广义表的扩展特性,嵌套
广义表的元素可以是子表，而子表
的元素又可以是子表,…
L5
aa
b c d
L1 L2 L4
(b,c,d)
图5.8 广义表的层次结构
嵌套特性使得广义
表具有层次结构
5.3.2 广义表的存储结构与广义表的
递归算法
? 广义表的存储结构
链式存储结构
方法一, 每个节点仍由两部分构成：
指针域和数据域。
为了标明该节点是原子还是列表，在数
据域中加一个分量，存储节点的类型。
－－－－ 扩展线性链表
a ∧ ∧
1
0
∧a0
1 ∧
b0 d0 ∧c0
head
1 ∧
tag next
data.ptr
tag next
data.val
( a ) 元素类型是原子 ( b ) 元素类型是列表
( c ) 广义表
(a,(b,c,d))
图5, 9 扩展线性链表的存储方式
示例,广义表 (a,(b,c,d))的结构
方法二, 列表类型的广义表元素分成
表头和表尾两个指针域；
为了标明该节点是原子还是列表，在数
据域中加一个分量，存储节点的类型。
－－－－ 头尾链表
示例,广义表 (a,(b,c,d))的结构
e ∧
1
0
∧a0
1
b0 d0c0
head
1 ∧
tag ptr.tp
ptr.hp
tag
val
( a ) 元素类型是原子 ( b ) 元素类型是列表
( c ) 广义表
(a,(b,c,d))
图5, 1 0 头尾链表的存储方式
1 ∧
1 1 ∧
广义表的递归算法
? 思路一：
对于原子类型的数据，直接操作；对
于列表型的数据，将其分解成表头与表尾
两部分，再分别进行递归调用。（ 分而治
之 ）
? 思路二：
对于原子型数据，直接操作；对于列
表型数据，可以把列表中各项看成是并列
的，依次对各项进行递归处理。
借用字符串来存储广义表的, 逻
辑, 表示形式；
以, 分治, 思想为基础递归将各
项广义表信息填入具体存储结构。
根据广义表的, 逻辑, 表示
形式完成广义表的, 物理, 构造：
5.4 本章小结
?基本内容：
1,数组与线性表的关系
2,行主序寻址与列主序寻址
3,特殊矩阵的存储策略
4,兼具线性关系与层次关系的复杂
结构：广义表
? 基本要求：
了解数组的两种存储表示方法, 并掌握数组在
以行为主的存储结构中的 地址计算 方法 。
掌握对特殊矩阵进行 压缩存储 时的 下标变换公
式 。
了解 稀疏矩阵 的两种压缩存储方法的特点和适
用范围, 领会以 三元组 表示稀疏矩阵时进行矩阵
运算采用的处理方法 。
掌握 广义表 的结构特点及其存储表示方法, 熟
练掌握任意一种结构的链表, 学会 对非空广义表
进行分解 的两种分析方法：即可将一个非空广义
表分解为表头和表尾两部分或者分解为 n个子表 。
学会利用分治法的算法设计思想编制递归算
法的方法 。
