第五章 数组和广义表

1第5章数组和广义表主要内容： 数组的基本概念数组的顺序表示和实现 矩阵的压缩存储 广义表的基本概念 广义表的存储结构2数组和广义表概述数组与广义表是线性表的推广从数据结构来看，数组与广义表是线性结构，其特殊之处在于其元素的类型被进行了扩充，是特殊的线性结构。

数组：线性表的元素也是线性表，且元素类型相同 广义表：表的元素既可以是原子，也可以是表，且元素类型可以不同从数据类型来看，数组与广义表的数据元素类型特殊，操作特点也和线性表有很大差异数组不对元素进行插入删除 广义表多采用递归的操作数组和广义表是元素类型被扩充了的特殊线性表3§5.1 数组的定义1. 数组的定义数组：是由一组类型相同的数据元素构成的有序集合，每个数据元素称为一个数组元素。

每个元素受n(n ≥1)个线性关系的约束，或者说每个数据元素是由下标和值组成偶对的一个集合，即在数组中，对于每一个数组元素，总有一组反映其在n 个线性关系中序号的下标[i 1, i 2, ……, i n ]与之对应，这样的数组称为n 维数组。

形式定义：n_ARRAY(D,R)D—数组的元素R=(R 1, R 2, …, R n )，为数组元素间的关系 数组元素每个下标[i 1, i 2, ……, i n ]的取值范围为0≤j i ≤b i -1(i =1,2,...,n )4例如：二维数组2_Array =(D,R )D={ a ij |i =0...m -1, j =0...n -1 } R={Row,Col}Row ={ <a i,j ,a i,j+1>| 0≤i ≤m -1，0≤j ≤n -2 } Col ={ <a i,j ,a i+1,j > | 0≤i ≤m -2，0≤j ≤n -1 }每个数组元素属于同一数据类型，由下标(i,j )唯一确定其位置每一个数组元素a i,j 都受两个关系Row 和Col 的约束Row(行关系)：a i,j+1是a ij 在行关系中的直接后继Col(列关系)：a i+1,j 是a ij 在列关系中的后继元素每个下标i,j 有其限定其范围m -1和n -15N 维数组的抽象类型定义ADT Array{数据对象: D 数据关系: R 基本操作:InitArray(Array &A, int n, int bound[ ]);//bound[ ]= b 1, b 2, ……, b nDestroyArray (Array &A);Value(Array A, ElemType &e, int index[ ]);// index[ ]= i 1, i 2, ……, i nAssign(Array &A, ElemType e, int index[ ]);}ADT Array6数组-线性表的推广数学上：把数组看成向量，多维数组是向量的推广0001020,11011121,11,01,11,21,1n n m n m m m m n a a a a a a a a A a a a a −−×−−−−−⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦00010,110111,111,01,11,1n n n m m m n a a a a a a A a a a −−×−−−−⎡⎤⎡⎤⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦⎣⎦0001020,11011121,111,01,11,21,1[][][]n n m m m m m n a a a a a a a a A a a a a −−×−−−−−⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦例如：二维数组A 可看成m 行向量组成的向量，也可看成n 个列向量组成的向量。