严蔚敏版数据结构第五章课件.ppt

1、1数据结构课程的内容数据结构课程的内容2第第5章章 数组和广义表（数组和广义表（Arrays&Lists）元素的值并非原子类型，可以再分解，表中元素也是一元素的值并非原子类型，可以再分解，表中元素也是一个线性表（即广义的线性表）。个线性表（即广义的线性表）。所有数据元素仍属所有数据元素仍属同一数据类型同一数据类型。5.1 数组的定义数组的定义5.2 数组的顺序表示和实现数组的顺序表示和实现5.3 矩阵的压缩存储矩阵的压缩存储5.4 广义表的定义广义表的定义5.5 广义表的存储结构广义表的存储结构数组和广义表的特点：数组和广义表的特点：一种特殊的线性表一种特殊的线性表35.1 数组的定义数组的定

2、义 数组：数组：由一组名字相同、下标不同的变量构成由一组名字相同、下标不同的变量构成注意：注意：本章所讨论的数组与高级语言中的数组有所区别：高本章所讨论的数组与高级语言中的数组有所区别：高级语言中的数组是顺序结构；而级语言中的数组是顺序结构；而本章的数组既可以是顺序的，本章的数组既可以是顺序的，也可以是链式结构也可以是链式结构，用户可根据需要选择。，用户可根据需要选择。答：答：对的对的。因为：。因为：数组中各元素具有数组中各元素具有统一的类型统一的类型；数组元素的下标一般具有数组元素的下标一般具有固定的上界和下界固定的上界和下界，即数组一，即数组一旦被定义，它的维数和维界就不再改变。旦被定义，

3、它的维数和维界就不再改变。数组的数组的基本操作比较简单基本操作比较简单，除了结构的初始化和销毁之，除了结构的初始化和销毁之外，只有存取元素和修改元素值的操作。外，只有存取元素和修改元素值的操作。讨论：讨论：“数组的处理比其它复杂的结构要简单数组的处理比其它复杂的结构要简单”，对吗？，对吗？4n一维数组存储方式一维数组存储方式35 27 49 18 60 54 77 83 41 020 1 2 3 4 5 6 7 8 9l l l l l l l l l l LOC(i)=LOC(i-1)+l=a+i*lLOC(i)=LOC(i-1)+l=a+i*l,i 0 a,i=0 a+i*la5二维数组的

4、特点：二维数组的特点：2 2个下标，个下标，每个元素每个元素ai,j受到两个关系受到两个关系（行关系和列关系）的约束：（行关系和列关系）的约束：一个一个mn的二维数组可以的二维数组可以看成是看成是m行的一维数组，或行的一维数组，或者者n列的一维数组。列的一维数组。N N维数组的特点：维数组的特点：n n个下标，个下标，每个元素受到每个元素受到n n个关系约束个关系约束一个一个n维数组可以看成是维数组可以看成是由若干个由若干个n1维数组组成的线性表。维数组组成的线性表。a11 a12 a1n a21 a22 a2n am1 am2 amn Amn=6N维数组的数据类型定义维数组的数据类型定义n_

5、ARRAY=(D,R)其中：Ri=|aj1,j2,jijn,aj1,j2,ji+1jn D 数据关系：数据关系：R=R1,R2，.Rn 数据对象：数据对象：D=aj1,j2jn|ji为数组元素的第为数组元素的第i 维下标维下标，aj1,j2jn Elemset数组的抽象数据类型定义数组的抽象数据类型定义略略，参见教材参见教材P90P90构造数组、销毁数组、读数组元素、写数组元素构造数组、销毁数组、读数组元素、写数组元素基本操作：基本操作：75.2 5.2 数组的顺序存储表示和实现数组的顺序存储表示和实现问题：问题：计算机的存储结构是一维的，而数组一般是多维计算机的存储结构是一维的，而数组一般是

