第四章数组 数组可以看成是一种特殊的线性表。即线性表中数 据元素本身也是一个线性表 §4.1数组的定义和特点 ★定义 mxn ( a ★数组特点 今数组结构固定 今数据元素同构 ★数组运算 心给定一组下标,存取相应的数据元素 今给定一组下标,修改数据元素的值
第四章 数组 数组可以看成是一种特殊的线性表，即线性表中数 据元素本身也是一个线性表 §4.1 数组的定义和特点 定义 = m m mn n n m n a a a a a a a a a A ... ... ... ... ... ... ... ... ... ... ... 1 2 21 22 2 11 12 1 数组特点 ❖数组结构固定 ❖数据元素同构 数组运算 ❖给定一组下标，存取相应的数据元素 ❖给定一组下标，修改数据元素的值 ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )
§4.2数组的顺序存储结构 ★次 a 今 按列序为主序存放 a 21 m1 a12 a 11a12 a a 22 a21a22 a 2n a 2 a m mn a a 2n 0c(aij)=Loc(a11)+(-1)m+(i-1)1 mn n
§4.2 数组的顺序存储结构 次序约定 ❖以行序为主序 ❖以列序为主序 a11 a12 …….. a1n a21 a22 …….. a2n am1 am2 …….. amn …………………. Loc( aij)=Loc(a11)+[(i-1)n+(j-1)]*l 按行序为主序存放 amn …….. am2 am1 ………. a2n …….. a22 a21 a1n ……. a12 0 a11 1 n-1 m*n-1 n 按列序为主序存放 0 1 m-1 m*n-1 m amn …….. a2n a1n ………. am2 …….. a22 a12 am1 ……. a21 a11 a11 a12 …….. a1n a21 a22 …….. a2n am1 am2 …….. amn …………………. Loc(aij)=Loc(a11)+[(j-1)m+(i-1)]*l
§4.3矩阵的压缩存储 ★对称矩阵 a11a12 ●。●●0● 21 a 22······a2n n nn 按行序为主序: all a21 a22 a31 a32 ann 234 (n+1)2 kJ(-1)/2+/-1,i2J j(j-1)/2+i-1,i<j
§4.3 矩阵的压缩存储 对称矩阵 − + − − + − = j j i i j i i j i j k ( 1)/ 2 1, ( 1)/ 2 1， a11 a12 …. … ….. a1n a21 a22…….. ……. a2n an1 an2 …….. ann …………………. a11 a21 a22 a31 a32 …... an1 …... ann k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序：
★三角矩阵 a100 21a 22 0 0 nlan2an3……a nn 按行序为主序 all a21 a22 a31 a32 anI n(n-1)/2n(n+1)2-1 Loc(aij)=Loc(a11+It+g-D)*I
三角矩阵 a11 0 0 …….. 0 a21 a22 0 …….. 0 an1 an2 an3…….. ann …………………. 0 Loc(aij)=Loc(a11)+[( +(j-1)]*l i(i-1) 2 a11 a21 a22 a31 a32 …... an1 …... ann k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序：
★对角矩阵 1a120 a 0 21a a 22a23 0 0a32a33a340 00 1,n-2 -1,n-1am-1,n 00 n,n-1 nn 按行序为主序 all a12 a21 a22 a23 ann-1 ann 34 (n-1)2n(n+1)/2 Loc(ai)=Loc(a1)+2(i-1)+(-1)
对角矩阵 a11 a12 0 …………… . 0 a21 a22 a23 0 …………… 0 0 0… an-1,n-2 an-1,n-1 an-1,n 0 0 … …an,n-1 ann. 0 a32 a33 a34 0 ……… 0 …………………………… Loc(aij)=Loc(a11)+2(i-1)+(j-1) a11 a12 a21 a22 a23 …... …... ann-1 ann k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序：
4.1数组的定 数组可看成是一种特殊的线性表,其特殊在于, 表中的数所元素本身也是一种线性表。 数组是我们最熟悉的数据类型,在早期的高级 语言中,数组是唯一可供使用的数据类型。由 于数组中各元素具有统一的类型,并且数组元 素的下标一般具有固定的上界和下界,因此 数组的处理比其它复杂的结构更为简单。多维 数组是向量的推广。例如,二维数组 1112 a 1n a21a22 cn mn am1 am2 .. amn
数组可看成是一种特殊的线性表，其特殊在于， 表中的数所元素本身也是一种线性表。 数组是我们最熟悉的数据类型，在早期的高级 语言中，数组是唯一可供使用的数据类型。由 于数组中各元素具有统一的类型，并且数组元 素的下标一般具有固定的上界和下界，因此， 数组的处理比其它复杂的结构更为简单。多维 数组是向量的推广。例如，二维数组： a11 a12 … a1n a21 a22 … a2n … … … … am1 am2 … amn Amn = 4.1 数组的定义
可以看成是由个行向量组成的向量,也可以看成是 个列向量组成的向量。 在C语言中,一个二维数组类型可以定义为其分量 类型为一维数组类型的一维数组类型,也就是说, typedef elemtype array2[m][n] 等价于 typedef elemtype array[n] typedef arrayl array2[m] 同理,一个维数组类型可以定义为其数据元素为维 数组类型的一维序组类型。 数组一旦被定义,它的维数和维界就不再改变。因 此,除了结构的初始化和销毁之外,数组只有存取 元素和修改元素值的操作
可以看成是由个行向量组成的向量，也可以看成是 个列向量组成的向量。 在C语言中，一个二维数组类型可以定义为其分量 类型为一维数组类型的一维数组类型，也就是说， typedef elemtype array2[m][n]; 等价于： typedef elemtype array1[n]; typedef array1 array2[m]; 同理，一个维数组类型可以定义为其数据元素为维 数组类型的一维序组类型。 数组一旦被定义，它的维数和维界就不再改变。因 此，除了结构的初始化和销毁之外，数组只有存取 元素和修改元素值的操作
2数组的顺序表示和实现 由于计算机的内存结构是—维的,因此用 维内存来表示多维数组,就必须按某种次序 将数组元素排成一列序列,然后将这个线性 序列存放在存储器中。 又由于对数组一般不做插入和删除操作, 也就是说,数组一旦建立,结构中的元素个 数和元素间的关系就不再发生变化。因此 一般都是采用顺序存储的方法来表示数组
2 数组的顺序表示和实现 由于计算机的内存结构是一维的，因此用一 维内存来表示多维数组，就必须按某种次序 将数组元素排成一列序列，然后将这个线性 序列存放在存储器中。 又由于对数组一般不做插入和删除操作， 也就是说，数组一旦建立，结构中的元素个 数和元素间的关系就不再发生变化。因此， 一般都是采用顺序存储的方法来表示数组
通常有两种顺序存储方式 (1)行优先顺序—将数组元素按行排列,第i+1个行 向量紧接在第个行向量后面。以二维数组为例,按 行优先顺序存储的线性序列为: a11,a12a1na21a22…a2n……,am1am2,amn 在 PASCAL、C语言中,数组就是按行优先顺序存 储的。 (2)列优先顺序—将数组元素按列向量排列,第j+1 个列向量紧接在第个列向量之后,A的m*个元素 按列优先顺序存储的线性序列为 a11a21…am1,a12a22…am2〃……an1an2……anm 在 FORTRAN语言中,数组就是按列优先顺序存储的
通常有两种顺序存储方式： ⑴行优先顺序——将数组元素按行排列，第i+1个行 向量紧接在第i个行向量后面。以二维数组为例，按 行优先顺序存储的线性序列为： a11,a12,…,a1n,a21,a22,…a2n,……,am1,am2,…,amn 在PASCAL、C语言中，数组就是按行优先顺序存 储的。 ⑵列优先顺序——将数组元素按列向量排列，第j+1 个列向量紧接在第j个列向量之后，A的m*n个元素 按列优先顺序存储的线性序列为： a11,a21,…,am1,a12,a22,…am2,……,an1,an2,…,anm 在FORTRAN语言中，数组就是按列优先顺序存储的
以上规则可以推广到多维数组的情况:优先 顺序可规定为先排最右的下标,从右到左, 最后排最左下标:列优先顺序与此相反, 先排最左下标,从左向右,最后排最右下 按上述两种方式顺序存储的序组,只要 知道开始结点的存放地址(即基地址), 维数和每维的上、下界,以及每个数组元 素所占用的单元数,就可以将数组元素的 存放地址表示为其下标的线性函数。因此 数组中的任一元素可以在相同的时间内存 取,即顺序存储的数组是一个随机存取结 构
以上规则可以推广到多维数组的情况：优先 顺序可规定为先排最右的下标，从右到左， 最后排最左下标：列优先顺序与此相反， 先排最左下标，从左向右，最后排最右下 标。 按上述两种方式顺序存储的序组，只要 知道开始结点的存放地址（即基地址）， 维数和每维的上、下界，以及每个数组元 素所占用的单元数，就可以将数组元素的 存放地址表示为其下标的线性函数。因此， 数组中的任一元素可以在相同的时间内存 取，即顺序存储的数组是一个随机存取结 构