由此可知:
二维数组中的每一个元素 最多可有二个直接前驱和两个直接后 继（边界除外），故是一种典型的非线性结构。
5.1 数组的定义
▪ 二维数组的抽象数据类型定义
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}
大家好
CH5 数组和广义表
5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储
5.3.1 特殊矩阵 5.3.2 稀疏矩阵
5.4 广义表的定义 5.5 广义表的存储结构
教学内容
本章先介绍数组的定义及基本运算，然后介绍数组的存 储结构及特殊矩阵的压缩存储，之后讨论稀疏矩阵的三 种存储方法，最后介绍广义表的概念、基本运算和存储 结构。
① 数组中各元素具有统一的类型； ② 数组元素的下标一般具有固定的上界和下界，即数
组一旦被定义，它的维数和维界就不再改变。 ③数组的基本操作比较简单。
问题：数组与线性表的区别与联系？
相同之处：
它们都是若干个相同数据类型的数据元素a0,a1,a2,…，
an-1构成的有限序列。 不同之处：
(1)数组要求其元素占用一块地址连续的内存单元空间，而 线性表无此要求；
5.1 数组的定义
n维数组的抽象数据类型定义
ADT Arrayn{ 数据对象:
D={aj1j2…jn| aj1j2…jn ∈ElemSet,其中 ji =0,1,… , bi-1, i =1,…,n}
数据关系:
S={R1 ,R2 ,…… ,Rn}
Ri={<aj1…ji…jn,aj1…ji+1…jn>| 0≤jk≤bk-1,1≤k≤n 且k≠i,
LOC(a00)
地址计算公式:
Loc(aij)＝Loc(a00)＋( i×n＋j) L
a00 …… a0n-1 …… ai0 …… ain-1 …… am-1,0 …… am-1,,n-1
第0行 第i行 第m-1行
例1：
一个二维数组A，行下标的范围是1到6，列下标的范围是 0到7，每个数组元素用相邻的6个字节存储，存储器按字 节编址。那么，这个数组的体积是( 288 )个字节。
▪ 最左边下标变化最慢，最右边下标变化最 快，右边下标变化一遍，与之相邻的左边 下标才变化一次。
(2)线性表的元素是逻辑意义上不可再分的元素，而数组中 的每个元素还可以是一个数组；
(3)数组的操作主要是向某个下标的数组元素中存放数据和 取某个下标的数组元素，这与线性表的插入和删除操作不
同。
5.1 数组的定义
二维数组
a00
a01 a0n-1
A a10
a11 a1n-1
在此:
a a a m-1,0
5.2 数组的顺序表示和实现
1.一维数组
地址计算公式: LOC(ai)＝ LOC(a0)＋i×L LOC(ai+1)＝ LOC( ai )＋L
LOC(a0)
a0
L
a1
……
LOC(ai)
ai
LOC(ai+1)
ai+1
……
an-1
5.2 数组的顺序表示和实现
2.二维数组及多维数组
（1）行优先顺序存储
0≤ji≤bi-2 ,
aj1…ji…jn,aj1…ji+1…jn∈D}
基本操作:
InitArray(&A,n,bound1,…，boundn)
DestroyArray(&A) value(A,&e,index1,…,indexn) Assign(&A,e,index1,…,indexn)
} ADT Arrayn
基本操作:
InitArray(&A,2,m,n)
DestroyArray(&A)
value(A,&e,i,j)
Assign(&A,e,i,j)
} ADT Array2
5.1 驱和三个直接后继，三维 以上数组可以作类似分析。
因此，可以把三维以上的数组称为多维数组，多维数组 可有多个直接前驱和多个直接后继，故多维数组是一种 非线性结构。
m-1,1
m-1,n-1
1. 可以将二维数组A看成是由m个行向量[X0,X1, …,Xm-1]T组成，其中 ，Xi＝( ai0, ai1, ….,ain-1)， 0≤i≤m－1；
2. 可以将二维数组A看成是由n个列向量[y0, y1, ……,yn-1]组成，其中 ， Yj＝(a0j, a1j, …..,am-1j)， 0≤j≤n－1。
例2 :
设数组a[1…60, 1…70]的基地址为2000，每个元素占2个 存储单元，若以行序为主序顺序存储，则元素a[32,31]的 存储地址为 ( 6400 ) 。
5.2 数组的顺序表示和实现
可以推广到多维数组的行优先顺序存储 行优先顺序存储也称为低下标优先或左边下标优先于 右边下标。 多维数组按行优先存放到内存的规律：
5.1 数组的定义
一、数组的基本概念
数组的定义
即数组是由n个具有相同数据类型的数据元素a1， a2 ，…，an组成的有限序列，且该有限序列必须存储
在一块地址连续的存储单元中。 数组的下标：数组元素的位置。
▪ 一维数组 ▪ 二维数组 ▪ 多维数组
注意：
(1)C语言的数组定义下标从0开始。 (2) 数组的处理相比其它复杂的结构要简单。
教学目标
（1） 了解数组的逻辑结构和存储表示；掌握数组在以 行/列为主的存储结构中的地址计算方法；
（2） 掌握特殊矩阵的压缩存储方式及下标变换公式； （3） 了解稀疏矩阵压缩存储方法的特点和适用范围，
理解以三元组表示的稀疏矩阵进行矩阵运算采用的处理 方法；
（4） 掌握广义表的结构特点极其存储表示方法，以及 对非空广义表进行分解的两种分析方法。
5.2 数组的顺序表示和实现
存储结构的选择:
由于对数组一般不做插入和删除操作，也就是说，数组 一旦建立，结构中的元素个数和元素间的关系就不再发 生变化。因此，一般都是采用顺序存储的方法来表示数 组。
由于计算机的内存结构是一维的，因此用一维内存来表 示多维数组，就必须按某种次序将数组元素排成一列序 列，然后将这个线性序列存放在存储器中。