ch5 数组和广义表

1、1第第5章章 数组和广义表（数组和广义表（Arrays & Lists）5.1 数组的定义数组的定义5.2 数组的顺序表示和实现数组的顺序表示和实现5.3 矩阵的压缩存储矩阵的压缩存储(即数组的应用即数组的应用)5.4 广义表的定义广义表的定义5.5 广义表的存储结构广义表的存储结构2线性表线性表具有相同类型的数据元素的有限序列。具有相同类型的数据元素的有限序列。限制插入、删除位置限制插入、删除位置线性表线性表具有相同类型的数据元素的有限序列。具有相同类型的数据元素的有限序列。限制元素类型为字符限制元素类型为字符栈栈仅在表尾进行插入和删除操作的线性表。仅在表尾进行插入和删除操作的线性表

2、。队列队列在一端进行插入操作，而另一端进行在一端进行插入操作，而另一端进行 删除操作的线性表。删除操作的线性表。串串零个或多个字符组成的有限序列零个或多个字符组成的有限序列 。特殊线性表特殊线性表第第5章章 数组和广义表数组和广义表 3线性表线性表具有相同类型的数据元素的有限序列。具有相同类型的数据元素的有限序列。将元素的类型进行扩充将元素的类型进行扩充广义线性表广义线性表（多维）数组（多维）数组线性表中的数据元素可以是线性表中的数据元素可以是线性表，但所有元素的类型相同。线性表，但所有元素的类型相同。广义表广义表线性表中的数据元素可以是线性表，线性表中的数据元素可以是线性表，且元素的类型可以

3、不相同。且元素的类型可以不相同。第第5章章 数组和广义表数组和广义表 45.1 数组的定义数组的定义数组是由一组数组是由一组类型相同类型相同的数据元素构成的的数据元素构成的有序有序集集合合，每个数据元素称为一个数组元素（简称为元每个数据元素称为一个数组元素（简称为元素），每个元素受素），每个元素受n(n1)个个线性关系线性关系的约束，的约束，每每个元素在个元素在n个线性关系中的序号个线性关系中的序号i1、i2、in称为称为该元素的下标，并称该数组为该元素的下标，并称该数组为 n 维数组。维数组。 数组的特点数组的特点元素本身可以具有某种结构，属于同一数据类型；元素本身可以具有某种结构，属于同一

4、数据类型；数组是一个具有固定格式和数量的数据集合。数组是一个具有固定格式和数量的数据集合。5 a11 a12 a1n a21 a22 a2n am1 am2 amnA=例如，元素例如，元素a22受两个线性关系的约束，在行上有受两个线性关系的约束，在行上有一个行前驱一个行前驱a21和一个行后继和一个行后继a23，在列上有一个列，在列上有一个列前驱前驱a12和和一个列后继和和一个列后继a32。数组示例数组示例5.1 数组的定义数组的定义6 a11 a12 a1n a21 a22 a2n am1 am2 amnA= A=(A1，A2，An) 其中：其中： Ai=(a1i，a2i，ami) (1in)

5、二维数组是数据元素为线性表的线性表。二维数组是数据元素为线性表的线性表。5.1 数组的定义数组的定义7ADT Array 数据对象数据对象： Daj1,j2, .,ji,jn| ji =0,.,bi -1, i=1,2,.,n 数据关系数据关系： RR1, R2, ., Rn Ri | 0 jk bk -1, 1 k n 且且k i, 0 ji bi -2, i=2,.,n ADT Array 基本操作基本操作:5.1 数组的定义数组的定义8二维数组的定义二维数组的定义:数据对象数据对象: : D = aij | 0ib1-1, 0 jb2-1数据关系数据关系: : R = ROW, COL

6、ROW = | 0ib1-2, 0jb2-1 COL = | 0ib1-1, 0 jb2-29基本操作基本操作：InitArray (&A, n, bound1, ., boundn)DestroyArray(&A)操作结果：操作结果：若维数若维数 n 和各维长度合法，则构造相应的和各维长度合法，则构造相应的 数组数组A，并返回，并返回OK。操作结果：操作结果：销毁数组销毁数组A。10Value(A, &e, index1, ., indexn) 初始条件：初始条件：A是是n维数组，维数组，e为元素变量，随后是为元素变量，随后是n 个个 下标值。下标值。 操作结果：操作

