学习要求 第五章数组和广义表 ■掌握数组在以行序为主的存储中的地址计算方法。 ■掌握特殊矩阵和稀疏矩阵的存储方法。 ■掌握广义表的结构特点及其存储表示方法。 -1 1945
— 1— — 1— 学习要求 掌握数组在以行序为主的存储中的地址计算方法。 掌握特殊矩阵和稀疏矩阵的存储方法。 掌握广义表的结构特点及其存储表示方法。 第五章 数组和广义表
目录页 Contents Page 数组的定义 第五章数组 数组的顺序表示和实现 和广义表 矩阵的压缩存储 广义表的定义 广义表的存储结构 -2 1945
— 2— — 2— Contents Page 目录页 数组的顺序表示和实现 矩阵的压缩存储 数组的定义 广义表的定义 广义表的存储结构
5.1 数组的定义 数组的定义 >数组是由下标和值组成的序对的有限集合。 >数组中每组有定义的下标，都存在一个与其 对应的值，这个值称为数组元素。 >数组中的每个数据元素都对应一组下标 (j1j2j),每个下标的取值范围是0≤j 当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＝{ | 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
5.1数组的定义 ■二维数组 (C11 02 A=(a,2,…,&n）(p=m或n) A」 021 02 a2n) mxn 每个元素是行向量 a=(a1,a2,…,am）1≤i≤m 【ami am2 ·amn a11 12 021 022 每个元素是列向量 Amxn 02n j=(a1y,a2j,…,am）1≤j≤n a m2 mn
— 6— 5.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 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 j ( a1 j ,a 2 j ,,amj ) 1 j n i ( ai1,ai2 ,,ain ) 1 i m ( , , , ) (p m n) A 1 2 p 或 每个元素是行向量 每个元素是列向量 ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )
目录页 Contents Page 数组的定义 第五章数组 数组的顺序表示和实现 和广义表 矩阵的压缩存储 广义表的定义 广义表的存储结构 一7 1945
— 7— — 7— Contents Page 目录页 数组的顺序表示和实现 矩阵的压缩存储 数组的定义 广义表的定义 广义表的存储结构
5.2数组的顺序表示和实现 类型特点 1)只有引用型操作，没有加工型操作 2)数组是多维的结构，而存储空间是一个一 维的结构 ■有两种顺序映象的方式 1)以行序为主序 2)以列序为主序 -8- 145
— 8— 5.2 数组的顺序表示和实现 类型特点 1) 只有引用型操作，没有加工型操作 2) 数组是多维的结构，而存储空间是一个一 维的结构 有两种顺序映象的方式 1) 以行序为主序 2) 以列序为主序
5.2 数组的顺序表示和实现 ■数组是多维的结构，存储空间是一个一维的结构 >二维数组以行序为主序 >二维数组以列序为主序 2 3 3 1 3 4 4 5 6 8 5 5 9 10 11 12 6 6 7 7 10 8 8 2 5 8 11 9 3 6 9 12 10 10 11 11 0 -9 12 12 1945
— 9— 5.2 数组的顺序表示和实现 数组是多维的结构，存储空间是一个一维的结构 二维数组以行序为主序 二维数组以列序为主序
5.2 数组的顺序表示和实现 >按列序为主序存放 a00 a10 第1列 800 801 a0,n-1 am-10 a10 811 a1,n-1 ao1 au 第2列 .. am-1,0 a m-1,1 m-1,n-1 am-11 。e● L0c(ai)=L0c(ao)+(？ )XL a0,1 a1,n-1 第m列 e。a -10 am-Ln-1 1945
— 10 — 5.2 数组的顺序表示和实现 按列序为主序存放 Loc( aij )= Loc( a00 ) + ( j×m + i )×L a00 a10 … am-1,0 a01 a11 … am-1,1 … a0,n-1 a1,n-1 … am-1,n-1 a00 a01 … a0,n-1 a10 a11 … a1,n-1 … … … … am-1,0 am-1,1 … am-1,n-1 ? 第1列 第2列 第m列 a00 a10 … am-1,0 a01 a11 … am-1,1 … a0,n-1 a1,n-1 … am-1,n-1