数据结构与算法 第五章

数组中的元素一般同时属于多个线性表，故属于广义线性表。一般的高级程序设计语言都支持数组。但在高级程序设计语言中，重点是数组的使用，而我们这里重点是数组的内部实现，即高级程序设计语言或其他应用如何在计算机内部处理数组。其中主要问题是数组的存储方式与寻址。十字链表多作为存储结构使用，其典型的应用是存储稀疏矩阵。第第55555555章章数组与十字链表数组与十字链表§§§§§§§§5.15.15.15.15.15.15.15.1数组数组数组数组数组数组数组数组数组是一种十分常用的结构，大多数程序设计语言都直接支持数组类型。数组的基本操作主要是元素定位，本节的主要内容是讨论数组的存储映射方法。数组是由一组类型相同的数据元素构成，每个数据元素称为一个数组元素（简称元素），每个元素受nnnn个线性关系约束（nnnn≥1111），若它在第1111～第nnnn个线性关系中的序号分别为iiii1111、iiii2222……………………iiiinnnn,,,,则称它的下标为iiii1111、iiii2222……………………iiiinnnn，若该数组的名为AAAA，则记下标为iiii1111、iiii2222……………………iiiinnnn,,,,的元素为，称该数组为n维数组。另一方面，可借助线性表的概念递归地定义：数组定义为一个元素可直接按序号寻址的线性表A=(AA=(AA=(AA=(A1111,A,A,A,A2222,,,,…………,A,A,A,Ammmm))))若AAAAiiii是简单元素（不是数组），则AAAA是一维数组；若AAAAiiii是（k-1)k-1)k-1)k-1)维数组，则AAAA是kkkk维数组。这里，i=1,2,i=1,2,i=1,2,i=1,2,…………,m.,m.,m.,m.而kkkk是大于0000的整数。§§5.1.15.1.15.1.15.1.15.1.15.1.15.1.15.1.1数组的定义与运算数组的定义与运算从此定义可直接看出，数组是从线性表的推广而来。图5555-1111为一个3333维数组的元素关系示意图。对一维数组的操作，也可以像线性表那样多种多样。对多维数组，由于是多个线性表的组合，所以情况会复杂些，此时，主要的操作通常是下列两种：给定一组下标，读出相应的元素。给定一组下标，修改相应的元素。它们本质上只对应一种操作：寻址，即根据下标定位相应的元素，所以下面主要针对此问题讨论。图图--一个一个33维数组的元素关系示意维数组的元素关系示意321iiia1321−iiia321,1iiia−321,1iiia−1321+iiia321,1iiia+321,1iiia+数组是一种特殊的数据结构，一般要求元素的存储地址能根据它的下标（即逻辑关系）计算出来。所以，数组一般也只采用顺序存储结构。讨论数组元素地址时，将数组的第1111个元素的起始存储单元作为参考单元，参考单元的绝对地址称为该数组的首地址，数组其他元素的相对地址均相对于首元素的起始地址。设iiii1111、iiii2222、…………、iiiinnnn为某nnnn维数组中的一个元素的下标，则用Loc(iLoc(iLoc(iLoc(i1111,i,i,i,i2222,,,,…………,i,i,i,innnn))))表示此元素的相对地址。对一维数组，与线性表类似，可使用顺序存储方式。但对多维数组，其已不属于线性结构的范畴，所以，不能直接使用顺序存储方式。但多维数组有其特殊性，具有线性结构的痕迹，它可唯一地转换为一维结构，反之亦然。从转换后的一维结构，可根据元素的存储位置推算出元素的逻辑关系（下标）。据此，可以将多维数组映射为一维结构，然后使用顺序存储方式。§§5.1.25.1.25.1.25.1.25.1.25.1.25.1.25.1.2数组的存储结构与寻址问题数组的存储结构与寻址问题一维数组的每个元素只含一个下标，其实质上是线性表，存储方法与普通线性表的顺序存储方法完全相同，即将数组元素按它们的逻辑次序存储在一片连续区域内。设一维数组为　　　　A=(aA=(aA=(aA=(a0000,,,,a1a1a1a1,,,,…………,a,a,a,an-1n-1n-1n-1))))则它的元素aaaaiiii的相对地址为Loc(i)=iLoc(i)=iLoc(i)=iLoc(i)=i····cccc这里，cccc表示每个元素占用的存储单元数目。一般地，若数组下标范围为闭区间[l[l[l[l1111,h,h,h,h1111]]]]内的整数，即A=(aA=(aA=(aA=(allll1111,,,,alalalal2222,,,,…………,ah,ah,ah,ah1111))))则元素aaaaiiii的相对地址为Loc(i)=(i-lLoc(i)=(i-lLoc(i)=(i-lLoc(i)=(i-l1111))))····cccc§§5.1.35.1.35.1.35.1.35.1.35.1.35.1.35.1.3一维数组的存储与寻址一维数组的存储与寻址二维数组的每个元素只含2222个下标，其已不是一般的线性表。如果将二维数组的第1111个下标理解为行号，第2222个下标理解为列号，然后按行列次序排列各元素，则二维数组呈阵列形状。例如aaaa11111111aaaa12121212…………aaaa1n1n1n1naaaa21212121aaaa22222222…………aaaa2n2n2n2n　　A=A=A=A=……………………　　　aaaam1m1m1m1aaaam2m2m2m2…………aaaamnmnmnmn是一个行号为1111到mmmm，列号为1111到nnnn的二维数组元素阵列。对这类非线性结构的存储，需将多维关系映射为一维（线性）关系，即要确定多维到一维的映射。常用的映射方法有两种：按行与按列。§§5.1.45.1.45.1.45.1.45.1.45.1.45.1.45.1.4二维数组的存储二维数组的存储((((一))))按行存储按行存储的基本思想是：先行后列，即先存储行号较小的元素，行号相同者，先存储列号较小者。例如，对上列的二维数组AAAA，按行存储的次序为aaaa11111111aaaa12121212…………aaaa1n1n1n1naaaa21212121aaaa22222222…………aaaa2n2n2n2n……………………aaaam1m1m1m1aaaam2m2m2m2…………aaaamnmnmnmn────────────────────────────────────────────────────────────第1111行元素第2222行元素第mmmm行元素设二维数组的行下标与列下标变化范围分别为闭区间[l[l[l[l1111,h,h,h,h1111]]]]与[l[l[l[l2222,h,h,h,h2222]]]]，按行存储，则它的任一元素aaaaijijijij的相对地址计算公式为Loc(i,j)=((hLoc(i,j)=((hLoc(i,j)=((hLoc(i,j)=((h2222-l-l-l-l2222+1)(i-l+1)(i-l+1)(i-l+1)(i-l1111)+(j-l)+(j-l)+(j-l)+(j-l2222))))))))····cccc这里，cccc为每个元素所占单元数目，iiii∈[l[l[l[l1111,h,h,h,h1111]]]]，jjjj∈[l[l[l[l2222,h,h,h,h2222]]]]且iiii与jjjj为整数。该公式的正确性是容易证明的。例5555-1.1.1.1.设某二维数组的两个下标的范围分别为[-1,2][-1,2][-1,2][-1,2]与[0,1][0,1][0,1][0,1]，则它的元素按行存储的次序为（用aaaaiiii表示元素，每个元素占两个单元）：它的元素aaaa-1,1-1,1-1,1-1,1的相对地址计算如下Loc(-1,1)Loc(-1,1)Loc(-1,1)Loc(-1,1)＝((1-0+1)(-1+1)+(1-0))((1-0+1)(-1+1)+(1-0))((1-0+1)(-1+1)+(1-0))((1-0+1)(-1+1)+(1-0))****2222＝2222相对相对地址地址0000000022222222444444446666666688888888101010101010101012121212121212121414141414141414元素元素aaaaaaaa-1,0-1,0-1,0-1,0-1,0-1,0-1,0-1,0aaaaaaaa-1,1-1,1-1,1-1,1-1,1-1,1-1,1-1,1aaaaaaaa0,00,00,00,00,00,00,00,0aaaaaaaa0,10,10,10,10,10,10,10,1aaaaaaaa1,01,01,01,01,01,01,01,0aaaaaaaa1,11,11,11,11,11,11,11,1aaaaaaaa2,02,02,02,02,02,02,02,0aaaaaaaa2,12,12,12,12,12,12,12,1((((二))))按列存储按列存储的基本思想是：先列后行，即先存储列号较小者，列号相同者先存储行号较小者。例如，前述的二维数组AAAA按列存储的次序为　　aaaa11111111aaaa21212121…………aaaam1m1m1m1aaaa12121212aaaa22222222…………aaaam2m2m2m2……………………aaaa1n1n1n1naaaa2n2n2n2n…………aaaamnmnmnmn────────────────────────────────────────────────────────────────────────第1111列元素第2222列元素第nnnn列元素设二维数组的行下标与列下标变化范围分别为闭区间[l[l[l[l1111,h,h,h,h1111]]]]与[l[l[l[l2222,h,h,h,h2222]]]]，按列存储，每个元素占cccc个存储单元，则它的任一元素aijaijaijaij的相对地址计算公式为Loc(i,j)=((j-lLoc(i,j)=((j-lLoc(i,j)=((j-lLoc(i,j)=((j-l2222)(h)(h)(h)(h1111––––llll1111+1)+(i-l+1)+(i-l+1)+(i-l+1)+(i-l1111))))))))····cccc该公式的正确性是容易证明的。对2222维数组，还可以有其他映射（2222维向1111维的映射）方法，如按正对角线、反对角线等，这里就不去讨论了。下面将二维数组的结果推广到多维数组。对nnnn维数组，也一般采用两种存储映射方式，它们分别是二维数组的按行与按列存储的推广。((((一))))按行存储这是一种““““左””””下标优先的存储方法，即第1111（最左）下标的下标值较小的元素较先存储，第1111下标值相同者，按第2222下标优先存储，对任意的k1k1k1k1，对第1~(k-1)1~(k-1)1~(k-1)1~(k-1)维相同者，先存储第kkkk维中下标值较小者。§§5.1.55.1.55.1.55.1.55.1.55.1.55.1.55.1.5多维数组的存储多维数组的存储例5555-2222设某三维数组aaaa的三个下标范围分别为[2,4][2,4][2,4][2,4]，[0,1][0,1][0,1][0,1]，[1,3][1,3][1,3][1,3]则它按行存储的次序为　aaaa201201201201aaaa202202202202aaaa203203203203aaaa211211211211aaaa212212212212aaaa213213213213（接下行）aaaa301301301301aaaa302302302302aaaa303303303303aaaa311311311311aaaa312312312312aaaa3133