7、结果：若各下标不超界，则若各下标不超界，则e赋值为所指定的赋值为所指定的A 的元素值，并返回的元素值，并返回OK。Assign(&A, e, index1, ., indexn)初始条件：初始条件：A是是n维数组，维数组，e为元素变量，随后是为元素变量，随后是n 个下个下 标值。标值。操作结果：操作结果：若下标不超界，则将若下标不超界，则将e的值赋给所指定的的值赋给所指定的A的的 元素，并返回元素，并返回OK。基本操作基本操作：11数组的基本操作数组的基本操作 存取：给定一组下标，读出对应的数组元素；存取：给定一组下标，读出对应的数组元素； 修改：给定一组下标，存储或修改与其相对应的修

8、改：给定一组下标，存储或修改与其相对应的数组元素。数组元素。存取和修改操作本质上只对应一种操作存取和修改操作本质上只对应一种操作寻址寻址数组应该采用何种方式存储？数组应该采用何种方式存储？数组没有插入和删除操作，所以，不用预留空间，数组没有插入和删除操作，所以，不用预留空间，适合采用顺序存储。适合采用顺序存储。5.1 数组的定义数组的定义12类型特点类型特点:1) 只有引用型操作，没有加工型操作只有引用型操作，没有加工型操作;2) 数组是多维的结构，而存储空间是一数组是多维的结构，而存储空间是一个个 一维的结构。一维的结构。有两种顺序映象的方式有两种顺序映象的方式:1)以行序为主序以行序为主序

9、(低下标优先低下标优先);2)以列序为主序以列序为主序(高下标优先高下标优先);5.2 数组的顺序表示和实现数组的顺序表示和实现 135.2 数组的顺序表示和实现数组的顺序表示和实现一维一维设一维数组的下标的范围为闭区间设一维数组的下标的范围为闭区间l，h，每个每个数组元素占用数组元素占用 c 个存储单元，则个存储单元，则其其任一元任一元素素 ai 的的存储地址可由下式确定：存储地址可由下式确定： Loc(ai)Loc(al) (il)c c al ai-1 ai ah al+1 Loc(al)Loc(ai)14常用的映射方法有两种：常用的映射方法有两种：按按行行优先：优先：先行后列先行后列，

10、先存储行号较小的元素，先存储行号较小的元素，行号相同者先存储列号较小的元素。行号相同者先存储列号较小的元素。 按按列列优先：优先：先列后行先列后行，先存储列号较小的元素，先存储列号较小的元素，列号相同者先存储行号较小的元素。列号相同者先存储行号较小的元素。 二维数组二维数组内内 存存二维结构二维结构一维结构一维结构5.2 数组的顺序表示和实现数组的顺序表示和实现二维二维15l2h2 l1h1(a) 二维数组二维数组aij前面的元素个数前面的元素个数=阴影部分的面积阴影部分的面积=整行数每行元素个数整行数每行元素个数+本行中本行中aij前面的元素个数前面的元素个数=( (i - -l1) )(

11、(h2 - -l21) )( (j - -l2) )本行中本行中aij前面的元素个数前面的元素个数每行元素个数每行元素个数整整行行数数aij按行优先存储的寻址按行优先存储的寻址5.2 数组的顺序表示和实现数组的顺序表示和实现二维二维16第第l1行行第第l1+1行行al1l2 al1h2 a(l1+1)l2 a(l1+1)h2 aij ah1h2Loc( (aij) )Loc( (al1l2) )( (i - -l1) )( (h2 - -l21) )( (j - -l2) )个元素个元素Loc(aij)Loc(al1l2)(il1)(h2l21)(jl2)c按行优先存储的寻址按行优先存储的寻址

12、按列优先存储的寻址方法与此类似。按列优先存储的寻址方法与此类似。5.2 数组的顺序表示和实现数组的顺序表示和实现二维二维17Loc (j1, j2, jn)=LOC(0,0,0)若是若是N维数组，其中任一元素的地址该如何计算？维数组，其中任一元素的地址该如何计算？niii1jC其中其中Cn=L, Ci-1=biCi， 1in Ci = bi+1 bi+2 bn L一个元素长度一个元素长度数组基址数组基址前面若干元素占用前面若干元素占用的地址字节总数的地址字节总数第第i i维长度维长度与所存元素个数有关的系与所存元素个数有关的系数，可用递推法求出数，可用递推法求出教材已给出教材已给出低维优先低维

