数据结构(第5章).

《数据结构(第5章).》由会员分享，可在线阅读，更多相关《数据结构(第5章).（74页珍藏版）》请在金锄头文库上搜索。

1、第五章 数组、特殊矩阵和广义表 教学内容：5.1 多维数组 5.2 特殊矩阵的压缩存储 5.3 稀疏矩阵 5.4 广义表 教学目的：理解多维数组的结构特点和在内存中的两种顺序存储方式； 理解并掌握矩阵和特殊矩阵元素在存储区中地址的计算； 领会稀疏矩阵的压缩方式和简单运算； 了解广义表的定义和基本运算。 教学重点：多维数组的逻辑结构； 多维组的两种顺序存储方式，计算给定元素在存储区中的地址； 对称矩阵、三角矩阵的压缩存储方式； 稀疏矩阵的三元组表表示方法。 教学难点： 稀疏矩阵的压缩存储表示下的运算的实现 学时安排：4学时 Date1数据结构讲义 5.1 多维数组 w 数组的逻辑结构 w 数组的

2、内存映象 Date2数据结构讲义 5.1.1 数组的逻辑结构 w 数组是我们熟悉的一种数据结构，可以看作线性表的 推广。数组作为一种数据结构其特点是结构中的元素本 身可以是具有某种结构的数据，但属于同一数据类型， 比如：一维数组可以看作一个线性表，二维数组可以看 作“数据元素是一维数组”的一维数组，三维数组可以看作 “数据元素是二维数组”的一维数组，依此类推。 Date3数据结构讲义 数组是一个具有固定格式和数量的数据有序集，每一个 数据元素有唯一的一组下标来标识，因此，在数组上不能 做插入、删除数据元素的操作。通常在各种高级语言中数 组一旦被定义，每一维的大小及上下界都不能改变。在数 组中通

3、常做下面两种操作： (1) 取值操作：给定一组下标，读其对应的数据元素。 (2) 赋值操作：给定一组下标，存储或修改与其相对应 的数据元素。 我们着重研究二维和三维数组，因为它们的应用是广泛 的，尤其是二维数组。 Date4数据结构讲义 5.1.2 数组的内存映象 w 通常，数组在内存被映象为向量，即用向量作为数组 的一种存储结构，这是因为内存的地址空间是一维的， 数组的行列固定后，通过一个映象函数，则可根据数组 元素的下标得到它的存储地址。 w 对于一维数组按下标顺序分配即可。 w 对多维数组分配时，要把它的元素映象存储在一维存 储器中，一般有两种存储方式：一是以行为主序（或先 行后列）的顺

4、序存放，如BASIC、PASCAL、COBOL、C等 程序设计语言中用的是以行为主的顺序分配，即一行分 配完了接着分配下一行。另一种是以列为主序（先列后 行）的顺序存放，如FORTRAN语言中，用的是以列为主 序的分配顺序，即一列一列地分配。 Date5数据结构讲义 以行为主序的分配规律是：最右边的下标先变化， 即最右下标从小到大，循环一遍后，右边第二个下标 再变，从右向左，最后是左下标。以列为主序分 配的规律恰好相反：最左边的下标先变化，即最左下 标从小到大，循环一遍后，左边第二个下标再变， ，从左向右，最后是右下标。 Date6数据结构讲义 例如一个23二维数组，逻辑结构可以用左图表 示。

5、以行为主序的内存映象如右图（a）所示。 分配 顺序为：a11 ，a12 ，a13 ，a21 ，a22 ，a23 ；以列为主序 的分配顺序为：a11 ，a21 ，a12 ，a22 ，a13 ，a23 ；它 的内存映象如右图（b）所示。 Date7数据结构讲义 设有mn二维数组Amn，下面我们看按元素的下标求其 地址的计算： 以“以行为主序”的分配为例：设数组的基址为LOC(a11) ，每个数组元素占据l个地址单元，那么aij 的物理地址可用 一线性寻址函数计算： LOC(aij) = LOC(a11) + ( (i-1)*n + j-1 ) * l 在C语言中，数组中每一维的下界定义为0，则：

