数据结构第五章wyz.ppt

西安科技大学精品课程 第5章 数组和广义表 1．教学目的： 掌握数组和广义表的定义、特点及典型算法。 2．教学要求： ①掌握数组在以行为主的存储结构中的地址计算方法。 ②掌握矩阵实现压缩存储时的下标变换。 ③理解稀疏矩阵的两种存储方式的特点和适用范围，领会以三元组表示稀疏矩阵时进行运算采用的处理方法。 ④掌握广义表的定义及其存储结构，学会将广义表分解为表头，表尾的方法。 3．教学重点： ①掌握特殊矩阵的压缩存储。 ②掌握稀疏矩阵采用三元组存储时典型算法的实现。 ③广义表的定义、运算。 4．教学难点： 数组的十字链表存储结构。 第5章 数组和广义表 5.1 数组 5.2 特殊矩阵的压缩存储 5.3 稀疏矩阵的压缩存储 5.4 广义表 5.1 数组 5.1.1 数组的逻辑结构 特点：元素本身可以是具有某种结构的数据，但属于同一数据类型。 数组是非常有用的数据结构，几乎所有的高级程序设计语言都提供了数组类型。 比如：一维数组可以看作一个线性表，二维数组可以看作“数据元素是一维数组”的一维数组，依此类推。 如图是一个m行n列的二维数组 矩阵Am×n看成n个列向量的线性表 ， 推广： n维数组—每个数据元素受n个关系的约束，任一单个关系，仍是线性关系。 也可看成m个行向量的线性表 Am×n= a11 a12 … a1j … a1n a21 a22 … a2j … a2n ai1 ai2 … aij … ain … … … … … … … … am1 am2 … amj … amn B = ( βi β2 β1 βm … … a11 a12 … a1j … a1n a21 a22 … a2j … a2n ai1 ai2 … aij … ain am1 am2 … amj … amn … … … … … … … … Am×n= a11 a12 … a1j … a1n a21 a22 … a2j … a2n ai1 ai2 … aij … ain am1 am2 … amj … amn Am×n= … … … … … … … … A=(α 1 α 2 … α j …α n ) 通过以上分析可总结出数组具有以下性质： ⑴ 数组中数据元素数目固定。 ⑵ 数组中数据元素具有相同的数据类型。 ⑶ 数组中每一个数据元素由唯一的一组下标来标识。 ⑷ 数组是随机存取的存储结构。 在数组上不能做插入、删除数据元素的操作。 通常在各种高级语言中，数组一旦被定义，每一维的大小及上下界都不能改变。 ⑴ 取值操作：给定一组下标，读其对应的数据元素。 ⑵ 赋值操作：给定一组下标，存储或修改其相对应的数据元素。 两种操作： 二维数组形式化表示为： A=(D,R) D={a0,0,a0,1,……a0,m,……,am-1,n-1} R={Row,Col} Row={a0,0,a0,1,a0,1,a0,2……,……a0,n-2,a0,n-1,a1,0,a1,1……} Col ={ a0,0,a1,0,a1,0,a2,0……,……an-2,0,an-1,0,a0,1,a1,1……｝ 其中 Row是行关系，Col是列关系 5.1.2 数组的存储结构 数组的顺序存储结构有两种： 1. 按行序存储。如：BASIC、 COBOL和PASCAL语言。 2. 按列序存储。如：FORTRAN语言。 a23 a22 a21 a13 a12 a11 a23 a22 a21 a13 a12 a11 a23 a13 a22 a12 a21 a11 (a) 2×3数组的逻辑状态 (b) 以行为主序 (c) 以列为主序 图5.2 2×3数组的物理状态 设数组的基址为LOC(a11)，每个数组元素占据k个地址单元，那么aij的物理地址计算： 设有二维数组Amn，按元素的下标求其地址的计算： 2 以“以列为主序”的分配比例： LOC(aij)=LOC(a11)+((j-1)*m+(i-1))*k 1 以“以行为主序”的分配为例： LOC(aij)=LOC(a11)+((i-1)*n+j-1)*k 3在C语言中，数组中每一维的下界定义为0，则： LOC(aij)=LOC(a00)+(i*n+j)*k 在矩阵A中求出每一行的最小值元素，然后判