第五章数组和广义表 ●51数组的定义 ●52数组的顺序表示和实现 ●53矩阵的压缩存储 ●5.3.1特殊矩阵 ●5.32稀疏矩阵 °54广义表的定义 55广义表的存储结构 北京邮电大学自动化学院
北京邮电大学自动化学院 1 第五章 数组和广义表 ⚫ 5.1 数组的定义 ⚫ 5.2 数组的顺序表示和实现 ⚫ 5.3 矩阵的压缩存储 ⚫ 5.3.1 特殊矩阵 ⚫ 5.3.2 稀疏矩阵 ⚫ 5.4 广义表的定义 ⚫ 5.5 广义表的存储结构
51数组的定义 数组和广义表可看成是一种特殊的线性表,其特殊在于,表 中的所有元素本身也是一种线性表。 数组是我们最熟悉的数据类型,在早期的高级语言中,数组 是唯一可供使用的数据类型。由于数组中各元素具有统一的 类型,并且数组元素的下标一般具有固定的上界和下界,因 此,数组的处理比其它复杂的结构更为简单。多维数组是向 量的推广。例如,二维数组: 2 2 2n mxn 2 mn 北京邮电大学自动化学院
北京邮电大学自动化学院 2 ⚫ 数组和广义表可看成是一种特殊的线性表，其特殊在于，表 中的所有元素本身也是一种线性表。 = m m m n n n m n a a a a a a a a a A 1 2 2 1 2 2 2 1 1 1 2 1 ⚫ 数组是我们最熟悉的数据类型，在早期的高级语言中，数组 是唯一可供使用的数据类型。由于数组中各元素具有统一的 类型，并且数组元素的下标一般具有固定的上界和下界，因 此，数组的处理比其它复杂的结构更为简单。多维数组是向 量的推广。例如，二维数组： 5.1 数组的定义
51数组的定义 二维数组可以看成是由行向量组成的向量,也可以看成是 列向量组成的向量 ●同样,可把三维数组看成是一个线性表,表中每一个数组 元素为一个二维数组。依次类推,可把n维数组看成是一个 线性表,表中每一个数据元素是一个n-1维数组。 数组的运算:数组一旦被定义,它的维数和维界就不再改 变。因此,除了结构的初始化和销毁之外,数组只有存取 元素和修改元素值的操作。 即给定一组下标,存取或修改相应的数组元素。 北京邮电大学自动化学院
北京邮电大学自动化学院 3 ⚫ 二维数组可以看成是由行向量组成的向量，也可以看成是 列向量组成的向量。 ⚫ 同样，可把三维数组看成是一个线性表，表中每一个数组 元素为一个二维数组。依次类推，可把n维数组看成是一个 线性表，表中每一个数据元素是一个n-1维数组。 ⚫ 数组的运算：数组一旦被定义，它的维数和维界就不再改 变。因此，除了结构的初始化和销毁之外，数组只有存取 元素和修改元素值的操作。 ⚫ 即给定一组下标，存取或修改相应的数组元素。 5.1 数组的定义
52数组的顺序表示和实现 ●1、顺序存储结构 顺序存储结构:用一组地址连续的存储单元依次存放数据元 素,称为数组的顺序存储结构。 ●由于计算机的内存结构是一维的,因此用一维内存来表示多 维数组,就必须按某种次序将数组元素排成一列序列,然后 将这个线性序列存放在存储器中。 由于对数组一般不做插入和删除操作,也就是说,数组一旦 建立,结构中的元素个数和元素间的关系就不再发生变化。 因此,一般都是采用顺序存储的方法来表示数组。 北京邮电大学自动化学院 4
北京邮电大学自动化学院 4 ⚫ 1、顺序存储结构 5.2 数组的顺序表示和实现 ⚫ 顺序存储结构：用一组地址连续的存储单元依次存放数据元 素，称为数组的顺序存储结构。 ⚫ 由于计算机的内存结构是一维的，因此用一维内存来表示多 维数组，就必须按某种次序将数组元素排成一列序列，然后 将这个线性序列存放在存储器中。 ⚫ 由于对数组一般不做插入和删除操作，也就是说，数组一旦 建立，结构中的元素个数和元素间的关系就不再发生变化。 因此，一般都是采用顺序存储的方法来表示数组
2、顺序存储方式 通常有两种顺序存储方式: (1)行优先顺序—将数组元素按行排列,第|+1个行向量紧接在 第个行向量后面。以二维数组为例,按行优先顺序存储的线性 序列为:a1,a12…,a1mna21a222n…,amn1,amn2,,lamn ●在 PASCAL、C语言中,数组就是按行优先顺序存储的。 (2)列优先顺序—将数组元素按列向量排列,第j+1个列向量紧 接在第个列向量之后,A的mn个元素按列优先顺序存储的线 性序列为: a1a21…ama12a22yam2yana2ny…,amn ●在 FORTRAN语言中,数组就是按列优先顺序存储的。 北京邮电大学自动化学院
北京邮电大学自动化学院 5 ⚫ 通常有两种顺序存储方式： 2、顺序存储方式 ⚫ ⑴行优先顺序——将数组元素按行排列，第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,……,a1n,a2n,…,amn ⚫ 在FORTRAN语言中，数组就是按列优先顺序存储的