数据结构第5章 数组和广义表

1、第五章第五章 数组和广义表数组和广义表本章主要介绍多维数组的概念及在计算机中的存本章主要介绍多维数组的概念及在计算机中的存放，放，特殊矩阵特殊矩阵的压缩存储及相应运算的压缩存储及相应运算，广义表广义表的的概念和概念和存储结构及其相关运算的实现。通过本章存储结构及其相关运算的实现。通过本章学习，要求掌握如下内容：学习，要求掌握如下内容：1 1多维数组的定义及在计算机中的存储表示；多维数组的定义及在计算机中的存储表示；2 2对称矩阵、三角矩阵、对角矩阵等特殊矩阵对称矩阵、三角矩阵、对角矩阵等特殊矩阵在计算机中的压缩存储表示及地址计算公式；在计算机中的压缩存储表示及地址计算公式；3 3稀疏矩阵的三元

2、组表示及转置算法实现；稀疏矩阵的三元组表示及转置算法实现；4 4广义表存储结构表示及基本运算。广义表存储结构表示及基本运算。5.1 多维数组5.1.1多维数组的定义5.1.2多维数组的存储5.2 矩阵的压缩存储 5.2.1 特殊矩阵 5.2.2 稀疏矩阵5.3 广义表5.15.1 多维数组多维数组数组：数组： 由一组名字相同、下标不同的同类型的元素由一组名字相同、下标不同的同类型的元素 组成组成 数组特点数组特点 数组结构固定数组结构固定,下标一般具有下标一般具有固定的上界和下界固定的上界和下界 数据元素数据元素具有具有统一的类型统一的类型 数组运算数组运算 给定一组下标，给定一组下标，取取相

3、应的数据元素相应的数据元素. 给定一组下标，给定一组下标，修修改数据元素的值改数据元素的值.数组的处理比其它复杂的结构要简单数组的处理比其它复杂的结构要简单5.1.15.1.1多维数组的定义多维数组的定义与高级语言中数组的区别：与高级语言中数组的区别： 1、本章所讨论的数组是一种、本章所讨论的数组是一种数据结构数据结构，而高级语，而高级语 言中数组是一种言中数组是一种数据类型数据类型。2、高级语言高级语言中的数组是中的数组是顺序结构顺序结构；而本章的数组；而本章的数组 既可以是既可以是顺序的，顺序的，也可以是也可以是链式结构链式结构，用户可，用户可 根据需要选择。根据需要选择。5.1.15.1

4、.1多维数组的定义多维数组的定义一维数组一维数组一维数组可以看成是一个线性表或一个向量，它在计算机内一维数组可以看成是一个线性表或一个向量，它在计算机内是存放在一块是存放在一块连续的存储单元连续的存储单元中，适合于中，适合于随机查找随机查找。有一个直接前驱和一个直接后继有一个直接前驱和一个直接后继二维数组二维数组二维数组可以看成是向量的推广。二维数组可以看成是向量的推广。有两个直接前驱和两个直接后继有两个直接前驱和两个直接后继 例如，设例如，设A A是一个有是一个有m m行行n n列的二维数组，则列的二维数组，则A A可以表示为可以表示为：a00 a01 a0n-1 a10 a11 a1n-1

5、 . A= am-1 0 am-1 1 am-1 n-1 三维数组三维数组最多可有三个直接前驱和三个直接后继最多可有三个直接前驱和三个直接后继多维数组多维数组把三维以上的数组称为多维数组，把三维以上的数组称为多维数组，可有多个直接前驱和多个直接后继可有多个直接前驱和多个直接后继是一种非线性结构是一种非线性结构。总结：总结： 一维数组可以看作一个线性表，一维数组可以看作一个线性表， 二维数组可以看作二维数组可以看作“数据元素是一维数组数据元素是一维数组”的一维的一维数组，数组， 三维数组可以看作三维数组可以看作“数据元素是二维数组数据元素是二维数组”的一维数的一维数组，依组，依 此类推。此类推。

6、在在C C语言中的描述语言中的描述typedeftypedef intint datatypedatatype; ;datatypedatatype array1N; array1N; datatypedatatype array2array2MN;MN;datatypedatatype array3XYZ;array3XYZ; 数组一旦被定义，它的维数和维界就不再数组一旦被定义，它的维数和维界就不再改变。因此，数组只有存取元素和修改元素值改变。因此，数组只有存取元素和修改元素值的操作。的操作。考虑问题的基本出发点：考虑问题的基本出发点： 计算机的内存结构是一维的。因此用一维内存来存多计算机的