6、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 Date8数据结构讲义 同理对于三维数组Amnp，即mnp数组，对于数组元素 aijk其物理地址为： LOC(aijk)=LOC(a111)+( ( i-1) *n*p+ (j-1)*p +k-1)*l 推广到一般的三维数组：Ac1.d1 c2.d2 c3.d3，则aijk 的物理地址为： LOC(i,j)=LOC(a

7、 c1 c2 c3)+( (i- c1) *( d2 - c2 + 1)* (d3- c3 + 1)+ (j- c2) *( d3- c3 + 1)+(k- c3)*l Date9数据结构讲义 三维数组的逻辑结构和以行为主序的分配示意图如 图所示。 Date10数据结构讲义 例5.1 若矩阵Amn 中存在某个元素aij满足：aij是第i行中 最小值且是第j列中的最大值，则称该元素为矩阵A的一个 鞍点。试编写一个算法，找出A中的所有鞍点。 基本思想：在矩阵A中求出每一行的最小值元素，然后 判断该元素它是否是它所在列中的最大值，是则打印出， 接着处理下一行。矩阵A用一个二维数组表示。 Date11

8、数据结构讲义 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 算法的时间性能为O(m*(n+m*n)。 Date12数据结构讲义 5.2 特殊矩阵的压缩存储 w 对称矩阵 w 三角矩阵 w 带状矩阵 Da

9、te13数据结构讲义 5.2.1 对称矩阵 w 对称矩阵的特点是：在一个n阶方阵中，有aij=aji ，其 中1i , jn，如图所示是一个阶对称矩阵。 Date14数据结构讲义 对称矩阵关于主对角线对称，因此只需存储上三角或下 三角部分即可。比如，只存储下三角中的元素aij，其特点 是中ji且1in，对于上三角中的元素aij ，它和对应的aji 相等，因此当访问的元素在上三角时，直接去访问和它对 应的下三角元素即可，这样，原来需要n*n个存储单元， 现在只需要n(n+1)/2个存储单元了，节约了n(n-1)/2个存储 单元，当n较大时，这是可观的一部分存储资源。 Date15数据结构讲义 如

10、何只存储下三角部分？对下三角部分以行为主序顺序 存储到一个向量中去，在下三角中共有n*(n+1)/2个元素， 因此，不失一般性，设存储到向量SAn(n+1)/2中，存储 顺序可用下图示意，这样，原矩阵下三角中的某一个元素 aij则具体对应一个sak，下面的问题是要找到k与i、j之间的 关系。 Date16数据结构讲义 对于下三角中的元素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

11、的关系为： k=i*(i-1)/2+j-1 (kn*(n+1)/2 ) 若imumu=A-=A-nunu; B-; B-nunu=A-=A-mumu; B-; B-tutu=A-=A-tutu; ; /* /*稀疏矩阵的行、列、元素个数稀疏矩阵的行、列、元素个数*/*/ if (B-if (B-tutu0)0) /*/*有非零元素则转换有非零元素则转换*/*/ q=1;q=1; for ( for (colcol=1;=1; col colnunu); ); col col+)+) /*/*按按A A的列序转换的列序转换*/*/ for (p=1; pfor (p=1; ptutu); p+)

12、; p+) /*/*扫描整个三元组表扫描整个三元组表*/*/ if (A-datap.j=if (A-datap.j=colcol ) ) B-dataq.i= A-datap.j ; B-dataq.i= A-datap.j ; B-dataq.j= A-datap.i ; B-dataq.j= A-datap.i ; B-dataq.v= A-datap.v; B-dataq.v= A-datap.v; q+; q+; return B; return B; /*/*返回的是转置矩阵的指针返回的是转置矩阵的指针*/*/ Date29数据结构讲义 分析该算法，其时间主要耗费在分析该算法，其时

13、间主要耗费在colcol和和p p的二重循环上，的二重循环上， 所以时间复杂性为所以时间复杂性为O(n*t)O(n*t)，( (设设mm、n n是原矩阵的行、列是原矩阵的行、列 ，t t是稀疏矩阵的非零元素个数是稀疏矩阵的非零元素个数) )，显然当非零元素的个，显然当非零元素的个 数数t t和和m*nm*n同数量级时，算法的时间复杂度为同数量级时，算法的时间复杂度为O(m*nO(m*n 2 2 ) )， 和通常存储方式下矩阵转置算法相比，可能节约了一定和通常存储方式下矩阵转置算法相比，可能节约了一定 量的存储空间，但算法的时间性能更差一些。量的存储空间，但算法的时间性能更差一些。 Date30

14、数据结构讲义 上述算法效率低的原因是算法要从上述算法效率低的原因是算法要从A A的三元组表中寻的三元组表中寻 找第一列、第二列、找第一列、第二列、，要反复搜索，要反复搜索A A表，若能直接确表，若能直接确 定定A A中每一三元组在中每一三元组在B B中的位置，则对中的位置，则对A A的三元组表扫描的三元组表扫描 一次即可。这是可以做到的，因为一次即可。这是可以做到的，因为A A中第一列的第一个中第一列的第一个 非零元素一定存储在非零元素一定存储在B.data1B.data1，如果还知道第一列的非如果还知道第一列的非 零元素的个数，那么第二列的第一个非零元素在零元素的个数，那么第二列的第一个非零元素在B.dataB.data 中的位置便等于第一列的第一个非零元素在中的位置便等于第一