《数据结构数组》PPT课件.ppt

数据结构 数组,4.1 数组的定义,数组是我们最熟悉的数据类型，在早期的高级语言中，数组是唯一可供使用的数据类型。由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单,4.1 数组的定义,多维数组是向量的推广。例如，二维数组： a00 a01 a0n-1 a10 a11 a1n-1 am-10 am-11 am-1n-1,Amn=,可以看成是由m个行向量组成的向量，也可以看成是n个列向量组成的向量。,4.1 数组的定义,4.2 数组的顺序表示和实现,由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。 又由于对数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。,4.2 数组的顺序表示和实现,行优先顺序将数组元素按行排列，第i+1个行向量紧接在第i个行向量后面。以二维数组为例，按行优先顺序存储的线性序列为： 列优先顺序将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后，按列优先顺序存储的线性序列为：,a0,1,a0,0,a0,2,a1,0,a1,1,a1,2,a0,1,a0,0,a0,2,a1,0,a1,1,a1,2,d,a1,0,a0,0,a2,0,a2,1,a0,1,a1,1,a1,0,a0,0,a2,0,a0,1,a1,1,a2,1,d,例如，二维数组Amn按“行优先顺序”存储在内存中，假设每个元素占用d个存储单元。 元素aij的存储地址应是数组的基地址加上排在aij前面的元素所占用的单元数。因为aij位于第i行、第j列，前面i-1行一共有in个元素，第i行上aij前面又有j个元素，故它前面一共有(in+j）个元素，因此，aij的地址计算函数为： LOC(aij)=LOC(a00)+i*n+j*d (0im， 0jn),注：C语言中数组元素采用行主序的存放方法，即行优先顺序。,一个mn的二维数组可以看成是m行的一维数组，或者n列的一维数组。,a0,0 a0,1 a0,n-1 a1,0 a1,1 a1,n-1 am-1,0 am-1,1 am-1,n-1,Amn=,4.2 数组的顺序表示和实现,4.2 数组的顺序表示和实现,同样，三维数组Aijk按“行优先顺序”存储，其地址计算函数为： LOC(aijk)=LOC(a000)+inp+jp+kd 注：只要知道以下三要素便可随时求出任一元素的地址（意义：数组中的任一元素可随机存取） 开始结点的存放地址（即基地址）； 维数和每维的上、下界； 每个数组元素所占用的单元数,例：一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是 多少个字节。 答： Volume=m*n*L=(6-1+1)*(7- 0 +1)*6=48*6=288 例 设数组a60, 70的基地址为2048，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a32,58的存储地址？ 答：根据行优先公式 LOC(aij)=LOC(a00)+(i*n+j)*k (0im，0jn) 得：LOC(a32,58)=2048+(32*70+58)*26644,5.3 数组的压缩存储,所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，下面我们讨论几种特殊矩阵的压缩存储。,5.3.1 特殊矩阵 5.3.2 稀疏矩阵 5.3.1 特殊矩阵,5.3 数组的压缩存储,1、对称矩阵 在一个n阶方阵A中，若元素满足下述性质： aij=aji （0i,jn-1） 则称A为对称矩阵。如图5.1便是一个5阶对称矩阵。,5.3.1 特殊矩阵,5.3 数组的压缩存储,对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。不失一般性，我们按“行优先顺序”存储主对角线（包括对角线）以下的元素，其存储形式如图所示：,1 5 1 3 7 a00 5 0 8 0 0 a10 a11 1 8 9 2 6 a20 a21 a22 3 0 2 5 1 7 0 6 1 3 an-1 0 an-1 1 an-1 n-1 图 5.1 对称矩阵,若ij，则ai j在下三角形中。 ai j之前的i行（从第0行到第i-1行）一共有1+2+I = i(i+1)/2个元素，在第i行上， ai j之前恰有j个元素（即ai0, ai1, ai2, aij-1），因此有： k=i(i+1)/2+j 0kn(n+1)/2 若ij，则aij是在上三角矩阵中。因为aij=aji，所以只要交换上述对应关系式中的i和j即可得到： k=j(j+1)/2+i 0 kn(n+1)/2 令 I=max(i,j)， J=min(i,j)，则k和 i, j的对应关系可统一为： k=I(I+1)/2+J 0 kn(n+1)/2,5.3 数组的压缩存储,因此，aij的地址可用下列式计算： LOC(aij)=LOC(sak) =LOC(sa0)+kd=LOC(sa0)+I(I+1)/2+Jd 有了上述的下标交换关系，对于任意给定一组下标 (i，j)，均可在sak中找到矩阵元素aij，反之，对所有 的k=0,1,2,n(n-1)/2-1，都能确定sak中的元素在矩阵中的位置(i,j)。由此，称san(n+1)/2为阶对称矩阵A的压缩存储，见下图： k=0 1 2 3 n(n-1)/2 n(n-1)/2-1 例如a21和a12均存储在 sa4中，这是因为 k=I(I+1)/2+J=2(2+1)/2+1=4,5.3 数组的压缩存储,5.3 数组的压缩存储,2、对角矩阵 对角矩阵中，所有的非零元素集中在以主对角线为了中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。下图给出了一个三对角矩阵。,非零元素仅出现在主对角(aii,0in-1上，以及紧邻主对角线上面的那条对角线上(aii+1,0in-2)和紧邻主对角线下面的那条对角线上(ai+1 i,0in-2)。显然，当i-j1时，元素aij=0。 由此可知，一个k对角矩阵(k为奇数)A是满足下述条件的矩阵： 若i-j(k-1)/2 ， 则元素 aij=0。 对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。,5.3 数组的压缩存储,对这种矩阵，我们也可按行优序为主序来存储。除第0行和第n-1行是2个元素外，每行的非零元素都要是3个，因此，需存储的元素个数为3n-2。,K=0 1 2 3 4 5 3n-2 3n-1 数组sa中的元素sak与三对角带状矩阵中的元素aij存在一一对应关系，在aij之前有i行,共有3i-1个非零元素，在第i行，有j-i+1个非零元素，这样，非零元素aij的地址为：,5.3 数组的压缩存储,LOC(i,j) = LOC(0,0)+3i-1+(j-i+1)d = LOC(0,0)+(2i+j)d 上例中，a34对应着 a21对应着,sa10,k=2i+j=23+4=10,sa5,k=22+1=5,由此，我们称sa03n-1是n阶三对角阵的压缩存储表示。,5.3 数组的压缩存储,5.3 数组的压缩存储,5.3.2 稀疏矩阵,5.3 数组的压缩存储,5.3.2 稀疏矩阵,三元组顺序表,行逻辑链接顺序表,十字链表,5.3 数组的压缩存储,1、三元组顺序表,5.3 数组的压缩存储,1、三元组顺序表,5.3 数组的压缩存储,1、三元组顺序表,已知 三 元 组 表 A,求 三 元 组 表 B,5.3 数组的压缩存储,1、三元组顺序表,5.3 数组的压缩存储,2、十字链表,