数据结构经典课件

1、第5章 数组和广义表1教学目的：掌握数组和广义表的定义、特点及典型算法。2教学要求： 掌握数组在以行为主的存储结构中的地址计算方法。 掌握矩阵实现压缩存储时的下标变换。 理解稀疏矩阵的两种存储方式的特点和适用范围，领会以三元组表示稀疏矩阵时进行运算采用的处理方法。 掌握广义表的定义及其存储结构，学会将广义表分解为表头，表尾的方法。3教学重点： 掌握特殊矩阵的压缩存储。 掌握稀疏矩阵采用三元组存储时典型算法的实现。 广义表的定义、运算。4教学难点：数组的十字链表存储结构。图5.1 Amn的二维数组5.1 数组5.1.1 数组的逻辑结构 是线性表的推广 数组特点：元素本身可以是具有某种结构的数据，

2、但属于同一数据类型。 比如：一维数组可以看作一个线性表，二维数组可以看作“数据元素是一维数组”的一维数组，依此类推。图5.1是一个m行n列的二维数组。图5.2 矩阵Amn看成n个列向量的线性表 图5.3 矩阵Amn看成m个行向量的线性表 推广： n维数组每个数据元素受n个关系的约束，任一单个关系，仍是线性关系。通过以上分析可总结出数组具有以下性质： 数组中数据元素数目固定。 数组中数据元素具有相同的数据类型。 数组中每一个数据元素由唯一的一组下标来标识。 数组是随机存取的存储结构。 在数组上不能做插入、删除数据元素的操作。 通常在各种高级语言中数组一旦被定义，每一维的大小及上下界都不能改变。两

3、种操作： 取值操作：给定一组下标，读其对应的数据元素。 赋值操作：给定一组下标，存储或修改其相对应的数据元素。 二维数组形式化表示为： 数组的顺序存储结构有两种： 2Array（D,R） D=aij | i =c1,c1+1,d1, j=c2,c2+1,d2, aijD0 R=Row,Col Row| c1 i d1 ,c2 j d2-1, aij, ai(j+1) D0 Col | c1 i d1-1 ,c2 j d2, aij, a(i+1)j D0 5.1.2 数组的存储结构 数组的顺序存储结构有两种： 1. 按行序存储。如：BASIC、 COBOL和PASCAL语言。 2. 按列序存储

4、。如：FORTRAN语言。 二维数组Amn以行为主的存储序列为： a11, a12, ，a1n, a21, a22, , a2n, , am1, am2, , amn 而以列为主的存储序列为： a11, a21, ，am1，a12, a22, , am2, , a1n, a2n, , amn设有二维数组Amn，按元素的下标求其地址的计算：以“以行为主序”的分配为例：设数组的基址为LOC(a11)，每个数组元素占据l个地址单元，那么aij的物理地址计算为： LOC(aij)=LOC(a11)+(i-1)*n+j-1)*l 在C语言中，数组中每一维的下界定义为0，则： LOC(aij)=LOC(a

5、00)+(i*n+j)*l 推广到一般二维数组：Ac1.d1c2.d2，aij地址计算函数为： LOC(aij)=LOC(a c1 c2)+(i-c1)*(d2-c2+1)+(j-c2)*l 同理对于三维数组Amnp，即mnp数组，aijk其物理地址为： LOC(aijk)=LOC(a111)+(i-1)*n*p+(j-1)*p+k-1)*l 推广到一般的三维数组：Ac1.d1c2.d2c3.d3，则aijk物理地址为： LOC(i,j,k)=LOC(a c1 c2 c3)+(i-c1)*(d2 -c2+1)*(d3-c3+1) +(j-c2) *(d3-c3+1)+(k-c3)*l 容易看出

