《数据结构》课程教学资源：第二章 数组

答是要 2.1数组的定义 2.2数组的版序表示与实现 2.3距阵的压缩存储

内容提要 2.1 数组的定义 2.2 数组的顺序表示与实现 2.3 距阵的压缩存储

21数组 数组:相同类型数据的有序集合。是数据结构中最 基本的结构类型 数组的操作: 通过给定下标取出相应元素的值 通过给定下标修改相应元素的值 数组只有顺序存储结构,多维数组实际 上也是按照一维数组存放的 二维数组aNIM]中每个单元占有L个字节,那么a 的存储位置 组的 Loc(ai=Loc(aoo+(M+j*L akiko.k 三维数组aPNM中每单元占个字的存情位 的存储位置: Loc(aik=Loc(a000)+(i N*M+j*M+k)I

2.1 数组 数组：相同类型数据的有序集合。是数据结构中最 基本的结构类型 数组的操作： 通过给定下标取出相应元素的值 通过给定下标修改相应元素的值 数组只有顺序存储结构，多维数组实际 上也是按照一维数组存放的 二维数组a[N][M]中每个单元占有L个字节，那么a[i][j] 的存储位置： Loc(aij)=Loc(a00)+(i*M+j)*L 三维数组a[P][N][M]中每单元占L个字节，那么a[i][j][k] 的存储位置： Loc(aijk)=Loc(a000)+(i*N*M+j*M+k)*L n维数组的 a[k1][k2]..[kn] 的存储位置 如何求？

2数组的顺表示与线现 数组的顺序表示 ∥---数组的版序存信表示 include ∥|准头文件提供宏 va start, va arg 和 va end,用于存取变长参数表 # define maX Array dim8∥假设数组维数的最大值为8 ty pede struct t ElemType‘base; ∥数组元素基址,由 InitArray分配 int dim ∥/数组维数 int bounds;∥数组维界基址,由 nitArray分配 int constants;∥/数组映象函数常量基址, ∥/由 nitArray分配 Array 数组的顺序实现(见书P93)

2.2 数组的顺序表示与实现 数组的顺序表示 //---------数组的顺序存储表示----------- #include // 标准头文件,提供宏va_start,va_arg // 和va_end，用于存取变长参数表 #define MAX_ARRAY_DIM 8 // 假设数组维数的最大值为8 typedef struct { ElemType *base; // 数组元素基址，由InitArray分配 int dim; // 数组维数 int *bounds; // 数组维界基址，由InitArray分配 int *constants; // 数组映象函数常量基址， // 由InitArray分配 }Array; 数组的顺序实现（见书 P93）

23的的纺在 利用数组猜存信矩阵|a0a1C 20a21a22 a04020320以压缩存储的矩阵夕 a30 a31 a32 a33 10a11a2a31 特殊矩阵 三角矩阵 a20a21a2a32 (1)三角矩阵 00c01 30 a31 a32 a33 )对称矩阵 10a11a12 对称矩阵 (3)带状矩阵 a21 a22 a 2、稀疏矩阵 a32 a33 NxM个单元中,只有T个非 带状矩阵 零元素,当T/N×M)<=0.05时, 就是稀疏矩阵

2.3 距阵的压缩存储 利用数组压缩存储矩阵 可以压缩存储的矩阵有两种： 1、特殊矩阵 (1)三角矩阵 (2)对称矩阵 (3)带状矩阵 2、稀疏矩阵 NM个单元中，只有T个非 零元素，当T/(N  M)<=0.05时， 就是稀疏矩阵。                       a00 a10 a11 C a20 a21 a22 a30 a31 a32 a33 下三角矩阵                       a00 a10 a20 a30 a10 a11 a21 a31 a20 a21 a22 a32 a30 a31 a32 a33 对称矩阵                       a00 a01 a10 a11 a12 a21 a22 a23 a32 a33 带状矩阵

的的能cm (1)三角矩阵的压缩存储 需要将矩阵中的三角区域的数据按照顺序存放 到一维数组中即可,关键的问题是确定矩阵的两个 下标团与一维数组的下标的对应关系: 以上三角矩阵为例,A[=前面的元素个数 是: N+N-1+N-2+.+N+1=(2N-+1)2 在本行前面有i个元素,因此,在一维数组中, A[的位置:k=1(2N-+1)2+i ao0 a01 a02 a03 11a12a13 ooao1 a02 a12a13a22a23a a 33

距阵的压缩存储(cont’d) (1)三角矩阵的压缩存储 只需要将矩阵中的三角区域的数据按照顺序存放 到一维数组中即可，关键的问题是确定矩阵的两个 下标[i][j]与一维数组的下标[k]的对应关系： 以上三角矩阵为例，A[i][j](j>=i)前面的元素个数 是： N+N-1+N-2+…+N-i+1=i*(2N-i+1)/2 在本行前面有j-i个元素，因此，在一维数组中， A[i][j]的位置：k= i*(2N-i+1)/2+j-i                       a00 a01 a02 a03 a11 a12 a13 a22 a23 a33 a00 a01 a02 a03 a11 a12 a13 a22 a23 a33

单的 2)对称矩阵的压缩存储 可以米用三角矩阵的方式 3)带状矩阵的压缩存储 只需将非零元素存放在一维数组中,矩阵 下标与一维数组下标k的对应关系: k=i3-1+j-(i-1)=2*计+j 10a11a12 a21a22a23 aooao1a1oa11a12a21a2 2a2 a2la a32 a 带状矩阵

距阵的压缩存储(cont’d) (2)对称矩阵的压缩存储 可以采用三角矩阵的方式 (3)带状矩阵的压缩存储 只需将非零元素存放在一维数组中，矩阵 下标[i][j]与一维数组下标k的对应关系： k=i*3-1+j-(i-1)=2*i+j a00 a01 a10 a11 a12 a21 a22 a23 a32 a33                       a00 a01 a10 a11 a12 a21 a22 a23 a32 a33 带状矩阵

距的cn (4)稀硫矩阵的压缩存储 ①顺序存储:三元组的顺序表 元组=(行,列值 数据类型定义: #definen 500 typedef struct int 1, j ∥行列下标 Elemtype e, ∥零值 STriple typedef struct t Triple data NI int mu. nu. tu ∥矩阵的行数、列数和非零值的个数 )Matrix

距阵的压缩存储(cont’d) (4)稀疏矩阵的压缩存储 ① 顺序存储：三元组的顺序表 三元组＝(行,列,值) 数据类型定义： #define N 500 typedef struct { int i,j; //行列下标 Elemtype e; //非零值 }Triple; typedef struct { Triple data[N]; int mu, nu, tu; //矩阵的行数、列数和非零值的个数 }Matrix;

距的压存信c 三元组数组存放的稀疏矩阵转置算法 转置操作:即将A[[改成A[将N×M矩阵 改成M×N矩阵 00-30015 01290000 12000180 0000000 9002400 30000140 00000-7 00240000 000000 01800000 0140000 500-7000 000000

三元组数组存放的稀疏矩阵转置算法 转置操作：即将A[i][j]改成A[j][i],将NM矩阵 改成M  N矩阵。                       0 12 9 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 0 15 0 0 -7 0 0 0                       0 0 -3 0 0 15 12 0 0 0 18 0 9 0 0 24 0 0 0 0 0 0 0 -7 0 0 0 0 0 0 0 14 0 0 0 0 0 0 0 0 0 0 距阵的压缩存储(cont’d)

单的 三元组数组存放的稀疏矩阵转置算法 算法思想 1)扫描整个三元组数组,将每个三元组的和 互换。 0129000002 2.0.9 0000000 20-302-3 30000140 00240000 01800000 3.2.24 3.24 l500-70004118 4.18 5.0.15 5.15 53-735-7

三元组数组存放的稀疏矩阵转置算法 算法思想： (1)扫描整个三元组数组，将每个三元组的i和j 互换。                       0 12 9 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 0 15 0 0 -7 0 0 0 0,1,12 0,2, 9 2,0,-3 2,5,14 3,2,24 4,1,18 5,0,15 5,3,-7 1,0,12 2,0, 9 0,2,-3 5,2,14 2,3,24 1,4,18 0,5,15 3,5,-7 距阵的压缩存储(cont’d)

单的 三元组数组存放的稀疏矩阵转置算法 算法思想 (2)原来的三元组数组是按照行序存放的,j互 9112换后也要调整称为行序存放的方式。这需要事 0.29先指导转置后每行非零元素的个数,也就是原 0 矩阵每列非零元素的个数。通过单独扫描一次 314整个三元组数组,就可以计算得到这些数据 13224有了这些数据,就可以确定转置后的矩阵的每 行的非零元素在数组中的位置。 41,18 5.3.-7 0123456 numi]2221010 pos[jl0246778

算法思想： (2) 原来的三元组数组是按照行序存放的，ij互 换后也要调整称为行序存放的方式。这需要事 先指导转置后每行非零元素的个数，也就是原 矩阵每列非零元素的个数。通过单独扫描一次 整个三元组数组，就可以计算得到这些数据。 有了这些数据，就可以确定转置后的矩阵的每 行的非零元素在数组中的位置。 三元组数组存放的稀疏矩阵转置算法 0,1,12 0,2, 9 2,0,-3 2,5,14 3,2,24 4,1,18 5,0,15 5,3,-7 num[i] 2 2 2 1 0 1 0 rpos[i] 0 2 4 6 7 7 8 0 1 2 3 4 5 6 距阵的压缩存储(cont’d)