资源描述：
《《数据结构》数组和广义表》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第5章数组和广义表5.1数组的定义与运算5.2数组的顺序存储结构5.3矩阵的压缩存储5.4广义表习题5.1数组的定义与运算数组定义：类似于线性表，一个两维数组的逻辑结构可形式地表示为2_Array=(D,R)其中D={aij
2、i=0,1,…,m-1,j=0,1,…,n-1}，aij是同类型数据元素的集合。R={ROW,COL}是数据元素上关系的集合。ROW={
3、0≤i≤m-1,0≤j≤n-2}每一行上的列关系。COL={
4、0≤i≤m-2,0≤j≤n-1}每一个列上的行关系。 行列关系跟线性表已经大不相同了,见图5.1所示。a01a02…a0n
5、-1a11a12…a1n-1…………am-11am-12…am-1n-1图5.1二维数组元素关系二维数组中的每一个元素aij都受到两个关系的约束：ROW(行关系)和COL(列关系)。aij+1是aij在行关系中的直接后续元素；而ai+1j是aij在列关系中的直接后续元素。和线性表一样，所有的数据元素属于同一数据类型。每个数据元素对应于一组下标(i,j)。将这个概念依次类推，可以写出n维数组的逻辑结构，但最常用的是二维数组。也可以从另一个角度来定义二维数组，即将二维数组看成这样一个线性表：它的每一个数据元素是一个线性表(一维数组)。例如，图5.1所示的是一个二维数组，以m行n列的矩阵形式
6、表示。它可以看成是一个线性表：A=(α0,α1,α2,α3,…,αP)(p=m-1或n-1)其中每一个数据元素αj是一个列向量的线性表αj=(a0j,a1j,a2j,…,am-1j)或者αi是一个行向量的线性表：αi=(ai0,ai1,ai2,…,ain-1)这种定义二维数组的方法也可以推广到n维数组，即认为n维数组是一个线性表，它的每一个数据元素是一个n-1维数组。 在数组结构最常用的操作：给定数组的下标i，对相应元素ai作取数、赋值的操作，操作方法根据其存储结构决定。5.2数组的顺序存储结构由于数组一般不作插入或删除操作，也就是说，一旦建立了数组，则结构中的数据元素个数和元素之间的
7、关系就不再发生变动，因此，采用顺序存储结构表示数组。顺序结构即是用一组连续的存储单元来存放数组结构。内存地址是一维的，而数组结构可能是多维的。如何将多维的数组挤入一维的地址中，就有了策略问题：按行序为主序(rowmajororder)。首先，存放数组的第一行，然后，按顺序存放数组的各行；按列序为主序(columnmajororder)。首先，存放数组的第一列，然后，按顺序存放数组的各列，如图5.2所示。大多数程序设计语言是按行主序来排列数组元素的，但列主序也是常见的。(a)二维数组(b)行序(c)列序图5.2二维数组的两种存储方式数组的顺序存储方式，给对数组元素的随机存取带来方便。因为
8、，数组是同类型数据元素的集合，所以，每一个数据元素所占用的内存空间的单元数是相同的，故只要给出首地址，可以使用统一的地址公式，求出数组中任意元素的地址。这里以二维数组的行主序为例，讨论数组元素的地址计算方法。 二维数组aij(m×n)LOC(i,j)=LOC(0,0)+(i×n+j)×s(0≤i≤m-1,0≤j≤n-1)其中，s是每个数据元素所占存储单元的个数。 可将二维数组的元素想象为一个一维数组，大小为p，则推出三维数组的地址计算方法。 三维数组aijk(m×n×p)：LOC(i,j,k)=LOC(0,0,0)+(i×n+j)×s×p+k×sLOC(i,j,k)=LOC(0,0,0
9、)+(i×n×p+j×p+k)×s (0≤i≤m-1,0≤j≤n-1，0≤k≤p-1)可将概念依次类推，可以写出n维数组地址计算方法。5.3矩阵的压缩存储在工程应用中，矩阵有着重要的作用。许多实际问题的解决需要大量数据的综合计算，而这些大量数据之间总是表现出二维数组的逻辑结构。而这种二维数组结构在数学上称为矩阵。 为了使矩阵的各种运算能有效地进行，必须在算法的空间和时间复杂度上下功夫。首先我们考虑如何减少空间复杂度，即找一种高效的存储方法，再在相应的存储结构上找高效的算法。许多矩阵的数据分布是有特征的，那就要利用这种特征，尽量减少数据的存储量。5.3.1特殊矩阵a.对称矩阵定义：若有一
10、个n阶矩阵A中的元素满足下述性质aij=aji1≤i,j≤n则称为n阶对称矩阵。对称矩阵可以只给每一对对称元素分配一个存储空间，则可将n×n的二维矩阵，压缩存储到n(n+1)/2个元的空间中。在这里讨论以行序为主序存储其下三角(包括对角线)中的对称矩阵元素。假设以一维数组s[n(n+1)/2]作为n阶对称矩阵A的存储结构，数组元素s[k]于矩阵元素aij之间转换公式如下。存储示意：对于任意给出的数组下标(i,j)，均可以在sa[]中找到矩阵元素