6、多维 的，怎样存放？的，怎样存放？解决办法：解决办法：事先约定按某种次序将数组元素排成一列序列，事先约定按某种次序将数组元素排成一列序列，然后将这个线性序列存入存储器中。然后将这个线性序列存入存储器中。例如：例如：在二维数组中，我们既可以规定按在二维数组中，我们既可以规定按行行存储，也可以存储，也可以规定按规定按列列存储存储。注意：注意：若规定好了次序，则数组中任意一个元素的存放地址便若规定好了次序，则数组中任意一个元素的存放地址便有规律可寻，可形成地址计算公式；有规律可寻，可形成地址计算公式；约定的次序不同，则计算元素地址的公式也有所不同；约定的次序不同，则计算元素地址的公式也有所不同；C

7、C和和PASCALPASCAL中一般采用行优先顺序；中一般采用行优先顺序；FORTRANFORTRAN采用列优先。采用列优先。8设一般的二维数组是设一般的二维数组是AcAc1 1.d.d1 1,c,c2 2.d.d2 2，这里这里c c1 1,c,c2 2不一定是不一定是0 0。无论规定行优先或列优先，只要知道以下三要素便可随时求出无论规定行优先或列优先，只要知道以下三要素便可随时求出任一元素的地址（任一元素的地址（这样数组中的任一元素便可以这样数组中的任一元素便可以随机存取随机存取！）：二维数组二维数组列优先列优先存储的通式为：存储的通式为：LOC(aij)=LOC(ac1，c2)+(j-c

8、2)*(d1-c1+1)+i-c1)*L ac1,c2 ac1,d2 aij ad1,c2 ad1,d2 Amn=单个元素单个元素长度长度aij之前的之前的行数行数数组基址数组基址总列数，即总列数，即第第2 2维长度维长度aij本行前面的本行前面的元素个数元素个数开始结点的存放地址（即基地址）开始结点的存放地址（即基地址）维数和每维的上、下界；维数和每维的上、下界；每个数组元素所占用的单元数每个数组元素所占用的单元数则则行优先行优先存储时的地址公式为：存储时的地址公式为：LOC(aij)=LOC(ac1，c2)+(i-c1)*(d2-c2+1)+j-c2)*L9二维数组二维数组(书上书上)11

9、1101121202111101101000mnananamaaamaaamaaaa行优先存放：行优先存放：设数组开始存放位置设数组开始存放位置 LOC(0,0)，每个元素占，每个元素占用用 l 个存储单元个存储单元 LOC(i,j)=LOC(0,0)+(i*m+j)*l10例例2：已知二维数组已知二维数组Am,m按行存储的元素地址公式是：按行存储的元素地址公式是：Loc(aij)=Loc(a11)+(i-1)*m+(j-1)*K,按列存储的公式是？按列存储的公式是？Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*K （尽管是方阵，但公式仍不同）（尽管是方阵，但公式仍不同）例例

10、1软考题软考题：一个二维数组一个二维数组A，行下标的范围是，行下标的范围是1到到6，列下标的范围是列下标的范围是0到到7，每个数组元素用相邻的，每个数组元素用相邻的6个字节存储，个字节存储，存储器按字节编址。那么，这个数组的体积是存储器按字节编址。那么，这个数组的体积是 个字节。个字节。288例例3：00年计算机系考研题年计算机系考研题设数组设数组a160,170的的基地址为基地址为2048，每个元素占，每个元素占2个存储单元，若以列序为主序个存储单元，若以列序为主序顺序存储，则元素顺序存储，则元素a32,58的存储地址为的存储地址为 。8950LOC(aij)=LOC(ac1，c2)+(j-

11、c2)*(d1-c1+1)+i-c1)*L得：得：LOC(a32,58)=2048+(58-1)*(60-1+1)+32-1)*28950答：请注意审题！答：请注意审题！利用列优先通式：利用列优先通式：答：答：Volume=m*n*L=6*8*6=48*6=28811行向量行向量 下标下标 i 页向量页向量 下标下标 i列向量列向量 下标下标 j 行向量行向量 下标下标 j 列向量列向量 下标下标 k 二维数组二维数组 三维数组三维数组12三维数组三维数组 各维元素个数为各维元素个数为 m1,m2,m3 下标为下标为 i1,i2,i3的数组元素的存储地址：的数组元素的存储地址：（按页（按页/行

