数据结构与算法：第五章数组和广义表学习指导材料

《数据结构与算法：第五章数组和广义表学习指导材料》由会员分享，可在线阅读，更多相关《数据结构与算法：第五章数组和广义表学习指导材料（9页珍藏版）》请在装配图网上搜索。

1、第五章 数组和广义表本章介绍的数组与广义表可视为线性表的推广，其特点是数据元素仍然是一个表。本章讨论多维数组的逻辑结构和存储结构、特殊矩阵、矩阵的压缩存储、广义表的逻辑结构和存储结构等。5.1 多维数组5.1.1 数组的逻辑结构数组是我们很熟悉的一种数据结构，它可以看作线性表的推广。数组作为一种数据结构其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型，比如：一维数组可以看作一个线性表，二维数组可以看作“数据元素是一维数组”的一维数组，三维数组可以看作“数据元素是二维数组”的一维数组，依此类推。图5.1是一个m行n列的二维数组。a11 a12 a1na21 a22 a2n a

2、m1 am2 amn图5.1m行n列的二维数组A=5.1.2 数组的内存映象现在来讨论数组在计算机中的存储表示。通常，数组在内存被映象为向量，即用向量作为数组的一种存储结构，这是因为内存的地址空间是一维的，数组的行列固定后，通过一个映象函数，则可根据数组元素的下标得到它的存储地址。对于一维数组按下标顺序分配即可。 对多维数组分配时，要把它的元素映象存储在一维存储器中，一般有两种存储方式：一是以行为主序（或先行后列）的顺序存放，如BASIC、PASCAL、COBOL、C等程序设计语言中用的是以行为主的顺序分配，即一行分配完了接着分配下一行。另一种是以列为主序（先列后行）的顺序存放，如FORTRA

3、N语言中，用的是以列为主序的分配顺序，即一列一列地分配。以行为主序的分配规律是：最右边的下标先变化，即最右下标从小到大，循环一遍后，右边第二个下标再变，从右向左，最后是左下标。以列为主序分配的规律恰好相反：最左边的下标先变化，即最左下标从小到大，循环一遍后，左边第二个下标再变，从左向右，最后是右下标。例如一个23二维数组，逻辑结构可以用图5.2表示。以行为主序的内存映象如图5.3（a）所示。 分配顺序为：a11 ，a12 ，a13 ，a21 ，a22 ，a23 ; 以列为主序的分配顺序为：a11 ，a21 ，a12 ，a22 ，a13 ，a23 ; 它的内存映象如图5.3（b）所示。a11a1

4、1a12a21a11a12a13a13a12a21a22a23a21a22a22a13a23a23 图5.2 23数组的逻辑状态 (a) 以行为主序 (b) 以列为主序图5.3 23数组的物理状态设有mn二维数组Amn，下面我们看按元素的下标求其地址的计算：以“以行为主序”的分配为例：设数组的基址为LOC(a11)，每个数组元素占据l个地址单元，那么aij 的物理地址可用一线性寻址函数计算：LOC(aij) = LOC(a11) + ( (i-1)*n + j-1 ) * l这是因为数组元素aij的前面有i-1行，每一行的元素个数为n，在第i行中它的前面还有j-1个数组元素。在C语言中，数组中

5、每一维的下界定义为0，则：LOC(aij) = LOC(a00) + ( i*n + j ) * l推广到一般的二维数组：Ac1.d1 c2.d2，则aij的物理地址计算函数为：LOC(aij)=LOC(a c1 c2)+( (i- c1) *( d2 - c2 + 1)+ (j- c2) )*l例51 若矩阵Amn 中存在某个元素aij满足：aij是第i行中最小值且是第j列中的最大值，则称该元素为矩阵A的一个鞍点。试编写一个算法，找出A中的所有鞍点。 基本思想：在矩阵A中求出每一行的最小值元素，然后判断该元素它是否是它所在列中的最大值，是则打印出，接着处理下一行。矩阵A用一个二维数组表示。算

