数据结构—第五章 数组和广义表1.ppt

第五章数组和广义表
数组的类型定义
矩阵的压缩存储
数组的顺序表示和实现
广义表的类型定义
广义表的存储结构
学****提要:
,并掌握数组在以行为主的存储结构中的地址计算方法。
。
,领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。
。
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
基本操作:
数组的类型定义
基本操作:
InitArray(&A, n, bound1, ..., boundn)
DestroyArray(&A)
Value(A, &e, index1, ..., indexn)
Assign(&A, e, index1, ..., indexn)
InitArray(&A, n, bound1, ..., boundn)
操作结果:若维数 n 和各维长度合法,
则构造相应的数组A,并
返回OK。
DestroyArray(&A) 操作结果:销毁数组A。
Value(A, &e, index1, ..., indexn)
初始条件:A是n维数组,e为元素变量,
随后是n 个下标值。
操作结果:若各下标不超界,则e赋值为
所指定的A 的元素值,并返
回OK。
Assign(&A, e, index1, ..., indexn)
初始条件:A是n维数组,e为元素
变量,随后是n 个下标值。 操作结果:若下标不超界,则将e的
值赋给所指定的A的元
素,并返OK。
二维数组的定义:
数据对象:
D = {aij | 0≤i≤b1-1, 0 ≤j≤b2-1}
数据关系:
R = { ROW, COL }
ROW = {<ai,j,ai,j+1> | 0≤i≤b1-2, 0≤j≤b2-1}
COL = {<ai,j,ai+1,j> | 0≤i≤b1-1, 0≤ j≤b2-2}
二维数组的定义:
数组的顺序表示和实现
类型特点:
(1) 只有引用型操作,没有加工型操作;
(2) 数组是多维的结构,而存储空间是
一个一维的结构。
有两种顺序映象的方式:
(1)以行序为主序
(2)以列序为主序