ch5- 数组和广义表(全)

1、1 元素的值并非原子类型，可以再分解，表中元素也是一元素的值并非原子类型，可以再分解，表中元素也是一个线性表（即广义的线性表）。个线性表（即广义的线性表）。 所有数据元素仍属所有数据元素仍属同一数据类型同一数据类型。5.1 数组的定义数组的定义5.2 数组的顺序表示和实现数组的顺序表示和实现5.3 矩阵的压缩存储矩阵的压缩存储5.4 广义表的定义广义表的定义5.5 广义表的存储结构广义表的存储结构数组和广义表的特点：数组和广义表的特点：一种特殊的线性表一种特殊的线性表2数组：数组： 由一组名字相同、下标不同的变量构成由一组名字相同、下标不同的变量构成注意：注意： 本章所讨论的数组与高级语言中的

2、数组有所区别：高本章所讨论的数组与高级语言中的数组有所区别：高级语言中的数组是顺序结构；而级语言中的数组是顺序结构；而本章的数组既可以是顺序的，本章的数组既可以是顺序的，也可以是链式结构也可以是链式结构，用户可根据需要选择。，用户可根据需要选择。答：答：对的对的。因为：。因为： 数组中各元素具有数组中各元素具有统一的类型统一的类型； 数组元素的下标一般具有数组元素的下标一般具有固定的上界和下界固定的上界和下界，即数组一，即数组一旦被定义，它的维数和维界就不再改变。旦被定义，它的维数和维界就不再改变。数组的数组的基本操作比较简单基本操作比较简单，除了结构的初始化和销毁之，除了结构的初始化和销毁之

3、外，只有存取元素和修改元素值的操作。外，只有存取元素和修改元素值的操作。讨论：讨论：“数组的处理比其它复杂的结构要简单数组的处理比其它复杂的结构要简单”，对吗？，对吗？3一维数组的特点：一维数组的特点：1 1个下标，个下标，a ai i 是是a ai+1i+1的直接前驱的直接前驱2 2个下标，个下标，每个元素每个元素ai,j受到两个关系受到两个关系（行关系和列关系）的约束：（行关系和列关系）的约束：一个一个mn的二维数组可以的二维数组可以看成是看成是m行的一维数组，或行的一维数组，或者者n列的一维数组。列的一维数组。N N维数组的特点：维数组的特点：n n个下标，个下标，每个元素受到每个元素受

4、到n n个关系约束个关系约束一个一个n维数组可以看成是维数组可以看成是由若干个由若干个n1维数组组成的线性表。维数组组成的线性表。 a11 a12 a1n a21 a22 a2n am1 am2 amn Amn=4n_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构造数

5、组、销毁数组、读数组元素、写数组元素构造数组、销毁数组、读数组元素、写数组元素基本操作：基本操作：5问题：问题：计算机的存储结构是一维的，而数组一般是多维的，计算机的存储结构是一维的，而数组一般是多维的，怎样存放？怎样存放？解决办法：解决办法：事先约定按某种次序将数组元素排成一列序列，事先约定按某种次序将数组元素排成一列序列，然后将这个线性序列存入存储器中。然后将这个线性序列存入存储器中。例如：例如：在二维数组中，我们既可以规定按在二维数组中，我们既可以规定按行行存储，也可以存储，也可以规定按规定按列列存储存储。注意：注意： 若规定好了次序，则数组中任意一个元素的存放地址便若规定好了次序，则数

6、组中任意一个元素的存放地址便有规律可寻，可形成地址计算公式；有规律可寻，可形成地址计算公式； 约定的次序不同，则计算元素地址的公式也有所不同；约定的次序不同，则计算元素地址的公式也有所不同； C C和和PASCALPASCAL中一般采用行优先顺序；中一般采用行优先顺序；FORTRANFORTRAN采用列优先。采用列优先。6无论规定行优先或列优先，只要知道以下三要素便可随时求出任无论规定行优先或列优先，只要知道以下三要素便可随时求出任一元素的地址（一元素的地址（这样数组中的任一元素便可以随机存取！这样数组中的任一元素便可以随机存取！）：二维数组二维数组列优先列优先存储的通式为：存储的通式为：LO

