武汉软件工程职业学《数据结构讲义》第07讲 数组.docVIP

1．掌握数组的基本概念及数组的顺序存储结构。 2.了解并熟悉特殊矩阵的压缩存储。 3．掌握稀疏矩阵的三元存储。 教学重点： 数组的概念及顺序存储结构。 稀疏矩阵的转置矩阵。 教学难点： 稀疏矩阵的转置矩阵 授课内容 2.6 数组 2.6.1 数组的基本概念 数组是一种常用对数据结构，几乎所有的程序设计语言都把数组类型设定为固有类型。按一定格式排列起来的一列同一属性的项目,是相同类型的数据元素的集合。有一维数组A[]、二维数组A[5][]、三维数组A[][5][5]、多维数组等。二维数组：每一行都是一个线性表，每一个数据元素既在一个行表中，又在一个列表中2-6-1（a）所示，（如PASCAL 、C等）；但在有的语言（如FORTRAN）中采用的是以列序为主的存储方式，如图2-6-1（b）所示。 在C语言中，数组中任一元素A[i][j]的存储位置可用下列公式计算： LOC（A[i][j]）=LOC（A[0][0]）+（i*col+j）*L其中，LOC（A[0][0]）为数组的起始位置，L每个数据元素所占存储单元个数。 由于在定义数组时，LOC（A[0][0]）、L和col是已知的，因此可以根据上式计算出任一元素的存储地址，实现随机存取。 2.6.3 特殊矩阵的压缩存储 矩阵在科学与工程计算机中有广泛的应用。在用高级语言编程中，通常用二维数组来表示矩阵。这样，利用上面的地址计算公式可以快速访问矩阵中的每个元素。然而，实际应用中会遇到一些特殊的矩阵，所谓特殊矩阵，是指矩阵中值相同的元素或着零元素的部分有一定的规律。例如，对称矩阵、三角矩阵和三对角矩阵都是特殊矩阵。 若一个n阶矩阵A中的元素满足：Aij=Aij（1≤ i≤ n ，1≤ j ≤ n）则称A为对矩阵；当一个方阵的主对角线以上或以上的所有元素皆为零时，该矩阵为三角矩阵；除了主对角线上和直接在主对角线上下方的对角线的元素外，其他所有元素皆为零的矩阵称为三角矩阵。图2-6-2是两种特殊矩阵的形式。 为了节省存储空间，可以对这些矩阵进行压缩存储。所谓压缩存储就是为多个值相同的元素只分配给一个存储空间，对零元素不分配存储空间。由于特殊矩阵中非零元素的分布有明显的规律，因此我们可将其压缩存储到一个一维数组中，并找到每个非零元素在一维数组中的对应关系。 2.6.4 稀疏矩阵的三元组存储 当一个m×n的矩阵A中有k个非零元素，若km×n 且这些非零元素在矩阵中的分布有没有一定的规律时，则称这种矩阵为稀疏矩阵。 例如，式（２.６.１）所示的矩阵Ｍ和它的转置矩阵Ｎ，在３０个元素中只有７个非零元素，显然是一个稀疏矩阵。 5 0 0 12 0 0 5 0 8 0 0 0 0 16 0 0 0 0 0 0 0 0 M= 8 0 11 0 27 0 N= 0 16 11 0 4 0 0 0 0 0 0 12 0 0 0 0 0 0 4 0 0 0 0 0 27 0 0 0 0 0 0 0 按照压缩存储概念，只需存储稀疏矩阵的非零元素。但是，为了实现矩阵的各种运算，除了存储非零元素外，还必须同时记下它所在的行和列。这样，一个三元组（ｉ,ｊ,Ａij）便唯一的确定了矩阵的一个非零元素，其中ｉ、ｊ分别表示非零元素的行号和列号，Ａij表示非零元素值。 下列７个三元组表示了式（２.６.１）中的矩阵Ｍ的７个非零元素： （１,１,５）（１,４,１２）（２,３,１６）（３,１,８）（３,３,１１）（３,５,２７）（５,３,４） 1、 三元组顺序表 假设以顺序存储结构来表示三元组表（triple table）,则可得到稀疏矩阵的一种压缩存储方式，即三元组顺序表，简称三元组表。 其结构描述如下： Typedef struct{ int i,j; ELEMTP v; }TripleTp ; Typedef struct{ TripleTp elem[MAXSIZE]; int m,n,t; }SpmaTp; 在此，elem域中表示非零元素的三元组是按以行为主的顺序排列的。假设a和b是SpM