12、行/列存放）列存放）LOC(i1,i2,i3)=a+(i1*m2*m3+i2*m3+i3)*l 前前i1页总页总元素个数元素个数第第i1页的页的前前i2行行总总元素个数元素个数13 n 维数组维数组 各维元素个数为各维元素个数为 m1,m2,m3,mn 下标为下标为 i1,i2,i3,in 的数组元素的存储地址：的数组元素的存储地址：limianjnjknkj*111LOC(i1,i2,in)=a+(i1*m2*m3*mn+i2*m3*m4*mn+in-1*mn+in)*l 14Loc(jLoc(j1 1,j,j2 2,j jn n)=LOC(0,0,)=LOC(0,0,0)0)若是若是N维数

13、组，其中任一元素的地址该如何计算？维数组，其中任一元素的地址该如何计算？niii1jC其中其中Cn=L,Ci-1=biCi，1in一个元一个元素长度素长度数组基址数组基址前面若干元素占用前面若干元素占用的地址字节总数的地址字节总数第第i i维长度维长度与所存元素个数有关的系与所存元素个数有关的系数，可用递推法求出数，可用递推法求出教材已给出教材已给出低维低维优先的地址计算公式，优先的地址计算公式，见见P93P93（5-25-2）式）式该式称为该式称为n n维数组的映像函数维数组的映像函数：15#define MAX_ARRAY_DIM 8 /假设最大维数为假设最大维数为8 typedef st

14、ruct ELemType*base;/数组元素基址数组元素基址 int dim;/数组维数数组维数 int *bound;/数组数组各维长度信息保存区各维长度信息保存区基址基址 int *constants;/数组数组映像函数常量映像函数常量的基址的基址 Array;即即Ci信息保存区信息保存区数组的基本操作函数说明（有数组的基本操作函数说明（有5个）个）（请阅读教材（请阅读教材P93-95P93-95）N维数组的顺序存储表示维数组的顺序存储表示（见教材见教材P93P93）以以销毁数组销毁数组函数为例函数为例16顺序存储方式：顺序存储方式：按低地址优先（或高地址优先）顺序存入一维按低地址优先

15、（或高地址优先）顺序存入一维数组。数组。行指针向量行指针向量a11a12a1nam1am2amn补充：补充：链式存储方式：链式存储方式：用用带行指针向量的单链表带行指针向量的单链表来表示。来表示。注：数组的运算参见下一节实例（稀疏矩阵的转置）注：数组的运算参见下一节实例（稀疏矩阵的转置）（难点是多维数组与一维数组的地址映射关系难点是多维数组与一维数组的地址映射关系）175.3 5.3 矩阵的压缩存储讨论：讨论：1.什么是压缩存储？什么是压缩存储？若多个数据元素的若多个数据元素的值都相同值都相同，则只分配一个元素值的存储空间，则只分配一个元素值的存储空间，且零元素不占存储空间。且零元素不占存储空

16、间。2.所有二维数组（矩阵）都能压缩吗？所有二维数组（矩阵）都能压缩吗？未必，要看矩阵是否具备以上压缩条件。未必，要看矩阵是否具备以上压缩条件。3.什么样的矩阵具备以上压缩条件？什么样的矩阵具备以上压缩条件？一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等。阵等。4.什么叫什么叫稀疏矩阵？稀疏矩阵？矩阵中非零元素的个数较少（一般小于矩阵中非零元素的个数较少（一般小于5%5%）重点介绍稀疏矩阵的压缩和相应的操作。重点介绍稀疏矩阵的压缩和相应的操作。18特殊矩阵的压缩存储特殊矩阵的压缩存储 特殊矩阵是指非零元素或零元素的分布有特殊矩阵

17、是指非零元素或零元素的分布有一定规律的矩阵。一定规律的矩阵。特殊矩阵的压缩存储主要是针对阶数很高特殊矩阵的压缩存储主要是针对阶数很高的特殊矩阵。为节省存储空间，对可以不的特殊矩阵。为节省存储空间，对可以不存储的元素，如零元素或对称元素，不再存储的元素，如零元素或对称元素，不再存储。存储。对称矩阵对称矩阵 三对角矩阵三对角矩阵19对称矩阵的压缩存储对称矩阵的压缩存储设有一个设有一个 n n 的对称矩阵的对称矩阵 A。11121110122221201112111010020100Annnnnnnnaaaaaaaaaaaaaaaa在矩阵中，在矩阵中，aij=aji20 为节约存储空间，只存对角线及

