文档介绍：数据结构
刘家芬 Sept 2011
第五章数组和广义表
数组是大家非常熟悉的数据结构,可以看成是一种特殊形式的线性表。
广义表是另一种特殊形式的线性表,在许多方面有广泛的应用。
数组和广义表的特殊性在于:表中的元素本身也是一种数据结构。
本章目标
数组的定义
数组的顺序表示和实现
矩阵的压缩存储
特殊矩阵
稀疏矩阵
广义表的定义
广义表的存储结构
数组的定义
数组的程序设计语言定义
int a[10]; int b[3][5];
数组是由n(n>1)个具有相同数据类型的数据元素a1,a2,…,an组成的有序序列,且该序列必须存储在一块地址连续的存储单元中。
数组中的数据元素具有相同数据类型。
数组是一种随机存取结构,给定一组下标,就可以访问与其对应的数据元素。
数组中的数据元素个数是固定的。
多维数组的抽象数据类型定义
n维数组
n维数组中有b1b2 … bn个数据元素,每个数据元素都受到n维关系的约束。
数组中的每个数据元素都对应于一组下标,每个下标的取值范围是0≤ji≤bi-1,称为第i维的长度。
n=1时,n维数组是一个定长的线性表。
n维数组的直观定义
设二维数组A=(aij)mn,则
A=(α0,α1,…,αp) (p=m-1或n-1)
其中每个数据元素αj是一个列向量(线性表) :
αj =(a0j ,a1j ,…,am-1,j) 1≦j≦n-1
或是一个行向量:
αi =(ai0 ,ai0 ,…,ai,n-1) 1≦i≦m-1
a00 a01 … a0,n-1
a10 a11 … a1,n-1
……………
am-1,0 am-1,1 …am-1,n-1
A=
数组一般不做插入和删除操作,也就是说,数组一旦建立,结构中的元素个数和元素间的关系就不再发生变化。因此,一般都是采用顺序存储的方法来表示数组。
问题:计算机的内存结构是一维地址结构,对于多维数组,将其映射到一维结构时,有个次序约定问题。
即必须按某种次序将数组元素排成一列序列,然后将这个线性序列存放到内存中。
数组的顺序存储
通常有两种顺序存储方式:
以行序为主序(Row Major Order) :将数组元素按行排列,第i+1个行向量紧接在第i个行向量后面。
PASCAL、C是按行优先顺序存储的。
以列序为主序(Column Major Order) :将数组元素按列向量排列,第j+1个列向量紧接在第j个列向量之后。
FORTRAN是按列优先顺序存储的
数组的顺序存储
对n维数组A=(aj1 j2…jn) ,LOC[a0,0, …, 0]表示元素a0,0, …, 0的地址。假设每个数据元素占L个存储单元,若以行序为主序存储,n维数组中任一元素aj1 j2… jn的地址是:
LOC[aj1j2…jn]=LOC[a0,0, …, 0]+
[(b2…bn)j1+ (b3…bn)j2+ …+ bn(jn-1-1) + (jn-1)] L