数据结构第五章数组和广义表

则称A为对称矩阵。
压缩存储方案
只存下三角 只存上三角

（1）只存放下三角部分（行优先）
a11
a21 … ai1 … a22 … ai2 … … … … aii …
k=
ann
i (i 1) j 2
j ( j 1) i 2
i≥j i＜ j
an1
an2
an3
a11 a21
a22 a31 … 3 4
选择压缩存储的方法应遵循两条原则：
一是尽可能地压缩数据量；
二是压缩后仍然可以比较容易地进行各项基本操作

5.3.1 特殊矩阵

一、对称矩阵
定义
若一个n阶方阵A中元素满足下
列条件： aij＝aji （其中 1 ≤i, j≤n）
a11 a12 a13 a1n a 21 a 22 a 23 a 2 n a 31 a 32 a 33 a 3 n an1 an 2 an 3 ann
5.2 数组的顺序表示和实现
可以推广到多维数组的行优先顺序存储
行优先顺序存储也称为低下标优先或左边下标优先于
右边下标。
多维数组按行优先存放到内存的规律：
最左边下标变化最慢，最右边下标变化最 快，右边下标变化一遍，与之相邻的左边 下标才变化一次。 因此，在算法中，最左边下标可以看成是 外循环，最右边下标可以看成是最内循环。
CH5 数组和广义表

5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储

5.3.1 特殊矩阵 5.3.2 稀疏矩阵

5.4 广义表的定义 5.5 广义表的存储结构

教学内容
本章先介绍数组的定义及基本运算，然后介绍数组的存
储结构及特殊矩阵的压缩存储，之后讨论稀疏矩阵的三
a1n
a2n … ain … ann
k=
(i 1)(2n i 2) j i 1 i≤j 2
0 i＞j
C
aii
注：数组元素sa[0]中存放的是常数c或0
压缩存储方案
k= c
0 a11 1 … … a1n n a22 n+1 a23 … aii … ain … an,n n(n+1)/2
5.2 数组的顺序表示和实现
（2）列优先顺序存储 LOC(a00)
a0,0 …… am-1,0
第 0列
地址计算公式:
…… a0,j …… am-1,j …… a0,n-1 …… am-1,n-1
第n-1列 第j列
Loc(aij)＝Loc(a00)＋(j×m＋i)L
5.2 数组的顺序表示和实现
Ri={<aj1…ji…jn,aj1…ji+1…jn>| 0≤jk≤bk-1,1≤k≤n 且k≠i,
0≤ji≤bi-2 ,
aj1…ji…jn,aj1…ji+1…jn∈D}
基本操作:
InitArray(&A,n,bound1,…，boundn)
DestroyArray(&A)
value(A,&e,index1,…,indexn)
i j i j