7、C(aij)=LOC(ac1，c2)+(j-c2)*(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

8、-c2)*L7例1软考题：一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是 个字节。 288例3：00年计算机系考研题设数组a160, 170的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a32,58的存储地址为 。8950LOC(aij)=LOC(ac1，c2)+(j-c2)*(d1-c1+1)+i-c1)*L得：LOC(a32,58)=2048+(58-1)*(60-1+1)+32-1)*28950答：请注意审题！答：请注意审题！利用列优先通式：答：答： Volume=m*n*

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

10、 ELemType *base; /数组元素基址数组元素基址 int dim; /数组维数数组维数 int *bound; /数组数组各维长度信息保存区各维长度信息保存区基址基址 int *constants; /数组数组映像函数常量映像函数常量的基址的基址 Array;即即Ci信息保存区信息保存区数组的基本操作函数说明（有数组的基本操作函数说明（有5个）个）（请阅读教材（请阅读教材P93-95P93-95）以销毁数组函数为例以销毁数组函数为例10Status InitArray(Array &A,int dim,) /若维数若维数dimdim和各维长度合法，则和各维长度合法，则并返回

11、并返回OKOK if(dimMAX_ARRAY_DIM) return ERROR; A.dim=dim; A.bounds=(int *)malloc(dim * sizeof(int); if(!a.bounds) exit(OVERFLOW); /若各维长度合法，则存入若各维长度合法，则存入A.bounds,A.bounds,并求出并求出A A的元素总数的元素总数elemtotalelemtotal elemtotal=1; va_start(ap.dim); /ap/ap为为va_listva_list类型，是存放变长参数表信类型，是存放变长参数表信息的类型息的类型数组的基本操作函数说

12、明（数组的基本操作函数说明（5个）个） （见教材见教材P93-95P93-95）11 for(i=0;idim;+i) A.boundsi=va_arg(ap,int); if(A.boundsi=0;-i) A.constantsi=A.boundsi+1*A.constantsi+1; return OK; 12数组基址指针数组基址指针各维长度保各维长度保存区指针存区指针映像函数映像函数CiCi保存区指针保存区指针Status DestroyArray(Array &A) /销毁数组销毁数组A A if ( ! A . base ) return ERROR; free( A .

13、base ); A . base = NULL; if ( ! A.bounds ) return ERROR; free( A . bounds ); A . bounds = NULL; if ( !A.constants ) return ERROR; free ( A. constants ) ; A. constants = NULL; return OK; 13Status Locate(Array A,va_list ap,int &off) /若若apap指示的各下标值合法，则求出该元素在指示的各下标值合法，则求出该元素在A A中，相对地址中，相对地址offoff of

14、f=0; for(i=0;iA.dim;+i) ind=va_arg(ap,int); if(indA.boundsi) return OVERFLOW; off+=A.constantsi *ind; return OK; 14Status Value(Array A,ElemType &e,) /A/A是是n n维数组，维数组，e e为元素变量，随后是为元素变量，随后是n n个下标值，若个下标值，若各下标不超界，则各下标不超界，则e e赋值为所指定的赋值为所指定的A A的元素值，即将指的元素值，即将指定元素值读到定元素值读到e e变量中。变量中。 va_start(ap,e); i

15、f(result=Locate(A,ap,off)=0) return result; e=*(A.base+off); return OK; 15Status Assign(Array &A,ElemType e,) /A/A是是n n维数组，维数组，e e为元素变量，随后是为元素变量，随后是n n个下标值，个下标值，若各下标不超界，则若各下标不超界，则e e的值赋为所指定的的值赋为所指定的A A的元素值，的元素值， va_start(ap,e); if(result=Locate(A,ap,off)=0) return result; *(A.base+off)=e; return

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

17、（矩阵）都能压缩吗？未必，要看矩阵是否具备以上压缩条件。未必，要看矩阵是否具备以上压缩条件。3. 什么样的矩阵具备以上压缩条件？什么样的矩阵具备以上压缩条件？ 一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等。阵等。4. 什么叫什么叫稀疏矩阵？稀疏矩阵？矩阵中非零元素的个数较少（一般小于矩阵中非零元素的个数较少（一般小于5%5%）重点介绍稀疏矩阵的压缩和相应的操作。重点介绍稀疏矩阵的压缩和相应的操作。18问题：问题：如果只存储如果只存储稀疏矩阵中的非零元素，那这些元素的稀疏矩阵中的非零元素，那这些元素的位置信息位置信息该如何表示？

18、该如何表示？解决思路：解决思路：对每个非零元素对每个非零元素增开增开若干存储单元，例如存放其所若干存储单元，例如存放其所在的行号和列号，便可准确反映该元素所在位置。在的行号和列号，便可准确反映该元素所在位置。实现方法：实现方法：将每个非零元素用一个三元组将每个非零元素用一个三元组（i，j，aij）来表示，）来表示，则每个则每个稀疏矩阵可用一个稀疏矩阵可用一个三元组表三元组表来表示。来表示。二、稀疏矩阵的操作二、稀疏矩阵的操作19行下标行下标列下标列下标元素值元素值例例2 2：写出右图所示稀疏写出右图所示稀疏矩阵的压缩存储形式。矩阵的压缩存储形式。0 12 9 0 0 00 0 0 0 0 0

19、-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)(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 020法法2 2：用

20、三元组矩阵表示：用三元组矩阵表示：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-7注意：注意：为更可靠描述，为更可靠描述，通常再加一行通常再加一行“总体总体”信息：即信息：即总行数、总总行数、总列数、非零元素总个列数、非零元素总个数数668ijvalue稀疏矩阵压缩存储的稀疏矩阵压缩存储的缺点缺点：将失去随机存取功能将失去随机存取功能 :-(2176531211202NUM( i)6543POS( i )21i0 12 9 0 0 0

21、0 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)22用途：用途：方便稀疏矩阵的加减运算；方便稀疏矩阵的加减运算；方法：方法：每个非每个非0元素占用元素占用5个域。个域。right downvji同一列中下一非同一列中下一非零元素的指针零元素的指针同一行中下一非

22、同一行中下一非零元素的指针零元素的指针十字链表的特点：十字链表的特点：每行非零元素链接每行非零元素链接成带表头结点的循环链表；成带表头结点的循环链表；每列非零元素也链接每列非零元素也链接成带表头结点的循环链表。成带表头结点的循环链表。则每个非零元素既是行循环链表中的一个结点；又是列循环则每个非零元素既是行循环链表中的一个结点；又是列循环链表中的一个结点，即链表中的一个结点，即呈十字链状。呈十字链状。以刚才的以刚才的稀疏矩阵稀疏矩阵为例：为例：122100H1931182523 #define MAXSIZE 125000 #define MAXSIZE 125000 /设非零元素最大个数设非零

23、元素最大个数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 中中 int mu; int mu; /矩阵总行数矩阵总行数 int nu;

24、int nu; /矩阵总列数矩阵总列数 int tu; int tu; /矩阵中非零元素总个数矩阵中非零元素总个数 TsMatrixTsMatrix; ; 三元组表的顺序存储表示三元组表的顺序存储表示（见教材（见教材P98P98）：）：/一个结点的结构定义一个结点的结构定义/整个三元组表的定义整个三元组表的定义240 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 0 9 0 0 24 0 00 0 0 0 0 -70 0 14 0 0 00 0 0 0

25、 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（以转置运算为例）（以转置运算为例）目的：目的：25答：答：肯定不正确！肯定不正确！除了：除了： （1 1）每个元素的行下标和列下标互换（即三元组）每个元素的行下标和列下标互换（即三元组中的中的i i和

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

27、种说法正确吗？ 有两种实现方法有两种实现方法压缩转置压缩转置( (压缩压缩) )快速转置快速转置提问：提问：26思路：思路：反复扫描反复扫描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

28、, -7)11 22col q1234 p123427Status 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;压缩转

