第5章 数组和广义表
目的：线性结构到非线性结构的过渡，了解包含子结构的线性结构，
理解链式存储结构在表达非线性数据结构中的作用。理解数据压缩存储后的运算实现。
内容：使用二维数组表示矩阵及运算；三角矩阵、对称矩阵、稀疏矩
阵等各种压缩存储方法实现矩阵运算；广义表的概念、双链表示和实现。
要求：理解多维数组的存储结构；熟悉特殊矩阵的压缩存储方法；掌
握稀疏矩阵三元组从顺序表、行的单链表到十字链表等到多种存储结构的演变过程；理解广义表的概念，熟悉广义表的存储结构。
重点：讨论多种由顺序存储结构和链式存储结构有机结合的存储结
构，以矩阵为例，研究在相同的逻辑结构（矩阵）和操作要求（矩阵运算）情况下，根据各种矩阵的不同特性，采用多种存储结构实现矩阵运算。
难点：稀疏矩阵的多种存储和实现。 实验：特殊矩阵的存储和运算。
5.1 数组
5-1 数组有什么特点？“数据结构”课程中为什么要研究数组？
【答】在高级程序设计语言中，数组是一种数据类型。数组是线性结构及其他数据结构实现顺序存储结构的基础。
在数据结构中，数组是一种常用的数据结构。一维数组可以看成一个顺序存储结构的线性表，二维数组定义为“其数据元素为一维数组”的线性表。矩阵通常采用二维数组存储，但对特殊矩阵和稀疏矩阵可采用一些特殊方法进行压缩存储。
5-2 什么是随机存取结构？为什么说一维数组是一种随机存取结构？
【答】随机存取结构指读写一个元素的时间复杂度是O(1)。一维数组的每个元素地址是其下标的线性函数Loc(a)?Loc(a)?i?c，计算地址的时
i0- 43 -
间复杂度是O(1)，因此一维数组是一种随机存储结构。
5-3 二维数组有哪些存储结构？有什么不同特点？都是随机存取结构吗？
【答】顺序二维数组和动态二维数组的存储结构不同。
① 顺序二维数组的所有元素连续存储，有行主序或列主序两种存储次序，存储结构见教材图5.2。每个元素ai,j的地址是下标i、j的线性函数，地址计算公式如下，设二维数组有m行n列，每元素占c个字节。
Loc(a)?Loc(a)?(i?n?j)?c（行主序） Loc(a)?Loc(a)?(j?m?i)?c（列主序）
无论行主序或列主序，计算元素地址花费的时间都是O(1)，都是随机存取结构。
② 动态二维数组包含多个分散存储的一维数组，见教材图5.3，计算元素地址是两个线性关系，时间复杂度是O(1)，因此，二维数组都是随机存取结构。
i,j0,0i,j0,05.2 特殊矩阵的压缩存储
5.2.1 三角矩阵、对称矩阵和对角矩阵的压缩存储
习5-5采用二维数组存储矩阵是否具有随机存取特性？有哪些矩阵需要压缩存储？为什么要压缩？各采用怎样的压缩存储方式？各种压缩存储方式是否具有随机存取特性？
【答】无论静态存储或动态存储的二维数组都是随机存取结构，即存或取一个元素的时间复杂度是O(1)，因此，采用二维数组存储矩阵具有随机存取特性。
当矩阵阶数较大且矩阵中有很多零元素或部分非零元素具有某种分布规律时，需要将矩阵压缩存储，即使用较少的存储空间存储矩阵元素。需要压缩存储的矩阵有对称矩阵、三角矩阵、稀疏矩阵等，压缩存储的原则是：有规律的重复元素只存储一份；不存储零元素。采用压缩存储的矩阵仍然能够正确地进行各种矩阵运算。
根据矩阵的特点采用不同的压缩存储方式，各矩阵的压缩存储结构如图5.1所示。
① 特殊矩阵，如对称矩阵、三角矩阵、对角矩阵等，将所有元素
- 44 -
映射成一种线性关系压缩存储，或者采用动态二维数组只存储按规律分布的非零元素。这两种压缩存储方式都具有随机存取特性。
② 稀疏矩阵，其非零元素很少且分布无规律，将每个非零元素表示成一个三元组（行号,列号,元素值），稀疏矩阵的压缩存储问题则转化为三元组线性表的存储问题。有三元组顺序表、三元组单链表、行（列）的单链表、十字链表等存储结构，这些压缩存储结构都不具有随机存取特性。
矩阵矩阵二维数组特殊矩阵（零元素分布规律、不存储分布规律的零元素） 三角矩阵对称矩阵对角矩阵 线性压缩存储非零元素区域一维数组三角形的二维数组
稀疏矩阵（零元素分布不规律、不存储零元素）图5.1 矩阵的存储结构分类
5-1】上三角矩阵的压缩存储原则是怎样的？有哪些压
缩存储方式？画出示意图，写出元素的地址计算公式。
n个元素ai,j（0【答】设An?[ai,j]是一个n（n>0）阶上三角矩阵，由n×
≤i,j
上三角矩阵的压缩存储原则是，只存储主对角线及以上三角部分的矩阵元素。两种压缩存储结构如图5.2所示，都具有随机存取特性。
5-4 【思考题
0a0,01a0,1??n-1a0,n-1na1,1??2n-1a1,n-1??i(2n-i+1)/2?i(2n-i-1)/2+j?ai,i?ai,j?i(2n-i-1)/2+n-1?n(n+1)/2-1ai,n-1?an-1,n-1 三元组顺序表（排序）三元组单链表（排序）三元组行的单链表（排序）三元组十字链表（排序） 第0行，n个元素 第1行，n-1个元素 第i行，n-i个元素 第n-1行（a）上三角矩阵的行主序线性压缩存储int[][]element01ielement.length-1an-1,n-1（b）上三角矩阵的三角形二维数组压缩存储int[]0a0,0a1,1?1a0,1??j?a1,n-1element[i].length-1a0,n-1element[i][j]0≤i≤j 图5.2 上三角矩阵的压缩存储结构 - 45 - （a）线性压缩存储上三角矩阵 将上三角矩阵主对角线及其以上元素ai,j，按行主序顺序压缩成线性存储结构，各元素ai,j的存储地址如下，存储元素个数为n?(n?1)/2。 Loc(ai,j)?Loc(a0,0)?n?(n?1)???(n?i?1)?j?i?Loc(a0,0)?i?(2?n?i?1)?j20?i?j?n 计算各元素地址时间为O(1)，因此，上三角矩阵线性压缩存储结构是随机存取结构。 （b）使用三角形的二维数组压缩存储上三角矩阵 使用二维数组存储上三角矩阵主对角线及其以上元素ai,j，第i行一维数组长度为n-i。ai,j存储在mat[i][j-i]处，计算地址时间为O(1)，因此，此存储结构也是随机存取结构。 5.2.2 稀疏矩阵的压缩存储 1. 稀疏矩阵三元组顺序表 采有三元组顺序表存储的稀疏矩阵类声明如下，使用排序顺序表对象作为成员变量。 public class SeqMatrix //三元组顺序存储的稀疏矩阵类 { int rows,columns; //矩阵行数、列数 SortedSeqList } 采用顺序表存储稀疏矩阵非零元素三元组线性表，必须将三元组按元素行列次序排序存储，为输出矩阵和执行相加等操作提供高效运算的基础。如果不排序，则输出矩阵和矩阵相加等运算的效率极低，每获得一个元素值都要在顺序表中查找指定行列的元素，即使零元素也在查找不成功之后才能确定，每次查找的时间复杂度是O(n)，n是非零元素个数。 2. 稀疏矩阵三元组行的单链表 【思考题5-2】画出前述稀疏矩阵B5?6及A+=B非零元素三元组行的单链表存储结构。 - 46 - ① 以下稀疏矩阵B，行的单链表如图5.3所示，未画单链表头结点。 5?6行指针顺序表Tripledata01∧2?(0,2,-11)(2,3,51)∧(3,0,10)∧(4,1,99)∧next?00?11?0?00B5?6??000?0?100?0990??170?矩阵rowscolumnsrowlist?6000?matrix5行数列数5100??000?000??0n5element排序单链表(0,4,-17)∧长度数组 矩阵行数rows-1图5.3 稀疏矩阵B5?6行的单链表 ② A见教材例5.2，稀疏矩阵相加运算A+=B结果及行的单链表如 图5.4所示。 5?6A5?6?B5?6?000000??0200000?????0005100???290360028????09950000??element012?∧Triplenext(1,1,20)∧(2,3,51)∧(3,0,29)(4,1,99)(3,2,36)(4,2,50)∧(3,5,28)∧矩阵matrixrowscolumnsrowlist56行数列数n5长度数组 矩阵行数rows-1图5.4 稀疏矩阵A+=B行的单链表 3. 稀疏矩阵十字链表 习5-9 画出以下稀疏矩阵非零元素三元组的十字链表存储结构。 ?0?0??59???0?0??0??18000320015?0000000??000860043??0000000? 0000000??0000000?00065000??A7?8【答】 - 47 -