13、优先的地址计算公式，的地址计算公式，见见P93（5-2）式式该式称为该式称为n n维数组的映像函数维数组的映像函数： C i = b i+1 b i+2 b n L5.2 数组的顺序表示和实现数组的顺序表示和实现NN维维18“行序为主序行序为主序” 即即 “低下标优低下标优先先”“列序为主序列序为主序” 即即 “高下标优高下标优先先”如如: A324 的存储次序为的存储次序为:(0,0,0),(0,0,1),(0,0,2),(0,0,3),(0,1,0),(0,1,3),(1,0,0),(1,1,0),(1,1,3),(2,0,0),(2,1,3)(0,0,0),(1,0,0),(2,0,0)

14、,(0,1,0),(2,1,0),(0,0,1),(0,1,1),(0,0,2),(2,1,2),(0,0,3),(2,1,3)则则 A324 的存储次序为的存储次序为:19例例2：已知二维数组已知二维数组Am,m按行存储的元素地址公式是：按行存储的元素地址公式是： Loc(aij)= Loc(a11)+(i-1)*m+(j-1)*K 按列存储的公式是？按列存储的公式是？ Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*K （尽管是方阵，但公式仍不同）（尽管是方阵，但公式仍不同）例例1软考题软考题：一个二维数组一个二维数组A A，行下标的范围是，行下标的范围是1到到6， 列下标

15、的范围是列下标的范围是0到到7，每个数组元素用相邻的，每个数组元素用相邻的6个字节存个字节存储，存储器按字节编址。那么，这个数组的体积是多少储，存储器按字节编址。那么，这个数组的体积是多少个字节？个字节？ 288答：答： Volume=m*n*L=(6-1+1)*(7- 0 +1)*6=48*6=288练习：练习：20例例3：设数组设数组a160, 170的基地址为的基地址为2048，每个元，每个元素占素占2个存储单元，若以列序为主序顺序存储，则元素个存储单元，若以列序为主序顺序存储，则元素a32,58的存储地址为的存储地址为 。LOC(aij)=LOC(ac1，c2)+(j-c2)*(d1-

16、c1+1)+i-c1)*L得：得：LOC(a32,58)=2048+(58-1)*(60-1+1)+32-1)*28950答：答：请注意审题！请注意审题！ 利用列优先通式：利用列优先通式：8950练习：练习：21#define MAX_ARRAY_DIM 8 /假设最大维数为假设最大维数为8 8 typedef struct ELemType *base; /数组元素基址数组元素基址 int dim; /数组维数数组维数 int *bound; /数组数组各维长度信息保存区各维长度信息保存区基址基址 int *constants; /数组数组映像函数常量映像函数常量的基址的基址 Array;即

17、即Ci信息保存区信息保存区数组的基本操作函数说明（有数组的基本操作函数说明（有4个）个）（请阅读教材（请阅读教材P93-95）N维数组的顺序存储表示（见教材见教材P93）以销毁数组函数为例以销毁数组函数为例22 ：利用宏利用宏va_start、va_arg和和va_end提供提供遍历未知数目和类型的函数参数表的功能。遍历未知数目和类型的函数参数表的功能。Va_start ( va_list ap, x )：初始化初始化ap，使其指向所，使其指向所在函数的参数在函数的参数x x之后的第一个参数。之后的第一个参数。Va_arg ( va_list ap , 类型类型)：返回返回apap当前指向的参