29、置算法描述压缩转置算法描述：（见教材（见教材P99）/用三元组表存放稀疏矩阵用三元组表存放稀疏矩阵M M，求，求M M的转置矩阵的转置矩阵T T/q q是转置矩阵是转置矩阵T T的结点编号的结点编号/colcol是扫描是扫描M M三元表列序的变量三元表列序的变量/p是是M M三元表中结点编号三元表中结点编号281 1、主要时间消耗在主要时间消耗在查找查找M.datap.j=colM.datap.j=col的元素的元素，由两重循，由两重循环完成环完成: : for(col=1; col=M.nu; col+) 循环次数循环次数nu for(p=1; p=M.tu; p+) 循环次数循环次数tu所

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

31、压缩转置算法不能滥用。前提：前提：仅适用于非零元素个数很少（即仅适用于非零元素个数很少（即tutumumu* *nunu）的情况。）的情况。压缩转置算法的效率分析压缩转置算法的效率分析：29三三元元组组表表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.data

32、a.data中的元素直接送入中的元素直接送入b.datab.data的恰当位的恰当位置上（置上（即即M M三元组的三元组的p p指针不回溯指针不回溯）。）。关键：关键：怎样寻找怎样寻找b.datab.data的的“恰当恰当”位置？位置？ p1234 q 3 530如果能如果能预知预知M矩阵矩阵每一列每一列( (即即T的每一行的每一行) )的的非零元素个数非零元素个数，又能预知又能预知第一个非零元素第一个非零元素在在b.datab.data中的中的位置位置, ,则扫描则扫描a.data时便可以将每个元素准确定位（时便可以将每个元素准确定位（因为已知若干参考点因为已知若干参考点）。）。技巧：技巧：