6、，数组元素的存储位置是其下标的线性函数，一旦数组下标的界偶确定之后，数组中的元素可随机存取。我们称具有这一特点的存储结构为随机存储结构。 对于维数组A(c1.d1, c2.d2，, cn.dn)，元素aj1j2jn的存储地址的计算公式: 例5.1 若矩阵Amn 中存在某个元素aij满足：aij是第i行中最小值且是第j列中的最大值，则称该元素为矩阵A的一个鞍点。试编写一个算法，找出A中的所有鞍点。 基本思想：在矩阵A中求出每一行的最小值元素，然后判断该元素是不是它所在列中的最大值，是则打印输出，接着处理下一行。矩阵A用一个二维数组表示。void saddle(int A,int m, int n

7、) 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)。5.2 特殊矩阵的压缩存储特殊矩阵：1.非零元素非常少； 2.矩阵元素的分布有一定规律所谓压

8、缩存储是指：为多个值相同的元素只分配一个存储空间，值为零的元素不分配空间。5.2.1 对称矩阵 特点：在一个n阶方阵中，有aij=aji ，其中1i,jn，如图5.3所示是一个5阶对称矩阵。 对于元素aij，特点是：ij且1in，下标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-1 (kj)在一维数组A中的位置为： Loci, j=Loc1,

9、 1+前i-1行非零元个数+第i行中aij前非零元个数 即：Loci, j=Loc1, 1+i(i-1)/2+j-1设存入向量：SAn*(n+1)/2+1中，SA k与aij的对应关系为：k=i*(i-1)/2+j-1 当ijn*(n+1)/2 当ij（2）上三角矩阵，也可以将其压缩存储到一个大小为n(n+1)/2的一维数组C中。其中元素aij(ij图5.8 带状矩阵A 三对角带状矩阵有如下特点： i=1, j=1, 2; 1in, j=i-1, i, i+1; i=n, j=n-1, n;时，aij非零，其它元素均为零。 当5.2.3 带状矩阵 1.确定存储该矩阵所需的一维向量空间的大小 假

10、设每个非零元素所占空间的大小为1个单元。 所需一维向量空间的大小为2+2+3（n-2）=3n-2，如图5.9所示。 图5.9 带状矩阵的压缩形式 2.确定非零元素在一维数组空间中的位置 Loci,j = Loc1,1+前i-1行非零元个数+第i行中aij前非零元个数； 前i-1行元素个数=3(i-1)-1（因为第1行只有2个非零元素）； 第i行中aij前非零元素个数=j-i+1，其中 -1 (ji) j-i=由此得到 Loci, j=Loc1, 1+3(i-1)-1+j-i+1 =Loc1, 1+2(i-1)+j-1 5.3 稀疏矩阵的压缩存储 设mn矩阵中有t个非零元素且tmn，这样的矩阵称

11、为稀疏矩阵。5.3.1 稀疏矩阵 非零元个数远远小于零元个数。图5.10 稀疏矩阵 三元组表的类型说明如下：define SMAX 1024 typedef struct int i, j; datatype v; SPNode; typedef struct int mu, nu, tu; SPNode dataSMAX; SPMatrix; 1) 用三元组表实现稀疏矩阵的转置运算如图所示的67矩阵M，它的转置矩阵就是76的矩阵N，并且N（row，col）=M（col， row），其中，1row7 ，1col6。 采用矩阵的正常存储方式时， 实现矩阵转置的经典算法如下：void TransM

