数据结构-清华大学严蔚敏PPT - 副本 (5)

第5章数组和广义表数组是一种人们非常熟悉的数据结构，几乎所有的程序设计语言都支持这种数据结构或将这种数据结构设定为语言的固有类型。数组这种数据结构可以看成是线性表的推广。科学计算中涉及到大量的矩阵问题，在程序设计语言中一般都采用数组来存储，被描述成一个二维数组。但当矩阵规模很大且具有特殊结构(对角矩阵、三角矩阵、对称矩阵、稀疏矩阵等)，为减少程序的时间和空间需求，采用自定义的描述方式。广义表是另一种推广形式的线性表，是一种灵活的数据结构，在许多方面有广泛的应用。5.1数组的定义数组是一组偶对(下标值，数据元素值)的集合。在数组中，对于一组有意义的下标，都存在一个与其对应的值。一维数组对应着一个下标值，二维数组对应着两个下标值，如此类推。数组是由n(n1)个具有相同数据类型的数据元素a1，a2，…，an组成的有序序列，且该序列必须存储在一块地址连续的存储单元中。◆数组中的数据元素具有相同数据类型。◆数组是一种随机存取结构，给定一组下标，就可以访问与其对应的数据元素。◆数组中的数据元素个数是固定的。5.1.1数组的抽象数据类型定义1抽象数据类型定义ADTArray{数据对象：ji=0,1,…,bi-1,1,2,…,n;D={aj1j2…jn|n0称为数组的维数，bi是数组第i维的长度，ji是数组元素第i维的下标，aj1j2…jn∈ElemSet}数据关系：R={R1,R2,…,Rn}Ri={aj1j2…ji…jn,aj1j2…ji+1…jn|0≦jk≦bk-1，1≦k≦n且k≠i，0≦ji≦bi-2，aj1j2…ji+1…jn∈D}基本操作：……}ADTArray由上述定义知，n维数组中有b1b2…bn个数据元素，每个数据元素都受到n维关系的约束。2直观的n维数组以二维数组为例讨论。将二维数组看成是一个定长的线性表，其每个元素又是一个定长的线性表。设二维数组A=(aij)mn，则A=(α1，α2，…，αp)(p=m或n)其中每个数据元素αj是一个列向量(线性表)：αj=(a1j，a2j，…，amj)1≦j≦n或是一个行向量：αi=(ai1，ai2，…，ain)1≦i≦m如图5-1所示。a11a12…a1na21a22…a2n……………am1am2…amnA=……………A=a11a12…a1na21a22…a2nam1am2…amna11a21┆am1a12a22┆am2a1na2n┆amn┆┆┆A=图5-1二维数组图例形式(a)矩阵表示形式(b)列向量的一维数组形式(c)行向量的一维数组形式5.2数组的顺序表示和实现数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。问题：计算机的内存结构是一维(线性)地址结构，对于多维数组，将其存放(映射)到内存一维结构时，有个次序约定问题。即必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放到内存中。二维数组是最简单的多维数组，以此为例说明多维数组存放(映射)到内存一维结构时的次序约定问题。通常有两种顺序存储方式⑴行优先顺序(RowMajorOrder)：将数组元素按行排列，第i+1个行向量紧接在第i个行向量后面。对二维数组，按行优先顺序存储的线性序列为：a11,a12,…,a1n,a21,a22,…a2n,……,am1,am2,…,amnPASCAL、C是按行优先顺序存储的，如图5-2(b)示。⑵列优先顺序(ColumnMajorOrder)：将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后，对二维数组，按列优先顺序存储的线性序列为：a11,a21,…,am1,a12,a22,…am2,……,an1,an2,…,anmFORTRAN是按列优先顺序存储的，如图5-2(c)。图5-2二维数组及其顺序存储图例形式a11a12…a1na21a22…a2n……………am1am2…amnA=(a)二维数组的表示形式(b)行优先顺序存储(c)列优先顺序存储a11a12…a1n第1行a21a22…a2n第2行am1am2…Amn第m行┆┆……a11a21…am1第1列a12a22…am2第2列a1ma2m…amn第n列┆┆……设有二维数组A=(aij)mn，若每个元素占用的存储单元数为l(个)，LOC[a11]表示元素a11的首地址，即数组的首地址。1以“行优先顺序”存储⑴第1行中的每个元素对应的(首)地址是：LOC[a1j]=LOC[a11]+(j-1)lj=1,2,…,n(2)第2行中的每个元素对应的(首)地址是：LOC[a2j]=LOC[a11]+nl+(j-1)lj=1,2,…,n………⑶第m行中的每个元素对应的(首)地址是：LOC[amj]=LOC[a11]+(m-1)nl+(j-1)lj=1,2,…,n由此可知，二维数组中任一元素aij的(首)地址是：LOC[aij]=LOC[a11]+[(i-1)n+(j-1)]l(5-1)i=1,2,…,mj=1,2,…,n根据(5-1)式，对于三维数组A=(aijk)mnp，若每个元素占用的存储单元数为l(个)，LOC[a111]表示元素a111的首地址，即数组的首地址。以“行优先顺序”存储在内存中。三维数组中任一元素aijk的(首)地址是：LOC(aijk)=LOC[a111]+[(i-1)np+(j-1)p+(k-1)]l(5-2)推而广之，对n维数组A=(aj1j2…jn)，若每个元素占用的存储单元数为l(个)，LOC[a11…1]表示元素a11…1的首地址。则以“行优先顺序”存储在内存中。n维数组中任一元素aj1j2…jn的(首)地址是：LOC[aj1j2…jn]=LOC[a11…1]+[(b2…bn)(j1-1)+(b3…bn)(j2-1)+…+bn(jn-1-1)+(jn-1)]l(5-3)2以“列优先顺序”存储⑴第1列中的每个元素对应的(首)地址是：LOC[aj1]=LOC[a11]+(j-1)lj=1,2,…,m(2)第2列中的每个元素对应的(首)地址是：LOC[aj2]=LOC[a11]+ml+(j-1)lj=1,2,…,m………⑶第n列中的每个元素对应的(首)地址是：LOC[ajn]=LOC[a11]+(n-1)ml+(j-1)lj=1,2,…,m由此可知，二维数组中任一元素aij的(首)地址是：LOC[aij]=LOC[a11]+[(i-1)m+(j-1)]l(5-1)i=1,2,…,nj=1,2,…,m5.3矩阵的压缩存储在科学与工程计算问题中，矩阵是一种常用的数学对象，在高级语言编程时，通常将一个矩阵描述为一个二维数组。这样，可以对其元素进行随机存取，各种矩阵运算也非常简单。对于高阶矩阵，若其中非零元素呈某种规律分布或者矩阵中有大量的零元素，若仍然用常规方法存储，可能存储重复的非零元素或零元素，将造成存储空间的大量浪费。对这类矩阵进行压缩存储：◆多个相同的非零元素只分配一个存储空间；◆零元素不分配空间。5.3.1特殊矩阵特殊矩阵：是指非零元素或零元素的分布有一定规律的矩阵。1对称矩阵若一个n阶方阵A=(aij)nn中的元素满足性质：aij=aji1≦i,j≦n且i≠j则称A为对称矩阵，如图5-3所示。图5-3对称矩阵示例1513730251706135080018926A=a11a21a22a31a32a33…………an1an2…annA=对称矩阵中的元素关于主对角线对称，因此，让每一对对称元素aij和aji(i≠j)分配一个存储空间，则n2个元素压缩存储到n(n+1)/2个存储空间，能节约近一半的存储空间。不失一般性，假设按“行优先顺序”存储下三角形(包括对角线)中的元素。设用一维数组(向量)sa[0…n(n+1)/2]存储n阶对称矩阵，如图5-4所示。为了便于访问，必须找出矩阵A中的元素的下标值（i,j）和向量sa[k]的下标值k之间的对应关系。saa11a21a22a31a32a33…an1an2…annK1234…n(n-1)/2…n(n+1)/2图5-4对称矩阵的压缩存储示例若i≧j：aij在下三角形中，直接保存在sa中。aij之前的i-1行共有元素个数：1+2+…+(i-1)=i(i-1)/2而在第i行上，aij之前恰有j-1个元素，因此，元素aij保存在向量sa中时的下标值k之间的对应关系是：k=i(i-1)/2+j-1i≧j若ij：则aij是在上三角矩阵中。因为aij=aji，在向量sa中保存的是aji。依上述分析可得：k=j(j-1)/2+i-1ij对称矩阵元素aij保存在向量sa中时的下标值k与（i,j）之间的对应关系是：i(i-1)/2+j-1当i≧j时j(j-1)/2+i-1当ij时K=1≦i,j≦n(5-4)根据上述的下标对应关系，对于矩阵中的任意元素aij，均可在一维数组sa中唯一确定其位置k；反之，对所有k=1,2,…,n(n+1)/2，都能确定sa[k]中的元素在矩阵中的位置(i,j)。称sa[0…n(n+1)/2]为n阶对称矩阵A的压缩存储。2三角矩阵以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵的下三角（不包括主对角线）中的元素均为常数c(一般为0)。下三角矩阵正好相反，它的主对角线上方均为常数，如图5-5所示。a11a12…a1nca22…a2ncc…ann………a11c…ca21a22…can1an2…ann………图5-5三角矩阵示例(b)下三角矩阵示例(a)上三角矩阵示例三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到向量sa[0…n(n+1)/2]中，其中c存放在向量的第1个分量中。上三角矩阵元素aij保存在向量sa中时的下标值k与（i,j）之间的对应关系是：下三角矩阵元素aij保存在向量sa中时的下标值k与（i,j）之间的对应关系是：i(i-1)/2+j-1当i≧j时n(n+1)/2当ij时K=1≦i,j≦n(5-5)i(i-1)/2+j-1当i≦j时n(n+1)/2当ij时K=1≦i,j≦n(5-6)3对角矩阵矩阵中，除了主对角线和主对角线上或下方若干条对角线上的元素之外，其余元素皆为零。即所有的非零元素集中在以主对角线为了中心的带状区域中，如图5-6所示。a11a120….0a21a22a230….00a32a33a340….0………….0….00ann-1ann0….0an-1n-2an-1n-1an-1nA=图5-6三对角矩阵示例如上图三对角矩阵，非零元素仅出现在主对角(aii,1≦i≦n)上、主对角线上的那条对角线(aii+1,1≦i≦n-1)、主对角线下的那条对角线上(ai+1i,1≦i≦n-1)。显然，当|i-j|1时，元素aij=0。由此可知，一个k对角矩阵(k为奇数)A是满足下述条件：当|i-j|(k-1)/2时，aij=0对角矩阵可按行优先顺序或对角线顺序，将其压缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。仍然以三对角矩阵为例讨论。当i=1，j=1、2，或i=n，j=n-1、n或1in-1,j=i-1、i、i+1的元素aij外，其余元素都是0。对这种矩阵，当以按“行优先顺序”存储时，第1行和第n行是2个非零元素，其余每行的非零元素都要是3个，则需存储的元素个数为3n-2。saa11a12a21a22a23a32a33a34…ann-1annK12345678…3n-33n-2图5-7三对角矩阵的压缩存储示例如图5-7所示三对角矩阵的压缩存储形式。数组sa中的元素sa[k]与三对角矩阵中的元素aij存在一一对应关系，在aij之前有i-1行,共有3i-1个非零元素，在第i行，有j-i+1个非零元素，这样，非零元素aij的地址为：LOC[aij]=LOC[a11]+[3i-1+(j-i+1)]l=LOC[a11]+(2i+j)l上例