6、法如下：void saddle (int A ,int m, int n) /*m,n是矩阵A的行和列*/ int i,j,min; for (i=0;im;i+) /*按行处理*/ min=Ai0 for (j=1; jn; j+) if (Aijmin ) min=AIj;/*找第I行最小值*/ for (j=0; jn; j+)/*检测该行中的每一个最小值是否是鞍点*/if (AIj=min ) k=j; p=0; while (pm & Apj=m) printf (%d,%d,%dn, i ,k,min); /* if */ /*for i*/ 算法的时间性能为O(m*(n+m*n)

7、。5.2 特殊矩阵的压缩存储对于一个矩阵结构显然用一个二维数组来表示是非常恰当的，但在有些情况下，比如常见的一些特殊矩阵，如三角矩阵、对称矩阵、带状矩阵、稀疏矩阵等，从节约存储空间的角度考虑，这种存储是不太合适的。下面从这一角度来考虑这些特殊矩阵的存储方法。5.2.1 对称矩阵对称矩阵的特点是：在一个n阶方阵中，有aij=aji ，其中1i , jn，如图5.5所示是一个阶对称矩阵。对称矩阵关于主对角线对称，因此只需存储上三角或下三角部分即可，比如，我们只存储下三角中的元素aij，其特点是中ji且1in，对于上三角中的元素aij ，它和对应的aji相等，因此当访问的元素在上三角时，直接去访问和

8、它对应的下三角元素即可，这样，原来需要n*n个存储单元，现在只需要n(n+1)/2个存储单元了，节约了n(n-1)/2个存储单元，当n较大时，这是可观的一部分存储资源。A=图5.5 5阶对称方阵及它的压缩存储如何只存储下三角部分呢？对下三角部分以行为主序顺序存储到一个向量中去，在下三角中共有n*(n+1)/2个元素，因此，不失一般性，设存储到向量SAn(n+1)/2中，存储顺序可用图5.6示意，这样，原矩阵下三角中的某一个元素aij则具体对应一个sak，下面的问题是要找到k与i、j之间的关系。012345n(n+1)/2- 1a11a21a22a31a32a33an1an2a n第3行第2行第

9、n行第1行图5.6 一般对称矩阵的压缩存储对于下三角中的元素aij，其特点是：ij且1in，存储到SA中后，根据存储原则，它前面有i-1行，共有1+2+i-1=i*(i-1)/2个元素，而aij又是它所在的行中的第j个，所以在上面的排列顺序中，aij是第i*(i-1)/2+j个元素，因此它在SA中的下标k与i、j的关系为：k=i*(i-1)/2+j-1 (kn*(n+1)/2 )若ij，则aij是上三角中的元素，因为aij=aji ，这样，访问上三角中的元素aij时则去访问和它对应的下三角中的aji即可，因此将上式中的行列下标交换就是上三角中的元素在SA中的对应关系：k=j*(j-1)/2+i

10、-1 (kn*(n+1)/2 ) 综上所述，对于对称矩阵中的任意元素aij，若令I=max(i,j)，J=min(i,j)，则将上面两个式子综合起来得到：k=I*(I-1)/2+J-1。5.3 稀疏矩阵设m*n矩阵中有t个非零元素且tmu=A-nu; B-nu=A-mu; B-tu=A-tu;/*稀疏矩阵的行、列、元素个数*/ if (B-tu0)/*有非零元素则转换*/ q=0; for (col=1; colnu); col+)/*按A的列序转换*/ for (p=1; ptu); p+)/*扫描整个三元组表*/ if (A-datap.j=col ) B-dataq.i= A-datap

11、.j ; B-dataq.j= A-datap.i ;B-dataq.v= A-datap.v;q+; /*if*/ /*if(B-tu0)*/ return B;/*返回的是转置矩阵的指针*/ /*TransM1*/算法5.1稀疏矩阵转置分析该算法，其时间主要耗费在col和p的二重循环上，所以时间复杂性为O(n*t)，(设m、n是原矩阵的行、列，t是稀疏矩阵的非零元素个数)，显然当非零元素的个数t和m*n同数量级时，算法的时间复杂度为O(m*n2)，和通常存储方式下矩阵转置算法相比，可能节约了一定量的存储空间，但算法的时间性能更差一些。 算法5.1的效率低的原因是算法要从A的三元组表中寻找第

12、一列、第二列、，要反复搜索A表，若能直接确定A中每一三元组在B中的位置，则对A的三元组表扫描一次即可。这是可以做到的，因为A中第一列的第一个非零元素一定存储在B.data1，如果还知道第一列的非零元素的个数，那么第二列的第一个非零元素在B.data中的位置便等于第一列的第一个非零元素在B.data中的位置加上第一列的非零元素的个数，如此类推，因为A中三元组的存放顺序是先行后列，对同一行来说，必定先遇到列号小的元素，这样只需扫描一遍A.data即可。 根据这个想法，需引入两个向量来实现 ：numn+1和cpotn+1，numcol表示矩阵A中第col列的非零元素的个数（为了方便均从1单元用起），

13、cpotcol初始值表示矩阵A中的第col列的第一个非零元素在B.data中的位置。于是cpot的初始值为： cpot1=1；cpotcol=cpotcol-1+numcol-1； 2coln 例如对于矩阵图5.11矩阵A的num 和cpot的值如下：Col 1 2 3 4 5 6 numcol 2 1 1 2 0 1 cpotcol 1 3 4 5 7 7图5.15 矩阵A的num与cpot值依次扫描A.data，当扫描到一个col列元素时，直接将其存放在B.data的cpotcol位置上，cpotcol加，cpotcol中始终是下一个col列元素在B.data中的位置。下面按以上思路改进转