12、atrix（ datatype sourcenm, datatype destmn） int i, j; for(i=0; im; i+) for (j=0; jmu= A.nu ; B-nu= A.mu ; B-tu= A.tu ; if (B-tu0) j=1; for(k=1; k=A.nu; k+) for(i=1; idataj.row=A.datai.col B-dataj.col=A.datai.row; B-dataj.e=A.datai.e; j+; 【算法5.1 基于稀疏矩阵的三元组表示矩阵的转置算法】 时间复杂度为O（A.nA.len）, 最坏情况当A.len=A.mA.

13、n时，时间复杂度为O（A.mA.n2）。采用正常方式实现矩阵转置的算法时间复杂度为O（A.mA.n）。 方法二： 依次按三元组表A的次序进行转置，转置后直接放到三元组表B的正确位置上。这种转置算法称为快速转置算法。 为了能将待转置三元组表A中元素一次定位到三元组表B的正确位置上，需要预先计算以下数据： (1) 待转置矩阵每一列中非零元素的个数。 (2) 待转置矩阵每一列中第一个非零元素在三元组表B中的正确位置。 为此， 需要设两个数组 numcol用来存放A中第col列非零元素个数 positioncol用来存放A中第col列中第一个非零元素在三元组表B中的正确位置。 其中：（1）numcol

14、的计算方法： 将三元组表A扫描一遍，对于其中列号为k的元素，给相应的numk加1。 （2）positioncol的计算方法： position1=1， positioncol=position col-1+numcol-1，其中2colA.nu。 具体算法如下： FastTransposeTSMatrix (TSMatrix *A) /*基于矩阵的三元组表示， 采用快速转置法， 将矩阵A转置为B所指的矩阵*/ int col, t, p， q; int numMAXSIZE, positionMAXSIZE; B-tu=A-tu; B-nu=A-mu; B-mu=A-nu; if (B-tu)

15、 for (col=1; colnu; col+) numcol=0; for(t=1; ttu; t+) numA-datat.col+; /*计算每一列的非零元素的个数*/ position1=1; for(col=2; colnu; col+) /*求col列第一个非零元素在B.data的位置 */ positioncol=positioncol-1+numcol-1; for(p=1; pdataq.row=A.datap.col; B-dataq.col=A.datap.row; B-dataq.e=A.datap.e positioncol+; 【算法5.2 快速稀疏矩阵转置算法】

16、 快速转置算法时间耗费在四个并列的单循环上，这四个并列的单循环分别执行了A.nu，A.tu，A.nu，A.tu次，因而总的时间复杂度为O(A.nu)+O(A.tu)+O(A.nu)+O(A.tu)。 当待转置矩阵M中非零元素个数接近于A.muA.nu 时，其时间复杂度接近于经典算法的时间复杂度O(A.muA.nu)。 空间耗费上除了三元组表所占用的空间外，还需要两个辅助向量空间，即num1.A-nu，position1.A-nu。可见，算法在时间上的节省，是以更多的存储空间为代价的。 2) 用三元组表实现稀疏矩阵的乘法运算 两个矩阵相乘也是矩阵的一种常用的运算。设矩阵M是m1n1矩阵，N是m2

17、n2矩阵；若可以相乘，则必须满足矩阵M的列数n1与矩阵N的行数m2相等，才能得到结果矩阵Q=MN（一个m1n2的矩阵）。 数学中矩阵Q中的元素的计算方法如下： 其中： 1im1, 1jn2。 图5.17 Q=MN 图5.17给出了一个矩阵相乘的例子。当矩阵M、N是稀疏矩阵时，我们可以采用三元组表的表示形式来实现矩阵的相乘。图5.18 矩阵M、N、Q的三元组表 因为三元组表只对矩阵的非零元素做存储。所以可以采用固定三元组表a中的元素（i，k，Mik）（1im1，1kn1），在三元组表b中找所有行号为k的对应元素（k，j， Nkj）（1km2，1jn2）进行相乘、 累加，从而得到Qij，即以三元组

18、表a中的元素为基准， 依次求出其与三元组表b的有效乘积。 算法中附设两个向量num 、first ，其中numrow表示三元组表b中第row行非零元素个数（1rowm2）， firstrow表示三元组表b中第row行第一个非零元素所在的位置。显然，firstrow+1-1指向三元组表b中第row行最后一个非零元素的位置。 5.3.2 稀疏矩阵的十字链表存储* 与用二维数组存储稀疏矩阵比较，用三元组表表示的稀疏矩阵不仅节约了空间，而且使得矩阵某些运算的运算时间比经典算法还少。 但是在进行矩阵加法、减法和乘法等运算时，有时矩阵中的非零元素的位置和个数会发生很大的变化。如A=A+B， 将矩阵B加到矩

19、阵A上，此时若还用三元组表表示法，势必会为了保持三元组表“以行序为主序”而大量移动元素。 在十字链表中，矩阵的每一个非零元素用一个结点表示， 该结点除了（row，col，value）以外，还要有以下两个链域： right：用于链接同一行中的下一个非零元素； down：用于链接同一列中的下一个非零元素。 再附设一个存放所有行链表的头指针的一维数组和一个存放所有列链表的头指针的一维数组。图5.15(b)给出了稀疏矩阵图5.15(a)的十字链表。十字链表的结构类型说明如下： typedef struct OLNode int row, col; /* 非零元素的行和列下标 */ datatype v

20、alue; struct OLNode * right, *down; /* 非零元所在行、列表的后继链域 */ OLNode; *OLink; typedef struct OLink * row-head, *col-head; /* 行、 列链表的头指针向量 */ int m, n, len; /* 稀疏矩阵的行数、 列数、 非零元素的个数 */ CrossList; CreateCrossList (CrossList * M) /* 采用十字链表存储结构， 创建稀疏矩阵M */ if(M!=NULL) free(M); scanf(&m, &n, &t); /* 输入M的行数, 列数

21、和非零元素的个数 */ M-m=m; M-n=n; M-len=t; If(!(M-row-head=(OLink * )malloc(m+1)*sizeof(OLink) exit(OVERFLOW); If(!(M-col-head=(OLink * )malloc(n+1)*sizeof(OLink) exit(OVERFLOW); M-row-head =M-col-head =NULL; /* 初始化行、 列头指针向量， 各行、 列链表为空的链表 */ for(scanf(&i, &j, &e); i!=0; scanf(&i, &j, &e) if(!(p=(OLNode *) m

22、alloc(sizeof(OLNode) exit(OVERFLOW); p-row=i; p-col=j; p-value=e; /* 生成结点 */ if(M-row-headi= =NULL) M-row-headi=p; else /* 寻找行表中的插入位置 */ for(q=M-row-headi; q-right&q-right-colright) p-right=q-right; q-right=p; /* 完成插入 */ if(M-col-headj=NULL) M-col-headj=p; else /*寻找列表中的插入位置*/ for(q=M-col-headj; q-do

23、wn&q-down-rowdown) p-down=q-down; q-down=p; /* 完成插入 */ 【算法5.4 建立稀疏矩阵的十字链表】 建十字链表的算法的时间复杂度为O（ts），s=MAX（m，n)。5.4 广 义 表 * 广义表的定义 广义表是n个数据元素a1，a2，ai，an的有序序列。 一般记为： ls=（a1，a2，a3， ，an） 广义表广泛地应用于人工智能等领域的表处理语言LISP语言中。 List(D,R)D=ai| ai Atomset 或 ai Lists R=|ai,ai+1 D 1=i=n-1其中 （1）ai是单个元素或是一个广义表，称为ls的原子或子表 （

24、2）长度：n是广义表的长度。 （3）表头：a1是广义表ls的表头 （4）表尾：其余元素组成的表是表尾。 （5）广义表示一个递归定义的表。下面给出一些广义表的例子，以加深对广义表概念的理解。 D=（）空表；其长度为零。 A=(a，(b， c) 表长度为2的广义表，其中第一个元素是单个数据a，第二个元素是一个子表(b，c)。 B=(A， A， D) 长度为3的广义表， 其前两个元素为表A， 第三个元素为空表D。 C=(a，C) 长度为2递归定义的广义表，C相当于无穷表(a，(a,(a，()。 下面以广义表A为例， 说明求表头、 表尾的操作： head（A）=a 表A的表头是a。 tail（A）=（

25、b， c） 表A的表尾是（b， c）。 广义表的表尾一定是一个表。 广义表的性质从上述广义表的定义和例子可以得到广义表的重要性质： 广义表是一种多层次的数据结构。广义表的元素可以是单元素，也可以是子表，而子表的元素还可以是子表，。 广义表可以是递归的表。例如表C 就是一个递归的表。 广义表可以为其它表所共享。如广义表B就共享表A。 在表B中不必列出表A的内容，只要通过子表的名称就可以引用该表。 广义表基本运算 基本操作，取头操作（Head）和取尾操作（Tail）。 根据广义表的表头、表尾的定义可知，对于任意一个非空的广义表，其表头可能是单元素也可能是广义表，而表尾必为广义表。例如：A（）B（e）C（a，（b，c，d）D（A，B，C）E（a，E）F（）那么：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）（）例如：L=(a，(b，(c，d)，e)，f) 如何访问到d？ 在广义表上可以定义与线性表类似的一些操作，如建立、插入、删除、拆开、连接、复制、遍历等。Crea