33、利用利用带辅助向量带辅助向量的三元组表，它正好携带每行（或列）的三元组表，它正好携带每行（或列）的非零元素个数的非零元素个数 NUM(i)以及每行（或列）的第一个非以及每行（或列）的第一个非零元素在三元组表中的位置零元素在三元组表中的位置POS(i) 等信息。等信息。i123456NUM(i)202112POS( i )133567不过我们需要的是不过我们需要的是按列生成的按列生成的M矩阵的辅助向量。矩阵的辅助向量。规律：规律：POS(1)1POS(i)POS(i-1)+NUM(i-1)请回忆：请回忆：请注意请注意a.dataa.data特征：每列首个非零元素必定先被扫描到。特征：每列首个非零

34、元素必定先被扫描到。31讨论：讨论：按列优先按列优先的辅助向量求出后，的辅助向量求出后，下一步该如何操作？下一步该如何操作？由由a.dataa.data中每个元素的中每个元素的列列信息，即可直接查出信息，即可直接查出b.datab.data中的中的重要参考点之位置，进而可确定当前元素之位置！重要参考点之位置，进而可确定当前元素之位置！col123456numcol222110cpotcol1规律：规律： cpot(1)1cpotcol 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 0

35、15 0 0 -7 0 0M 3 5 7 8 8col 1 2 3 4 5 632Status 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(col = 2; col =M.nu; col+) cposcol =c

36、poscol-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/先统计每列非零元素个数先统计每列非零元素个数/再生成每列首元位置辅助向量表再生成每

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

38、tutu) ) 压缩快速转置：压缩快速转置：O(O(nu+nu+tutu)牺牲空间效率换时间效率。牺牲空间效率换时间效率。快速转置算法的效率分析快速转置算法的效率分析：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+) 循环次数循环次数