14、置算法如下：SPMatrix * TransM2 (SPMatrix *A) SPMatrix *B; int i,j,k; int numn+1,cpotn+1; B=malloc(sizeof(SPMatrix); /*申请存储空间*/ B-mu=A-nu; B-nu=A-mu; B-tu=A-tu;/*稀疏矩阵的行、列、元素个数*/ if (B-tu0)/*有非零元素则转换*/ for (i=1;inu;i+) numi=0; for (i=1;itu;i+)/*求矩阵A中每一列非零元素的个数*/ j= A-datai.j; numj+; cpot1=1; /*求矩阵A中每一列第一个非零

15、元素在B.data中的位置*/for (i=2;inu;i+) cpoti= cpoti-1+numi-1; for (i=1; itu); i+)/*扫描三元组表*/ j=A-datai.j;/*当前三元组的列号*/ k=cpotj;/*当前三元组在B.data中的位置*/ B-datak.i= A-datai.j ; B-datak.j= A-datai.i ; B-datak.v= A-datai.v;cpotj+; /*for i */ /*if (B-tu0)*/ return B;/*返回的是转置矩阵的指针*/ /*TransM2*/算法5.2稀疏矩阵转置的改进算法分析这个算法的时

16、间复杂度：这个算法中有四个循环，分别执行n，t，n-1，t次，在每个循环中，每次迭代的时间是一常量，因此总的计算量是O（n+t）。当然它所需要的存储空间比前一个算法多了两个向量。5.3.2 稀疏矩阵的十字链表存储三元组表可以看作稀疏矩阵顺序存储，但是在做一些操作（如加法、乘法）时，非零项数目及非零元素的位置会发生变化，这时这种表示就十分不便。在这节中，我们介绍稀疏矩阵的一种链式存储结构十字链表，它同样具备链式存储的特点，因此，在某些情况下，采用十字链表表示稀疏矩阵是很方便的。图5.18是一个稀疏矩阵的十字链表。用十字链表表示稀疏矩阵的基本思想是：对每个非零元素存储为一个结点，结点由5个域组成，

17、其结构如图5.19表示，其中：row域存储非零元素的行号，col域存储非零元素的列号，v域存储本元素的值，right，down是两个指针域。rowcolvdownright 图5.19 十字链表的结点结构5.4 广义表顾名思义，广义表是线性表的推广。也有人称其为列表（Lists，用复数形式以示与统称的表List的区别）。5.4.1 广义表的定义和基本运算广义表的定义和性质我们知道，线性表是由n个数据元素组成的有限序列。其中每个组成元素被限定为单元素，有时这种限制需要拓宽。例如，中国举办的某体育项目国际邀请赛，参赛队清单可采用如下的表示形式：（俄罗斯，巴西，（国家，河北，四川），古巴，美国，（）

18、，日本）在这个拓宽了的线性表中，韩国队应排在美国队的后面，但由于某种原因未参加，成为空表。国家队、河北队、四川队均作为东道主的参赛队参加，构成一个小的线性表，成为原线性表的一个数据项。这种拓宽了的线性表就是广义表。广义表（Generalized Lists）是n（n0）个数据元素a1，a2，ai，an的有序序列，一般记作：ls（a1，a2，ai，an）其中：ls是广义表的名称，n是它的长度。每个ai（1in）是ls的成员，它可以是单个元素，也可以是一个广义表，分别称为广义表ls的单元素和子表。当广义表ls非空时，称第一个元素a1为ls的表头（head），称其余元素组成的表（a2，ai，an）为

19、ls的表尾（tail）。显然，广义表的定义是递归的。为书写清楚起见，通常用大写字母表示广义表，用小写字母表示单个数据元素，广义表用括号括起来，括号内的数据元素用逗号分隔开。下面是一些广义表的例子：A （）B （e）C （a，（b，c，d）D （A，B，C）E （a，E）F （）广义表的性质从上述广义表的定义和例子可以得到广义表的下列重要性质：广义表是一种多层次的数据结构。广义表的元素可以是单元素，也可以是子表，而子表的元素还可以是子表，。广义表可以是递归的表。广义表的定义并没有限制元素的递归，即广义表也可以是其自身的子表。例如表E就是一个递归的表。广义表可以为其他表所共享。例如，表A、表B、表

20、C是表D的共享子表。在D中可以不必列出子表的值，而用子表的名称来引用。广义表的上述特性对于它的使用价值和应用效果起到了很大的作用。广义表可以看成是线性表的推广，线性表是广义表的特例。广义表的结构相当灵活，在某种前提下，它可以兼容线性表、数组、树和有向图等各种常用的数据结构。当二维数组的每行（或每列）作为子表处理时，二维数组即为一个广义表。另外，树和有向图也可以用广义表来表示。由于广义表不仅集中了线性表、数组、树和有向图等常见数据结构的特点，而且可有效地利用存储空间，因此在计算机的许多应用领域都有成功使用广义表的实例。广义表基本运算广义表有两个重要的基本操作，即取头操作（Head）和取尾操作（Tail）。根据广义表的表头、表尾的定义可知，对于任意一个非空的列表，其表头可能是单元素也可能是列表，而表尾必为列表。例如：Head（B） e Tail（B）（）Head（C） a Tail（C）（b，c，d）Head（D） A Tail（D）（B，C）Head（E） a Tail（E）（E）Head（F）（） Tail（F）（）