18、数当前指向的参数的值，并修改的值，并修改ap，使得，使得ap指向下一个参数（指向下一个参数（“类型类型”为参数类型）。为参数类型）。Va_end ( va_list ap)：用在所有的参数处理完毕之后，用在所有的参数处理完毕之后，表示表示ap使用完毕。使用完毕。几个函数说明：几个函数说明：23Status InitArray (Array &A, int dim,) /若维数若维数dim和各维长度合法，则和各维长度合法，则并返回并返回OK if (dimMAX_ARRAY_DIM) return ERROR; A.dim=dim; A.bounds=(int *)malloc(dim

19、* sizeof(int); if(!a.bounds) exit (OVERFLOW); / 分配存放分配存放“各维长度各维长度”的空间的空间 /若各维长度合法，则存入若各维长度合法，则存入A.bounds, ,并求出并求出A的元素总数的元素总数elemtotal elemtotal=1; va_start(ap, dim); /ap为为va_list类型，是存放变长参数表信息的类型，将类型，是存放变长参数表信息的类型，将ap指指向向dim后后的第一个参数的第一个参数数组的基本操作函数说明（数组的基本操作函数说明（5个）个） （见教材见教材P93-95）24 for(i=0;idim;+i)

20、 A.boundsi=va_arg (ap, int); / 返回返回ap当前指向的参数，并按参数类型将当前指向的参数，并按参数类型将ap指向下一个参数指向下一个参数 if (A.boundsi=0;-i) A.constantsi=A.boundsi+1*A.constantsi+1; return OK; b i+1 C i+1 26数组基址指针数组基址指针各维长度保各维长度保存区指针存区指针映像函数映像函数Ci保存区指针保存区指针Status DestroyArray (Array &A) /销毁数组销毁数组A A if ( ! A.base ) return ERROR; fr

21、ee(A.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; 数组的基本操作函数数组的基本操作函数 27Status Locate(Array A, va_list ap, int &off) /若若ap指示的各下标值合法，则求出该元素在指示的各下标值合法，则求出该元素在A中相对地

22、址中相对地址off off=0; for(i=0;iA.dim;+i) ind= va_arg(ap, int); if (indA.boundsi) return OVERFLOW; off += A.constantsi * ind ; C i j i return OK; 数组的基本操作函数数组的基本操作函数 28Status Value(Array A, ElemType &e,) /A是是n n维数组，维数组，e e为元素变量，随后是为元素变量，随后是n n个下标值，若各下个下标值，若各下 标不超界，则标不超界，则e e赋值为所指定的赋值为所指定的A A的元素值，即将指定元素

23、的元素值，即将指定元素 值读到值读到e e变量中。变量中。 va_start (ap, e); / / 将将apap指向指向e e后的参数后的参数 if (result=Locate(A, ap, off)=0) return result; e=*(A.base+off); return OK; 数组的基本操作函数数组的基本操作函数 29Status Assign(Array &A,ElemType e,) /A是是n n维数组，维数组，e e为元素变量，随后是为元素变量，随后是n n个下标值，若各下个下标值，若各下 标不超界，则标不超界，则e e的值赋为所指定的的值赋为所指定的A

24、A的元素值，的元素值， va_start(ap,e); if( (result=Locate(A,ap,off ) )=0) return result; *(A.base+off)=e; return OK; 数组的基本操作函数数组的基本操作函数 30行指针向量行指针向量a11a12a1nam1am2amn 链式存储方式：链式存储方式：用带行指针向量的单链表来表示。用带行指针向量的单链表来表示。注：注：数组的运算参见下一节实例（稀疏矩阵的转置）数组的运算参见下一节实例（稀疏矩阵的转置）补充：补充： 315.3 矩阵的压缩存储一一. 特殊矩阵的压缩存储特殊矩阵的压缩存储 二二. 稀疏矩阵的压缩

25、存储稀疏矩阵的压缩存储三三. 稀疏矩阵的转置操作稀疏矩阵的转置操作 325.3 矩阵的压缩存储讨论：讨论：1. 什么是压缩存储？什么是压缩存储？若多个数据元素的若多个数据元素的值都相同值都相同，则只分配一个元素值的，则只分配一个元素值的存储空间，且零元素不占存储空间。存储空间，且零元素不占存储空间。2. 什么样的矩阵具备压缩条件？什么样的矩阵具备压缩条件？ 特殊矩阵（对称矩阵，对角矩阵，三角矩阵）特殊矩阵（对称矩阵，对角矩阵，三角矩阵）和稀疏矩阵。和稀疏矩阵。33特殊矩阵：特殊矩阵：矩阵中很多值相同的元素并且它们的分布矩阵中很多值相同的元素并且它们的分布有一定的规律。有一定的规律。稀疏矩阵稀疏

26、矩阵: :矩阵中非零元素的个数较少（一般小于矩阵中非零元素的个数较少（一般小于5%）压缩存储的基本思想是：压缩存储的基本思想是： 为多个值为多个值相同相同的元素只分配的元素只分配一个一个存储空间；存储空间； 对对零零元素元素不分配不分配存储空间。存储空间。 特殊矩阵和稀疏矩阵特殊矩阵和稀疏矩阵5.3 矩阵的压缩存储34一一. 特殊矩阵的压缩存储特殊矩阵的压缩存储对称矩对称矩阵阵 3647862842481697460582957A对称矩阵特点：对称矩阵特点：aij=aji如何压缩存储？如何压缩存储？只存储下三角部分的元素。只存储下三角部分的元素。35(a) 下三角矩阵下三角矩阵 (b) 存储说

27、明存储说明 (c) 计算方法计算方法aij在一维数组中的序号在一维数组中的序号=阴影部分的面积阴影部分的面积= i( (i+1) )/2+ j+1一维数组下标从一维数组下标从0开始开始aij在一维数组中的下标在一维数组中的下标k= i( (i+1) )/2+ j 0 in- -10 j n- -1 aij每行元素个数每行元素个数12iaij在本行中的序号在本行中的序号aij第第0行行第第1行行第第i-1行行一一. 特殊矩阵的压缩存储特殊矩阵的压缩存储对称矩对称矩阵阵 36对于对于下三角下三角中的元素中的元素aij（ij），在数组，在数组SA中的下标中的下标k与与i、j的关系为：的关系为：ki(

28、i1)/2j 。上三角上三角中的元素中的元素aij（ij），），因为因为aijaji，则访问和则访问和它对应的元素它对应的元素aji即可，即：即可，即：kj(j1)/2i 。第第1行行第第n-1行行第第0行行 a00 a10 a11 a20 a21 a22 aij a n-10 an-11 an-1n-1 第第2行行0 1 2 3 4 5 k n(n+1)/2-1一一. 特殊矩阵的压缩存储特殊矩阵的压缩存储对称矩对称矩阵阵 37一一. 特殊矩阵的压缩存储特殊矩阵的压缩存储三角矩阵三角矩阵 3 cc c c6 2c c c4 81 c c7 46 0 c8 29 5 7(a)下三角矩阵下三角矩阵

29、3 4 8 1 0c2 9 4 6cc 5 7cc c 0 8cc c c 7(b)上三角矩阵上三角矩阵如何压缩存储？如何压缩存储？只存储上三角（或下三角）部分的元素。只存储上三角（或下三角）部分的元素。38矩阵中任一元素矩阵中任一元素aij在在数组数组中的下标中的下标k与与i、j的对应关系：的对应关系：i( (i1) )/2j 当当ijn( (n1) )/2 当当ijk=下三角矩阵的压缩存储下三角矩阵的压缩存储0 1 2 3 4 5 k n(n+1)/2第第1行行第第0行行 a00 a10 a11 a20 a21 aij an-1n-1 第第2行行 c a22存储存储下三角下三角元素元素对角

30、线上方的常数对角线上方的常数只存一个只存一个一一. 特殊矩阵的压缩存储特殊矩阵的压缩存储三角矩阵三角矩阵 39矩阵中任一元素矩阵中任一元素aij在在数组数组中的下标中的下标k与与i、j的对应关系：的对应关系： i( (2ni1) )/2ji 当当ijn( (n1) ) /2 当当ijk=上三角矩阵的压缩存储上三角矩阵的压缩存储存储存储上三角上三角元素元素对角线上方的常数对角线上方的常数只存一个只存一个一一. 特殊矩阵的压缩存储特殊矩阵的压缩存储三角矩阵三角矩阵 40对角矩阵：对角矩阵：所有非零元素都集中在以主对角线为中心所有非零元素都集中在以主对角线为中心的带状区域中，除了主的带状区域中，除了

31、主对角线和它的上下方若干条对对角线和它的上下方若干条对角线的元素外，所有其他元素都为零。角线的元素外，所有其他元素都为零。 a00 a01 0 0 0a10 a11 a12 0 00 a21 a22a23 00 0 a32a33 a340 0 0 a43 a44A=一一. 特殊矩阵的压缩存储特殊矩阵的压缩存储对角矩阵对角矩阵 41a00 a01 0 0 0a10 a11 a12 0 00 a21 a22a23 00 0 a32a33 a340 0 0 a43 a44A=将带状区将带状区域立起来域立起来0 a00a01a10 a11 a12a21 a22 a23a32 a33 a34a43 a4

32、4 0B=sj- -i+1t=i映射到二维数组映射到二维数组B中，映射关系中，映射关系一一. 特殊矩阵的压缩存储特殊矩阵的压缩存储对角矩阵对角矩阵 42按行按行存储存储 元素元素aij在一维数组中的序号在一维数组中的序号=2 + 3( (i1) )+( ( ji + 2) )=2i+ j+1 一维数组下标从一维数组下标从0开始开始元素元素aij在一维数组中的下标在一维数组中的下标=2i+ j(b) 寻址的计算方法寻址的计算方法(c) 压缩到一维数组中压缩到一维数组中a00 a01 a10 a11 a12 a21 a22 a23 a32 a33 a34 a43 a440 1 2 3 4 5 6

33、7 8 9 10 11 12(a) 三对角矩阵三对角矩阵 0 0 0 0 00 00 0 0 0 0 A=a00 a01a10 a11 a12a21 a22 a23a32 a33 a34a43 a44一一. 特殊矩阵的压缩存储特殊矩阵的压缩存储对角矩阵对角矩阵 43二、稀疏矩阵的压缩存储二、稀疏矩阵的压缩存储问题：问题：如果只存储如果只存储稀疏矩阵中的非零元素，那这些元素的稀疏矩阵中的非零元素，那这些元素的位置信息位置信息该如何表示？该如何表示？解决思路：解决思路：对每个非零元素对每个非零元素增开增开若干存储单元，例如存放其所若干存储单元，例如存放其所在的行号和列号，便可准确反映该元素所在位置

34、。在的行号和列号，便可准确反映该元素所在位置。实现方法：实现方法：将每个非零元素用一个三元组将每个非零元素用一个三元组（i，j，aij）来表示，来表示，则每个则每个稀疏矩阵可用一个稀疏矩阵可用一个三元组表三元组表来表示。来表示。44将稀疏矩阵中的每个非零元素表示为将稀疏矩阵中的每个非零元素表示为：( (行号，列号，非零元素值行号，列号，非零元素值) )三元组三元组定义三元组：定义三元组：二、稀疏矩阵的压缩存储二、稀疏矩阵的压缩存储#define MAXSIZE 125000 /设非零元素最大个数设非零元素最大个数125000 typedef struct int i; /元素行号元素行号 in

35、t j; /元素列号元素列号 ElemType e; /元素值元素值 Triple;/一个结点的结构定义一个结点的结构定义45三元组表三元组表：将稀疏矩阵的非零元素对应的三元组所将稀疏矩阵的非零元素对应的三元组所构成的集合，构成的集合，按行优先的顺序排列成一个线性表。按行优先的顺序排列成一个线性表。三元组表三元组表( (0,0,15), (1,1,11), (2,3,6), (4,0,9) )15 0 0 0 0 0 0 11 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 9 0 0 0 0 0A=如何存储三元组表？如何存储三元组表？二、稀疏矩阵的压缩存储二、稀疏矩阵的压缩存

36、储46稀疏矩阵的压缩存储稀疏矩阵的压缩存储三元组顺序表三元组顺序表二、稀疏矩阵的压缩存储二、稀疏矩阵的压缩存储typedef struct Triple dataMAXSIZE+1; /三元组表，以行为主序存入一维向量三元组表，以行为主序存入一维向量 data 中中 int mu; /矩阵总行数矩阵总行数 int nu; /矩阵总列数矩阵总列数 int tu; /矩阵中非零元素总个数矩阵中非零元素总个数 TsMatrix; /整个三元组表的定义整个三元组表的定义47采用采用链接链接存储结构存储三元组表，每个非零元素对应存储结构存储三元组表，每个非零元素对应的三元组存储为一个链表结点，结构为：的

37、三元组存储为一个链表结点，结构为： rowcolitemdownrightrow：存储非零元素的行号存储非零元素的行号col：存储非零元素的列号存储非零元素的列号item：存储非零元素的值存储非零元素的值right：指针域，指向同一行中的下一个三元组指针域，指向同一行中的下一个三元组down：指针域，指向同一列中的下一个三元组指针域，指向同一列中的下一个三元组稀疏矩阵的压缩存储稀疏矩阵的压缩存储十字链表十字链表二、稀疏矩阵的压缩存储二、稀疏矩阵的压缩存储480 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

38、 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 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目的：目的：三、稀疏矩阵的转置操作三、稀疏矩阵的转置操作

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

40、矩阵，只要把每个元素的元素的行下标和列下标互换行下标和列下标互换，就完成了对该矩阵的转置运，就完成了对该矩阵的转置运算，这种说法正确吗？算，这种说法正确吗？ 有两种实现方法有两种实现方法压缩转置压缩转置( (压缩压缩) )快速转置快速转置提问：提问：50算法算法 压缩转置压缩转置基本思想：基本思想：直接取，顺序存直接取，顺序存。即。即在在A的三元组顺序的三元组顺序表中表中依次依次找第找第0列、第列、第1列、列、直到最后一列的三元直到最后一列的三元组，并将找到的每个三元组的行、列交换后组，并将找到的每个三元组的行、列交换后顺序顺序存存储到储到B的三元组顺序表中。的三元组顺序表中。 三、稀疏矩阵的

41、转置操作三、稀疏矩阵的转置操作51方法方法1 1：压缩转置压缩转置思路：思路：反复扫描反复扫描a.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 q1234 p1234521.

42、 设置转置后矩阵设置转置后矩阵B的行数、列数和非零元个数；的行数、列数和非零元个数；2. 在在B中设置初始存储位置中设置初始存储位置pb；3. for (col=最小列号最小列号; col=最大列号最大列号; col+) 3.1 在在A中查找列号为中查找列号为col的三元组；的三元组； 3.2 交换其行号和列号，存入交换其行号和列号，存入B中中pb位置；位置； 3.3 pb+；算法算法 压缩转置压缩转置伪代码伪代码三、稀疏矩阵的转置操作三、稀疏矩阵的转置操作53Status TransPoseSMatrix ( TSMatrix M, TSMatrix &T)T.mu=M.nu; T.

43、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）/用三元组表存放稀疏矩阵用三元组表存放稀疏矩阵M M，求，求M的转置矩阵的转置矩阵T/q是转置矩阵是转置矩阵T T的结点编号的结点编

44、号/col是扫描是扫描M三元表列序的变量三元表列序的变量/p是是M三元表中结点编号三元表中结点编号541、主要时间消耗主要时间消耗在查找在查找M.datap.j=col的元素的元素，由两重循环，由两重循环完成完成: : for(col=1; col=M.nu; col+) 循环次数循环次数nu for(p=1; p=M.tu; p+) 循环次数循环次数tu所以该算法的时间复杂度为所以该算法的时间复杂度为O(O(nu*tu) ) - -即即M的列数与的列数与M中非零元素的个数中非零元素的个数之积之积最恶劣情况：最恶劣情况：M M中全是非零元素，此时中全是非零元素，此时tu=mu*nu， 时间复杂

45、度为时间复杂度为 O(O(nu2*mu ) )注：注：若若M M中基本上是非零元素时，即使用非压缩传统转置算法中基本上是非零元素时，即使用非压缩传统转置算法的时间复杂度也不过是的时间复杂度也不过是O(O(nu*mu) ) （程序见（程序见教材教材P99P99）结论：结论：压缩转置算法不能滥用。压缩转置算法不能滥用。前提：前提：仅适用于非零元素个数很少（即仅适用于非零元素个数很少（即tumu*nu）的情况。）的情况。压缩转置算法的效率分析压缩转置算法的效率分析：55分析：分析：A中第中第0列的第一个非零元素一定存储在列的第一个非零元素一定存储在B中下中下标为标为0的位置上，该列中其它非零元素应存

46、放在的位置上，该列中其它非零元素应存放在B中中后面连续的位置上，那么第后面连续的位置上，那么第1列的第一个非零元素在列的第一个非零元素在B中的位置便等于第中的位置便等于第0列的第一个非零元素在列的第一个非零元素在B中的位中的位置加上第置加上第0列的非零元素的个数，以此类推。列的非零元素的个数，以此类推。 基本思想：基本思想：顺序取，直接存。顺序取，直接存。即即在在A中依次取三元中依次取三元组，交换其行号和列号放到组，交换其行号和列号放到B 中中适当适当位置。位置。算法算法 快速转置快速转置如何确定当前从如何确定当前从A中取出的三元组在中取出的三元组在B中的位置？中的位置？三、稀疏矩阵的转置操作

47、三、稀疏矩阵的转置操作56方法方法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.data中的元素直接送入中的元素直接送入b.data的恰当位置的恰当位置上（上（即即M M三元组的三元组的p p指针不回溯指针不回溯）。）。关

48、键：关键：怎样寻找怎样寻找b.data的的“恰当恰当”位置？位置？ p1234 q 3 557引入两个数组作为辅助数据结构：引入两个数组作为辅助数据结构：numnu：存储矩阵存储矩阵A中某列的非零元素的个数；中某列的非零元素的个数；cpotnu：初值表示矩阵初值表示矩阵A中某列的第一个非零元素中某列的第一个非零元素在在B中的位置。中的位置。 数据结构设计：数据结构设计：cpot0=0；cpotcol=cpotcol- -1+numcol- -1； 1colnunum与与cpot存在如下递推关系：存在如下递推关系：算法算法 快速转置快速转置三、稀疏矩阵的转置操作三、稀疏矩阵的转置操作58如果能如

49、果能预知预知M矩阵矩阵每一列每一列( (即即T的每一行的每一行) )的的非零元素个数非零元素个数，又，又能预知能预知第一个非零元素第一个非零元素在在b.datab.data中的中的位置位置, ,则扫描则扫描a.data时便时便可以将每个元素准确定位（可以将每个元素准确定位（因为已知若干参考点因为已知若干参考点）。）。技巧：技巧：利用利用带辅助向量带辅助向量的三元组表，它正好携带每行（或列）的三元组表，它正好携带每行（或列）的非零元素个数的非零元素个数 NUM(i)以及每行（或列）的第一个非以及每行（或列）的第一个非零元素在三元组表中的位置零元素在三元组表中的位置POS(i) 等信息。等信息。设

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

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

52、 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 6601. 设置转置后矩阵设置转置后矩阵B的行数、列数和非零元素的个数；的行数、列数和非零元素的个数；2. 计算计算A中每一列的非零元素个数；中每一列的非零元素个数；3. 计算计算A中每一列的第一个非零元素在中每一列的第一个非零元素在B中的下标；中的下标；4. 依次取依次取A中的每一个非零元素对应的三元组；中的每一个非零元素对应的三元组； 4.1 确定该元素在确定该元素在B中的下标中的下标pb； 4.2 将该元素的行号列号交换后存入将该元素的行号列号交换后存入B

53、中中pb的位置；的位置； 4.3 预置该元素所在列的下一个元素的存放位置；预置该元素所在列的下一个元素的存放位置；算法算法 快速转置快速转置伪代码伪代码三、稀疏矩阵的转置操作三、稀疏矩阵的转置操作61Status 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 ; +nu

54、m col ; cpos 1 =1; for(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

55、的转置矩阵的转置矩阵T/初始化初始化M中各列元素个数为中各列元素个数为0/再生成每列首元位置辅助向量表再生成每列首元位置辅助向量表/p指向指向a.data，循环次数为非，循环次数为非0元素总个数元素总个数tu/查辅助向量表得查辅助向量表得q，即，即T中位置中位置/重要语句！重要语句！修改向量表中列坐标值，供修改向量表中列坐标值，供同同一列一列下一非零元素定位之用！下一非零元素定位之用！621. 与常规算法相比，附加了生成辅助向量表的工作。增开了与常规算法相比，附加了生成辅助向量表的工作。增开了2个长度为列长的数组个长度为列长的数组( (num 和和cpos ）。 传统转置：传统转置：O( mu

56、*nu) 压缩转置：压缩转置：O ( mu*tu) 压缩快速转置：压缩快速转置：O( nu+tu)牺牲空间效率换时间效率牺牲空间效率换时间效率。快速转置算法的效率分析快速转置算法的效率分析：2. 从时间上，此算法用了从时间上，此算法用了4个并列的单循环个并列的单循环，而且其中前，而且其中前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+) 循环次

57、数循环次数nu;nu; for( p =1; p =M.tu ; p + ) 循环次数循环次数tu;tu; 该算法的时间复杂度该算法的时间复杂度(nu*2)+(tu*2)=O (nu+tu）讨论：讨论：最恶劣情况是最恶劣情况是tu=nu*mu( (即矩阵中全部是非零元素），即矩阵中全部是非零元素），而此时的时间复杂度也只是而此时的时间复杂度也只是O(mu*nu)，并未超过传统转置算法，并未超过传统转置算法的时间复杂度。的时间复杂度。小结：小结：稀疏矩阵相乘的算法见教材稀疏矩阵相乘的算法见教材P101-103635.4 广义表的定义广义表的定义广义表是线性表的推广，也称为列表（广义表是线性表的推广，也称为列表（lists）记为：记为： LS = ( a1 , a2 , ， an ) 广义表名广义表名1. 定义：定义： 第一个元素是表头，而其余元素第一个元素是表头，而其余元素组成的表组成的表称为表尾；称为表尾； 用用小写小写字母表示字母表示原子类型原子类型，用，用大写大写字母表示字母表示列表列表。n是表长是表长在广义表中约定：在广义表中约定：讨论：讨论：广义表与线性表的区别和联系？广义表与线性表的区别和联系？ 广义表中元素广义表中元素既可以既可以是原子类型，是原子类型，也可以也可以是列表；是列表；当每个元素都为原子且类型相同时，就是线性表。当每个元素都为原子