武汉软件工程职业学院《数据结构讲义》第07讲 数组.doc

第二章线性表和数组第七讲 数组1掌握数组的基本概念及数组的顺序存储结构。2.了解并熟悉特殊矩阵的压缩存储。3掌握稀疏矩阵的三元存储。 教学重点：1、 数组的概念及顺序存储结构。2、 稀疏矩阵的转置矩阵。 教学难点： 稀疏矩阵的转置矩阵 授课内容2.6 数组2.6.1 数组的基本概念数组是一种常用对数据结构，几乎所有的程序设计语言都把数组类型设定为固有类型。计算机系统的内存是连续的空间，为了方便的存取处理大量的相关性数据，我们定义一种“连续的存储区域”，并使用一个名称指向此区域的起点，通过名称及偏移的方式，可以很容易的存取到该区域内的数据，此即为数组。数组 是由下标（index）和值（value）组成的序对（indexvalue pairs）集合。简单地讲，数组就是按一定格式排列起来的一列同一属性的项目,是相同类型的数据元素的集合。我们经常使用数组来存放一连串数据类型相同的数据。因此，数组具有两个特性是：1.数组中的元素间的地址是连续的。2.数组中所有元素的数据类型是相同的。数组的类型有一维数组A10、二维数组A56、三维数组A355、多维数组等。数组元素 在数组中，对于每组有定义的下标，都存在一个与其相对应的值，这个值通常称为数组元素。二维数组：每一行都是一个线性表，每一个数据元素既在一个行表中，又在一个列表中。在c语言中，其被定义为： ELEMTP arraynamerowcol； 在二维数组中，每个元素都受到行关系和列关系的约束，例如有一个而外数组Amn，对于第i行第j列的元素Aij，Aij+1是该元素在行关系中的直接后继元素；而Ai+1j是该元素在列关系中的直接后继元素。所以，可以把二维数组看成是一个一维数组，它有row个元素，每个数据元素又是一个col个数据元素的一维数组。对数组一般讨论下面两种运算：给定一组有定义的下标，存取相应的数据元素；给定一组有定义的下标，修改相应数据元素（或其中的某个数据项）的值。2.6.2 数组的顺序存储结构数组是一顺序存储方式在计算机中的，而随机存取是顺序存储结构的主要特征。大部分高级语言采用以行序为主的存储方式，如图2-6-1（a）所示，（如PASCAL 、C等）；但在有的语言（如FORTRAN）中采用的是以列序为主的存储方式，如图2-6-1（b）所示。 在C语言中，数组中任一元素Aij的存储位置可用下列公式计算：LOC（Aij）=LOC（A00）+（i*col+j）*L其中，LOC（A00）为数组的起始位置，L每个数据元素所占存储单元个数。由于在定义数组时，LOC（A00）、L和col是已知的，因此可以根据上式计算出任一元素的存储地址，实现随机存取。 2.6.3 特殊矩阵的压缩存储 矩阵在科学与工程计算机中有广泛的应用。在用高级语言编程中，通常用二维数组来表示矩阵。这样，利用上面的地址计算公式可以快速访问矩阵中的每个元素。然而，实际应用中会遇到一些特殊的矩阵，所谓特殊矩阵，是指矩阵中值相同的元素或着零元素的部分有一定的规律。例如，对称矩阵、三角矩阵和三对角矩阵都是特殊矩阵。 若一个n阶矩阵A中的元素满足：Aij=Aij（1 i n ，1 j n）则称A为对矩阵；当一个方阵的主对角线以上或以上的所有元素皆为零时，该矩阵为三角矩阵；除了主对角线上和直接在主对角线上下方的对角线的元素外，其他所有元素皆为零的矩阵称为三角矩阵。图2-6-2是两种特殊矩阵的形式。 为了节省存储空间，可以对这些矩阵进行压缩存储。所谓压缩存储就是为多个值相同的元素只分配给一个存储空间，对零元素不分配存储空间。由于特殊矩阵中非零元素的分布有明显的规律，因此我们可将其压缩存储到一个一维数组中，并找到每个非零元素在一维数组中的对应关系。 2.6.4 稀疏矩阵的三元组存储 当一个mn的矩阵A中有k个非零元素，若km=a-n;b-n=a-m;b-t=a-t; if(a-t!=0) q=0; for(col=l;coln;col+) for (p=0;pt;p+) if (a-elemp.j= =col) b-elemq.i=a-elem p.j; b-elemq.j=a-elem p.i; b-elemq.v=a-elem p.v; q +; 分析这个算法 除少数附加空间，例如p,q,和col外，它需要的存储量仅为两个三元组表a、b所需要的空间。因此，当非零元素个数tm n/3时，其所需储存空间比直接用二维数组要省略。至于执行时间，因算法的主要工作是在col 和p的重循环中完成的，故算法的执行时间为O（n t）。 当非零元素个数t的数量级为m n 时，其执行时间变为O（m n2）。这比直接用二维数组表示矩阵的转置算法的时间复杂级O（m n）要差。不难看出，此算法之所以耗费时间，问题在于其形成转置矩阵的一行，都必须对a.elem从头到尾扫描一遍。能否对a.elem只扫描一次，就能得到要求的b.elem呢？为此，我们提出另一种方法(2)按照a.elem中三元组的次序进行转置要实现对a.elem扫描一次就能得到b.elem，必须每扫描一个元素就直接将它放到b.elem中应有的位置上。因此，首先要知道a.elem中的元素在b.elem中的存储位置。这就要预先确定矩阵M中每一列（即N中每一行）的第一个非零元素在b.elem中应有的位置。为此，需要设置两个数组num1.n和pot1.n，分别存放在矩阵M 中每一列的非零元素个数和每一列的第1个非零元素在b.elem中的位置，即numcol表示矩阵M中第col列中非零个数；Potcol的初值表示M中第col列的第1个非零在b.elem中的位置。显然有：pot1=0；potcol=potcol-1+numcol-1 （2=colm=a-n;b-n=a-m;b-t=a-t; if(a-t ！=0) for(col=1;coln;col+) numcol=0; for(k=0;kt;k+) numa-elemk.j+; pot1=0; for(col=2;coln;col+) potcol=potcol-1+numcol-1; for(p=0;pt;p+) col=a-elemp.j;q=potcol; b-elemq.i=a-elemp.j; b-elemq.j=a-elemp.i; b-elemq.v=a-elemp.v; potcol+;算法分析此算法比前一个算法多用了两个辅助数据。但从时间上看，算法中有4个并列的循环语句，它们分别执行n,t,n-1和t次，因此算法的执行时间为O（n+1）。当t和mn等数量级时，该算法的执行时间为O（mn），但是在tmu=m; M -nu=n; M -tu =t; for(k=0;krheadk=NULL; for(k=0;kcheadk=NULL; for(scanf(&i,&j,&v);i!=0;scanf(&I,&j,&v) p=(OLNode * ) malloc (sizeof(OLNode); p-row=i;p-col=j;p-val=v; p-right=p-down = NULLif(M - rheadi = = NULL) M - rheadi = p;else / * 寻找行表中的插入位置 * / for(q = M - rheadi;(q - right)&(q - right - j right); p - right q - right; q - right = p; / * 完成行插入 * /if(M-cheadj=NULL) M-cheadj=p;else