7、内存结构是一维的。因此用一维内存来存多维数组，就必须维数组，就必须按某种次序将数组元素排成线性序列按某种次序将数组元素排成线性序列，然后将这个线性序列顺序存放在存储器中然后将这个线性序列顺序存放在存储器中。数组一旦建立，结构中的元素个数和元素间的关系就数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，不再发生变化。因此，一般都是采用顺序存储的方法一般都是采用顺序存储的方法来表示数组来表示数组。5.2 5.2 多维数组的存储多维数组的存储两种顺序存储方式两种顺序存储方式行优先顺序行优先顺序将数组元素按行排列将数组元素按行排列在在PASCALPASCAL、C C语言中，数组就是按行

8、优先顺序存储的。语言中，数组就是按行优先顺序存储的。列优先顺序列优先顺序将数组元素按列向量排列将数组元素按列向量排列在在FORTRANFORTRAN语言中，数组就是按列优先顺序存储的。语言中，数组就是按列优先顺序存储的。推广到多维数组的情况：推广到多维数组的情况：行优先顺序：先排最右下标，从右到左，最后排最左下标。行优先顺序：先排最右下标，从右到左，最后排最左下标。 因此，在算法中，最左边下标可以看成是外循环，最右边下标可因此，在算法中，最左边下标可以看成是外循环，最右边下标可以看以看 成是最内循环。成是最内循环。列优先顺序：先排最左下标，从左向右，最后排最右下标。列优先顺序：先排最左下标，从

9、左向右，最后排最右下标。 因此，在算法中，最右边下标可以看成是外循环，最左边下标可以看因此，在算法中，最右边下标可以看成是外循环，最左边下标可以看成是最内循环。成是最内循环。 按行序为主序存放按行序为主序存放 am-1,n-1 . am-1,1 am-1,0 . a1n-1 . a11 a10 a0,n-1 . a01 a00 a00 a01 . a0,n-1 a10 a11 . a1,n-1 am-1,0 am-1,1 am-1,n-1 .01n-1m*n-1n am-1,n-1 . a1,n-1 a0,n-1 . am-1,1 . a11 a01 am-1,0 . a10 a00 a00

10、a01 . a0n-1 a10 a11 . a1n-1 am-10 am-11 . am-1n-1 . 按列序为主序存放按列序为主序存放01m*n-1m-1m计算机如何实现数组元素的随机存取？计算机如何实现数组元素的随机存取？ 按上述两种方式顺序存储的序组，只要知道：按上述两种方式顺序存储的序组，只要知道：开始结点的存放地址（即基地址），开始结点的存放地址（即基地址），维数维数每维的上、下界每维的上、下界每个数组元素所占用的单元数，每个数组元素所占用的单元数， 就可以将数组元素的就可以将数组元素的存放地址表示为存放地址表示为其下标的线其下标的线性函数性函数。因此，数组中的任一元素可以在相同的时

11、间。因此，数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构。内存取，即顺序存储的数组是一个随机存取结构。如何计算数组元素的地址？如何计算数组元素的地址？计算二维数组元素地址的通式计算二维数组元素地址的通式二维数组二维数组列优先列优先存储的通式为：存储的通式为：LOC(aij)=LOC(a00)+(j*b1+i)*L则则行优先行优先存储时的地址公式为：存储时的地址公式为：LOC(aij)=LOC(a00)+(i*b2+j)*L设一般的二维数组是设一般的二维数组是A0.bA0.b1 1-1, 0.b-1, 0.b2 2-1-11b21,b11,0b11b2i,iji01b

12、20,00mna.a.a.a.a.a.aAbi称为第称为第i维维的长度的长度计算三维数组元素地址的通式计算三维数组元素地址的通式设一般的三维数组是设一般的三维数组是A0.b1-1, 0.b2-1，0.b3-1按按“行优先顺序行优先顺序”存储，其任一元素存储，其任一元素A Aijkijk地址计地址计算函数为：算函数为：LOC(aLOC(aijkijk)=LOC(a)=LOC(a000000)+()+(i i* *b b2 2* *b b3 3+ +j j* *b b3 3+k)+k)* *L L按按“列优先顺序列优先顺序”存储，其任一元素存储，其任一元素A Aijkijk地址计地址计算函数为：算

