数据结构课件第5章数组和广义表.ppt

1 第 第5 5 章章 数数组组和和广广义义表表 5.1 5.1 数组的逻辑结构数组的逻辑结构 5.2 5.2 数组的顺序存储结构数组的顺序存储结构 5.3 5.3 矩阵的压缩存储矩阵的压缩存储 5.4 5.4 广义表广义表 5.15.1 数组的逻辑结构数组的逻辑结构 5.25.2 数组的顺序存储结构数组的顺序存储结构 5.35.3 矩阵的压缩存储矩阵的压缩存储 5.45.4 广义表广义表 数组数组 ( (array) array) 是最常用的数据结构之一。几乎所有是最常用的数据结构之一。几乎所有 的程序设计语言都把数组类型设定为固有类型。的程序设计语言都把数组类型设定为固有类型。 数组的定义数组的定义 线性结构中的数据都是非结构的原子类型，元素的线性结构中的数据都是非结构的原子类型，元素的 值是不再分解的。而数组可以看成是线性表在下述含义值是不再分解的。而数组可以看成是线性表在下述含义 上的扩展：上的扩展： 5.1 5.1 数组的逻辑结构数组的逻辑结构 2 数组的基本数组的基本操作操作 表中的数据元素本身也是一种数据结构。表中的数据元素本身也是一种数据结构。 数组是由下标和值组成的序对集合。在数组中，一数组是由下标和值组成的序对集合。在数组中，一 旦给定下标，都存在一个与其相对应的值，这个值就称旦给定下标，都存在一个与其相对应的值，这个值就称 为数组元素。为数组元素。 也可以说，数组中的每个数据元素都对应于一组下也可以说，数组中的每个数据元素都对应于一组下 标（标（ j j 1 1 , , j j2 2 , , , , j j n n ），每个下标取值范围是），每个下标取值范围是 11j j i i b b i i ， b b i i 称称 为第为第 i i 维的长度（维的长度（ i i = = 1, 1, 2, 2, , , n n）。显然，当）。显然，当 n n = = 1 1 时，时，n n 维数组就退化为定长的线性表。反之，维数组就退化为定长的线性表。反之，n n 维数组也可以看维数组也可以看 成是线性表的推广。成是线性表的推广。 3 5.1.1 5.1.1 数组的定义数组的定义 可以把二维数组看成是这样一个定长线性表：它的可以把二维数组看成是这样一个定长线性表：它的 每个数据元素也是一个定长线性表。每个数据元素也是一个定长线性表。 A A mm n n = = a a 1111 a a 2121 a a mm1 1 a a 1212 a a 2222 a a m2m2 a a 1313 a a 2323 a a m3m3 a a 1.n 1.n a a 2 2, n, n a a m, nm, n 4 例如，下面是一个二维数组，且以例如，下面是一个二维数组，且以 mm 行行 n n 列的矩阵列的矩阵 形式表示。形式表示。 每个数据元素每个数据元素 j j 是一个列向量形式的线性表是一个列向量形式的线性表 A A mm n n = = a a 1, 1, n n a a 2, 2, n n a a m, nm, n a a 1313 a a 2323 a a mm, 3, 3 a a 1212 a a 2222 a a mm, 2, 2 a a 1111 a a 2121 a a mm,1 ,1 二维数组二维数组 A A 还可以看成是一个线性表：还可以看成是一个线性表： A A = ( = ( 1 1, , 2 2 , , , , n n ) ) j j = ( = ( a a 1 1j j , , a a2 2j j , , , , a am m, , j j ) ) 1 1 j j n n 每个数据元素是一个行向量形式的线性表每个数据元素是一个行向量形式的线性表 B=(B=( 1 1 2 2 3 3 , , mm ) ) A A mm n n = = ( ( ( ( a a11 11 a a 1212 a a 1, 1, n n ) , ) , , ( , ( a am m, 1, 1 a a mm, 2 , 2 a a mm, , n n ) ) ) ) ( ( a a21 21 a a 2222 a a 2, 2, n n ) , , ) , , i i = ( = ( a ai i 1 1 , , a a i i 2 2 , , , , a ai i, n , n ) ) 1 1 i i mm 5 数组一旦被定义，它的维数和维界就数组一旦被定义，它的维数和维界就 不再改变。因此，除了结构的初始化和销不再改变。因此，除了结构的初始化和销 毁之外，数组只有存取数据元素和修改数毁之外，数组只有存取数据元素和修改数 据元素值的操作。据元素值的操作。 6 5.1.2 数组的抽象类型定义 ADT Array ADT Array D=aD=aj1j2j3 j1j2j3jnjn|n |n0,0,称为数组的维数称为数组的维数, , j j i i 是数组的第是数组的第i i维下标维下标 ,1,1 j j i i bi, bi为数组第i维的长度， a aj1j2j3 j1j2j3jnjn ElementSetElementSet 数据关系：数据关系： =R=R 1 1 , ,R R 2 2 , ., .R R n n R R i i =| 1 | 1 j j k k b bk k , 1, 1 k k n n 且且 k k i, i, 1 1 j j i i b bi-1 i-1, a , aj1j2.jn j1j2.jn ,a ,a j1ji+1j1ji+1jnjn D,iD,i=1,n=1,n 基本操作基本操作: : InitArrayInitArray (A, n, bound1, , (A, n, bound1, , boundnboundn ); ); 操作结果：如果维数操作结果：如果维数 n n 和各维长度合法，则构造和各维长度合法，则构造 相应的数组相应的数组 A A，并且返回并且返回 TRUETRUE。 8 5.1.2 5.1.2 数组的抽象类型定义数组的抽象类型定义 DestroyArray(ADestroyArray(A): ):销毁数组销毁数组A A。 GetValue(A,eGetValue(A,e, index, index 1 1 , , , , indexindex n n ): 初始条件：初始条件：A A 是是 n n 维数组，维数组，e e 为元素变量，随后是为元素变量，随后是 n n 个下标值。个下标值。 操作结果：若各下标合法，则用操作结果：若各下标合法，则用e e返回数组中由返回数组中由 由由indexindex 1 1 , , indexindex n n 所指定的元素的值所指定的元素的值. . SetValueSetValue ( A, e, index ( A, e, index 1 1 , , , , indexindex n n ); ); 初始条件：初始条件：A A 是是 n n 维数组，维数组，e e 为元素变量，随后是为元素变量，随后是 n n 个下标值。个下标值。 操作结果：若各下标合法，则将数组操作结果：若各下标合法，则将数组A A中由中由 indexindex 1 1 , , indexindex n n 所指定的元素的值置为所指定的元素的值置为e. e. 由于内存储器的结构是一维的。一维数组可直接采由于内存储器的结构是一维的。一维数组可直接采 用顺序存储。用一维的内存存储表示多维数组时，需按用顺序存储。用一维的内存存储表示多维数组时，需按 某种次序将数组中元素排成一线性序列，再将这个线性某种次序将数组中元素排成一线性序列，再将这个线性 序列存放在一维的内存中，即数组的顺序存储结构表示序列存放在一维的内存中，即数组的顺序存储结构表示 。 顺序存储的定位公式顺序存储的定位公式 5.2 5.2 数组的顺序存储结构数组的顺序存储结构 9 数组的顺序存储表示数组的顺序存储表示 基本操作的算法描述基本操作的算法描述 用顺序存储结构来存储数组中的元素，一定要按照用顺序存储结构来存储数组中的元素，一定要按照 某种次序将元素排成一个线性序列。有两种存储方式：某种次序将元素排成一个线性序列。有两种存储方式： (1) (1) 以列为主序以列为主序 ( ( column column major major order order ) ) 的存储方式的存储方式 ，即按列优先，逐列顺序存储。，即按列优先，逐列顺序存储。 (2) (2) 以行为主序以行为主序 ( ( row row major major order order ) ) 的存储方式，即的存储方式，即 按行优先，逐行顺序存储。按行优先，逐行顺序存储。 10 5.2.1 5.2.1 顺序存储的定位公式顺序存储的定位公式 a a 2121 a a 1111 a a mm, 1, 1 a a 2222 a12 a a mm, 2, 2 a a 1, 1, n n a a 2, 2, n n a a mm, , n n a a 2121 a a 1111 a a mm, 1, 1 a a 2121 a a 1111 A A mm,1 ,1 a a 2121 a a 1111 a a mm, 1, 1 a a 2222 a a 1212 a a mm, 2, 2 a a 2222 a a 1212 a a mm, 2, 2 a a 2222 a a 1212 a a mm, 2, 2 a a 1, 1, n n a a 2, 2, n n a a mm, , n n a a 1, 1, n n a a 2, 2, n n a a mm, , n n a a 1, 1, n n a a 2, 2, n n a a mm n n 11 列主次序存放 a a 1212 a a 1111 a a 1.n1.n a a 2222 a a 2121 a a 2, 2, n n a a mm, 1, 1 a a mm, 2, 2 a a mm, , n n a a 1212 a a 1111 a a 1.n1.n a a 2222 a a 2121 a a 2, 2, n n a a mm, 1, 1 a a mm, 2, 2 a a mm, , n n a a 1212 a a 1111 a a 1, 1, n n a a 1212 a a 1111 a a 1, 1, n n a a 2222 a a 2121 a a 2, 2, n n a a 2222 a a 2121 a a 2, 2, n n a a mm, 1, 1 a a mm, 2, 2 a a mm, , n n a a mm, 1, 1 a a mm, 2, 2 a a mm, , n n 12 行主次序存放 对于数组，一旦规定了它对于数组，一旦规定了它 的维数和各维的长度，便可以的维数和各维的长度，便可以 为它分配存储空间。反之，只为它分配存储空间。反之，只 要给出一组下标，便可以求得要给出一组下标，便可以求得 相应数组的存储位置。相应数组的存储位置。 13 （）一维数组的地址计算：（）一维数组的地址计算： 设一维数组为：设一维数组为：=(a=(a 1 1,a ,a2 2 ,a a i i ,a,a n n ), ),数组中每个元数组中每个元 素占素占sizesize个存储单元，则元素个存储单元，则元素a a i i 的存储地址为：的存储地址为： Loc(AiLoc(Ai)=Loc(A1)+(i-1)*size)=Loc(A1)+(i-1)*size。 数组的地址计算数组的地址计算 14 二维数组的二维数组的地址计算地址计算 假设每个数据元素占假设每个数据元素占 1 1 个存储单元，且以行序为主序的进行存个存储单元，且以行序为主序的进行存 储，则二维数组储，则二维数组 A A 中任一元素中任一元素 a a ij ij 的存储位置可以由下面定位公式的存储位置可以由下面定位公式 确定确定 LOCLOC ( (AAi i , , j j) = ) = LOCLOC (A1, 1) + n*(i-1)+ (A1, 1) + n*(i-1)+(j-1)(j-1) 其中：其中： LOCLOC ( (AAi i , , j j) ) 是是 a a ij ij 的存储位置；的存储位置； LOCLOC (A1, 1) (A1, 1) 是是 a a11 11 的存储位置，即二维数组 的存储位置，即二维数组 A A 的起始存储位置，也称为基地址或基址；的起始存储位置，也称为基地址或基址； n n是数组第二维的长度是数组第二维的长度。 15 假设每个数据元素占假设每个数据元素占sizesize个存储单元，则二维数组个存储单元，则二维数组 A A 中任一元素中任一元素 a aij ij 的存储位置可以由下面定位公式确定的存储位置可以由下面定位公式确定 LOCLOC ( (AAi i , , j j) = ) = LOCLOC (A1, 1) + (n*(i-1)+ (A1, 1) + (n*(i-1)+(j-1)*(j-1)*sizesize 三维数组的三维数组的地址计算地址计算 三维数组三维数组A(1:r,1:m,1:n)A(1:r,1:m,1:n)。假设每个数据元素占。假设每个数据元素占sizesize个存个存 储单元，且以行序为主序的进行存储，首元素储单元，且以行序为主序的进行存储，首元素a a111 111的地址 的地址 为为Loc(A111),Loc(A111),求任意元素求任意元素a aijk ijk的地址。 的地址。 显然，显然，a ai11 i11地址为 地址为 oc(Ai11)=Lococ(Ai11)=Loc(A111)+(i-1)*m*n(A111)+(i-1)*m*n, ,因为在该元素因为在该元素 之前有之前有i-1i-1个个m*nm*n的二维数组。的二维数组。 16 不难得到三维数组任意元素不难得到三维数组任意元素a aijk ijk的地址： 的地址： Loc(AijkLoc(Aijk)=Loc(A111)+(i-1)*m*n+(j-1)*n+(k-)=Loc(A111)+(i-1)*m*n+(j-1)*n+(k- 1)*size,1)*size,其中：其中： irir, , jmjm, , knkn。 矩阵矩阵 ( (matrix) matrix) 是很多科学与工程计算问题中研究的是很多科学与工程计算问题中研究的 数学对象。在数据结构中，我们感兴趣的不是矩阵本身数学对象。在数据结构中，我们感兴趣的不是矩阵本身 ，而是如何存储矩阵的元素而使矩阵的各种运算能够有，而是如何存储矩阵的元素而使矩阵的各种运算能够有 效地进行。效地进行。 特殊矩阵特殊矩阵包括两个部份：元素分布有特殊规律的 矩阵矩阵, ,找到找到规律对应的公式，实现压缩存储。非零元 素很少的稀疏矩阵，可采用只存矩阵，可采用只存非零元素的方法实现压 缩存储。 5.3 5.3 矩阵的压缩存储矩阵的压缩存储 17 特殊矩阵的压缩存储特殊矩阵的压缩存储 所谓压缩存储是指：为多个值相同的元素只分配一所谓压缩存储是指：为多个值相同的元素只分配一 个存储空间；对零元不分配空间。个存储空间；对零元不分配空间。 18 稀疏矩阵的逻辑结构稀疏矩阵的逻辑结构 稀疏矩阵的存储结构稀疏矩阵的存储结构 假若相同的元素或者零元素在矩阵中的分布有一定假若相同的元素或者零元素在矩阵中的分布有一定 规律，则称特殊矩阵。特殊矩阵主要有规律，则称特殊矩阵。特殊矩阵主要有 3 3 种：对称矩阵种：对称矩阵 、三角矩阵、带状矩阵。、三角矩阵、带状矩阵。 在所有这些统称为在所有这些统称为 “特殊矩阵特殊矩阵” ” 的的矩阵中，非零矩阵中，非零 元的分布都有一个明显的规律，从而都可以将其压缩存元的分布都有一个明显的规律，从而都可以将其压缩存 储到一维数组中，并且找到每个非零元在一维数组中的储到一维数组中，并且找到每个非零元在一维数组中的 对应关系。对应关系。 19 5.3.1 5.3.1 特殊矩阵的压缩存储特殊矩阵的压缩存储 若一个若一个 n n 阶矩阵阶矩阵 MM 中的元素满足下述性质中的元素满足下述性质 1. 1. 对称矩阵对称矩阵 a aij ij = = a a ji ji 1 1 i i，j j n n 则称为则称为 n n 阶对称矩阵。阶对称矩阵。 20 对于对称矩阵，可以为每一对对称元只分配一个存对于对称矩阵，可以为每一对对称元只分配一个存 储空间，这样就可以将储空间，这样就可以将 n n 2 2 个元压缩存储到个元压缩存储到 n n( (n n+1)/2 +1)/2 个个 元的空间中。元的空间中。 假设以行序为主序存储对称矩阵的假设以行序为主序存储对称矩阵的下三角下三角（包括对（包括对 角线）中的元。以一维数组角线）中的元。以一维数组 B B n n( (n n+1)/2 +1)/2 作为作为 n n 阶对称阶对称 矩阵矩阵 MM 的存储结构，的存储结构， 21 a a 3131 a a 2222 a a 2121 a a 1111 a a n n, , n n a a n n,1 ,1 B Loc(AijLoc(Aij=1=1 2 2 3 3 4 4 Loc(AijLoc(Aij)=Loc(A11)+i*(i-1)/2+j-1 (ij)=Loc(A11)+i*(i-1)/2+j-1 (ij) 三角矩阵分为下三角矩阵和上三角矩阵。所谓下三角矩阵分为下三角矩阵和上三角矩阵。所谓下( (上上 ) ) 三角矩阵是指矩阵的上三角矩阵是指矩阵的上 ( (下下) ) 三角三角 ( (不包括对角线不包括对角线) ) 中的中的 元均为常数元均为常数 c c 或为零的或为零的 n n 阶矩阵。阶矩阵。 2. 2. 三角矩阵三角矩阵 22 下三角矩阵下三角矩阵 三角矩阵除了和对称矩阵一样，只存储矩阵的下三角矩阵除了和对称矩阵一样，只存储矩阵的下( (上上 ) ) 三角中的元之外，再加上一个存储常数三角中的元之外，再加上一个存储常数 c c 的存储空间的存储空间 即可。即可。 上三角矩阵上三角矩阵 一个一个 n n 阶方阵，若它的全部非零元素落在一个以对阶方阵，若它的全部非零元素落在一个以对 角线为中心的带状区域中，则称该矩阵为带状矩阵，或角线为中心的带状区域中，则称该矩阵为带状矩阵，或 对角矩阵。这个带状区域若包含主对角线上下各对角矩阵。这个带状区域若包含主对角线上下各 b b 条对条对 角线道上元素，那么，角线道上元素，那么，b b 称为该带状矩阵的半带宽，或称为该带状矩阵的半带宽，或 称该带状矩阵的带宽为称该带状矩阵的带宽为 (2 (2b b+1)+1)。 3. 3. 带状矩阵带状矩阵 0 0 0 0 b b 条条 b b 条条 23 在带状矩阵中，当在带状矩阵中，当 | | i i- -j j | | b b 时，时，a a ij ij = = 0 0。该方阵共有该方阵共有 (2(2b b+1)+1)n n- -( (b b+1)+1)b b 个非零元素。个非零元素。 a a 1111 D D = = a a 1212 a a 1313 0 0 0 0 a a 2121 a a 2222 a a 2323 a a 2424 0 0 a a 3131 a a 3232 a a 3333 a a 3434 a a 3535 0 0 a a 4242 a a 4343 a a 4444 a a 4545 0 0 0 0 a a 5353 a a 5454 a a 5555 D D 矩阵是一个矩阵是一个 5 5 阶、半带宽为阶、半带宽为 2 2 的带状矩阵，在其的带状矩阵，在其 主对角线主对角线 a a11 11、 、a a22 22、 、a a33 33、 、a a44 44、 、a a55 55 上下各有 上下各有 2 2 条对角线，条对角线， 共有共有 (2 (2b b+1)+1)n n- -( (b b+1)+1)b b = 19 = 19 个非零元素。个非零元素。 24 例如：例如： 带状矩阵中最常见的是三对角带状矩阵。带状矩阵中最常见的是三对角带状矩阵。 25 特点：特点： 当当 i=1 j=1,2i=1 j=1,2 1data-data 原始的三元组表原始的三元组表 A A.data.data r r c c v v 1 1 2 2 12 12 1 1 3 3 9 9 3 3 1 1 -3-3 3 3 6 6 1414 4 4 3 3 2424 5 5 2 2 1818 6 6 1 1 1515 6 6 4 4 -7-7 36 利用三元组顺序表存储实现矩阵的转置利用三元组顺序表存储实现矩阵的转置 c c 3 3 6 6 1 1 5 5 1 1 4 4 6 6 3 3 r r 1 1 1 1 2 2 2 2 3 3 3 3 4 4 6 6 v v -3 -3 15 15 12 12 18 18 9 9 24 24 -7 -7 1414 void void TransposeTSMatrixTransposeTSMatrix ( ( TSMatrixTSMatrix A, A, TSMatrixTSMatrix *B ) *B ) / / 采用三元组表结构，求稀疏矩阵采用三元组表结构，求稀疏矩阵 A A 的转置矩阵的转置矩阵 B B。在程序中，。在程序中， intint i,j,ki,j,k; / ; / j j 指示指示 B B-data -data 中三元组的序号，中三元组的序号， / / i i 指示指示 A A.data.data 中三元组的序号，中三元组的序号， / / k k指示指示A A 的列号（即的列号（即B B 的行号）的行号） B-m = B-m = A.nA.n; ; / / 将稀疏矩阵将稀疏矩阵 A A 的列数值作为其转置矩阵的列数值作为其转置矩阵 B B 的行数值的行数值 B-n = B-n = A.mA.m; ; / / 将稀疏矩阵将稀疏矩阵 A A 的行数值作为其转置矩阵的行数值作为其转置矩阵 B B 的列数值的列数值 B- B-lenlen = = A.lenA.len; ; / / 转置矩阵转置矩阵 B B与稀疏矩阵与稀疏矩阵A A的非零元个数相等的非零元个数相等 算法编算法编( (稀稀疏矩阵疏矩阵“ “列序列序” ”递增转置算法递增转置算法) ) if ( B-if ( B-lenlen0 ) 0 ) j = 1;j = 1; 37 for (k = 1; k B-dataj.rowdataj.row = = A.datai.colA.datai.col; ; / / 稀疏矩阵稀疏矩阵A A的列域值成为其转置矩阵的列域值成为其转置矩阵 B B 的行域值的行域值 B- B-dataj.coldataj.col = = A.datai.rowA.datai.row; ; / / 稀疏矩阵稀疏矩阵 A A 的行域值成为其转置矩阵的行域值成为其转置矩阵 MM 的列域值的列域值 B- B-dataj.edataj.e = = A.datai.eA.datai.e; ; / / 将稀疏矩阵将稀疏矩阵 MM 的非零元值赋给其转置矩阵的非零元值赋给其转置矩阵 T T j+; j+; / B-data / B-data 中三元组的序号加中三元组的序号加 1 1 / if ( / if ( A.dataA.data ) ) 结束结束 / / if ( B-if ( B-lenlen0 ) 0 ) 结束结束 38 算法分析算法分析 一般矩阵的转置算法（经典算法）为：一般矩阵的转置算法（经典算法）为： 39 for ( for ( colcol = 0; = 0; colcol if ( ! ( M-row_headrow_head = ( = (OlinkOlink * *) ) mallocmalloc ( (m+1) ( (m+1) * * sizeofsizeof ( (OlinkOlink) ) ) ) ) ) ) exit ( OVERFLOW ); exit ( OVERFLOW ); if ( ! ( M- if ( ! ( M-col_headcol_head = ( = (OlinkOlink * *) ) mallocmalloc ( (n+1) ( (n+1) * * sizeofsizeof ( (OlinkOlink) ) ) ) ) ) ) exit ( OVERFLOW ); exit ( OVERFLOW ); if ( M ) free ( M ); if ( M ) free ( M ); scanfscanf ( ( / / 输入输入 MM 的行数、列数和非零元个数的行数、列数和非零元个数 M-m = m; M-n = n; M-M-m = m; M-n = n; M-lenlen = t; = t; 45 算法编写算法编写 for ( for ( scanfscanf ( i ! = 0; ( i ! = 0; scanfscanf ( exit ( OVERFLOW); p p- -row = i;row = i;/ / 生成新结点的行号域生成新结点的行号域 p p- - colcol = j; = j;/ / 生成新结点的列号域生成新结点的列号域 p p- -value = e;value = e;/ / 生成新结点的值域生成新结点的值域 46 M- M-row_headrow_head = NULL; = NULL; / / 初始化行头指针向量；令各行链表为空链表初始化行头指针向量；令各行链表为空链表 M- M-col_headcol_head = NULL; = NULL; / / 初始化列头指针向量；令各列链表为空链表初始化列头指针向量；令各列链表为空链表 if ( M- if ( M-row_headirow_headi = = NULL ) = = NULL ) M- M-row_headirow_headi = p; p = p; p- -right = NULL;right = NULL; else else for ( q = M-for ( q = M-row_headirow_headi; (q; (q- -right) right ); p p- -right = qright = q- -right; qright; q- -right = p;right = p; / / 完成行插入完成行插入 else if ( M- else if ( M-row_headirow_headi - - colcol j ) j ) / / 寻找在行表中的插入位置寻找在行表中的插入位置 p p- -right = M-right = M-row_headirow_headi; M-; M-row_headirow_headi = p; = p; 47 if ( M- if ( M-col_headjcol_headj = = NULL ) = = NULL ) M_col_headjM_col_headj = p; p = p; p- -down = NULL;down = NULL; else else for for ( ( q q = = M-M-col_headjcol_headj; ; (q(q- -down) down) down ); p p- -down = qdown = q- -down; qdown; q- -down = p;down = p; / / 完成列插入完成列插入 else if ( M- else if ( M-col_headjcol_headj - -row i ) row i ) / / 寻找在列表中的插入位置寻找在列表中的插入位置 p p- -down = M-down = M-row_headjrow_headj; M-; M-col_headjcol_headj = p; = p; / for / for 结束结束 return OK;return OK; / / CreateSMatrix_OLCreateSMatrix_OL 48 M-M-col_headcol_head M-M-row_headrow_head (1) (1) 输入输入 ( 1, 1, 3 ) ( 1, 1, 3 ) 1 1 1 1 3 3 p p (2) (2) 输入输入 ( 1, 3, 5 ) ( 1, 3, 5 ) p p 1 1 3 3 5 5 q q (3) (3) 输入输入 ( 1, 4, 9 ) ( 1, 4, 9 ) 1 1 4 4 9 9 p p q q (4) (4) 输入输入 ( 3, 1, 2 ) ( 3, 1, 2 ) 3 3 1 1 2 2 p p q q 49 (5) (5) 输入输入 ( 2, 3, 4 ) ( 2, 3, 4 ) 2 2 3 3 4 4 q q (6) (6) 输入输入 ( 2, 2, 8 ) ( 2, 2, 8 ) q q 创建稀疏矩阵创建稀疏矩阵 MM 的十字链表的十字链表 if ( if ( M.rheadiM.rheadi = = NULL ) = = NULL ) M.rheadiM.rheadi = p; p = p; p- -right = NULL;right = NULL; for for ( ( q q = = M-M-col_headicol_headi; ; (q(q- -down) down) down ); p p- -down = qdown = q- -down; qdown; q- -down = p;down = p; if ( M-if ( M-row_headirow_headi - -j j ) j j ) p p- -right = M-right = M-row_headi;Mrow_headi;M-row_headirow_headi = p; = p; if ( M-if ( M-col_headjcol_headj = = NULL ) = = NULL ) M- M-col_headjcol_headj = p; p = p; p- -down = NULL;down = NULL; p q p p 2 2 2 2 8 8 if ( M-if ( M-col_headjcol_headj = = NULL ) = = NULL ) M- M-col_headjcol_headj = p; p = p; p- -down = NULL;down = NULL; for ( q = M-for ( q = M-row_headirow_headi; (q; (q- -right) right ); p p- -right = qright = q- -right; qright; q- -right = p;right = p; if ( M-if ( M-col_headjcol_headj = = NULL ) = = NULL ) M-M-col_headjcol_headj = = p; p; p p- -down down = = NULL;NULL; for ( q = M-for ( q = M-row_headirow_headi; (q; (q- -right) right ); p p- -right = qright = q- -right; qright; q- -right = p;right = p; if ( M-if ( M-col_headjcol_headj = = NULL ) = = NULL ) M- M-col_headjcol_headj = p; p = p; p- -down = NULL;down = NULL; if ( M-if ( M-row_headirow_headi = = NULL ) = = NULL ) M- M-row_headirow_headi = p; p = p; p- -right = NULL;right = NULL; for for ( ( q q = = M-M-col_headicol_headi; ; (q(q- -down) down) down ); p p- -down = qdown = q- -down; qdown; q- -down = p;down = p; if ( M-if ( M-row_headirow_headi = = NULL ) = = NULL ) M- M-row_headirow_headi = p; p = p; p- -right = NULL;right = NULL; 对于一个对于一个 mm 行行 n n 列，并且有列，并且有 t t 个非零元的稀疏矩个非零元的稀疏矩 阵，阵，CreateSMatrix_OLCreateSMatrix_OL 算法执行时间为算法执行时间为 O O( (t t s s) ) ，其中其中 s s = = maxmax mm, , n n 。 这是因为：每建立一个非零元的结点时都需要寻这是因为：每建立一个非零元的结点时都需要寻 查它在行表和列表中的插入位置，此算法对非零元输查它在行表和列表中的插入位置，此算法对非零元输 入的先后次序没有任何要求。入的先后次序没有任何要求。 反之，若按以行序为主序的次序依次输入三元组反之，若按以行序为主序的次序依次输入三元组 ，即可以将建立十字链表表示的算法改写成，即可以将建立十字链表表示的算法改写成 O O( (t t) ) 数量数量 级的（级的（t t 为非零元个数）的算法。为非零元个数）的算法。 算法分析算法分析 50 广义表广义表 ( (generalized generalized list) list) 是线性表的推广，有时也是线性表的推广，有时也 称为列表（称为列表（listslists，用复数形式以示与统称的表用复数形式以示与统称的表 list list 的区的区 别）。广泛地应用于人工智能等领域的别）。广泛地应用于人工智能等领域的 LISPLISP（表处理表处理 语言），把广义表作为基本的数据结构，就连程序也语言），把广义表作为基本的数据结构，就连程序也 表示为一系列的广义表。表示为一系列的广义表。 51 5.4 5.4 广义表广义表 广义表的逻辑结构广义表的逻辑结构 和数组一样，广义表也可以看成是线性表在下述含和数组一样，广义表也可以看成是线性表在下述含 义上的扩展：表中的数据元素本身也是一种数据结构。义上的扩展：表中的数据元素本身也是一种数据结构。 52 广义表的存储结构广义表的存储结构 53 5.4.1 5.4.1 广义表的逻辑结构广义表的逻辑结构 广义表一般记作：广义表一般记作：GGL L = ( = ( a a 1 1 , , a a2 2 , , , , a an n ) ) 其中：其中： n n 是广义表是广义表 GGL L 的长度；的长度； a a i i 可以是单个元素，也可以是广义表，分别称可以是单个元素，也可以是广义表，分别称 为广义表为广义表 GGL L 的原子和子表，习惯上用大写字母表示广的原子和子表，习惯上用大写字母表示广 义表的名称，用小写字母表示原子的名称。义表的名称，用小写字母表示原子的名称。 G GL L是广义表是广义表 ( ( a a 1 1 , , a a2 2 , , , , a an n ) ) 的名称； 的名称； 1. 1. 广义表的定义广义表的定义 54 当广义表当广义表 GLGL为非空时，称第一个元素为非空时，称第一个元素 a a 1 1 为为 GLGL的表头（的表头（headhead），），其余元素组成的表其余元素组成的表 ( ( a a2 2 , , a a3 3 , , , , a an n ) ) 是 是 GLGL的表尾（的表尾（tailtail）。 ）。显然显然 ，广义表的定义是一个递归的定义，因为在，广义表的定义是一个递归的定义，因为在 描述广义表时又用到了广义表的概念。描述广义表时又用到了广义表的概念。 例例5-15-1 A A = ( ) = ( )，A A 是一个空表，它的长度为零。是一个空表，它的长度为零。 例例5-25-2 B B = ( = (e e) )，B B 只有一个原子只有一个原子 e e，它的长度为它的长度为 1 1。 例例5-35-3 C C = = ( (a a, , ( (b b, , c c, , d d) ) )，C C 的长度为的长度为 2 2，两个元素分，两个元素分 别为原子别为原子 a a 和子表和子表 ( (b b, , c c, , d d) )。 例例5-45-4 D D = = ( (A A, , B B, , C C) )，D D 的长度为的长度为 3 3，三个元素分别，三个元素分别 为为 A A、B B 和和 C C，都是广义表。显然，将上面所述三个子都是广义表。显然，将上面所述三个子 表的值代入以后，则有表的值代入以后，则有 D D = ( ), ( = ( ), (e e), (), (a a, (, (b b, , c c, , d d) ) ) )。 例例5-55-5 E E = = ( (a a, , E E) )，这是一个递归表，它的长度为这是一个递归表，它的长度为 2 2 ，E E 相当于一个无限的广义表相当于一个无限的广义表 E E = ( = (a a, (, (a a, (, (a a, ), )。 55 2. 2. 广义表的三个重要结论广义表的三个重要结论 从上述定义和例子推出如下广义表的三个重要结论从上述定义和例子推出如下广义表的三个重要结论 (1) (1) 广义表的元素可以是子表，而子表的元素还可广义表的元素可以是子表，而子表的元素还可 以是子表，以是子表，。由此，广义表是一个多层次结构。由此，广义表是一个多层次结构。 (2) (2) 广义表可以为其他广义表所共享。例如在上述广义表可以为其他广义表所共享。例如在上述 例子中，广义表例子中，广义表 A A、B B 和和 C C 为为 D D 的子表，则在的子表，则在 D D 中可中可 以不必列出广义表的值，而是通过子表的名称引用。以不必列出广义表的值，而是通过子表的名称引用。 (3) (3) 广义表可以是一个递归表，即广义表也可以是广义表可以是一个递归表，即广义表也可以是 其本身的一个子表。例如广义表其本身的一个子表。例如广义表 E E 就是一个递归的表。就是一个递归的表。 56 e e c c d d b b a a B B A A C C D D 表示广义表表示广义表表示原子表示原子 57 和线性表相类似，可以对广义表进行的操作有查找和线性表相类似，可以对广义表进行的操作有查找 、插入、删除和取表元素等。由于广义表在结构上较线、插入、删除和取表元素等。由于广义表在结构上较线 性表复杂的多，因此，广义表操作的实现也不如线性表性表复杂的多，因此，广义表操作的实现也不如线性表 简单。在这些操作中，最重要的两个基本操作是：简单。在这些操作中，最重要的两个基本操作是： (1) (1) 取广义表表头取广义表表头 GetHeadGetHead：表中的第一个元素为表中的第一个元素为 此表的表头。此表的表头。 (2) (2) 取广义表表尾取广义表表尾 GetTailGetTail：表中除第一个元素外的表中除第一个元素外的 其余元素组成的表为此表的表尾。其余元素组成的表为此表的表尾