18、对角线以为节约存储空间，只存对角线及对角线以上的元素，或者只存对角线及对角线以下上的元素，或者只存对角线及对角线以下的元素。前者称为上三角矩阵，后者称为的元素。前者称为上三角矩阵，后者称为下三角矩阵。下三角矩阵。把它们按行存放于一个一维数组把它们按行存放于一个一维数组 B 中，称中，称之为对称矩阵之为对称矩阵 A 的压缩存储方式。的压缩存储方式。数组数组 B 共有共有 n+(n-1)+1=n*(n+1)/2 个元素。个元素。21上三角矩阵下三角矩阵33323130232221201312111003020100aaaaaaaaaaaaaaaa33323130232221201312111003

19、020100aaaaaaaaaaaaaaaa22下三角矩阵B a00 a10 a11 a20 a21 a22 a30 a31 a32 an-1n-1 0 1 2 3 4 5 6 7 8 n(n+1)/2-1若若 i j,数组元素数组元素Aij在数组在数组B中的存放位置中的存放位置为为 1+2+i+j=(i+1)*i/2+j前前i行行元素总数元素总数 第第i行第行第j个个元素前元素个数元素前元素个数11121110122221201112111010020100nnnnnnnnaaaaaaaaaaaaaaaa23若若 i j，数组元素，数组元素Aij在矩阵的下三角在矩阵的下三角部分，在数组部分，

20、在数组 B 中没有存放。因此，找它中没有存放。因此，找它的对称元素的对称元素Aji。Aji在数组在数组 B 的第的第(2*n-j-1)*j/2+i 的位置中找到。的位置中找到。26三、对角矩阵的压缩存储三、对角矩阵的压缩存储1121122232232221121110010000000000000000000AnnnnnnnnnnaaaaaaaaaaaaaB a00 a01 a10 a11 a12 a21 a22 a23 an-1n-2 an-1n-1 0 1 2 3 4 5 6 7 8 9 1027 三对角矩阵中除主对角线及在主对角线上三对角矩阵中除主对角线及在主对角线上 下最临近的两条对角

21、线上的元素外，所有下最临近的两条对角线上的元素外，所有其它元素均为其它元素均为0。总共有。总共有3n-2个非零元素。个非零元素。将三对角矩阵将三对角矩阵A中三条对角线上的元素按中三条对角线上的元素按行存放在一维数组行存放在一维数组 B 中，且中，且a00存放于存放于B0。在三条对角线上的元素在三条对角线上的元素aij 满足满足 0 i n-1,i-1 j i+1 在一维数组在一维数组 B 中中 Aij 在第在第 i 行，它前面行，它前面有有 3*i-1 个非零元素个非零元素,在本行中第在本行中第 j 列前面列前面有有 j-i+1 个，所以元素个，所以元素 Aij 在在 B 中位置中位置为为 k

22、=2*i+j。28一、一、稀疏矩阵的压缩存储稀疏矩阵的压缩存储问题：问题：如果只存储如果只存储稀疏矩阵中的非零元素，那这些元素的稀疏矩阵中的非零元素，那这些元素的位置信息位置信息该如何表示？该如何表示？解决思路：解决思路：对每个非零元素对每个非零元素增开增开若干存储单元，例如存放其所若干存储单元，例如存放其所在的行号和列号，便可准确反映该元素所在位置。在的行号和列号，便可准确反映该元素所在位置。实现方法：实现方法：将每个非零元素用一个三元组将每个非零元素用一个三元组（i，j，aij）来表示，）来表示，则每个则每个稀疏矩阵可用一个稀疏矩阵可用一个三元组表三元组表来表示。来表示。二、二、稀疏矩阵的

23、操作稀疏矩阵的操作29例例1：三元素组表中的每个结点对应于稀疏矩阵的三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该一个非零元素，它包含有三个数据项，分别表示该元素的元素的 、和和 。行下标行下标列下标列下标元素值元素值例例2 2：写出右图所示稀疏写出右图所示稀疏矩阵的压缩存储形式。矩阵的压缩存储形式。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 0(1,2,12)(1,2,12)，(1,3,9)(1,3,9)，(3,1,-3)(3,1,-3)，(3,5,14)