39、nu;nu; for( p =1; p =M.tu ; p + ) 循环次数循环次数tu;tu; 该算法的时间复杂度该算法的时间复杂度(nu(nu* *2)+(tu2)+(tu* *2)=O(2)=O(nu+tunu+tu）讨论：讨论：最恶劣情况是最恶劣情况是tu=nutu=nu* *mumu( (即矩阵中全部是非零元素），即矩阵中全部是非零元素），而此时的时间复杂度也只是而此时的时间复杂度也只是O(O(mumu* *nunu) )，并未超过传统转置算，并未超过传统转置算法的时间复杂度。法的时间复杂度。小结：小结：稀疏矩阵相乘的算法见教材稀疏矩阵相乘的算法见教材P101-103P101-103

40、34三、三、 十字链表十字链表3 0 0 50 -1 0 02 0 0 01 1 31 4 52 2-13 1 2 3536广义表是递归递归定义的线性结构线性结构， LS = ( 1, 2, , n )其中：i 或为原子 或为广义表例如例如: A = ( ) F = (d, (e) D = (a,(b,c), F) C = (A, D, F) B = (a, B) = (a, (a, (a, , ) ) )37广义表广义表 LS = ( 1, 2, , n )的结构特点的结构特点:1) 广义表中的数据元素有相对次序次序;2) 广义表的长度长度定义为最外层包含元素个数;3) 广义表的深度深度定义

41、为所含括弧的重数; 注意:“原子”的深度为 0 ; “空表”的深度为 1 。4) 广义表可以共享共享;5) 广义表可以是一个递归递归的表; 递归表的深度是无穷值，长度是有限值。386) 任何一个非空广义表非空广义表 LS = ( 1, 2, , n) 均可分解为 表头表头 Head(LS) = 1 和 表尾表尾 Tail(LS) = ( 2, , n) 两部分例如例如: D = ( E, F ) = (a, (b, c)，F )Head( D ) = E Tail( D ) = ( F )Head( E ) = a Tail( E ) = ( ( b, c) )Head( ( b, c) )

42、= ( b, c) Tail( ( b, c) ) = ( )Head( ( b, c) ) = b Tail( ( b, c) ) = ( c )Head( ( c ) ) = c Tail( ( c ) ) = ( )39E=(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, E)例例1：求下列广义表的长度。求下列广义表的长度。n=0，因为因为A是空表是空表n=1，表中元素，表中元素e是原子是原子n=2，a 为原子，为原子，(b,

43、c,d)为子表为子表n=3，3个元素都是子表个元素都是子表n=2，a 为原子，为原子，E为子表为子表D=(A,B,C)=( ),(e),(a,(b,c,d)，共享表共享表40ABDCeabcd A=( a , (b, A) )例例2 2：试用图形表示下列广义表试用图形表示下列广义表. .（设（设 代表原子，代表原子， 代表子表）代表子表） e D=(A,B,C)=( ( ),(e),( a, (b,c,d) ) )Aab的长度为的长度为3，深度为，深度为3的长度为的长度为2，深度为，深度为深度括号的重数深度括号的重数 结点的层数结点的层数41广义表是一个多层次多层次的线性结构线性结构例如：例如

44、：D=(E, F)其中: E=(a, (b, c) F=(d, (e)DEFa( ) d( )bce425.4 广义表的类型定义广义表的类型定义ADT Glist 数据对象数据对象：Dei | i=1,2,.,n; n0; eiAtomSet 或 eiGList, AtomSet为某个数据对象 数据关系：数据关系： LR| ei-1 ,eiD, 2in ADT Glist基本操作基本操作:43 结构的创建和销毁结构的创建和销毁 InitGList(&L); DestroyGList(&L); CreateGList(&L, S); CopyGList(&T, L

45、);基本操作基本操作 状态函数状态函数 GListLength(L); GListDepth(L); GListEmpty(L); GetHead(L); GetTail(L); 插入和删除操作插入和删除操作 InsertFirst_GL(&L, e); DeleteFirst_GL(&L, &e); 遍历遍历 Traverse_GL(L, Visit();44介绍两种特殊的基本操作：介绍两种特殊的基本操作：GetHead( L) 取表头取表头(可能是原子或列表可能是原子或列表);GetTail(L ) 取表尾取表尾(一定是列表一定是列表) 。广义表的抽象数据类型定义见广义表的抽象数据类型定义见教材教材P107-108P107-108451. GetTail【(b, k, p, h)】 ; 2. GetHead【( (a,b), (c,d) )】 ; 3. GetTail【( (a,b), (c,d) )】 ; 4. GetTail【 GetHead【(a,b),(c,d)】 ;例：例：求下列广义表操作的结果（求下列广义表操作的结果（严题集严题集5.10）(k, p, h)（b）(a,b)