数据结构第五章C剖析课件

数据数据结构第五章构第五章C剖析剖析 第五章第五章第五章第五章 多维数组和广义表多维数组和广义表多维数组和广义表多维数组和广义表5.1 5.1 多维数组多维数组多维数组多维数组5.2 5.2 矩阵的压缩存储矩阵的压缩存储矩阵的压缩存储矩阵的压缩存储 5.2.1 5.2.1 特殊矩阵特殊矩阵特殊矩阵特殊矩阵 5.2.2 5.2.2 稀疏矩阵稀疏矩阵稀疏矩阵稀疏矩阵5.3 5.3 广义表的概念广义表的概念广义表的概念广义表的概念5.4 5.4 广义表的存储广义表的存储广义表的存储广义表的存储本章主题本章主题本章主题本章主题：多维数组、特殊矩阵和广义表：多维数组、特殊矩阵和广义表：多维数组、特殊矩阵和广义表：多维数组、特殊矩阵和广义表 教学目的教学目的教学目的教学目的：掌握数组和广义表的定义、运算：掌握数组和广义表的定义、运算：掌握数组和广义表的定义、运算：掌握数组和广义表的定义、运算教学难点教学难点教学难点教学难点：矩阵的压缩存储：矩阵的压缩存储：矩阵的压缩存储：矩阵的压缩存储 对对对对许许许许多多多多应应应应用用用用程程程程序序序序来来来来说说说说，使使使使用用用用简简简简单单单单的的的的线线线线性性性性表表表表和和和和数数数数组组组组完完完完成成成成任任任任务务务务就就就就足足足足够够够够了了了了，但但但但是是是是有有有有一一一一些些些些应应应应用用用用程程程程序序序序不不不不能能能能使使使使用用用用简简简简单单单单线线线线性表来有效地实现。人们可以对线性表进行扩展，实现一些功能更强大、具有更多操作的性表来有效地实现。人们可以对线性表进行扩展，实现一些功能更强大、具有更多操作的性表来有效地实现。人们可以对线性表进行扩展，实现一些功能更强大、具有更多操作的性表来有效地实现。人们可以对线性表进行扩展，实现一些功能更强大、具有更多操作的高级线性结构高级线性结构高级线性结构高级线性结构。前前前前几几几几章章章章讨讨讨讨论论论论的的的的线线线线性性性性结结结结构构构构中中中中的的的的数数数数据据据据元元元元素素素素都都都都是是是是非非非非结结结结构构构构的的的的原原原原子子子子类类类类型型型型，元元元元素素素素的的的的值值值值是是是是不不不不再再再再分分分分解解解解的的的的。本本本本章章章章讨讨讨讨论论论论的的的的两两两两种种种种数据结构数据结构数据结构数据结构-数组和广义表可以看成是线性表在下述含义上的扩展：数组和广义表可以看成是线性表在下述含义上的扩展：数组和广义表可以看成是线性表在下述含义上的扩展：数组和广义表可以看成是线性表在下述含义上的扩展：表中的数据元素本身也是一个数据结构。表中的数据元素本身也是一个数据结构。表中的数据元素本身也是一个数据结构。表中的数据元素本身也是一个数据结构。多维数组和广义表的多维数组和广义表的多维数组和广义表的多维数组和广义表的逻辑特征逻辑特征逻辑特征逻辑特征是：一个数据元素可能有多个直接前趋和多个直接后继。是：一个数据元素可能有多个直接前趋和多个直接后继。是：一个数据元素可能有多个直接前趋和多个直接后继。是：一个数据元素可能有多个直接前趋和多个直接后继。5.1 5.1 多维数组多维数组多维数组多维数组 数组是我们最熟悉的数据类型，在早期的高级语言中，数组是唯一可供使用的结构类型。数组是我们最熟悉的数据类型，在早期的高级语言中，数组是唯一可供使用的结构类型。数组是我们最熟悉的数据类型，在早期的高级语言中，数组是唯一可供使用的结构类型。数组是我们最熟悉的数据类型，在早期的高级语言中，数组是唯一可供使用的结构类型。数数数数组组组组（ArrayArrayArrayArray）是是是是由由由由n(n1)n(n1)n(n1)n(n1)个个个个相相相相同同同同类类类类型型型型数数数数据据据据元元元元素素素素a a a a0 0 0 0，a a a al l l l，aaaai i i i，a a a an-1n-1n-1n-1构构构构成成成成的的的的有有有有限限限限序序序序列列列列。n n n n是是是是数数数数组组组组的的的的长长长长度度度度。其其其其中中中中数数数数组组组组中中中中的的的的数数数数据据据据元元元元素素素素a a a ai i i i是是是是一一一一个个个个数数数数据据据据结结结结构构构构，即即即即a ai i可可可可以以以以是是是是线线线线性性性性表表表表中中中中的的的的一一一一个个个个元元元元素素素素，本本本本身身身身也也也也可可可可以以以以是是是是一一一一个个个个线线线线性性性性表表表表，而而而而线线线线性性性性子子子子表表表表中中中中的的的的每每每每一一一一个个个个数数数数据据据据元元元元素素素素还还还还可可可可以以以以再再再再分分分分解解解解 。根根根根据据据据数数数数组组组组元元元元素素素素a a a ai i i i的的的的组组组组织织织织形形形形式式式式不不不不同同同同，数数数数组组组组可可可可以以以以分分分分为为为为一一一一维维维维数数数数组组组组、二维数组以及多维（二维数组以及多维（二维数组以及多维（二维数组以及多维（n n n n维）数组。维）数组。维）数组。维）数组。有时也把有时也把一维数组一维数组称为称为向量向量，二维数组二维数组称为称为矩阵矩阵。数组中每个元素都是由一个值和一组下标来确定的。同线。数组中每个元素都是由一个值和一组下标来确定的。同线性表一样，数组中的所有数据元素都必须属于同一数据类型。元素下标的个数被称为数组的维数。显然，当维数性表一样，数组中的所有数据元素都必须属于同一数据类型。元素下标的个数被称为数组的维数。显然，当维数为为1 1时，数组就退化为定长的线性表。时，数组就退化为定长的线性表。由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单。多维数组是向量的推广。例如，二维数组：其它复杂的结构更为简单。多维数组是向量的推广。例如，二维数组：a a1111 a a1212 a a1n1n a a2121 a a2222 a a2n2n a am1m1 a am2m2 a amnmn A Amn=可以看成是由可以看成是由可以看成是由可以看成是由m m m m个行向量组成的向量，也可以看成是个行向量组成的向量，也可以看成是个行向量组成的向量，也可以看成是个行向量组成的向量，也可以看成是n n n n个列向量组成的向量。个列向量组成的向量。个列向量组成的向量。个列向量组成的向量。二维数组中的每个元素二维数组中的每个元素二维数组中的每个元素二维数组中的每个元素a a a aijijijij均属于两个向量：第均属于两个向量：第均属于两个向量：第均属于两个向量：第i i i i行的行向量和第行的行向量和第行的行向量和第行的行向量和第j j j j列的列向量，即除边界外，每个元素列的列向量，即除边界外，每个元素列的列向量，即除边界外，每个元素列的列向量，即除边界外，每个元素a a a aijijijij都恰好有两个直接前趋和两个直接后继结点。都恰好有两个直接前趋和两个直接后继结点。都恰好有两个直接前趋和两个直接后继结点。都恰好有两个直接前趋和两个直接后继结点。二维数组仅有一个开始点二维数组仅有一个开始点二维数组仅有一个开始点二维数组仅有一个开始点a a a a11111111 ，它没有前趋；仅有一个终端结点它没有前趋；仅有一个终端结点它没有前趋；仅有一个终端结点它没有前趋；仅有一个终端结点a a a amnmnmnmn ，它没有后继。它没有后继。它没有后继。它没有后继。边界上的结点（开始结点和终端结点除外）只有一个直接前趋或者只有一个直接后继。边界上的结点（开始结点和终端结点除外）只有一个直接前趋或者只有一个直接后继。边界上的结点（开始结点和终端结点除外）只有一个直接前趋或者只有一个直接后继。边界上的结点（开始结点和终端结点除外）只有一个直接前趋或者只有一个直接后继。三维数组中的每个元素三维数组中的每个元素三维数组中的每个元素三维数组中的每个元素a a a aijkijkijkijk都属于三个向量：每个元素最多可以有三个直接前趋和三个直接后继。都属于三个向量：每个元素最多可以有三个直接前趋和三个直接后继。都属于三个向量：每个元素最多可以有三个直接前趋和三个直接后继。都属于三个向量：每个元素最多可以有三个直接前趋和三个直接后继。依次类推，依次类推，依次类推，依次类推，m m m m维数组的每个元素都属于维数组的每个元素都属于维数组的每个元素都属于维数组的每个元素都属于m m m m个向量，最多可以有个向量，最多可以有个向量，最多可以有个向量，最多可以有m m m m个直接前趋和个直接前趋和个直接前趋和个直接前趋和m m m m个直接后继。个直接后继。个直接后继。个直接后继。由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一个线性序列，然后将这个线性序列存放在存储器中。个线性序列，然后将这个线性序列存放在存储器中。个线性序列，然后将这个线性序列存放在存储器中。个线性序列，然后将这个线性序列存放在存储器中。又由于对数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就又由于对数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就又由于对数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就又由于对数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。通常有两种顺序存储方式通常有两种顺序存储方式通常有两种顺序存储方式通常有两种顺序存储方式：行优先顺序行优先顺序行优先顺序行优先顺序将数组元素按行排列，第将数组元素按行排列，第将数组元素按行排列，第将数组元素按行排列，第i+1i+1i+1i+1个行向量紧接在第个行向量紧接在第个行向量紧接在第个行向量紧接在第i i i i个行向量后面。以二维数组为例，按行优先个行向量后面。以二维数组为例，按行优先个行向量后面。以二维数组为例，按行优先个行向量后面。以二维数组为例，按行优先顺序存储的线性序列为：顺序存储的线性序列为：顺序存储的线性序列为：顺序存储的线性序列为：a a a a11111111,a,a,a,a12121212,a,a,a,a1n1n1n1n,a,a,a,a21212121,a,a,a,a22222222,a,a,a,a2n2n2n2n,a,a,a,am1m1m1m1,a,a,a,am2m2m2m2,a,a,a,amnmnmnmn 在在在在PASCALPASCALPASCALPASCAL、C C C C语言中，数组就是按行优先顺序存储的。语言中，数组就是按行优先顺序存储的。语言中，数组就是按行优先顺序存储的。语言中，数组就是按行优先顺序存储的。列优先顺序列优先顺序列优先顺序列优先顺序将数组元素按列向量排列，第将数组元素按列向量排列，第将数组元素按列向量排列，第将数组元素按列向量排列，第j+1j+1j+1j+1个列向量紧接在第个列向量紧接在第个列向量紧接在第个列向量紧接在第j j j j个列向量之后，个列向量之后，个列向量之后，个列向量之后，A A A A的的的的m*nm*nm*nm*n个元素按列优先个元素按列优先个元素按列优先个元素按列优先顺序存储的线性序列为：顺序存储的线性序列为：顺序存储的线性序列为：顺序存储的线性序列为：a a a a11111111,a,a,a,a21212121,a,a,a,am1m1m1m1,a,a,a,a12121212,a,a,a,a22222222,a,a,a,am2m2m2m2,a,a,a,an1n1n1n1,a,a,a,an2n2n2n2,a,a,a,anmnmnmnm 在在在在FORTRANFORTRANFORTRANFORTRAN语言中，数组就是按列优先顺序存储的。语言中，数组就是按列优先顺序存储的。语言中，数组就是按列优先顺序存储的。语言中，数组就是按列优先顺序存储的。假设有一个假设有一个假设有一个假设有一个342342342342的三维数组的三维数组的三维数组的三维数组A A A A，共有，共有，共有，共有24242424个元素，其逻辑结构如图所示。个元素，其逻辑结构如图所示。个元素，其逻辑结构如图所示。个元素，其逻辑结构如图所示。三维数组的标号由三个数字表示，即行、列、纵三个方向。三维数组的标号由三个数字表示，即行、列、纵三个方向。三维数组的标号由三个数字表示，即行、列、纵三个方向。三维数组的标号由三个数字表示，即行、列、纵三个方向。a a a a142142142142表示第表示第表示第表示第1 1 1 1行，第行，第行，第行，第4 4 4 4列，第列，第列，第列，第2 2 2 2纵的元素。如果对纵的元素。如果对纵的元素。如果对纵的元素。如果对A A A A342342342342（下标从（下标从（下标从（下标从1 1 1 1开始）采用以行优先的方法存放，即行下标变化最慢，纵下标变化最快，则顺序为：开始）采用以行优先的方法存放，即行下标变化最慢，纵下标变化最快，则顺序为：开始）采用以行优先的方法存放，即行下标变化最慢，纵下标变化最快，则顺序为：开始）采用以行优先的方法存放，即行下标变化最慢，纵下标变化最快，则顺序为：a a a a111111111111,a,a,a,a112112112112,a,a,a,a121121121121,a,a,a,a122122122122,a,a,a,a331331331331,a,a,a,a332332332332,a,a,a,a341341341341,a,a,a,a342342342342 a112a132a142a122a111a131a141a121a211a231a241a221a311a331a341a321a242a342 采用以纵优先的方法存放，即纵下标变化最慢，行下标变化采用以纵优先的方法存放，即纵下标变化最慢，行下标变化最快，则顺序为：最快，则顺序为：a a111111,a,a211211,a,a311311,a,a121121,a,a221221,a,a321321,a,a132132,a,a232232,a,a332332,a,a142142,a,a242242,a,a342342 以上规则可以推广到多维数组的情况：优先顺序可规定为先排最右的下标，从右到左，最后排最左下标：列以上规则可以推广到多维数组的情况：优先顺序可规定为先排最右的下标，从右到左，最后排最左下标：列优先顺序与此相反，先排最左下标，从左向右，最后排最右下标。优先顺序与此相反，先排最左下标，从左向右，最后排最右下标。按上述两种方式顺序存储的数组，只要知道开始结点的存放地址（即基地址），维数和每维的上、下界，以按上述两种方式顺序存储的数组，只要知道开始结点的存放地址（即基地址），维数和每维的上、下界，以及每个数组元素所占用的单元数，就可以将数组元素的存放地址表示为其下标的线性函数。因此，数组中的任一及每个数组元素所占用的单元数，就可以将数组元素的存放地址表示为其下标的线性函数。因此，数组中的任一元素可以在相同的时间内存取，即元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构。顺序存储的数组是一个随机存取结构。总结：总结：任任何何多多维维数数组组都都可可以以看看作作一一个个线线性性表表，这这时时线线性性表表中中的的每每个个数数据据元元素素也也是是一一个个线线性性表表。例例如如一一个个二二维维数数组组可可以看作是每个数据元素都是相同类型的一维数组。多维数组是特殊的线性表，是线性表的推广。以看作是每个数据元素都是相同类型的一维数组。多维数组是特殊的线性表，是线性表的推广。数组的性质：数组的性质：(1)(1)数数组组中中的的数数据据元元素素数数目目固固定定。一一旦旦定定义义了了一一个个数数组组，其其数数据据元元素素数数目目不不再再有有增增减减变变化化。它它属属于于静静态态分分配配存存储储空间的数据结构。空间的数据结构。(2)(2)数组中的数据元素必须具有相同的数据类型。数组中的数据元素必须具有相同的数据类型。(3)(3)数组中的每个数据元素都有一组唯一的下标值。数组中的每个数据元素都有一组唯一的下标值。(4)(4)数组是一种随机存储结构。可随机存取数组中的任意数据元素。数组是一种随机存储结构。可随机存取数组中的任意数据元素。例如，二维数组例如，二维数组例如，二维数组例如，二维数组A A A Amnmnmnmn按按按按“行优先顺序行优先顺序行优先顺序行优先顺序”存储在内存中，假设每个元素占用存储在内存中，假设每个元素占用存储在内存中，假设每个元素占用存储在内存中，假设每个元素占用d d d d个存储单元。个存储单元。个存储单元。个存储单元。元素元素元素元素a a a aijijijij的存储地址应是数组的基地址加上排在的存储地址应是数组的基地址加上排在的存储地址应是数组的基地址加上排在的存储地址应是数组的基地址加上排在a a a aijijijij前面的元素所占用的单元数。因为前面的元素所占用的单元数。因为前面的元素所占用的单元数。因为前面的元素所占用的单元数。因为a a a aijijijij位于第位于第位于第位于第i i i i行、第行、第行、第行、第j j j j列，列，列，列，前面前面前面前面i-1i-1i-1i-1行一共有行一共有行一共有行一共有(i-1)n(i-1)n(i-1)n(i-1)n个元素，第个元素，第个元素，第个元素，第i i i i行上行上行上行上a a a aijijijij前面又有前面又有前面又有前面又有j-1j-1j-1j-1个元素，故它前面一共有个元素，故它前面一共有个元素，故它前面一共有个元素，故它前面一共有(i-1)n+j-1(i-1)n+j-1(i-1)n+j-1(i-1)n+j-1个元素，因个元素，因个元素，因个元素，因此，此，此，此，a a a aijijijij的地址计算函数为：的地址计算函数为：的地址计算函数为：的地址计算函数为：LOC(a LOC(a LOC(a LOC(aijijijij)=LOC(a)=LOC(a)=LOC(a)=LOC(a11111111)+(i-1)*n+j-1*d)+(i-1)*n+j-1*d)+(i-1)*n+j-1*d)+(i-1)*n+j-1*d 同样，三维数组同样，三维数组同样，三维数组同样，三维数组A A A Amnpmnpmnpmnp可以看成是可以看成是可以看成是可以看成是m m m m个个个个npnpnpnp的二维数组的二维数组的二维数组的二维数组，按，按，按，按“行优先顺序行优先顺序行优先顺序行优先顺序”存储，其地址计算函数为：存储，其地址计算函数为：存储，其地址计算函数为：存储，其地址计算函数为：LOC(a LOC(a LOC(a LOC(aijkijkijkijk)=LOC(a)=LOC(a)=LOC(a)=LOC(a111111111111)+(i-1)*n*p+(j-1)*p+(k-1)*d)+(i-1)*n*p+(j-1)*p+(k-1)*d)+(i-1)*n*p+(j-1)*p+(k-1)*d)+(i-1)*n*p+(j-1)*p+(k-1)*d 上述讨论均是假设数组各维的下界是上述讨论均是假设数组各维的下界是上述讨论均是假设数组各维的下界是上述讨论均是假设数组各维的下界是1 1 1 1，更一般的二维数组是，更一般的二维数组是，更一般的二维数组是，更一般的二维数组是AcAcAcAc1 1 1 1.d.d.d.d1 1 1 1,c,c,c,c2 2 2 2.d.d.d.d2 2 2 2 ，这里，这里，这里，这里c c c c1 1 1 1,c,c,c,c2 2 2 2不一定是不一定是不一定是不一定是1 1 1 1。a a a aijijijij前一共有前一共有前一共有前一共有i-ci-ci-ci-c1 1 1 1行，二维数组一共有行，二维数组一共有行，二维数组一共有行，二维数组一共有d d d d2 2 2 2-c-c-c-c2 2 2 2+1+1+1+1列，故这列，故这列，故这列，故这i-ci-ci-ci-c1 1 1 1行共有行共有行共有行共有(i-c(i-c(i-c(i-c1 1 1 1)*(d)*(d)*(d)*(d2 2 2 2-c-c-c-c2 2 2 2+1)+1)+1)+1)个元素，第个元素，第个元素，第个元素，第i i i i行上行上行上行上a a a aijijijij前一共有前一共有前一共有前一共有j-cj-cj-cj-c2 2 2 2个元素，因此，个元素，因此，个元素，因此，个元素，因此，a a a aijijijij的地址计算函数为：的地址计算函数为：的地址计算函数为：的地址计算函数为：LOC(a LOC(a LOC(a LOC(aijijijij)=LOC(a)=LOC(a)=LOC(a)=LOC(ac c c c1 1 1 1c c c c2 2 2 2)+(i-c)+(i-c)+(i-c)+(i-c1 1 1 1)*(d)*(d)*(d)*(d2 2 2 2-c-c-c-c2 2 2 2+1)+j-c+1)+j-c+1)+j-c+1)+j-c2 2 2 2)*d)*d)*d)*d 例如，在例如，在例如，在例如，在C C C C语言中，数组各维下标的下界是语言中，数组各维下标的下界是语言中，数组各维下标的下界是语言中，数组各维下标的下界是0 0 0 0，因此在，因此在，因此在，因此在C C C C语言中，二维数组的地址计算公式为：语言中，二维数组的地址计算公式为：语言中，二维数组的地址计算公式为：语言中，二维数组的地址计算公式为：LOC(a LOC(a LOC(a LOC(aijijijij)=LOC(a)=LOC(a)=LOC(a)=LOC(a00000000)+(i*(d)+(i*(d)+(i*(d)+(i*(d2 2 2 2+1)+j)*d+1)+j)*d+1)+j)*d+1)+j)*d 【例例】对于给定的二维数组对于给定的二维数组float a34float a34，计算：，计算：(1)(1)数组数组a a中的数组元素数目；中的数组元素数目；(2)(2)若数组若数组a a的起始地址为的起始地址为10001000，且每个数组元素长度为，且每个数组元素长度为3232位位(即即4 4个字节个字节)，数组元素，数组元素a23a23的内存地址。的内存地址。【解解】(1)(1)由由于于C C语语言言中中数数组组的的行行、列列下下标标值值的的下下界界均均为为0 0，该该数数组组行行上上界界为为3-1=23-1=2，列列上上界界为为4-1=34-1=3，所所以以该该数数组组的的元元素数目共有素数目共有3*4=123*4=12个。个。(2)(2)由于由于C C语言采用行序为主序的存储方式，有：语言采用行序为主序的存储方式，有：LOC(a LOC(a2323)=LOC(a)=LOC(a0000)+(i*)+(i*（d d2 2+1)+j)*d+1)+j)*d =1000+(2*4+3)*4 =1000+(2*4+3)*4 =1044 =10445.2 5.2 矩阵的压缩存储矩阵的压缩存储矩阵的压缩存储矩阵的压缩存储 在在在在科科科科学学学学与与与与工工工工程程程程计计计计算算算算问问问问题题题题中中中中，矩矩矩矩阵阵阵阵是是是是一一一一种种种种常常常常用用用用的的的的数数数数学学学学对对对对象象象象，在在在在用用用用高高高高级级级级语语语语言言言言编编编编制制制制程程程程序序序序时时时时，简简简简单单单单而而而而又又又又自自自自然然然然的的的的方方方方法法法法，就是将一个就是将一个就是将一个就是将一个矩阵描述为一个二维数组。矩阵描述为一个二维数组。矩阵描述为一个二维数组。矩阵描述为一个二维数组。矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵运算也非常简单，并且存储的密度为矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵运算也非常简单，并且存储的密度为矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵运算也非常简单，并且存储的密度为矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵运算也非常简单，并且存储的密度为1 1 1 1。但但但但是是是是在在在在矩矩矩矩阵阵阵阵中中中中非非非非零零零零元元元元素素素素呈呈呈呈某某某某种种种种规规规规律律律律分分分分布布布布或或或或者者者者矩矩矩矩阵阵阵阵中中中中出出出出现现现现大大大大量量量量的的的的零零零零元元元元素素素素的的的的情情情情况况况况下下下下，看看看看起起起起来来来来存存存存储储储储密密密密度度度度仍仍仍仍为为为为1 1 1 1，但但但但实实实实际际际际上上上上占占占占用用用用了了了了许许许许多多多多单单单单元元元元去去去去存存存存储储储储重重重重复复复复的的的的非非非非零零零零元元元元素素素素或或或或零零零零元元元元素素素素，这这这这对对对对高高高高阶阶阶阶矩矩矩矩阵阵阵阵会会会会造造造造成成成成极极极极大大大大的的的的浪浪浪浪费费费费，为为为为了了了了节节节节省省省省存存存存储储储储空空空空间间间间，我们可以对这类矩阵进行压缩存储：我们可以对这类矩阵进行压缩存储：我们可以对这类矩阵进行压缩存储：我们可以对这类矩阵进行压缩存储：即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。5.2.1 5.2.1 5.2.1 5.2.1 特殊矩阵特殊矩阵特殊矩阵特殊矩阵 所谓所谓所谓所谓特殊矩阵特殊矩阵特殊矩阵特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，下面讨论几种特殊矩阵的压缩存储。是指非零元素或零元素的分布有一定规律的矩阵，下面讨论几种特殊矩阵的压缩存储。是指非零元素或零元素的分布有一定规律的矩阵，下面讨论几种特殊矩阵的压缩存储。是指非零元素或零元素的分布有一定规律的矩阵，下面讨论几种特殊矩阵的压缩存储。1 1 1 1、对称矩阵、对称矩阵、对称矩阵、对称矩阵 在一个在一个在一个在一个n n n n阶方阵阶方阵阶方阵阶方阵A A A A中，若元素满足下述性质：中，若元素满足下述性质：中，若元素满足下述性质：中，若元素满足下述性质：a a a aijijijij=a=a=a=ajijijiji 0i,jn-1 0i,jn-1 0i,jn-1 0i,jn-1则称则称则称则称A A A A为对称矩阵。下图便是一个为对称矩阵。下图便是一个为对称矩阵。下图便是一个为对称矩阵。下图便是一个5 5 5 5阶对称矩阵。阶对称矩阵。阶对称矩阵。阶对称矩阵。对对对对称称称称矩矩矩矩阵阵阵阵中中中中的的的的元元元元素素素素关关关关于于于于主主主主对对对对角角角角线线线线对对对对称称称称，故故故故只只只只要要要要存存存存储储储储矩矩矩矩阵阵阵阵中中中中上上上上三三三三角角角角或或或或下下下下三三三三角角角角中中中中的的的的元元元元素素素素，让让让让每每每每两两两两个个个个对对对对称称称称的的的的元元元元素素素素共共共共享享享享一一一一个个个个存存存存储储储储空空空空间间间间，这这这这样样样样，能能能能节节节节约约约约近近近近一一一一半半半半的的的的存存存存储储储储空空空空间间间间。不不不不失失失失一一一一般般般般性性性性，我我我我们们们们按按按按“行行行行优优优优先先先先顺顺顺顺序序序序”存存存存储储储储主主主主对对对对角角角角线线线线（包包包包括对角线）以下的元素，其存储形式如图所示：括对角线）以下的元素，其存储形式如图所示：括对角线）以下的元素，其存储形式如图所示：括对角线）以下的元素，其存储形式如图所示：1 5 1 3 7 a1 5 1 3 7 a1 5 1 3 7 a1 5 1 3 7 a00000000 5 0 8 0 0 a 5 0 8 0 0 a 5 0 8 0 0 a 5 0 8 0 0 a10101010 a a a a11111111 1 8 9 2 6 a 1 8 9 2 6 a 1 8 9 2 6 a 1 8 9 2 6 a20202020 a a a a21212121 a a a a22222222 3 0 2 5 1 3 0 2 5 1 3 0 2 5 1 3 0 2 5 1 7 0 6 1 3 a 7 0 6 1 3 a 7 0 6 1 3 a 7 0 6 1 3 an-1 0n-1 0n-1 0n-1 0 a a a an-1 1n-1 1n-1 1n-1 1 a a a an-1 2n-1 2n-1 2n-1 2 a a a an-1n-1n-1n-1 n-1n-1n-1n-1 在这个下三角矩阵中，第在这个下三角矩阵中，第在这个下三角矩阵中，第在这个下三角矩阵中，第i i i i行恰有行恰有行恰有行恰有i+1i+1i+1i+1个元素，元素总数为：个元素，元素总数为：个元素，元素总数为：个元素，元素总数为：n-1n-1n-1n-1 (i+1)=n(n+1)/2 (i+1)=n(n+1)/2 (i+1)=n(n+1)/2 (i+1)=n(n+1)/2 i=0i=0i=0i=0 因此，可以按图中箭头所指的次序将这些元素存放在一个向量因此，可以按图中箭头所指的次序将这些元素存放在一个向量因此，可以按图中箭头所指的次序将这些元素存放在一个向量因此，可以按图中箭头所指的次序将这些元素存放在一个向量sa0.n(n+1)/2-1sa0.n(n+1)/2-1sa0.n(n+1)/2-1sa0.n(n+1)/2-1中。为了便于访问对称矩中。为了便于访问对称矩中。为了便于访问对称矩中。为了便于访问对称矩阵阵阵阵A A A A中的元素，必须在中的元素，必须在中的元素，必须在中的元素，必须在a a a aijijijij和和和和saksaksaksak之间找一个对应关系。之间找一个对应关系。之间找一个对应关系。之间找一个对应关系。若若ijij，则，则a aijij在下三角形中。在下三角形中。a aijij之前的之前的i i行（从第行（从第0 0行到第行到第i-1i-1行）一共有行）一共有1+2+i=i(i+1)/21+2+i=i(i+1)/2个元素，在第个元素，在第i i行上，行上，a aijij之前恰有之前恰有j j个元素（即个元素（即a ai0i0,a,ai1i1,a,ai2i2,a,aij-1ij-1），因此有：），因此有：k=i*(i+1)/2+j 0kn(n+1)/2 k=i*(i+1)/2+j 0kn(n+1)/2 若若ijij，则，则a aijij是在上三角矩阵中。因为是在上三角矩阵中。因为a aijij=a=ajiji，所以只要交换上述对应关系式中的，所以只要交换上述对应关系式中的i i和和j j即可得到：即可得到：k=j*(j+1)/2+i 0kn(n+1)/2 k=j*(j+1)/2+i 0kn(n+1)/2 令令I=max(i,j)I=max(i,j)，J=min(i,j)J=min(i,j)，则，则k k和和i,ji,j的对应关系可统一为：的对应关系可统一为：k=I*(I+1)/2+J 0 kn(n+1)/2 k=I*(I+1)/2+J 0 kn(n+1)/2 因此，因此，a aijij的地址可用下列式计算：的地址可用下列式计算：LOC(a LOC(aijij)=LOC(sak)=LOC(sak)=LOC(sa0)+k*d=LOC(sa0+I*(I+1)/2+J*d =LOC(sa0)+k*d=LOC(sa0+I*(I+1)/2+J*d2 2、三角矩阵、三角矩阵 以主对角线划分，三角矩阵有以主对角线划分，三角矩阵有上三角上三角和和下三角下三角两种。上三角矩阵，它的下三角（不包括主对角线）中的元两种。上三角矩阵，它的下三角（不包括主对角线）中的元素均为常数。下三角矩阵正好相反，它的主对角线上方均为常数。在大多数情况下，三角矩阵常数为零。素均为常数。下三角矩阵正好相反，它的主对角线上方均为常数。在大多数情况下，三角矩阵常数为零。a a0000 a a0101 a a0 n-10 n-1 a a0000 c c c c c a c a1111 a a1 n-11 n-1 a a1010 a a1111 c c .c c a c c an-1 n-1n-1 n-1 a an-1n-1 0 0 a an-1n-1 1 1 a an-1n-1 n-1n-1 (a)(a)上三角矩阵上三角矩阵 (b)(b)下三角矩阵下三角矩阵 三三角角矩矩阵阵中中的的重重复复元元素素c c可可共共享享一一个个存存储储空空间间，其其余余的的元元素素正正好好有有n(n+1)/2n(n+1)/2个个，因因此此，三三角角矩矩阵阵可可压压缩缩存存储储到向量到向量sa0.n(n+1)/2+sa0.n(n+1)/2+1 1 中，其中中，其中c c存放在向量的最后一个分量中。存放在向量的最后一个分量中。上三角矩阵中，主对角线之上的第上三角矩阵中，主对角线之上的第上三角矩阵中，主对角线之上的第上三角矩阵中，主对角线之上的第p p p p行行行行(0pn)(0pn)(0pn)(0pjijijij 下三角矩阵的存储和对称矩阵类似，下三角矩阵的存储和对称矩阵类似，下三角矩阵的存储和对称矩阵类似，下三角矩阵的存储和对称矩阵类似，saksaksaksak和和和和aijaijaijaij对应关系是：对应关系是：对应关系是：对应关系是：i(i+1)/2+j ij i(i+1)/2+j ij i(i+1)/2+j ij i(i+1)/2+j ij n(n+1)/2 ij n(n+1)/2 ij n(n+1)/2 ij n(n+1)/2 i1i-j1i-j1i-j1时，元素时，元素时，元素时，元素a a a aijijijij=0=0=0=0。由此可知，一个由此可知，一个由此可知，一个由此可知，一个k k k k对角矩阵对角矩阵对角矩阵对角矩阵(k(k(k(k为奇数为奇数为奇数为奇数)A)A)A)A是满足下述条件的矩阵：若是满足下述条件的矩阵：若是满足下述条件的矩阵：若是满足下述条件的矩阵：若i-j(k-1)/2 i-j(k-1)/2 i-j(k-1)/2 i-j(k-1)/2，则元素，则元素，则元素，则元素 a a a aijijijij=0=0=0=0。对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一个向量中，并且也能找到每个非零元素和向对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一个向量中，并且也能找到每个非零元素和向对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一个向量中，并且也能找到每个非零元素和向对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。量下标的对应关系。量下标的对应关系。量下标的对应关系。上上上上述述述述的的的的各各各各种种种种特特特特殊殊殊殊矩矩矩矩阵阵阵阵，其其其其非非非非零零零零元元元元素素素素的的的的分分分分布布布布都都都都是是是是有有有有规规规规律律律律的的的的，因因因因此此此此总总总总能能能能找找找找到到到到一一一一种种种种方方方方法法法法将将将将它它它它们们们们压压压压缩缩缩缩存存存存储储储储到到到到一一一一个个个个向向向向量中，并且一般都能找到矩阵中的元素与该向量的对应关系，通过这个关系，量中，并且一般都能找到矩阵中的元素与该向量的对应关系，通过这个关系，量中，并且一般都能找到矩阵中的元素与该向量的对应关系，通过这个关系，量中，并且一般都能找到矩阵中的元素与该向量的对应关系，通过这个关系，仍能对矩阵的元素进行随机存取。仍能对矩阵的元素进行随机存取。仍能对矩阵的元素进行随机存取。仍能对矩阵的元素进行随机存取。5.2.2 5.2.2 5.2.2 5.2.2 稀疏矩阵稀疏矩阵稀疏矩阵稀疏矩阵 什么是稀疏矩阵？简单说，设矩阵什么是稀疏矩阵？简单说，设矩阵什么是稀疏矩阵？简单说，设矩阵什么是稀疏矩阵？简单说，设矩阵A A A A中有中有中有中有s s s s个非零元素，若个非零元素，若个非零元素，若个非零元素，若s s s s远远小于矩阵元素的总数（即远远小于矩阵元素的总数（即远远小于矩阵元素的总数（即远远小于矩阵元素的总数（即smnsmnsmnsmn），则称），则称），则称），则称A A A A为稀疏矩阵。为稀疏矩阵。为稀疏矩阵。为稀疏矩阵。假设在矩阵假设在矩阵假设在矩阵假设在矩阵A A A A中，有中，有中，有中，有s s s s个非零元素。令个非零元素。令个非零元素。令个非零元素。令 e=s/(m*n)e=s/(m*n)e=s/(m*n)e=s/(m*n)，称，称，称，称e e e e为矩阵的为矩阵的为矩阵的为矩阵的稀疏因子稀疏因子稀疏因子稀疏因子。通常认为。通常认为。通常认为。通常认为e0.05e0.05e0.05e0.05时称之为时称之为时称之为时称之为稀疏稀疏稀疏稀疏矩阵矩阵矩阵矩阵。在存储稀疏矩阵时，为了节省存储单元，很自然地想到使用压缩存储方法。但由于非零元素的分布一般是在存储稀疏矩阵时，为了节省存储单元，很自然地想到使用压缩存储方法。但由于非零元素的分布一般是在存储稀疏矩阵时，为了节省存储单元，很自然地想到使用压缩存储方法。但由于非零元素的分布一般是在存储稀疏矩阵时，为了节省存储单元，很自然地想到使用压缩存储方法。但由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须同时记下它所在的行和列的位置（没有规律的，因此在存储非零元素的同时，还必须同时记下它所在的行和列的位置（没有规律的，因此在存储非零元素的同时，还必须同时记下它所在的行和列的位置（没有规律的，因此在存储非零元素的同时，还必须同时记下它所在的行和列的位置（i,j)i,j)i,j)i,j)。于是，。于是，。于是，。于是，一个三元组一个三元组一个三元组一个三元组(i,j,a(i,j,a(i,j,a(i,j,aijijijij)唯一确定了矩阵唯一确定了矩阵唯一确定了矩阵唯一确定了矩阵A A A A的一个非零元素的一个非零元素的一个非零元素的一个非零元素。因此，稀疏矩阵可由表示非零元素的三元组及其行列数唯一确定。因此，稀疏矩阵可由表示非零元素的三元组及其行列数唯一确定。因此，稀疏矩阵可由表示非零元素的三元组及其行列数唯一确定。因此，稀疏矩阵可由表示非零元素的三元组及其行列数唯一确定。例如，下列三元组表例如，下列三元组表例如，下列三元组表例如，下列三元组表 (1,2,12)(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7)(1,2,12)(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7)(1,2,12)(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7)(1,2,12)(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7)加上加上加上加上(6,7)(6,7)(6,7)(6,7)这一对行、列值便可作为下列矩阵这一对行、列值便可作为下列矩阵这一对行、列值便可作为下列矩阵这一对行、列值便可作为下列矩阵M M M M的另一种描述。而由上述三元组表的不同表示方法可引出的另一种描述。而由上述三元组表的不同表示方法可引出的另一种描述。而由上述三元组表的不同表示方法可引出的另一种描述。而由上述三元组表的不同表示方法可引出稀疏矩阵不同的压缩存储方法。稀疏矩阵不同的压缩存储方法。稀疏矩阵不同的压缩存储方法。稀疏矩阵不同的压缩存储方法。0 12 9 0 0 0 0 0 0-3 0 0 15 0 12 9 0 0 0 0 0 0-3 0 0 15 0 12 9 0 0 0 0 0 0-3 0 0 15 0 12 9 0 0 0 0 0 0-3 0 0 15 0 0 0 0 0 0 0 12 0 0 0 18 0 0 0 0 0 0 0 0 12 0 0 0 18 0 0 0 0 0 0 0 0 12 0 0 0 18 0 0 0 0 0 0 0 0 12 0 0 0 18 0 -3 0 0 0 0 14 0 9 0 0 24 0 0 -3 0 0 0 0 14 0 9 0 0 24 0 0 -3 0 0 0 0 14 0 9 0 0 24 0 0 -3 0 0 0 0 14 0 9 0 0 24 0 0 0 0 24 0 0 0 0 0 0 0 0 0 7 0 0 24 0 0 0 0 0 0 0 0 0 7 0 0 24 0 0 0 0 0 0 0 0 0 7 0 0 24 0 0 0 0 0 0 0 0 0 7 0 18 0 0 0 0 0 0 0 14 0 0 0 0 18 0 0 0 0 0 0 0 14 0 0 0 0 18 0 0 0 0 0 0 0 14 0 0 0 0 18 0 0 0 0 0 0 0 14 0 0 0 15 0 0 7 0 0 0 0 0 0 0 0 0 15 0 0 7 0 0 0 0 0 0 0 0 0 15 0 0 7 0 0 0 0 0 0 0 0 0 15 0 0 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 稀疏矩阵稀疏矩阵稀疏矩阵稀疏矩阵 M M M M 和和和和 T T T TM=T=1 1 1 1、三元组表、三元组表、三元组表、三元组表 假设以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方法假设以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方法假设以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方法假设以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方法三元顺序表三元顺序表三元顺序表三元顺序表。#define maxsize 16#define maxsize 16#define maxsize 16#define maxsize 16 typedef int datatype;typedef int datatype;typedef int datatype;typedef int datatype;typedef struct typedef struct typedef struct typedef struct int i,j;int i,j;int i,j;int i,j;datatype v;datatype v;datatype v;datatype v;node;node;node;node;typedef structtypedef structtypedef structtypedef struct node datamaxsize;node datamaxsize;node datamaxsize;node datamaxsize;int m,n,t;int m,n,t;int m,n,t;int m,n,t;spmatrix;spmatrix;spmatrix;spmatrix;i j vi j vi j vi j v 0 1 12 0 1 12 0 1 12 0 1 12 0 2 9 0 2 9 0 2 9 0 2 9 2 0 -3 2 0 -3 2 0 -3 2 0 -3 2 5 14 2 5 14 2 5 14 2 5 14 3 2 24 3 2 24 3 2 24 3 2 24 4 1 18 4 1 18 4 1 18 4 1 18 5 0 15 5 0 15 5 0 15 5 0 15 5 3 -7 5 3 -7 5 3 -7 5 3 -7 0 12 9 0 0 0 0 0 12 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 14 0 -3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 0 24 0 0 0 0 0 18 0 0 0 0 0 0 18 0 0 0 0 0 15 0 0 7 0 0 0 15 0 0 7 0 0 0 设设A A为为spmatrixspmatrix型的结构变量，如图所示的稀疏矩阵的三元组的表示如下：型的结构变量，如图所示的稀疏矩阵的三元组的表示如下：下面以矩阵的转置为例，说明在这种压缩存储结构上如何实现矩阵的运算。下面以矩阵的转置为例，说明在这种压缩存储结构上如何实现矩阵的运算。下面以矩阵的转置为例，说明在这种压缩存储结构上如何实现矩阵的运算。下面以矩阵的转置为例，说明在这种压缩存储结构上如何实现矩阵的运算。一一一一个个个个mnmnmnmn的的的的矩矩矩矩阵阵阵阵A A A A，它它它它的的的的转转转转置置置置B B B B是是是是一一一一个个个个nmnmnmnm的的的的矩矩矩矩阵阵阵阵，且且且且aij=bjiaij=bjiaij=bjiaij=bji，0im0im0im0im，0jn0jn0jn0jn，即即即即A A A A的的的的行行行行是是是是B B B B的列，的列，的列，的列，A A A A的列是的列是的列是的列是B B B B的行的行的行的行。将将将将A A A A转置为转置为转置为转置为B B B B，就是将，就是将，就是将，就是将A A A A的三元组表的三元组表的三元组表的三元组表a.dataa.dataa.dataa.data置换为表置换为表置换为表置换为表B B B B的三元组表的三元组表的三元组表的三元组表b.datab.datab.datab.data，如果只是简单地交换，如果只是简单地交换，如果只是简单地交换，如果只是简单地交换a.dataa.dataa.dataa.data中中中中i i i i和和和和j j j j的内容，那么得到的的内容，那么得到的的内容，那么得到的的内容，那么得到的b.datab.datab.datab.data将是一个按列优先顺序存储的稀疏矩阵将是一个按列优先顺序存储的稀疏矩阵将是一个按列优先顺序存储的稀疏矩阵将是一个按列优先顺序存储的稀疏矩阵B B B B，要得到按行优先顺序存储的，要得到按行优先顺序存储的，要得到按行优先顺序存储的，要得到按行优先顺序存储的b.datab.datab.datab.data，就，就，就，就必须重新排列三元组的顺序。必须重新排列三元组的顺序。必须重新排列三元组的顺序。必须重新排列三元组的顺序。由于由于由于由于A A A A的列是的列是的列是的列是B B B B的行，因此，的行，因此，的行，因此，的行，因此，按按按按a.dataa.dataa.dataa.data的列序转置，所得到的转置矩阵的列序转置，所得到的转置矩阵的列序转置，所得到的转置矩阵的列序转置，所得到的转置矩阵B B B B的三元组表的三元组表的三元组表的三元组表b.datab.datab.datab.data必定是按行优先必定是按行优先必定是按行优先必定是按行优先存放的。存放的。存放的。存放的。