（2）只存放上三角部分
a11 a12
a22
a13
a23 … aii
…
… … … …
a1n
a2n … ain …
k=
(i 1)(2n i 2) j i 1 i≤j 2 ( j 1)(2n j 2) i j 1 i＞j 2
ann
a11 … a1n
ADT Array2{
数据对象 :D＝{aij|aij∈ElemSet,0≤i≤m－1,0≤j≤n－1} 数据关系:S＝{R1,R2} R1＝{< ai,j ,ai,j+1>| 0≤i≤m－1, 0≤j＜n－1} R2＝{< ai,j ,ai+1,j>| 0≤i＜m－1, 0≤j≤n－1} 基本操作:
相同之处：
它们都是若干个相同数据类型的数据元素a0,a1,a2,…，
an-1构成的有限序列。
不同之处：
(1)数组要求其元素占用一块地址连续的内存单元空间，而
线性表无此要求；
(2)线性表的元素是逻辑意义上不可再分的元素，而数组中
的每个元素还可以是一个数组；
(3)数组的操作主要是向某个下标的数组元素中存放数据和
一个二维数组A，行下标的范围是1到6，列下标的范围是
0到7，每个数组元素用相邻的6个字节存储，存储器按字
节编址。那么，这个数组的体积是( 288

)个字节。
例2 :
设数组a[1…60,
1…70]的基地址为2000，每个元素占2个
存储单元，若以行序为主序顺序存储，则元素a[32,31]的 存储地址为 ( 6400 ) 。
一维数组 二维数组
多维数组

注意：
(1)C语言的数组定义下标从0开始。
(2)
数组的处理相比其它复杂的结构要简单。
①
②
数组中各元素具有统一的类型；
数组元素的下标一般具有固定的上界和下界，即数
组一旦被定义，它的维数和维界就不再改变。
③数组的基本操作比较简单。

问题：数组与线性表的区别与联系？
……
an-1
5.2 数组的顺序表示和实现

2.二维数组及多维数组
（1）行优先顺序存储
LOC(a00)
a00 ……
第 0行
a0n-1
地址计算公式: ……
ai0
…… ain-1 …… am-1,0
第i行
Loc(aij)＝Loc(a00)＋( i×n＋j) L
……
am-1,,n-1
第m-1行

例 1：
各种矩阵运算也非常简单，并且存储的密度为1。

两类矩阵的压缩存储
特殊矩阵
稀疏矩阵
5.3.1 特殊矩阵

特殊矩阵

元素值的排列具有一定规律的矩阵。
常见的这类矩阵有：
对称矩阵
下（上）三角矩阵
对角线矩阵等等。

压缩存储方案：

对于这些特殊矩阵，应该充分利用元素值的分布规律，将其进行压 缩存储。
2. 可以将二维数组A看成是由n个列向量[y0, y1, ……,yn-1]组成，其中， Yj＝(a0j, a1j, …..,am-1j)， 0≤j≤n－1。
由此可知:
二维数组中的每一个元素 最多可有二个直接前驱和两个直接后 继（边界除外），故是一种典型的非线性结构。
5.1 数组的定义
二维数组的抽象数据类型定义
5.2 数组的顺序表示和实现

优点
只要知道以下三要素
①开始结点的存放地址（即基地址）；
②维数和每维的上、下界；
③每个数组元素所占用的单元数
就可以将数组元素的存放地址表示为其下标的线性函数。 因此:
数组中的任一元素可以在相同的时间内存取，即顺序
存储的数组是一个随机存取结构。
InitArray(&A,2,m,n) DestroyArray(&A)
value(A,&e,i,j)
Assign(&A,e,i,j) } ADT Array2
5.1 数组的定义

三维数组
三维数组最多可有三个直接前驱和三个直接后继，三维
以上数组可以作类似分析。
因此，可以把三维以上的数组称为多维数组，多维数组
（4）
掌握广义表的结构特点极其存储表示方法，以及
对非空广义表进行分解的两种分析方法。
5.1 数组的定义

一、数组的基本概念
数组的定义
即数组是由n个具有相同数据类型的数据元素a1，
a2 ，…，an组成的有限序列，且该有限序列必须存储
在一块地址连续的存储单元中。
数组的下标：数组元素的位置。
Assign(&A,e,index1,…,indexn)
} ADT Arrayn
5.2 数组的顺序表示和实现

存储结构的选择:
由于对数组一般不做插入和删除操作，也就是说，数组
一旦建立，结构中的元素个数和元素间的关系就不再发
生变化。因此，一般都是采用顺序存储的方法来表示数
组。
由于计算机的内存结构是一维的，因此用一维内存来表

缺点
为了在计算机内存中给数组开辟足够的内存空间，必须
预先确定每个数组下标的上、下界，有时这是比较困难
的。
5.3 矩阵的压缩存储

问题提出：
在科学与工程计算问题中，矩阵是一种常用的数学对象，
在高级语言编制程序时，简单而又自然的方法，就是将
一个矩阵描述为一个二维数组。
矩阵在这种存储表示之下，可以对其元素进行随机存取，
示多维数组，就必须按某种次序将数组元素排成一列序
列，然后将这个线性序列存放在存储器中。
5.2 数组的顺序表示和实现

1.一维数组
LOC(a0)
地址计算公式:
a0 a1
……
L
LOC(ai)＝ LOC(a0)＋i×L
LOC(ai+1)＝ LOC( ai )＋L
LOC(ai) LOC(ai+1)
ai
ai+1
ai1
…
aii
i(i-1)/2+i
…
an1
n(n-1)/2+1
…
an,n
n(n+1)/2
k＝ 1
2
… i(i-1)/2+1