24、(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)法法1 1：用线性表表示：用线性表表示：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 030法法2 2：用三元组矩阵表示：用三元组矩阵表示：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 0121213931-3351443245218611564-

25、7注意：注意：为更可靠描述，为更可靠描述，通常再加一行通常再加一行“总体总体”信息：即信息：即总行数、总总行数、总列数、非零元素总个列数、非零元素总个数数668ijvalue稀疏矩阵压缩存储的稀疏矩阵压缩存储的缺点缺点：将失去随机存取功能将失去随机存取功能 :-(31法三：法三：用用带辅助向量带辅助向量的三元组表示。的三元组表示。方法：方法：增加增加2个辅助向量：个辅助向量：记录每行非记录每行非0元素个数，用元素个数，用NUM（i）表示；表示；记录稀疏矩阵中每行第一个非记录稀疏矩阵中每行第一个非0元素元素在三元在三元组中的行号组中的行号，用，用POS（i）表示。表示。76531211202NU

26、M(i)6543POS(i)21i0 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 0-7461516182524341453-3139311221866vji0123456783用途：用途：通过三元组通过三元组高效访问稀疏矩阵高效访问稀疏矩阵中中任一非零元素。任一非零元素。规律：规律：POS(1)1 POS(i)POS(i-1)+NUM(i-1)32法四：法四：用用十字链表十字链表表示表示用途：用途：方便稀疏矩阵的加减运算；方便稀疏矩阵的加减运算；方法：方法：每个非每个非0元素占用元素占用5个域。

27、个域。right downvji同一列中下一非同一列中下一非零元素的指针零元素的指针同一行中下一非同一行中下一非零元素的指针零元素的指针十字链表的特点：十字链表的特点：每行非零元素链接每行非零元素链接成带表头结点的循环链表；成带表头结点的循环链表；每列非零元素也链接每列非零元素也链接成带表头结点的循环链表。成带表头结点的循环链表。则每个非零元素既是行循环链表中的一个结点；又是列循环则每个非零元素既是行循环链表中的一个结点；又是列循环链表中的一个结点，即链表中的一个结点，即呈十字链状。呈十字链状。以刚才的以刚才的稀疏矩阵稀疏矩阵为例：为例：122100H1931182533#define MAX

28、SIZE 125000#define MAXSIZE 125000 /设非零元素最大个数设非零元素最大个数125000125000 typedef struct typedef struct int i;int i;/元素行号元素行号 int j;int j;/元素列号元素列号 ElemType e;ElemType e;/元素值元素值 TripleTriple;typedef structtypedef struct TripleTriple dataMAXSIZE+1;dataMAXSIZE+1;/三元组表，以行为主序存入一维向量三元组表，以行为主序存入一维向量 data data 中中

29、int mu;int mu;/矩阵总行数矩阵总行数 int nu;int nu;/矩阵总列数矩阵总列数 int tu;int tu;/矩阵中非零元素总个数矩阵中非零元素总个数 TsMatrixTsMatrix;三元组表的顺序存储表示三元组表的顺序存储表示（见教材（见教材P98P98）：）：/一个结点的结构定义一个结点的结构定义/整个三元组表的定义整个三元组表的定义34二、二、稀疏矩阵的操作稀疏矩阵的操作 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 00 0 3 0 0 1512 0 0 0 18

30、 0 9 0 0 24 0 00 0 0 0 0 -70 0 14 0 0 00 0 0 0 0 0(1,2,12)(1,3,9)(3,1,-3)(3,5,14)(4,3,24)(5,2,18)(6,1,15)(6,4,-7)(1,3,-3)(1,6,15)(2,1,12)(2,5,18)(3,1,9)(3,4,24)(4,6,-7)(5,3,14)三三元元组组表表a.data三三元元组组表表b.data转置后转置后MT（以转置运算为例）（以转置运算为例）目的：目的：35答：答：肯定不正确！肯定不正确！除了：除了：（1 1）每个元素的行下标和列下标互换（即三元组）每个元素的行下标和列下标互换（

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

32、种说法正确吗？算，这种说法正确吗？有两种实现方法有两种实现方法压缩转置压缩转置(压缩压缩)快速转置快速转置提问：提问：36方法方法1 1：压缩转置压缩转置思路：思路：反复扫描反复扫描a.dataa.data中的中的列序列序，从小到大依次进行转置。，从小到大依次进行转置。三三元元组组表表a.data三三元元组组表表b.data(1,3,-3)(1,6,15)(2,1,12)(2,5,18)(3,1,9)(3,4,24)(4,6,-7)(5,3,14)(1,2,12)(1,3,9)(3,1,-3)(3,5,14)(4,3,24)(5,2,18)(6,1,15)(6,4,-7)11 22col q1

33、234 p123437Status TransPoseSMatrix(TSMatrix M,TSMatrix&T)T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu)q=1;for(col=1;col=M.nu;col+)for(p=1;p=M.tu;p+)if(M.datap.j=col)T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.value=M.datap.value;q+;return OK;/TranposeSMatrix;压缩转置算法描述压缩转置算法描述：（见教材（见教材P99）/用三元组表存放稀疏矩阵用三元

