数据结构之数组和广义表.ppt

Chap 5 数组和广义表 5.1 数组类型的定义 5.2 数组的顺序表示和实现 5.3 稀疏矩阵的压缩存储 5.4 广义表的类型 5.5 广义表的表示方法 5.1 数组的类型定义 ADT Array {　数据对象： D＝{aj1,j2,...,ji ,...jN | ji =0,..., bi -1, i=1,2,..,N,　称 N(0)为数组的维数,bi为数组第i维的长度， ji为数组元素的第i维下标，aj1...jN ∈ElemSet }　数据关系： 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,　　　　aj1,...,ji,...,jN , aj1,...ji+1,...,j N∈D, i=2,...,N } 基本操作} 数组中共有b1×b2×…×bn个元素，每个元素都处在 n 个关系中，但因为每个关系本身都是“线性关系”，所以数组也是线性结构。 看一个二维数组的简单情况。 　D={ai,j|0≤i≤m-1,0≤j≤n-1, ai,j ∈ ElemType}　R={ROW,COL}其中： COL ={ai-1,j, ai,j |i=1,…,m-2, 0≤j≤n-1, ai-1,j, ai,j ∈ ElemType}(称作“行关系”) ROW ={ ai,j-1, ai,j |j=1,…,n-2, 0≤i≤m -1, ai,j-1, ai,j ∈ ElemType}　(称作列关系) 和线性表类似，数组中的每个元素都对应于一组下标(j1,j2,…jN)，每个下标的取值范围是0≤ji ≤bi-1 ，称bi为第 i 维的长度(i=1,2,…,N)。 因此，也可以将数组看成是由“一组下标”和“元素值”构成的二元组的集合。 需要注意的是，在此给出的数组定义中，各维下标的下限均约定为常量 0，这只是C语言的限定。在一般情况下，数组每一维的下标ji的取值范围均可设置为任意值的整数。 基本操作 InitArray(A, n, bound1, ..., boundn) DestroyArray(A)　　 Value(A, e, index1, ..., indexn) Assign(A, e, index1, ..., indexn)} ADT Array Value(A, e, index1, ..., indexn) 初始条件： A 是 n 维数组，e 为元素变量,随后是 n 个下标值。 操作结果： 若各下标不超界，则e赋值为所 指定的A的元素值，并返回OK。 Assign(A, e, index1, ..., indexn) 初始条件： A 是 n 维数组，e 为元素变量，随后是 n 个下标值。 操作结果： 若下标不超界，则将 e 的值赋给A中指定下标的元素。 5.2 数组的顺序表示和实现 类型特点 1）只有引用型操作，没有加工型操作 2）数组是多维的结构，而存储空间是一个一维的结构 有两种顺序映像的方式： 1）以行序为主序（低下标优先） 2）以列序为主序（高下标优先） 由于数组中的数据元素之间是一个“多维的关系，而存储地址是一维的，因此数组的顺序存储表示要解决的是一个如何用一维的存储地址来表示多维的关系的问题。 “以列为主”的存储结构是对二维数组进行“按列切分”，即将数组中的数据元素“按列依次排放”在存储器中。 低下标优先变化 a000=A a001=B a002=C a010=D a011=E a012=F a100=G a101=H a102=I a110=J a111=K a112=L a000 = A a100 = G a010 = D a110 = J a001 = B a101 = H A011 = E a111 = K A002 = C a102 = I A012 = F a112 = L 行序为主序 假设二维数组 R[m][n] 中每个数据元素占L个存储地址，并以 LOC(i,j) 表示下标为 (i,j) 的数据元素的存储地址，则该数组中任何一对下标 (i,j) 对应的数据元素 在“以行为主”的顺序映象中的存储地址为：　　　LOC(i,j) = LOC(0,0) + (i×n+j) L ↑  称为数组的基地址或基址