文档介绍：CH5 数组和广义表
数组的定义
数组的顺序表示和实现
矩阵的压缩存储
广义表的定义
广义表的存储结构
数组和广义表可以视为是线性表的扩展,即线性表中的数据元素本身也是一个数据结构。
一维数组可以看作一个线性表,
二维数组可以看作“数据元素是一维数组”的一维数组,
三维数组可以看作“数据元素是二维数组”的一维数组,依此类推。
⒈二维数组定义
┌ a11 a12 … a1n ┐
Am×n= │ a21 a22 … a2n │
│· · │
│· · │
└ am1 am2 … amn ┘
Am×n可定义为一个线性表 A=(a1,a2,…,an), 其中:
每个数据元素aj(j=1,2,…n)又是一个列向量的线性表,
即:aj=(a1j,a2j,…,amj), 1≤j≤n
或者二维数组Amxn可定义为一个线性表:
A=(B1,B2,…,Bm) 其中:每个数据元素Bj又是一个行向量的线性表,即: Bj=(aj1,aj2,…,ajn), 1≤j≤m
即A =(B1,B2,…,Bm)
=((a11,a12,…,a1n),(a21,a22,…,a2n),…,(am1,am2,…,amn))
┌ a11 a12 … a1n ┐
Amxn= │ a21 a22 … a2n │
│· · │
│· · │
└ am1 am2 … amn ┘
类似地,可以定义n维数组。
数组的类型定义
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
基本操作:
二维数组的定义:
数据对象:
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}
基本操作:
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。