学习要求 第五章数组和广义表 ■掌握数组在以行序为主的存储中的地址计算方法。 ■掌握特殊矩阵和稀疏矩阵的存储方法。 ■掌握广义表的结构特点及其存储表示方法。 -1 1945
— 1— — 1— 学习要求 掌握数组在以行序为主的存储中的地址计算方法。 掌握特殊矩阵和稀疏矩阵的存储方法。 掌握广义表的结构特点及其存储表示方法。 第五章 数组和广义表
目录页 Contents Page 数组的定义 第五章数组 数组的顺序表示和实现 和广义表 矩阵的压缩存储 广义表的定义 广义表的存储结构 -2 1945
— 2— — 2— Contents Page 目录页 数组的顺序表示和实现 矩阵的压缩存储 数组的定义 广义表的定义 广义表的存储结构
5.1 数组的定义 数组的定义 >数组是由下标和值组成的序对的有限集合。 >数组中每组有定义的下标，都存在一个与其 对应的值，这个值称为数组元素。 >数组中的每个数据元素都对应一组下标 (j1j2j),每个下标的取值范围是0≤j<b, b称为第维的长度(=1,2，，n)。 > 当n=1时，n维数组就蜕化为定长的线性表。 数组可看成是一种特殊的线性表，线性表中 的数据元素本身也是一个数据结构。 1945
— 3— 5.1 数组的定义 数组的定义 数组是由下标和值组成的序对的有限集合。 数组中每组有定义的下标，都存在一个与其 对应的值，这个值称为数组元素。 数组中的每个数据元素都对应一组下标 ( j1,j2,…,jn)，每个下标的取值范围是0≤ji<bi， bi称为第i维的长度( i=1,2,…,n)。 当n=1时，n维数组就蜕化为定长的线性表。 数组可看成是一种特殊的线性表，线性表中 的数据元素本身也是一个数据结构
5.1数组的定义 ADT Array 数据对象： D={aj1j2,ji…jnlj:=0,…,b-1,i=l,2,,n} 数据关系： R={R1,R2,,Rn} Ri={aj1-jijn,aj,jitl,jn>|0≤jk≤bk-l, 1≤k≤n且k≠i,0≤j:≤b-2,i=2,,n} 基本操作： ADT Array 4 145
— 4— 5.1 数组的定义 ADT Array { 数据对象： D＝{aj1,j2, ...,,ji, ...,jn| ji =0,...,bi -1, i=1,2,..,n } 数据关系： R＝{R1, R2, ..., Rn} Ri＝{<aj1,... ji,... jn , aj1, ...ji+1, ...jn > | 0 jk bk -1, 1 k n且k i, 0 ji bi -2, i=2,...,n } 基本操作: } ADT Array
5.1 数组的定义 ■一维数组 0123456789 35 2749 18 60 54 77 83 41 02 L L0C0-C i=0 -5 Y食ee 1945
— 5— 5.1 数组的定义 一维数组 35 27 49 18 60 54 77 83 41 02 0 1 2 3 4 5 6 7 8 9 LOC(i) = LOC(i-1)+L = a+i*L, i > 0 a, i = 0 a L