安徽理工大学：《数据结构》课程教学资源（PPT课件讲稿，C语言版，2018）第5章 数组和广义表

第五章数组和广义表 学习要点 掌握数组在以行序为主的存储 中的地址计算方法。 掌握特殊矩阵和稀疏矩阵的存 储方法。 掌握广义表的结构特点及其存 储表示方法

第五章 数组和广义表 • 学习要点 ▪掌握数组在以行序为主的存储 中的地址计算方法。 ▪掌握特殊矩阵和稀疏矩阵的存 储方法。 ▪掌握广义表的结构特点及其存 储表示方法

5.1数组的类型定义 5.2数组的顺序表示和实现 5.3矩阵的压缩存储 5.4广义表的类型定义 5.5广义表的表示方法

5.1 数组的类型定义 5.3 矩阵的压缩存储 5.2 数组的顺序表示和实现 5.4 广义表的类型定义 5.5 广义表的表示方法

5.1数组的类型定义 数组的定义 数组是由下标和值组成的序对的有限 集合。数组中每组有定义的下标，都存 在一个与其对应的值，这个值称为数组 元素。即数组中的每个数据元素都对应 一组下标(j12,j),每个下标的取值 范围是0≤j<b,b称为第维的长度 (i=1,2,.,n)。 当n=1时，n维数组就蜕 化为定长的线性表

5.1 数组的类型定义 数组的定义： 数组是由下标和值组成的序对的有限 集合。数组中每组有定义的下标，都存 在一个与其对应的值，这个值称为数组 元素。即数组中的每个数据元素都对应 一组下标( j1 ,j2 ,…,jn )，每个下标的取值 范围是0≤ji< bi，bi称为第i维的长度 ( i=1,2,…,n)。 当n=1时，n维数组就蜕 化为定长的线性表

ADT Array 数据对象： D={ajlj=0,…,b1,i=1,2,,n 数据关系： R={R1,R2,,Rn} Ri={a,j,小，8，j+1,>|0≤jk≤bk-1, 1≤k≤n且k≠i,0≤j≤b-2,i=2,,n} 基本操作： }ADT Array

ADT Array { 数据对象： D＝{aj 1,j 2, ...,,ji, ...,j n | ji =0,...,bi -1, i=1,2,..,n } 数据关系： R＝{R1, R2, ..., Rn} Ri＝{ | 0  jk  bk -1, 1  k  n 且k  i, 0  j i  bi -2, i=2,...,n } } ADT Array 基本操作:

二维数组的定义： 数据对象： D=ai 0sisb-1,0 sjsb2-1 数据关系： R=ROW,COL ROW ={<aij,ait1j 0sisb-2,0sjsb2-1 COL={aij,ai+0sisb-1,0sjsb2-2}

二维数组的定义: 数据对象: D = {aij | 0≤i≤b1 -1, 0 ≤j≤b2 -1} 数据关系: R = { ROW, COL } ROW = {| 0≤i≤b1 -2, 0≤j≤b2 -1} COL = {| 0≤i≤b1 -1, 0≤ j≤b2 -2}

例如，对于如下形式的m*n阶矩阵， 可以用二维数组表示： a01 (a10 a11 …a1n-1 mxn ●●● (am-10 am-ll…am-ln-l) A=(a0,a1,…,ap (p=n-1或m-1)

例如,对于如下形式的m*n阶矩阵， 可以用二维数组表示： A=(a0 ,a1 ,…,ap ) (p=n-1或m-1) Am×n = a00 a01 … a0n-1 a10 a11 … a1n-1 … … … … am-10 am-11 … am-1n-1 ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )

5.2数组的顺序表示和实现 类型特点： 1)只有引用型操作，没有加工型操作 2)数组是多维的结构，而存储空间是 一个一维的结构。 有两种顺序映象的方式： 1)以行序为主序： 2)以列序为主序

5.2 数组的顺序表示和实现 类型特点: 1) 只有引用型操作，没有加工型操作； 2) 数组是多维的结构，而存储空间是 一个一维的结构。 有两种顺序映象的方式: 1)以行序为主序； 2)以列序为主序

按列序为主序存放 0 aoo 1 a40 20 …a0,n-1 3me40 m a10 .a1n-1 am am-1,0am-1,1…am-1,n-1 2m-1 m44 ao.n4 Loc(ai)=Loc(a00)+( )XL m*n-1 am-1n-1

按列序为主序存放 0 1 m-1 m*n-1 m 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 2m-1 ?

0 aoo 按行序为主序存放 1 ao1 3o0 01.a0,n1 a0,4 n a10 …a1,ns am-1,0am-1,1…am-1,n-1 2n-1 a n=1 am4,0 Loc(aii)=Loc(a0o)+()X L am11 m*n-1

按行序为主序存放 0 1 n-1 m*n-1 n Loc( aij )= Loc( a00 ) + ( i×n + j )× L a00 a01 … a0,n-1 a10 a11 … a1,n-1 … am-1,0 am-1,1 … am-1,n-1 2n-1 a00 a01 … a0,n-1 a10 a11 … a1,n-1 … … … … am-1,0 am-1,1 … am-1,n-1 ?

以“行序为主序”的存储映象 例如： a0.0 a0,1 a02 ao.o a,1 a0.2a1,0 a1.1 a12 a1,0 a1,2 二维数组A中任一元素a,的存储位置 LOC(i,j)=LOC(0,0)+(b2×i+j)×L 称为基地址或基址

例如： 称为基地址或基址。 以“行序为主序”的存储映象 二维数组A中任一元素ai,j 的存储位置 LOC(i,j) = LOC(0,0) + (b2×i＋j)× a0,1 a0,0 a0,2 a1,0 a1,1 a1,2 a0,1 a0,0 a0,2 a1,0 a1,1 a1,2 L L