34、组表存放稀疏矩阵M M，求，求M M的转置矩阵的转置矩阵T T/q q是转置矩阵是转置矩阵T T的结点编号的结点编号/colcol是扫描是扫描M M三元表列序的变量三元表列序的变量/p是是M M三元表中结点编号三元表中结点编号381 1、主要时间消耗主要时间消耗在查找在查找M.datap.j=colM.datap.j=col的元素的元素，由两重循，由两重循环完成环完成:for(col=1;col=M.nuM.nu;col+)循环次数循环次数nunu for(p=1;p=M.tuM.tu;p+)循环次数循环次数tutu所以该算法的时间复杂度为所以该算法的时间复杂度为O(O(nunu*tutu)-

35、即即M M的列数与的列数与M M中非零元素的个数之中非零元素的个数之积积最恶劣情况：最恶劣情况：M M中全是非零元素，此时中全是非零元素，此时tu=mutu=mu*nunu，时间复杂度为时间复杂度为 O(O(nunu2 2*mumu)注：注：若若M M中基本上是非零元素时，即使用非压缩传统转置算法中基本上是非零元素时，即使用非压缩传统转置算法的时间复杂度也不过是的时间复杂度也不过是O(O(nunu*mumu)（程序见（程序见教材教材P99P99）结论：结论：压缩转置算法不能滥用。压缩转置算法不能滥用。前提：前提：仅适用于非零元素个数很少（即仅适用于非零元素个数很少（即tutumumu*nunu

36、）的情况。）的情况。压缩转置算法的效率分析压缩转置算法的效率分析：39方法方法2 2 快速转置快速转置三三元元组组表表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,12)(1,3,9)(3,1,-3)(3,5,14)(4,3,24)(5,2,18)(6,1,15)(6,4,-7)思路：依次思路：依次把把a.dataa.data中的元素直接送入中的元素直接送入b.datab.data的恰当位的恰当位置上（置上（即即M M三元组的三元组的p p指针不回溯指针不回溯）。）

37、。关键：关键：怎样寻找怎样寻找b.datab.data的的“恰当恰当”位置？位置？p1234 q 3 540如果能如果能预知预知M矩阵矩阵每一列每一列(即即T的每一行的每一行)的的非零元素个数非零元素个数，又能预知又能预知第一个非零元素第一个非零元素在在b.datab.data中的中的位置位置,则扫描则扫描a.data时便可以将每个元素准确定位（时便可以将每个元素准确定位（因为已知若干参考点因为已知若干参考点）。）。技巧：技巧：利用利用带辅助向量带辅助向量的三元组表，它正好携带每行（或列）的三元组表，它正好携带每行（或列）的非零元素个数的非零元素个数 NUM(i)以及每行（或列）的第一个非以及

38、每行（或列）的第一个非零元素在三元组表中的位置零元素在三元组表中的位置POS(i)等信息。等信息。设计思路：设计思路：i123456NUM(i)202112POS(i)133567不过我们需要的是不过我们需要的是按列生成的按列生成的M矩阵的辅助向量。矩阵的辅助向量。规律：规律：POS(1)1POS(i)POS(i-1)+NUM(i-1)请回忆：请回忆：请注意请注意a.dataa.data特征：每列首个非零元素必定先被扫描到。特征：每列首个非零元素必定先被扫描到。41令：令：M中的列变量用中的列变量用col表示；表示；num col：存放存放M中第中第col 列中非列中非0 0元素个数，元素个数

39、，cpot col：存放存放M中第中第col列的第一个非列的第一个非0 0元素的位置，元素的位置，（即（即b.datab.data中待计算的中待计算的“恰当恰当”位置所需参考点）位置所需参考点）讨论：按列优先的辅助向量求出后，讨论：按列优先的辅助向量求出后，下一步该如何操作？下一步该如何操作？由由a.dataa.data中每个元素的列信息，即可直接查出中每个元素的列信息，即可直接查出b.datab.data中的中的重要参考点之位置，进而可确定当前元素之位置！重要参考点之位置，进而可确定当前元素之位置！col123456numcol222110cpotcol1规律：规律：cpot(1)1cpot

40、col cpotcol-1+numcol-10 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 3 5 7 8 8col 1 2 3 4 5 642Status FastTransposeSMatrix（TSMatirx M,TSMatirx&T）T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu)for(col=1;col=M.nu;col+)numcol=0;for(i=1;i=M.tu;i+)col=M.data i .j;+num col;cpos 1 =1;for

41、(col=2;col=M.nu;col+)cposcol=cposcol-1+num col-1 ;for(p=1;p=M.tu;p+)col=M.data p.j;q=cpos col;T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.value=M.datap.value;/for /ifreturn OK;/FastTranposeSMatrix;快速转置算法描述快速转置算法描述：/M/M用顺序存储表示，求用顺序存储表示，求M M的转置矩阵的转置矩阵T T/先统计每列非零元素个数先统计每列非零元素个数/再生成每列首元位置辅助向量表再生成每列首

42、元位置辅助向量表/p/p指向指向a.dataa.data，循环次数为非，循环次数为非0 0元素总个数元素总个数tutu/查辅助向量表得查辅助向量表得q q，即，即T T中位置中位置/重要语句！重要语句！修改向量表中列坐标值，供修改向量表中列坐标值，供同一列同一列下一非零元素定位之用！下一非零元素定位之用！431.1.与常规算法相比，附加了生成辅助向量表的工作。增开了与常规算法相比，附加了生成辅助向量表的工作。增开了2 2个长度为列长的数组个长度为列长的数组(num 和和cpos）。传统转置：传统转置：O(muO(mu*nu)nu)压缩转置：压缩转置：O(muO(mu*tu)tu)压缩快速转置：

43、压缩快速转置：O(nu+tu)O(nu+tu)牺牲空间效率换时间效率。牺牲空间效率换时间效率。快速转置算法的效率分析快速转置算法的效率分析：2.2.从时间上，此算法用了从时间上，此算法用了4 4个并列的单循环，而且其中前个并列的单循环，而且其中前3 3个个单循环都是用来产生辅助向量表的。单循环都是用来产生辅助向量表的。for(col=1;col=M.nu;col+)循环次数循环次数nu;nu;for(i=1;i=M.tu;i+)循环次数循环次数tu;tu;for(col=2;col=M.nu;col+)循环次数循环次数nu;nu;for(p=1;p=M.tu;p+)循环次数循环次数tu;tu;

44、该算法的时间复杂度该算法的时间复杂度(nu(nu*2)+(tu2)+(tu*2)=O(nu+tu2)=O(nu+tu）讨论：最恶劣情况是讨论：最恶劣情况是tu=nutu=nu*mu(mu(即矩阵中全部是非零元素），即矩阵中全部是非零元素），而此时的时间复杂度也只是而此时的时间复杂度也只是O(muO(mu*nu)nu)，并未超过传统转置算，并未超过传统转置算法的时间复杂度。法的时间复杂度。小结：小结：稀疏矩阵相乘的算法见教材稀疏矩阵相乘的算法见教材P101-103P101-103445.4 5.4 广义表的定义广义表的定义广义表是线性表的推广，也称为列表（广义表是线性表的推广，也称为列表（lis

45、ts）记为：记为：LS =(a1,a2,，an)广义表名广义表名 表头表头(Head）表尾表尾(Tail)1、定义：、定义：第一个元素是表头，而其余元素组成的表称为表尾；第一个元素是表头，而其余元素组成的表称为表尾；用小写字母表示原子类型，用大写字母表示列表。用小写字母表示原子类型，用大写字母表示列表。n n是表长是表长在广义表中约定：在广义表中约定：讨论：讨论：广义表与线性表的区别和联系？广义表与线性表的区别和联系？广义表中元素既可以是原子类型，也可以是列表广义表中元素既可以是原子类型，也可以是列表；当每个元素都为原子且类型相同时，就是线性表。当每个元素都为原子且类型相同时，就是线性表。45

46、2、特点：、特点：有次序性有次序性 有长度有长度 有深度有深度 可递归可递归 可共享可共享一个直接前驱和一个直接后继一个直接前驱和一个直接后继表中元素个数表中元素个数表中括号的重数表中括号的重数自己可以作为自己的子表自己可以作为自己的子表可以为其他广义表所共享可以为其他广义表所共享特别提示：任何一个非空表，表头可能是原子，也可能特别提示：任何一个非空表，表头可能是原子，也可能是列表；但表尾一定是列表。是列表；但表尾一定是列表。46E=(a,E)=(a,(a,E)=(a,(a,(a,.)，E为递归表为递归表1）A=()2）B=(e)3）C=(a,(b,c,d)4）D=(A,B,C)5）E=(a,

47、E)例例1：求下列广义表的长度。求下列广义表的长度。n=0，因为因为A是空表是空表n=1，表中元素，表中元素e是原子是原子n=2，a 为原子，为原子，(b,c,d)为子表为子表n=3，3个元素都是子表个元素都是子表n=2，a 为原子，为原子，E为子表为子表D=(A,B,C)=(),(e),(a,(b,c,d)，共享表共享表47ABDCeabcd A=(a,(b,A)例例2 2：试用图形表示下列广义表试用图形表示下列广义表.（设（设 代表原子，代表原子，代表子表）代表子表）e D=(A,B,C)=(),(e),(a,(b,c,d)Aab的长度为的长度为3，深度为，深度为3的长度为的长度为2，深度

48、为，深度为深度括号的重数深度括号的重数 结点的层数结点的层数48介绍两种特殊的基本操作：介绍两种特殊的基本操作：GetHead(L)取表头取表头(可能是原子或列表可能是原子或列表);GetTail(L)取表尾取表尾(一定是列表一定是列表)。广义表的抽象数据类型定义见广义表的抽象数据类型定义见教材教材P107-108P107-108491.GetTail【(b,k,p,h)】;2.GetHead【(a,b),(c,d)】;3.GetTail【(a,b),(c,d)】;4.GetTail【GetHead【(a,b),(c,d)】;例：例：求下列广义表操作的结果（求下列广义表操作的结果（严题集严题集

49、5.10）(k,p,h)（b）(a,b)5.GetTail【（e）】;6.GetHead【()】.7.GetTail【()】.()(a,b)()()(c,d)505.5 广义表的存储结构广义表的存储结构由于广义表的元素可以是不同结构（原子或列表），难以用由于广义表的元素可以是不同结构（原子或列表），难以用顺序存储结构表示顺序存储结构表示 ，通常用链式结构通常用链式结构，每个，每个元素元素用一个结用一个结点表示。点表示。表示原子，可设表示原子，可设2 2个域或个域或3 3个域，依习惯而选。个域，依习惯而选。valuetag=0标志域标志域 数值域数值域注意：列表的注意：列表的“元素元素”还可以是

50、列表，所以结点可能有两种形式还可以是列表，所以结点可能有两种形式tpatomtag=标志域标志域 值域值域表尾指针表尾指针法法2 2：标志域、值域、表尾指针：标志域、值域、表尾指针指向下一结点指向下一结点法法1 1：标志域，数值域：标志域，数值域51tphptag=1 标志域标志域 表头指针表头指针 表尾指针表尾指针2.2.表结点：表结点：表示列表，若表不空，则可分解为表头和表尾，表示列表，若表不空，则可分解为表头和表尾，用用3 3个域表示：个域表示：标志域，表头指针，表尾指针标志域，表头指针，表尾指针。A=()10e C=(a,(b,c,d)1110a0b0d0c11例：例：B=(e)A=N