《数据结构(第5章)》由会员分享，可在线阅读，更多相关《数据结构(第5章)（74页珍藏版）》请在金锄头文库上搜索。
1、2019年10月16日,数据结构讲义,1,第五章 数组、特殊矩阵和广义表,教学内容：5.1 多维数组 5.2 特殊矩阵的压缩存储 5.3 稀疏矩阵 5.4 广义表 教学目的：理解多维数组的结构特点和在内存中的两种顺序存储方式； 理解并掌握矩阵和特殊矩阵元素在存储区中地址的计算； 领会稀疏矩阵的压缩方式和简单运算； 了解广义表的定义和基本运算。 教学重点：多维数组的逻辑结构； 多维组的两种顺序存储方式，计算给定元素在存储区中的地址； 对称矩阵、三角矩阵的压缩存储方式； 稀疏矩阵的三元组表表示方法。 教学难点： 稀疏矩阵的压缩存储表示下的运算的实现 学时安排：4学时,2019年10月16日,数据结
2、构讲义,2,5.1 多维数组,数组的逻辑结构 数组的内存映象,2019年10月16日,数据结构讲义,3,5.1.1 数组的逻辑结构,数组是我们熟悉的一种数据结构，可以看作线性表的推广。数组作为一种数据结构其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型，比如：一维数组可以看作一个线性表，二维数组可以看作“数据元素是一维数组”的一维数组，三维数组可以看作“数据元素是二维数组”的一维数组，依此类推。,2019年10月16日,数据结构讲义,4,数组是一个具有固定格式和数量的数据有序集，每一个数据元素有唯一的一组下标来标识，因此，在数组上不能做插入、删除数据元素的操作。通常在各种高
3、级语言中数组一旦被定义，每一维的大小及上下界都不能改变。在数组中通常做下面两种操作： (1) 取值操作：给定一组下标，读其对应的数据元素。 (2) 赋值操作：给定一组下标，存储或修改与其相对应的数据元素。 我们着重研究二维和三维数组，因为它们的应用是广泛的，尤其是二维数组。,2019年10月16日,数据结构讲义,5,5.1.2 数组的内存映象,通常，数组在内存被映象为向量，即用向量作为数组的一种存储结构，这是因为内存的地址空间是一维的，数组的行列固定后，通过一个映象函数，则可根据数组元素的下标得到它的存储地址。 对于一维数组按下标顺序分配即可。 对多维数组分配时，要把它的元素映象存储在一维存储
4、器中，一般有两种存储方式：一是以行为主序（或先行后列）的顺序存放，如BASIC、PASCAL、COBOL、C等程序设计语言中用的是以行为主的顺序分配，即一行分配完了接着分配下一行。另一种是以列为主序（先列后行）的顺序存放，如FORTRAN语言中，用的是以列为主序的分配顺序，即一列一列地分配。,2019年10月16日,数据结构讲义,6,以行为主序的分配规律是：最右边的下标先变化，即最右下标从小到大，循环一遍后，右边第二个下标再变，从右向左，最后是左下标。以列为主序分配的规律恰好相反：最左边的下标先变化，即最左下标从小到大，循环一遍后，左边第二个下标再变，从左向右，最后是右下标。,2019年10月
5、16日,数据结构讲义,7,例如一个23二维数组，逻辑结构可以用左图表示。以行为主序的内存映象如右图（a）所示。 分配顺序为：a11 ，a12 ，a13 ，a21 ，a22 ，a23 ；以列为主序的分配顺序为：a11 ，a21 ，a12 ，a22 ，a13 ，a23 ；它的内存映象如右图（b）所示。,2019年10月16日,数据结构讲义,8,设有mn二维数组Amn，下面我们看按元素的下标求其地址的计算： 以“以行为主序”的分配为例：设数组的基址为LOC(a11)，每个数组元素占据l个地址单元，那么aij 的物理地址可用一线性寻址函数计算： LOC(aij) = LOC(a11) + ( (i-1
6、)*n + j-1 ) * l 在C语言中，数组中每一维的下界定义为0，则： LOC(aij) = LOC(a00) + ( i*n + j ) * l 推广到一般的二维数组：Ac1d1 c2d2，则aij的物理地址计算函数为： LOC(aij)=LOC(a c1 c2)+( (i- c1) *( d2 - c2 + 1)+ (j- c2) )*l,2019年10月16日,数据结构讲义,9,同理对于三维数组Amnp，即mnp数组，对于数组元素aijk其物理地址为： LOC(aijk)=LOC(a111)+( ( i-1) *n*p+ (j-1)*p +k-1)*l 推广到一般的三维数组：Ac1
7、d1 c2d2 c3d3，则aijk的物理地址为： LOC(i,j)=LOC(a c1 c2 c3)+( (i- c1) *( d2 - c2 + 1)* (d3- c3 + 1)+ (j- c2) *( d3- c3 + 1)+(k- c3)*l,2019年10月16日,数据结构讲义,10,三维数组的逻辑结构和以行为主序的分配示意图如图所示。,2019年10月16日,数据结构讲义,11,例5.1 若矩阵Amn 中存在某个元素aij满足：aij是第i行中最小值且是第j列中的最大值，则称该元素为矩阵A的一个鞍点。试编写一个算法，找出A中的所有鞍点。 基本思想：在矩阵A中求出每一行的最小值元素，然
8、后判断该元素它是否是它所在列中的最大值，是则打印出，接着处理下一行。矩阵A用一个二维数组表示。,2019年10月16日,数据结构讲义,12,void saddle (int A ,int m, int n) /*m,n是矩阵A的行和列*/ int i,j,min; for (i=0;i=m) printf (%d,%d,%dn, i ,k,min); 算法的时间性能为O(m*(n+m*n)。,2019年10月16日,数据结构讲义,13,5.2 特殊矩阵的压缩存储,对称矩阵 三角矩阵 带状矩阵,2019年10月16日,数据结构讲义,14,5.2.1 对称矩阵,对称矩阵的特点是：在一个n阶方阵中，
9、有aij=aji ，其中1i , jn，如图所示是一个阶对称矩阵。,2019年10月16日,数据结构讲义,15,对称矩阵关于主对角线对称，因此只需存储上三角或下三角部分即可。比如，只存储下三角中的元素aij，其特点是中ji且1in，对于上三角中的元素aij ，它和对应的aji相等，因此当访问的元素在上三角时，直接去访问和它对应的下三角元素即可，这样，原来需要n*n个存储单元，现在只需要n(n+1)/2个存储单元了，节约了n(n-1)/2个存储单元，当n较大时，这是可观的一部分存储资源。,2019年10月16日,数据结构讲义,16,如何只存储下三角部分？对下三角部分以行为主序顺序存储到一个向量中
10、去，在下三角中共有n*(n+1)/2个元素，因此，不失一般性，设存储到向量SAn(n+1)/2中，存储顺序可用下图示意，这样，原矩阵下三角中的某一个元素aij则具体对应一个sak，下面的问题是要找到k与i、j之间的关系。,2019年10月16日,数据结构讲义,17,对于下三角中的元素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)
11、/2 ) 若ij，则aij是上三角中的元素，因为aij=aji ，这样，访问上三角中的元素aij时则去访问和它对应的下三角中的aji即可，因此将上式中的行列下标交换就是上三角中的元素在SA中的对应关系： k=j*(j-1)/2+i-1 (kn*(n+1)/2 ) 综上所述，对于对称矩阵中的任意元素aij，若令I=max(i,j)，J=min(i,j)，则将上面两个式子综合起来得到： k=I*(I-1)/2+J-1。,2019年10月16日,数据结构讲义,18,5.2.2 三角矩阵,形如下图的矩阵称为三角矩阵，其中c为某个常数。其中(a)为下三角矩阵：主对角线以上均为同一个常数；(b)为上三角矩
12、阵，主对角线以下均为同一个常数；下面讨论它们的压缩存储方法。,2019年10月16日,数据结构讲义,19,1. 下三角矩阵 与对称矩阵类似，不同之处在于存完下三角中的元素之后，紧接着存储对角线上方的常量，因为是同一个常数，所以存一个即可，这样一共存储了n*(n+1)+1个元素，设存入向量：SAn*(n+1)+1中，这种的存储方式可节约n*(n-1)-1个存储单元，sak 与aji 的对应关系为：,2019年10月16日,数据结构讲义,20,2. 上三角矩阵 对于上三角矩阵，存储思想与下三角类似，以行为主序顺序存储上三角部分，最后存储对角线下方的常量。对于第1行，存储n个元素，第2行存储n-1个
13、元素，第p行存储(n-p+1)个元素，aij的前面有i-1行，共存储： 个元素，aij 是它所在的行中要存储的第（j-i+1）个也就是上三角存储顺序中的第 (i-1)*(2n-i+2)/2+(j-i+1)个，因此它在SA中的下标为：k=(i-1)*(2n-i+2)/2+j-i。 综上， sak 与aji 的对应关系为：,2019年10月16日,数据结构讲义,21,5.2.3 带状矩阵,n阶矩阵A称为带状矩阵，如果存在最小正数m ，满足当i-jm 时，aij =0，这时称w=2m-1为矩阵A的带宽。下图是一个w=3(m=2)的带状矩阵。带状矩阵也称为对角矩阵。由下图可看出，在这种矩阵中，所有非零
14、元素都集中在以主对角线为中心的带状区域中，即除了主对角线和它的上下方若干条对角线的元素外，所有其他元素都为零(或同一个常数c)。,2019年10月16日,数据结构讲义,22,一种压缩方法是将A压缩到一个n行w列的二维数组B中，如下图所示，当某行非零元素的个数小于带宽w时，先存放非零元素后补零。 那么aij 映射为b ij，映射关系为：,2019年10月16日,数据结构讲义,23,另一种压缩方法是将带状矩阵压缩到向量C中去，按以行为主序，顺序的存储其非零元素，如下图所示，按其压缩规律，找到相应的映象函数。 如当w=3时，映象函数为： k=2*i+j-3,2019年10月16日,数据结构讲义,24
15、,5.3 稀疏矩阵,稀疏矩阵的三元组表存储 稀疏矩阵的十字链表存储,2019年10月16日,数据结构讲义,25,5.3.1 稀疏矩阵的三元组表存储,将三元组按行优先的顺序，同一行中列号从小到大的规律排列成一个线性表，称为三元组表，采用顺序存储方法存储该表。如图(a)稀疏矩阵对应的三元组表为图(b)。,2019年10月16日,数据结构讲义,26,#define SMAX 1024 /*一个足够大的数*/ typedef struct int i,j; /*非零元素的行、列*/ datatype v; /*非零元素值*/ SPNode; /*三元组类型*/ typedef struct int m
16、u,nu,tu; /*矩阵的行、列及非零元素的个数*/ SPNode dataSMAX; /*三元组表*/ SPMatrix; /*三元组表的存储类型*/ 这样的存储方法确实节约了存储空间，但矩阵的运算从算法上可能变的复杂些。,2019年10月16日,数据结构讲义,27,1.稀疏矩阵的转置 设SPMatrix A; 表示一m*n的稀疏矩阵，其转置B则是一个n*m的稀疏矩阵，因此有 SPMatrix B; 。由A求B需： A的行、列转化成B的列、行； 将A.data中每一三元组的行列交换后转到B.data中； 以上两点完成之后，并没有完成B。因为我们前面规定三元组的是按一行一行且每行中的元素是按列号从小到大的规律顺序存放的，因此B也必须按此规律实现，A的转置B如图(a)所示，图(b)是它对应的三元组存储，就是说，在A的三元组存储基础
