第五章数组和广义表 学习要点 掌握数组在以行序为主的存储 中的地址计算方法。 掌握特殊矩阵和稀疏矩阵的存 储方法。 掌握广义表的结构特点及其存 储表示方法
第五章 数组和广义表 • 学习要点 ▪掌握数组在以行序为主的存储 中的地址计算方法。 ▪掌握特殊矩阵和稀疏矩阵的存 储方法。 ▪掌握广义表的结构特点及其存 储表示方法
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＝{<aj 1 , ... j i , ... j n , aj 1 , ...j i +1, ...j n > | 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 = {<ai,j,ai+1,j>| 0≤i≤b1 -2, 0≤j≤b2 -1} COL = {<ai,j,ai,j+1>| 0≤i≤b1 -1, 0≤ j≤b2 -2}