13、函数为：LOC(aLOC(aijkijk)=LOC(a)=LOC(a000000)+()+(k k* *b b1 1* *b b2 2+ +j j* *b b1 1+i)+i)* *L L若是若是N N维数组，其中任一元素的地址该如何计算？维数组，其中任一元素的地址该如何计算？LjbjaLOCLjjbjbbbjbbbaLOCaLOCniniknkinnnnnnjjj1110.0012431320.00,.,21)()().()()(开始结点的存放地址（即基地址）开始结点的存放地址（即基地址）维数和每维的上、下界；维数和每维的上、下界；每个数组元素所占用的单元数每个数组元素所占用的单元数其中其中

14、Cn=L, Ci-1=biCi， 1in（递归）递归）Loc(jLoc(j1 1,j,j2 2, ,j jn n)=LOC(0,0,)=LOC(0,0,0)0)niii1jC最基本的原理最基本的原理Ai1in的起始地址=第一个元素的起始地址该元素前面的元素个数单位长度+对于二维数组对于二维数组Ac1:d1,c2:d2,设每个元素占用设每个元素占用k个存储单元，个存储单元，LOC(c1,c2)是第一个元素是第一个元素ac1c2的存储位置，则的存储位置，则按行存放时按行存放时，aij的存储位置为：的存储位置为：LOC(i,j)=LOC(c1,c2)+(i-c1)*(d2-c2+1)+(j-c2)*

15、k按列存放时按列存放时,aij的存储位置为：的存储位置为：LOC(i,j)=LOC(c1,c2)+(j-c2)*(d1-c1+1)+(i-c1)*k2006-12006-1对于二维数组a04,15，设每个元素占1个存储单元，且以行为主序存储，则元素a2,1相对于数组空间起始地址的偏移量是()。 A5 B10 C15D25 20032003设数组a3.16，5.20的元素以列为主序存放，每个元素占用两个存储单元，则数组元素ai,j(3i16，5j20)的地址计算公式为_。 Aa-118+2i+28jBa-116+2i+28j Ca-144+2i+28j Da-146+2i+28j5.25.2 矩

16、阵的压缩存储矩阵的压缩存储在编程时，简单而又自然的方法，是在编程时，简单而又自然的方法，是将矩阵描述为将矩阵描述为一个二维数组一个二维数组。矩阵在这种存储表示之下，可以对。矩阵在这种存储表示之下，可以对其元素进行随机存取。其元素进行随机存取。 但是在一些特殊矩阵中，但是在一些特殊矩阵中，非零元素呈某种规律分布非零元素呈某种规律分布或者或者矩阵中有大量的零元素矩阵中有大量的零元素，如果仍用二维数组存，如果仍用二维数组存，会造成极大的浪费，尤其是处理高阶矩阵的时候。会造成极大的浪费，尤其是处理高阶矩阵的时候。 为了节省存储空间，为了节省存储空间， 我们可以对这类矩阵进行压缩我们可以对这类矩阵进行压

17、缩存储。存储。5.2.15.2.1 几种常见的特殊矩阵几种常见的特殊矩阵1 12 23 34 45 52 23 34 45 56 63 34 45 56 67 74 45 56 67 78 85 56 67 78 89 9对称矩阵在一个在一个n n阶方阵阶方阵A A中，若元素满足下中，若元素满足下述性质：述性质：a aij ij= =a aji ji 0i,jn-1 0i,jn-1，则称，则称A A为对称矩阵。为对称矩阵。特征特征：元素关于主对角线对称：元素关于主对角线对称压缩存储的办法：压缩存储的办法： 只存矩阵中上三角或下三角中只存矩阵中上三角或下三角中的元素。的元素。所需空间：所需空间：

18、2) 1() 1(10nniNni三角矩阵三角矩阵特征：特征：上三角矩阵上三角矩阵中，主对角中，主对角线的线的下三角中的元素均下三角中的元素均为常数为常数。在大多数情况。在大多数情况下，常数为下，常数为零零。下三角矩阵下三角矩阵正好相反。正好相反。压缩方法：压缩方法：只存上只存上( (下下) )三角阵中上三角阵中上( (下下) )三角中的元素三角中的元素常数常数c c可共享一个存储可共享一个存储空间空间所需空间：所需空间：1 12 23 34 45 50 03 34 45 56 60 00 05 56 67 70 00 00 07 78 80 00 00 00 09 91 12 23 34 4

19、5 54 43 34 45 56 64 44 45 56 67 74 44 44 47 78 84 44 44 44 49 91 10 00 00 00 02 23 30 00 00 03 36 65 50 00 04 47 79 97 70 05 58 81 12 29 91 14 44 44 44 42 23 34 44 44 43 36 65 54 44 44 47 79 97 74 45 58 81 12 29 912) 1(nnN上三角上三角下三角下三角对角矩阵对角矩阵特征：特征：所有的非零元素集中在以所有的非零元素集中在以主对角线主对角线为中心的带状区域中，为中心的带状区域中， 即

20、除了主对角线和主对角线相邻两即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，侧的若干条对角线上的元素之外，其余元素皆为零。其余元素皆为零。压缩存储的办法：压缩存储的办法： 只存对角线以及相邻两侧的若干只存对角线以及相邻两侧的若干条对角线上的元素。条对角线上的元素。存存三对角矩阵三对角矩阵所需的空间：所需的空间：1 11 10 00 00 02 23 37 70 00 00 04 45 53 30 00 00 06 67 75 50 00 00 08 89 9三对角矩阵三对角矩阵23 nN特征：只有特征：只有少量少量非零元素，且非非零元素，且非零元素的零元素的分布没有规律分布没有规律

21、。压缩存储的办法：压缩存储的办法： 只存非零元素。只存非零元素。所需空间：与非零元素的个数和所需空间：与非零元素的个数和存储方式有关。存储方式有关。稀疏矩阵稀疏矩阵1 12 20 00 05 50 03 30 00 00 00 04 40 00 00 00 00 06 60 00 00 00 00 08 80 05.2.25.2.2 特殊矩阵的压缩存储特殊矩阵的压缩存储矩阵类型矩阵类型对称矩阵对称矩阵三角矩阵三角矩阵三对角矩阵三对角矩阵压缩的基本思想：压缩的基本思想：只存有用的元素只存有用的元素由用二维数组改为用一维数组来存放由用二维数组改为用一维数组来存放说明：说明：按按C C语言中规定，下

22、标从语言中规定，下标从0 0开始开始不失一般性，按不失一般性，按“行优先顺序行优先顺序”存储存储关键问题关键问题如何确定一维数组的大小？如何确定一维数组的大小？如何确定矩阵元素在一维数组中的位置？从如何确定矩阵元素在一维数组中的位置？从而保证对矩阵元素的随机存取而保证对矩阵元素的随机存取A Aijij的位置的位置 = 该元素前的元素个数该元素前的元素个数= = 所需空间所需空间12334545671 12 23 34 45 52 23 34 45 56 63 34 45 56 67 74 45 56 67 78 85 56 67 78 89 9存储下三角存储下三角矩阵矩阵注意存储矩阵元素注意存

23、储矩阵元素的一维数组的下标的一维数组的下标是从是从0 0开始开始1 1 . . 对称矩阵对称矩阵如何确定一维数组的大小？如何确定一维数组的大小？2) 1( nnN设：存放下三角阵中的元素，设：存放下三角阵中的元素，则：如何确定元素则：如何确定元素A Aijij在一维数组中在一维数组中的位置？的位置？12334545671 1 2 2 3 3 4 4 5 52 2 3 3 4 4 5 5 6 63 3 4 4 5 5 6 6 7 74 4 5 5 6 6 7 7 8 85 5 6 6 7 7 8 8 9 9(1),2(1),2(A)()ijijijjiiijij Aijjjiij AALoc A

24、当在下三角阵中当在上三角阵中根据2. 2. 三角矩阵三角矩阵1 14 44 44 44 42 23 34 44 44 43 36 65 54 44 44 47 79 97 74 45 58 81 12 29 912) 1(nnN1233654如何确定一维数组的大小？如何确定一维数组的大小？设：在下三角阵中，设：在下三角阵中，则：如何确定元素则：如何确定元素A Aijij在一维数在一维数组中的位置？组中的位置？(1), 2(1) 2()iijijijnnijLoc A 当， 即下三角阵中的元素，当，即上三角阵中的常数3.3.三对角矩阵三对角矩阵1 11 10 00 00 02 23 37 70

25、00 00 04 45 53 30 00 00 06 67 75 50 00 00 08 89 923 nN如何确定一维数组的大小？如何确定一维数组的大小？如何确定元素如何确定元素A Aijij在一维数组中在一维数组中的位置？的位置？1123745367589)(ijALoc在在A Aijij之前有之前有i i行行, ,共有共有3 3* *i-1i-1个非零元素个非零元素, ,在第在第i i行，行， a aijij之前有之前有j-i+1j-i+1个非零元素，个非零元素，3*i-1+(j-i+1) = 2*i+j程序员试题程序员试题2004-1 对矩阵压缩存储的主要目的是_。 A方便运算B节省存

26、储空间 C降低计算复杂度D提高运算速度2003 将一个三对角矩阵Al.100，1.100中的元素按行存储在一维数组Bl.298中，矩阵A中的元素A66,65在数组B中的下标为_。 A195 B196C197D1985.2.3 5.2.3 稀疏矩阵的压缩存储稀疏矩阵的压缩存储顺序存储：顺序存储：三元组表三元组表链式存储：十字链表链式存储：十字链表1.1.三元组表存稀疏矩阵三元组表存稀疏矩阵考虑：考虑：只存非零元素只存非零元素一个非零元素的必需信息有：一个非零元素的必需信息有： (i, j, aij)记录一个稀疏矩阵的必需信息有：记录一个稀疏矩阵的必需信息有：行数行数M，列数，列数N，非零元素个数

27、，非零元素个数T1 12 20 00 05 50 03 30 00 00 00 04 40 00 00 00 00 06 60 00 00 00 00 08 80 0i ij jA Aijij0 00 01 10 01 12 20 04 45 51 11 13 32 21 14 43 32 26 64 43 38 8M=5N=5T=7三元组表的三元组表的C C语言描述语言描述typedef struct TriTupleNode datamaxsize; / /* *三元组表三元组表* */ / int m, n, t; ; / /* *m m行数行数,n,n列数列数,t,t非零元素个数非零元

28、素个数* */ / TriTupleTable; / 稀疏矩阵类型稀疏矩阵类型 i ij jV V#define maxsize 10000typedef int Elemtype;typedef struct /*三元组结点三元组结点*/ int i, j; /该非零元的行下标和列下标该非零元的行下标和列下标 Elemtype e; / 该非零元的值该非零元的值 TriTupleNode; / 三元组类型三元组类型三元组表表示法：三元组表表示法：1 12 212121 13 39 93 31 1-3-33 35 514144 43 324245 52 218186 61 115156 64

29、4-7-7注意：注意：三元组表中的三元组表中的元素按行（或列）排元素按行（或列）排列。列。m=6m=6n=6n=6t=8t=8i ij jv v稀疏矩阵压缩存储的稀疏矩阵压缩存储的缺点：将失去随机存取功能缺点：将失去随机存取功能1 12 23 34 45 56 67 78 80 12 9 0 0 00 0 0 0 0 0 -3 0 0 0 14 00 0 24 0 0 00 18 0 0 0 015 0 0 -7 0 05.2.45.2.4应用举例：应用举例： 稀疏矩阵的转置稀疏矩阵的转置1.矩阵转置的数学解释矩阵转置的数学解释 一个一个mn的矩阵的矩阵A，它的转置，它的转置B是一个是一个nm

30、的的矩阵，且矩阵，且aij=bji，0im，0jn。007650020060052700Aij=Bji求转置矩阵算法求转置矩阵算法028003600070500140M005280000007143600T用常规的二维数组表示时的算法用常规的二维数组表示时的算法 其时间复杂度为其时间复杂度为: O(mn) for (col=1; col=n; +col) for (row=1; row=m; +row) Tcolrow = Mrowcol;不正确！不正确！（1 1）每个元素的行下标和列下标互换（即三元组中的）每个元素的行下标和列下标互换（即三元组中的i i和和j j 互换互换）；）；（2 2）

31、T T的总行数的总行数m m和总列数和总列数n n与与M M值不同值不同（互换）；互换）；（3 3）重排重排三元组内元素顺序三元组内元素顺序，使转置后的三元组也按行，使转置后的三元组也按行 （或列）为主序有规律的排列。（或列）为主序有规律的排列。上述（上述（1 1）和（）和（2 2）容易实现，难点在）容易实现，难点在（3 3）。提问：提问：若采用三元组压缩技术存储稀疏矩阵，只要把每个若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的元素的行下标和列下标互换行下标和列下标互换，就完成了对该矩阵的转置运，就完成了对该矩阵的转置运算，这种说法正确吗？算，这种说法正确吗？ 有二种实现方法有二种实现方法

32、压缩转置压缩转置( (压缩压缩) )快速转置快速转置( (1, 2, 121, 2, 12) )( (1, 3, 91, 3, 9 ) )(3, 1, -3)(3, 1, -3)(3, 5, 14)(3, 5, 14)(4, 3, (4, 3, 24)24)(5, 2, 18)(5, 2, 18)(6, 1, 15)(6, 1, 15)(6, 4, -7)(6, 4, -7)(1, 3, -3)(1, 3, -3)(1, 6, 15)(1, 6, 15)( (2, 1, 122, 1, 12) )(2, 5, 18)(2, 5, 18)( (3, 1, 93, 1, 9) )(3, 4, 24

33、)(3, 4, 24)(4, 6, -7)(4, 6, -7)(5, 3, 14)(5, 3, 14)三三元元组组表表M.data三三元元组组表表T.data转置后转置后0 12 9 0 0 00 0 0 0 0 0-3 0 0 0 14 00 0 24 0 0 00 18 0 0 0 015 0 0 -7 0 0M=0 0 3 0 0 1512 0 0 0 18 0 9 0 0 24 0 00 0 0 0 0 -70 0 14 0 0 00 0 0 0 0 0T=?2.2.利用三元组表实现转置利用三元组表实现转置思想一：直接交换思想一：直接交换a.data中中i和和j的内容的内容 问题：问题

34、：b.data是一个按列优先顺序存储的稀疏矩阵是一个按列优先顺序存储的稀疏矩阵B 解决方法：重新排列解决方法：重新排列B中三元组的顺序。中三元组的顺序。0 02 25 50 03 30 00 04 40 00 00 06 6i ij jA Aijij0 01 12 20 02 25 51 11 13 32 21 14 43 32 26 6M=4N=2T=50 00 00 00 02 23 34 40 05 50 00 06 6i ij jB Bijij1 10 02 22 20 05 51 11 13 31 12 24 42 23 36 6Aij=Bjii ij jB Bijij1 10 02

35、 21 11 13 31 12 24 42 20 05 52 23 36 6ji 按按i i排序排序M=2N=4T=5行优先行优先列优先列优先b.mb.m= =a.na.n; ; b.nb.n= =a.ma.m; ; b.tb.t= =a.ta.t; ; / /* *基本信息的赋值基本信息的赋值* */ / /* *按交换按交换i i、j j的方式给的方式给B B的三元组赋值的三元组赋值* */ /for ( i=0; ifor ( i=0; ib.tb.t; i+ ) ; i+ ) b.datai.ib.datai.i= =a.datai.ja.datai.j; ; b.datai.jb.d

36、atai.j= =a.datai.ia.datai.i; ; b.datai.eb.datai.e= =a.datai.ea.datai.e;/ /* *扫描扫描B B，按，按i i排序排序* */ /i ij jA Aijij0 01 12 20 02 25 51 11 13 32 21 14 43 32 26 6M=4N=2T=5i ij jB Bijij1 10 02 22 20 05 51 11 13 31 12 24 42 23 36 6i ij jB Bijij1 10 02 21 11 13 31 12 24 42 20 05 52 23 36 6ji 按按i i排序排序M=2N

37、=4T=5思想二：在思想二：在A A中按列序找中按列序找三元组，写入三元组，写入B BB B的行优先即的行优先即A A的列优先的列优先对对B B的第的第colcol列列 ，扫描扫描三元组表三元组表a.dataa.data，找出所有列号等于，找出所有列号等于colcol的三元组，将它们的行号和列号互换后依次放入的三元组，将它们的行号和列号互换后依次放入b.datab.data中，即可得到中，即可得到B B的按行优先的压缩存储表示。的按行优先的压缩存储表示。0 02 25 50 03 30 00 04 40 00 00 06 6i ij jA Aijij0 01 12 20 02 25 51 11

38、 13 32 21 14 43 32 26 6M=4N=2T=50 00 00 00 02 23 34 40 05 50 00 06 6Aij=Bjii ij jB Bijij1 10 02 21 11 13 31 12 24 42 20 05 52 23 36 6M=2N=4T=5col=0，没有匹配的三元组，没有匹配的三元组col=1，找到，找到2，3，4col=2，找到，找到5，6 思路：思路：反复扫描反复扫描A.dataA.data中的中的列序列序，从小到大从小到大依次进行转置。依次进行转置。6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18

39、6 1 15 6 4 -7 i j e0 1 2 3 4 5 6 7 8A7 6 8 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 i j e0 1 2 3 4 5 6 7 8Bqppppppppqqqqppppppppcol=1col=2qqqVoid transmatrix(tripletable a,tripletable &b) int pa, pb, col; b.m=a.n; b.n=a.m; b.t=a.t; /*基本信息的赋值基本信息的赋值*/ if(b.t=0) printf(“A=0n”); retur

40、n 0; /*无非零元素无非零元素*/ pb=0; /*pb指向三元组表指向三元组表B中的当前位置中的当前位置*/ for(col=0; cola.n; col+) /*按列按列col扫描表扫描表A*/ for(pa=0; pa=a.t; pa+) /*pa指向表指向表A中的当前位置中的当前位置*/ /*找所有列号等于找所有列号等于col的三元组，的三元组，i,j互换写放入互换写放入B*/ if(a.datapa.j=col) b.datapb.i=a.datapa.j; b.datapb.j=a.datapa.i; b.datapb.e=a.datapa.e; pb+; 1 1、主要时间消耗

41、在主要时间消耗在查找查找A.datapa.jA.datapa.j= =colcol的元素的元素，由两重循，由两重循环完成环完成: : for(col=0; cola.n; col+) 循环次数循环次数n for(pa=0; pa=a.t; pa+) 循环次数循环次数t所以该算法的时间复杂度为所以该算法的时间复杂度为O(O(n*t) ) - -即即M M的列数与的列数与M M中非零元素的个数之中非零元素的个数之积积最坏情况最坏情况：M M中全是非零元素，此时中全是非零元素，此时t=mt=m* *n n， 时间复杂度为时间复杂度为 O(O(n2 2*m ) )注：注：若若M M中基本上是非零元素时

42、，即使用中基本上是非零元素时，即使用非压缩传统转置算法非压缩传统转置算法的时间复杂度也不过是的时间复杂度也不过是O(O(n*m) )结论：结论：压缩转置算法不能滥用。压缩转置算法不能滥用。前提前提：仅适用于非零元素个数很少（即仅适用于非零元素个数很少（即t tm m* *n n）的情况。的情况。算法的效率分析算法的效率分析三三元元组组表表A.data三三元元组组表表B.data(1, 3, -3)(2 ,1, 12)(2, 5, 18)(3, 1, 9)(4, 6, -7)(5, 3, 14)(1, 6, 15)(3, 4, 24)( (1, 2, 121, 2, 12) )( (1, 3,

43、91, 3, 9 ) )(3, 1, -3)(3, 1, -3)(3, 5, 14)(3, 5, 14)(4, 3, 24)(4, 3, 24)(5, 2, 18)(5, 2, 18)(6, 1, 15)(6, 1, 15)(6, 4, -7)(6, 4, -7)基本思想：基本思想：在在A A中按行序找三元组，确定该三元组在中按行序找三元组，确定该三元组在B B中的中的位置，写入位置，写入B B中适当位置。中适当位置。 即依次即依次把把A.dataA.data中的元素直接送入中的元素直接送入B.dataB.data的恰当位置上的恰当位置上 p0123 q 2 4思想三：思想三：快速转置快速转置

44、关键问题：如何确定每个三元组在关键问题：如何确定每个三元组在B B中的位置中的位置A A中某个三元组在中某个三元组在B B的中位置的中位置= = 每列的第一个非零元素在数组每列的第一个非零元素在数组B B中应有的位置中应有的位置 + + 每一列在它之前非零元素的个数每一列在它之前非零元素的个数注意：注意：根据根据M.dataM.data的特征，每列第一个非零元素必的特征，每列第一个非零元素必 定先被扫描到。定先被扫描到。为了求得每列的第一个非零元素在数组为了求得每列的第一个非零元素在数组B B中应有的位置需先求中应有的位置需先求1.1. 矩阵矩阵M M中的每一列中非零元的个数中的每一列中非零元

45、的个数令令：A A中的列变量用中的列变量用colcol表示；表示； cnumcnum colcol ：存放存放A A中第中第colcol 列中非列中非0 0元素个数元素个数 cposcpos colcol ：存放存放A A中第中第colcol列的第一个非列的第一个非0 0元素的位置元素的位置 （即（即A.dataA.data中待计算的中待计算的“恰当恰当”位置所需参考点）位置所需参考点）colcol123456cnumcolcnumcol 222110cposcolcposcol 0规律规律: cpos00 cposcol cposcol-1 + cnumcol-10 12 9 0 0 00

46、0 0 0 0 0 -3 0 0 0 14 00 0 24 0 0 00 18 0 0 0 015 0 0 -7 0 0M= 2 col 1 2 3 4 5 6 4 8 7 6 6 6 8 1 2 12 1 3 9 3 1 -3 3 5 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j v0 1 2 3 4 5 6 7 8M6 6 8 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 5 3 14 pppppppp4629753colcol1 12 23 34 45 56 6cnumcolcnumcol 2 22 22 21 1

47、1 10 0cposcolcposcol 1 13 35 57 78 89 9i j v0 1 2 3 4 5 6 7 8Tvoid fasttranstri(tritupletable a, tritupletable &b) int col；/*当前列号当前列号*/ int pa,pb; /*分别表示分别表示a,b的当前位置的当前位置*/ int cnumn, cposn; b.m=a.n; b.n=a.m; b.t=a.t; if(b.t=0) printf(“A=0n”); return 0; for(col=0;cola.n;col+) cnumcol=0; /每列元素的个数

48、初始化每列元素的个数初始化 /*统计统计a中每列非零元素的个数；中每列非零元素的个数；*/ for(pa=0; paa.t; pa+) col=a.datapa.j; cnumcol+; /*由递推关系计算由递推关系计算cpos的值的值*/ cpos0=0; for(col=1;col=a.n;col+) cposcol = cposcol-1 + cnumcol-1; /*扫描扫描a，将元素交换，将元素交换i,j写入写入b*/ for( pa=0; paa.t; pa+ ) col = a.datapa.j; pb = cposcol; b.datapb.i = a.datapa.j; b.

49、datapb.j = a.datapa.i; b.datapb.v = a.datapa.v; cposcol+; /修改向量表中列坐标值，供同一修改向量表中列坐标值，供同一列下一非零元素定位之用！列下一非零元素定位之用！ 1.1. 与常规算法相比，增加了与常规算法相比，增加了2 2个长度为列长的辅助数个长度为列长的辅助数组组( (cnum 和和cpos ）。快速转置算法的效率分析快速转置算法的效率分析：2.2. 从时间上，此算法用了从时间上，此算法用了4 4个并列的单循环，而且其个并列的单循环，而且其中前中前3 3个单循环都是用来产生辅助数组的。个单循环都是用来产生辅助数组的。 for(co

50、l = 0; col a.n; col+) 循环次数循环次数n;n; for( pa = 0; pa a.t; pa +) 循环次数循环次数t;t; for(col = 1; col a.n; col+) 循环次数循环次数n;n; for( pa=0; pa a.t ; pa + ) 循环次数循环次数t;t; 该算法的时间复杂度该算法的时间复杂度( (n n* *2)+(t2)+(t* *2)=2)=O(O(n+tn+t） 传统转置：传统转置：O(O(m m* *n n) ) 压缩转置：压缩转置：O(O(m m* *t t) ) 压缩快速转置：压缩快速转置：O(O(n+tn+t) )牺牲空间效

51、率换时牺牲空间效率换时 间效率。间效率。小结：小结：讨论：讨论：最坏情况是最坏情况是t=nt=n* *m m( (即矩阵中全部是非零元素），即矩阵中全部是非零元素），而此时的时间复杂度也只是而此时的时间复杂度也只是O(O(m m* *n n) )，并未超过传统转并未超过传统转置算法的时间复杂度。置算法的时间复杂度。链式存储结构o 带行指针向量的单链表表示Y每行的非零元用一个单链表存放 Y设置一个行指针数组，指向本行第一个非零元结点；若本行无非零元，则指针为空Y表头结点与单链表结点类型定义typedef struct node int col; int val; struct node *lin

52、k;JD;typedef struct node *TD;0200000000000210010070003A1 35 73 -11 -12 -24 2需存储单元个数为3t+mo 十字链表Y设行指针数组和列指针数组，分别指向每行、列第一个非零元Y结点定义tpedef struct node int row,col,val; struct node *down, *right;JD;row col valdownright34008000450003A113418225234广义表是第广义表是第2 2章提到的线性表的推广。线性表中的元素仅限于章提到的线性表的推广。线性表中的元素仅限于原子项，即不

53、可以再分，而广义表中的元素既可以是原子项原子项，即不可以再分，而广义表中的元素既可以是原子项，也可以是子表（另一个线性表）。，也可以是子表（另一个线性表）。5.3 5.3 广义表广义表5.4 5.4 广义表的定义广义表的定义广义表是线性表的推广，也称为列表（广义表是线性表的推广，也称为列表（lists）。广义表中元素。广义表中元素既可以是原子类型，也可以是列表。既可以是原子类型，也可以是列表。记为：记为： LS = ( a1 , a2 , ， an ) 广义表名广义表名 a1是表头是表头(Head） （ a2 ,an ）是表尾是表尾 (Tail)1、定义：、定义：n n是表长是表长 ai可以是

54、单个元素，也可以是广义表，分别称为广义表可以是单个元素，也可以是广义表，分别称为广义表LS的的原原子子和和子表子表；第一个第一个元素是表头元素是表头，而其余元素组成的，而其余元素组成的表表称为表尾称为表尾； 所以任何一个非空表，表头可能是原子，也可能是列表；但所以任何一个非空表，表头可能是原子，也可能是列表；但表尾表尾一定是列表一定是列表。 约定：用小写字母表示原子类型，用约定：用小写字母表示原子类型，用大写字母大写字母表示列表。表示列表。在广义表中约定：在广义表中约定：2、特点：、特点：1）次序性：）次序性：一个直接前驱和一个直接后继一个直接前驱和一个直接后继2）长度：）长度：表中表中最外层

55、最外层包含元素个数包含元素个数3）深度：）深度：当广义表全部用原子代替后，表当广义表全部用原子代替后，表中中括号的最大重数括号的最大重数 空表（空表（ ）的深度为）的深度为1，长度为，长度为0 ，原子的深度为，原子的深度为0.4）可递归：）可递归：自己可以作为自己的子表。自己可以作为自己的子表。 例例E=(a, E) 递归表的深度是无穷值，长度是递归表的深度是无穷值，长度是2。5）可共享）可共享: 可以为其它广义表所共享的表。可以为其它广义表所共享的表。6 6）任何一个非空广义表）任何一个非空广义表 LS = ( LS = ( 1, 1, 2, 2, , , n)n) 均可分解为均可分解为 表头表头 GetHead(LS) = 1 和和 表尾表尾 GetTa