第5章数组和广义表ppt课件

1、第第5章章 数组和广义表数组和广义表 元素的值并非原子类型，可以再分解，表中元素的值并非原子类型，可以再分解，表中 元素也是一个线性表即线性表的推行。元素也是一个线性表即线性表的推行。数组和广义表的特点：特殊的线性表数组和广义表的特点：特殊的线性表5.1 数组的定义数组的定义5.2 数组的顺序表示和实现数组的顺序表示和实现5.3 矩阵的紧缩存储矩阵的紧缩存储5.4 广义表的定义广义表的定义5.5 广义表的存储构造广义表的存储构造第第5章章 数组和广义表数组和广义表5.1 数组的定义 数组：数组： 由一组名字一样、下标不同的同类型的元素由一组名字一样、下标不同的同类型的元素 组成组成 数组特点数

2、组特点 数组构造固定数组构造固定,下标普通具有固定的上界和下界下标普通具有固定的上界和下界 数据元素具有一致的类型数据元素具有一致的类型 数组运算数组运算 给定一组下标，取相应的数据元素给定一组下标，取相应的数据元素. 给定一组下标，修正数据元素的值给定一组下标，修正数据元素的值.数组的处置比其它复杂的构造要简单数组的处置比其它复杂的构造要简单与高级言语中数组的区别：与高级言语中数组的区别： 1、本章所讨论的数组是一种数据构造，而高级言、本章所讨论的数组是一种数据构造，而高级言语语 中数组是一种数据类型。中数组是一种数据类型。2、高级言语中的数组是顺序构造；而本章的数组、高级言语中的数组是顺序

3、构造；而本章的数组 既可以是顺序的，也可以是链式构造，用户可根既可以是顺序的，也可以是链式构造，用户可根 据需求选择。据需求选择。1m10mnAAAA二维数组的特点：二维数组的特点：一维数组的特点：一维数组的特点： 1个下标，个下标，ai是是ai+1的直接前驱的直接前驱2 2个下标，每个元素个下标，每个元素aijaij遭到两个关系遭到两个关系行关系和列关系的约束：行关系和列关系的约束：一个一个m mn n的二维数组可以的二维数组可以看成是由看成是由m m行的一维数组组行的一维数组组成或由成或由n n列的一维数组组成。列的一维数组组成。A0A1.Am-1Ai=(ai0, ai1, , ai,n-

4、1) i=0,1,2,m-11n1,m1,1m1,0m1n1,11101n0,0100mnaaaaaaaaaA)aa(a)aa(a)aa(aA1n1,m1,1m1,0m1n1,11101n0,0100mn5.1 数组的定义 1n1,m1n1,1n0,1,1m11011,0m1000mnaaaaaaaaaA B0 B1 Bn-11n10mnBBBA二维数组是一个数据元素为线性表的线性表二维数组是一个数据元素为线性表的线性表j1,m1j0jjaaaBj=0,1,n-1qaij(1i m-2，1 j n-2)有两个前驱结点有两个前驱结点ai,j-1和和ai-1,j q 两个后继结点两个后继结点ai,

5、j+1和和 ai+1,jqa00没有前驱结点没有前驱结点,称之为开场结点称之为开场结点. qam-1,n-1没有后继结点没有后继结点,称之为终端结点称之为终端结点.q第第0行的元素行的元素a0j(j=1,n-1)q第第0列的元素列的元素ai0(i=1,m-1)只需一个前驱只需一个前驱只需一个后继只需一个后继我们可以把二维数组中的元素我们可以把二维数组中的元素aij看成是属于两个线性表看成是属于两个线性表:即第即第i行的线性表行的线性表Ai和第和第j列的线性表列的线性表Bjq第第m-1行的元素行的元素am-1,j(j=1,n-2)q第第n-1列的元素列的元素ai,n-1(i=1,m-2)同理，三

6、维数组同理，三维数组Amn l中每个元素属于三个线性表，每个元中每个元素属于三个线性表，每个元素素最多有三个前驱和三个后继。最多有三个前驱和三个后继。ai1,i2,i3 前驱：前驱： ai1-1,i2,i3 ，ai1,i2-1,i3， ai1,i2,i3-1 后继：后继： ai1+1,i2,i3 ， ai1,i2+1,i3， ai1,i2,i3+1推而广之推而广之 ，一个，一个n维数组可以看成是由假设干个维数组可以看成是由假设干个n1维数组组成维数组组成的线性表，在的线性表，在n维数组维数组Ab1 b2 bn中中, 每个元素每个元素ai1,i2,in(0 ij bi-1,j=1,2,n)属于属

7、于n个线性表个线性表, 每个元素最多有每个元素最多有n个前驱和个前驱和n个后继。个后继。ai1,i2,in 前驱：前驱：ai1-1,i2,in， ai1,i2-1,in，,，ai1,i2,in-1 后继：后继：ai1+1,i2,in， ai1,i2+1,in，ai1,i2,in+1数据对象数据对象: : D = aij | aij D = aij | aij ElemSet ElemSet ，0ib1-1, 0ib1-1, 0 jb2-10 jb2-1数据关系数据关系: : R = ROW, COL R = ROW, COL ROW = | 0ib1-1, ROW = | 0ib1-1, 0j

8、b2-20jb2-2 COL = | 0ib1-2, COL = | 0ib1-2, 0jb2-10jb2-1二维数组的二维数组的 定义定义:2b1bA InitArray(&A, n, bound1, ., boundn) 操作结果：假设维数操作结果：假设维数 n 和各维长度合法，那么构造和各维长度合法，那么构造相应相应 的数组的数组A，并前往，并前往OK。根本操作：根本操作： DestroyArray(&A) 操作结果：销毁数组操作结果：销毁数组A。Value(A, &e, index1, ., indexn)/取数组元素取数组元素 初始条件：初始条件：A是是n维数

9、组，维数组，e为元素变量，随后是为元素变量，随后是n 个下标值。个下标值。 操作结果：假设各下标不超界，那么操作结果：假设各下标不超界，那么e赋值为所指赋值为所指定的定的 A 的元素值，并前往的元素值，并前往OK。根本操作：根本操作：Assign(&A, e, index1, ., indexn)/修正数组元素修正数组元素 初始条件：初始条件：A是是n维数组，维数组，e为元素变量，随后是为元素变量，随后是 n 个下标值。个下标值。 操作结果：假设下标不超界，那么将操作结果：假设下标不超界，那么将e的值赋给的值赋给所指所指 定的定的A的元素，并前往的元素，并前往OK。5.2 数组的顺序存

10、储表示和实现问题：计算机的存储构造普通是一维的，而问题：计算机的存储构造普通是一维的，而n n维数组维数组(n2)(n2)普通是多维的，怎样存放？普通是多维的，怎样存放？处理方法：事先商定按某种次序将数组元素排成一序处理方法：事先商定按某种次序将数组元素排成一序 列，然后将这个线性序列存入存储器中。列，然后将这个线性序列存入存储器中。例如：在二维数组中，我们既可以规定按行存储，也例如：在二维数组中，我们既可以规定按行存储，也可以规定按列存储。可以规定按列存储。假设规定好了次序，那么数组中恣意一个元素的存放地址便假设规定好了次序，那么数组中恣意一个元素的存放地址便有有规律可寻，可构成地址计算公式

11、；规律可寻，可构成地址计算公式；商定的次序不同，那么计算元素地址的公式也有所不同；商定的次序不同，那么计算元素地址的公式也有所不同；C C和和PASCALPASCAL中普通采用行优先顺序；中普通采用行优先顺序；FORTRANFORTRAN采用列优先。采用列优先。 按行序为主序存放按行序为主序存放 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,

12、n-1 . am-1,1 . a11 a01 am-1,0 . a10 a00 a00 a01 . a0n-1 a10 a11 . a1n-1 am-10 am-11 . am-1n-1 . 按列序为主序存放按列序为主序存放01m*n-1m-1m计算二维数组元素地址的通式计算二维数组元素地址的通式二维数组列优先存储的通式为：二维数组列优先存储的通式为：LOC(aij)=LOC(a00)+(b1LOC(aij)=LOC(a00)+(b1* *j+i)j+i)* *L L那么行优先存储时的地址公式为：那么行优先存储时的地址公式为：LOC(aij)=LOC(a00)+(b2LOC(aij)=LOC(

13、a00)+(b2* *i+j)i+j)* *L L设普通的二维数组是设普通的二维数组是A0.b1-1, 0.b2-1A0.b1-1, 0.b2-11b21,b11,0b11b2i,iji01b20,00mna.a.a.a.a.a.aA计算三维数组元素地址的通式计算三维数组元素地址的通式设普通的三维数组是设普通的三维数组是A0.b1-1, 0.b2-1A0.b1-1, 0.b2-1，0.b3-10.b3-1按按“行优先顺序行优先顺序存储，其任一元素存储，其任一元素AijkAijk地地址计算函数为：址计算函数为：LOC(aijk)=LOC(a000)+(iLOC(aijk)=LOC(a000)+(

14、i* *b2b2* *b3+jb3+j* *b3+k)b3+k)* *L L假设是假设是N N维数组，其中任一元素的地址该如何计算？维数组，其中任一元素的地址该如何计算？LjbjaLOCLjjbjbbbjbbbaLOCaLOCniniknkinnnnnnjjj1110.0012431320.00,.,21)()().()()(开场结点的存放地址即基地址开场结点的存放地址即基地址维数和每维的上、下界；维数和每维的上、下界；每个数组元素所占用的单元数每个数组元素所占用的单元数其中其中Cn=L, Ci-1=biCi， 1in递归递归Loc(j1,j2,jn)=LOC(0,0,0)niii1jC5.3

15、 矩阵的紧缩存储 在科学与工程计算问题中，矩阵是一种常用在科学与工程计算问题中，矩阵是一种常用的数学对象，在高级言语编制程序时，将一个矩的数学对象，在高级言语编制程序时，将一个矩阵描画为一个二维数组。矩阵在这种存储表示之阵描画为一个二维数组。矩阵在这种存储表示之下，可以对其元素进展随机存取，各种矩阵运算下，可以对其元素进展随机存取，各种矩阵运算也非常简单。也非常简单。 但是在矩阵中非零元素呈某种规律分布或者但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，占用了许多矩阵中出现大量的零元素的情况下，占用了许多单元去存储反复的非零元素或零元素，这对高阶单元去存储反复的非零元素或

16、零元素，这对高阶矩阵会呵斥极大的浪费，为了节省存储空间，矩阵会呵斥极大的浪费，为了节省存储空间， 我们可以对这类矩阵进展紧缩存储：即为多个一我们可以对这类矩阵进展紧缩存储：即为多个一样的非零元素只分配一个存储空间；对零元素不样的非零元素只分配一个存储空间；对零元素不分配空间。分配空间。并非一切的矩阵都可以紧缩并非一切的矩阵都可以紧缩对称矩阵对称矩阵三角矩阵三角矩阵稀疏矩阵稀疏矩阵5.3.1 5.3.1 特殊矩阵特殊矩阵在一个在一个n n阶方阵阶方阵A A中，假设元素满足下述性质：中，假设元素满足下述性质： aij=aji 0i,jn-1 aij=aji 0i,jn-1 1 5 1 3 7 a0

17、0 5 0 8 0 0 a10 a 11 1 8 9 2 6 a20 a21 a22 3 0 2 5 1 . 7 0 6 1 3 an-1 0 an-1 1 an-1 2 an-1 n-1 对称矩阵对称矩阵1 1、对称矩阵、对称矩阵sak按行序为主序：按行序为主序：a00a10a11a20a21a22an-1,0an-1,n-1012345n(n-1)n(n+1)/2-11对称矩阵的存储方式对称矩阵的存储方式在对称矩阵中，第在对称矩阵中，第i i行恰有行恰有i+1i+1个元素，元素总数为：个元素，元素总数为： 可以将这些元素存放在一个向量可以将这些元素存放在一个向量 中中1 1、对称矩阵、对称

18、矩阵1n0i21)n(n1)(i 12/ ) 1(.0nnsa2为了便于访问对称矩阵为了便于访问对称矩阵A中的元素，我们必需在中的元素，我们必需在aij和和sak之间找一个对应关系。之间找一个对应关系。假设假设ij，那么，那么aij在下三角形中。在下三角形中。aij之前的之前的i行从第行从第0行行到第到第i-1行一共有行一共有1+2+i=i*(i+1)/2个元素，在第个元素，在第i行行上，上，aij之前恰有之前恰有j个元素即个元素即ai0,ai1,ai2,aij-1，因，因此有：此有： k=i*(i+1)/2+j 0kn(n+1)/2-1 假设假设ij，那么，那么aij是在上三角矩阵中。由于是

19、在上三角矩阵中。由于aij=aji，所以，所以只需交换上述对应关系式中的只需交换上述对应关系式中的i和和j即可得到：即可得到： k=j*(j+1)/2+i 0kn(n+1)/2-1 1 1、对称矩阵、对称矩阵 2、三角矩阵、三角矩阵以主对角线划分，三角矩阵有上三角和下三角两种。以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵中主对角线以下的元素均为常数上三角矩阵中主对角线以下的元素均为常数(a) 。下三角矩阵正好相反，主对角线以上的元素均为常数下三角矩阵正好相反，主对角线以上的元素均为常数(b)。 a00 a01 . a0,n-1 c a11 . a1,n-1 c c c am-1,n

20、-1 (a) 上三角矩阵上三角矩阵 a00 c . c a10 a11 c.c am-10 am-11 am-1,n-1 (b) 下三角矩阵下三角矩阵可以用向量可以用向量sa0.n(n+1)/2sa0.n(n+1)/2存储，将常量存入存储，将常量存入第一或最后一个单元第一或最后一个单元 5.3.2 5.3.2 稀疏矩阵稀疏矩阵1 1、什么是稀疏矩阵？、什么是稀疏矩阵？设矩阵设矩阵A A中有中有s s个非零元素，假设个非零元素，假设s s远远小于矩阵远远小于矩阵元素的总数即元素的总数即smsmn),n),那么称那么称A A为稀疏矩阵为稀疏矩阵。有有s s个非零元素。令个非零元素。令e=s/(me

21、=s/(mn)n)，称，称e e为矩阵的稀为矩阵的稀疏因子。通常以为疏因子。通常以为e0.05e0.05时为稀疏矩阵。时为稀疏矩阵。稀疏矩阵的紧缩存储方法稀疏矩阵的紧缩存储方法一、三元组顺序表一、三元组顺序表二、行逻辑联接的顺序表二、行逻辑联接的顺序表三、三、 十字链表十字链表存储稀疏矩阵时，为了节省存储单元，运用紧缩存储稀疏矩阵时，为了节省存储单元，运用紧缩 存储方法。存储方法。非零元素的分布普通是没有规律的，因此在存储非零元素的分布普通是没有规律的，因此在存储 非零元素的同时，还必需同时记下它所在的行和非零元素的同时，还必需同时记下它所在的行和 列的位置列的位置i,j)i,j)。一个三元组

22、一个三元组(i,j,aij)(i,j,aij)独一确定了矩阵独一确定了矩阵A A的一个非零的一个非零 元。因此，稀疏矩阵可由表示非零元的三元组及元。因此，稀疏矩阵可由表示非零元的三元组及 其行列数独一确定。其行列数独一确定。一、三元组顺序表一、三元组顺序表例如，以下稀疏矩阵例如，以下稀疏矩阵 5.3.2 5.3.2 稀疏矩阵稀疏矩阵可由三元组表可由三元组表(1,2,12),(1,3,9),(1,2,12),(1,3,9),(3,1,-3),3,1,-3),(3,6,14),(4,3,24),(3,6,14),(4,3,24),(5,2,18),5,2,18),(6,1,15),(6,4,-7)

23、(6,1,15),(6,4,-7)和矩阵和矩阵维数维数6,76,7独一确定独一确定 7600070015000001800000240001400003000000000009120M=123456 1 2 3 4 5 6 7 一、三元组顺序表一、三元组顺序表 #define MAXSIZE 12500 typedef struct int i, j; /该非零元的行下标和列下标该非零元的行下标和列下标 ElemType e; / 该非零元的值该非零元的值 Triple; / 三元组类型三元组类型typedef struct Triple dataMAXSIZE+1; int mu, nu,

24、tu; (mu行数行数,nu列数列数,tu非零元个数非零元个数) TSMatrix; / 稀疏矩阵类型稀疏矩阵类型三元组表表示法：三元组表表示法：121213931-3351443245218611564-7留意：三元组表中的留意：三元组表中的元素按行或列陈元素按行或列陈列。列。668ije稀疏矩阵紧缩存储的缺陷：将失去随机存取功能稀疏矩阵紧缩存储的缺陷：将失去随机存取功能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求转置矩阵算法求转置矩阵算法028003600070500140M00528

25、0000007143600T用常规的二维数组表示时的算法用常规的二维数组表示时的算法 其时间复杂度为其时间复杂度为: O(munu) for (c=1; c=nu; +c) for (r=1; r=mu; +r) Tcr = Mrc;三元组表示的转置(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)三三元元组组表表M.data三三

26、元元组组表表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=?不正确！不正确！1 1每个元素的行下标和列下标互换即三元组中的每个元素的行下标和列下标互换即三元组中的i i和和j j 互换；互换；2 2T T的总行数的总行数mumu和总列数和总列数nunu与与M M值不同互换；值不同互换；3 3重排三元组内元素顺序，使转置后

27、的三元组也按行重排三元组内元素顺序，使转置后的三元组也按行 或列为主序有规律的陈列。或列为主序有规律的陈列。上述上述1 1和和2 2容易实现，难点在容易实现，难点在3 3。提问：假设采用三元组紧缩技术存储稀疏矩阵，只需把每提问：假设采用三元组紧缩技术存储稀疏矩阵，只需把每个元素的行下标和列下标互换，就完成了对该矩阵的转置个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种说法正确吗？运算，这种说法正确吗？ 有两种实现方法有两种实现方法紧缩转置紧缩转置( (紧缩紧缩) )快速转置快速转置方法方法1 1：紧缩转置：紧缩转置思绪：反复扫描思绪：反复扫描M.dataM.data中的列序，从小到

28、大依次进展转置。中的列序，从小到大依次进展转置。6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j e0 1 2 3 4 5 6 7 8M7 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 8Tqppppppppqqqqppppppppcol=1col=2qqqStatus TransPoseSMatrix(TSMatrix M, TSMatrix &T)/用三元组表存放稀疏矩阵用三元组表存放稀疏矩

29、阵M，求，求M的转置矩阵的转置矩阵TT.mu=M.nu; T.nu=M.mu; T.tu=M.tu; /nu是列数是列数,mu是行数是行数,tu是非零元素个数是非零元素个数if (T.tu) q=1; /q是转置矩阵是转置矩阵T的结点编号的结点编号 for(col=1; col=M.nu; col+) for(p=1; p=M.tu; p+) /p是是M三元表中结点编号三元表中结点编号 if (M.datap.j=col) T.dataq.i=M.datap.j; T.dataq.j=M.datap.i; T.dataq.e=M.datap.e; q+; return OK; /Tranpos

30、eSMatrix紧缩转置算法描画：紧缩转置算法描画：1 1、主要时间耗费在查找、主要时间耗费在查找M.datap.j=colM.datap.j=col的元素，由两重循的元素，由两重循环完成环完成: for(col=1; col=M.nu; col+) : for(col=1; col=M.nu; col+) 循环次数循环次数nunu for(p=1; p=M.tu; p+) for(p=1; p=M.tu; p+) 循环次数循环次数tutu所以该算法的时间复杂度为所以该算法的时间复杂度为O(nuO(nu* *tu)tu) - -即即M M的列数与的列数与M M中非零元素的个数之积中非零元素的个

31、数之积最坏情况：最坏情况：M M中全是非零元素，此时中全是非零元素，此时tu=mutu=mu* *nunu， 时间复杂度为时间复杂度为 O(nu2 O(nu2* *mu )mu )注：假设注：假设M M中根本上是非零元素时，即使用非紧缩传统转置算中根本上是非零元素时，即使用非紧缩传统转置算法的时间复杂度也不过是法的时间复杂度也不过是O(nuO(nu* *mu)mu)结论：紧缩转置算法不能滥用。结论：紧缩转置算法不能滥用。前提：仅适用于非零元素个数很少即前提：仅适用于非零元素个数很少即tumutumu* *nunu的情况。的情况。紧缩转置算法的效率分析紧缩转置算法的效率分析方法方法2 2 快速转

32、置快速转置三三元元组组表表M.data三三元元组组表表T.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)思绪：依次把思绪：依次把M.dataM.data中的元素直接送入中的元素直接送入T.dataT.data的恰当位的恰当位置上即置上即M M三元组的三元组的p p指针不回溯。指针不回溯。关键：怎样寻觅关键：怎样寻觅T.

33、dataT.data的的“恰当恰当位置？位置？ p1234 q 3 5假设能预知假设能预知M M矩阵中每一列矩阵中每一列( (即即T T的每一行的每一行) )的非零元素的非零元素个数，又能预知每一列第一个非零元素在个数，又能预知每一列第一个非零元素在T.dataT.data中的中的位置位置, ,那么扫描那么扫描M.dataM.data时便可以将每个元素准确定位。时便可以将每个元素准确定位。设计思绪：设计思绪：留意：根据留意：根据M.dataM.data的特征，每列第一个非零元的特征，每列第一个非零元素必素必 定先被扫描到。定先被扫描到。令：令：M中的列变量用中的列变量用col表示；表示； nu

34、m col ：存放：存放M中第中第col 列中非列中非0元素个数，元素个数， cpot col ：存放：存放M中第中第col列的第一个非列的第一个非0元素的位置，元素的位置， 即即T.data中待计算的中待计算的“恰当恰当位置所需参考点位置所需参考点col123456numcol222110cpotcol1规律规律: cpot(1)1 cpotcol 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 col 1 2 3 4 5 6 5 9 8 7

35、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 pppppppp4629753col123456numcol222110cpotcol135789i j v0 1 2 3 4 5 6 7 8TStatus FastTransposeSMatrixTSMatirx M, TSMatirx &T T.mu = M.nu ;T.nu = M.mu ; T

36、.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 ; cpot 1 =1; for(col = 2; col =M.nu; col+) cpotcol=cpotcol-1+numcol-1 ; for( p =1; p =M.tu ; p + ) col =M.data p . j ; q =cpot col ; T.dataq.i = M.datap. j; T.dataq.j = M.datap. i; T

37、.dataq. e = M.datap.e; + + cpotcol ; /for /if return OK; /FastTranposeSMatrix;快速转置算法描画：快速转置算法描画：/M/M用顺序存储表示，求用顺序存储表示，求M M的转置矩阵的转置矩阵T T/先统计每列非零元素个数先统计每列非零元素个数/再生成每列首元位置辅助向量表再生成每列首元位置辅助向量表/p/p指向指向a.dataa.data，循环次数为非，循环次数为非0 0元素总个数元素总个数tutu/查辅助向量表得查辅助向量表得q q，即，即T T中位置中位置/修正向量表中列坐标值，供同一列下一修正向量表中列坐标值，供同一

38、列下一非零元素定位之用！非零元素定位之用！1. 1. 与常规算法相比，添加了与常规算法相比，添加了2 2个长度为列长的辅助数个长度为列长的辅助数组组(num (num 和和cpot cpot 。快速转置算法的效率分析：快速转置算法的效率分析：2. 2. 从时间上，此算法用了从时间上，此算法用了4 4个并列的单循环，而且其个并列的单循环，而且其中前中前3 3个单循环都是用来产生辅助数组的。个单循环都是用来产生辅助数组的。 for(col = 1; col =M.nu; col+) for(col = 1; col =M.nu; col+) 循环次循环次数数nu; nu; for( i = 1;

39、i =M.tu; i +) for( i = 1; i =M.tu; i +) 循环次数循环次数tu; tu; for(col = 2; col =M.nu; col+) for(col = 2; col =M.nu; col+) 循环次循环次数数nu;nu; for( p=1; p =M.tu ; p + ) for( p=1; p =M.tu ; p + ) 循循环次数环次数tu; tu; 该算法的时间复杂度该算法的时间复杂度(nu(nu* *2)+(tu2)+(tu* *2)=O(nu+tu2)=O(nu+tu 传统转置：传统转置：O(muO(mu* *nu) nu) 紧缩转置：紧缩转置

40、：O(muO(mu* *tu) tu) 紧缩快速转置：紧缩快速转置：O(nu+tu)O(nu+tu)牺牲空间效率换时牺牲空间效率换时 间效率。间效率。小结：小结：讨论：最坏情况是讨论：最坏情况是tu=nutu=nu* *mu(mu(即矩阵中全部是非零元即矩阵中全部是非零元素，而此时的时间复杂度也只是素，而此时的时间复杂度也只是O(muO(mu* *nu)nu)，并未超，并未超越传统转置算法的时间复杂度。越传统转置算法的时间复杂度。 三元组顺序表又称有序的双下标法，它的特点三元组顺序表又称有序的双下标法，它的特点是，非零元在表中按行序有序存储，因此便于进展是，非零元在表中按行序有序存储，因此便于

41、进展依行顺序处置的矩阵运算。然而，假设需随机存取依行顺序处置的矩阵运算。然而，假设需随机存取某一行中的非零元，那么需从头开场进展查找。某一行中的非零元，那么需从头开场进展查找。二、行逻辑联接的顺序表二、行逻辑联接的顺序表 #define MAXSIZE 500 typedef struct Triple dataMAXSIZE + 1; /三元组表三元组表 int rposMAXMN + 1; /每一行非零元的位置表每一行非零元的位置表 int mu, nu, tu; RLSMatrix; / 行逻辑链接顺序表类型行逻辑链接顺序表类型二、行逻辑联接的顺序表二、行逻辑联接的顺序表0 12 9 0

42、 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=121213931-3351443245218611564-7668ijerow123456numrow202112rposrow133567例如：给定一组下标，求矩阵的元素值例如：给定一组下标，求矩阵的元素值ElemType value(RLSMatrix M, int r, int c) p=M.rposr;/第第r行第一个非零值的位置行第一个非零值的位置 while (M.datap.i=r &M.datap.j i=i; p-j=j; p-e=

43、e; if(M.rheadi=NULL|M.rheadi-jj) p-right=M.rheadi; M.rheadi =p; /插入到第一个插入到第一个else for(q=M.rheadi; (q-right)&(q-right-jright); p-right=q-right;q-right=p; if(M.cheadj=NULL|M.cheadj-ii) p-down=M.cheadj; M.cheadj =p; else for(q=M.cheadj;(q-down)& q-down-idown); p-down=q-down;q-down=p;/end forRet

44、urn Ok;/CreateSMtrix_OL418234输入：输入：m=4,n=31,1,32,2,52,3,44,1,82,1,7113217225rhead1rhead2rhead3rhead4chead1 chead2chead33 0 0 50 -1 0 02 0 0 0矩阵相加算法矩阵相加算法A=0 2 0 -10 1 0 20 0 0 4B=A=A+BA=3 2 0 40 0 0 22 0 0 4对于每一行做如下处置对于每一行做如下处置A.cheadA.rhead1131 452 2 -13 122 2 11 4 -11 2 22 4 23 4 4B.rheadB.cheadAB

45、pa=A.rhead1;pb=B.rhead1;pre=NULL;for(j=1;jjj) pre=pa;pa=pa-right;A.cheadA.rhead1131 452 2 -13 122 2 11 4 -11 2 22 4 23 4 4B.rheadABprepbh1h3h4h2if(pa-jpb-j) 复制复制pb所指的结点赋值为所指的结点赋值为p； if(pre=NULL) A.rheadp-i=p; else pre-right=p; p-right=pa;pre=p; pb=pb-right;paA.cheadA.rhead1131 4522 -13 122 2 11 4 -1

46、1 2 22 4 23 4 4B.rheadB.cheadMNpapb1 2 2prehl1hl3hl4hl2if(A.cheadp-j=NULL & hlp-j=A.cheadp-j)A.cheadp-j=p;p-down=hlp-j;Else p-down=hlp-j-down; hlp-j-down=p; hlp-j=p;pA.cheadA.rhead1131 4522 -13 122 2 11 4 -11 2 22 4 23 4 4B.rheadB.cheadABpapb1 2 2prehl1hl3hl4hl2A.cheadA.rhead1131 4522 -13 122 2

47、11 4 -11 2 22 4 23 4 4B.rheadB.cheadABpapb1 2 2prehl1hl3hl4hl2If(Pa-j=pb-j) pa-e+=pa-e; if(e!=0)pre=pa; pa=pa- right;pb=pb-right; else 删除删除A中该结点中该结点A.cheadA.rhead1131 4422 -13 122 2 11 4 -11 2 22 4 23 4 4B.rheadB.cheadABPa=NULL1 2 2hl1hl3hl4hl2prePb=NULLA.cheadA.rhead1131 4422 -13 122 2 11 4 -11 2 2

48、2 4 23 4 4B.rheadB.cheadAB1 2 2hl1hl3hl4hl2papbA.cheadA.rhead1131 4422 -13 122 2 11 4 -11 2 22 4 23 4 4B.rheadB.cheadAB1 2 2hl1hl3hl4hl2papbA.cheadA.rhead1131 4422 -13 122 2 11 4 -11 2 22 4 23 4 4B.rheadB.cheadAB1 2 2hl1hl3hl4hl2ppbPa=NULLA.cheadA.rhead1131 4422 -13 122 2 11 4 -11 2 22 4 23 4 4B.rhe

49、adB.cheadAB1 2 2hl1hl3hl4hl2ppbPa=NULLA.cheadA.rhead1131 443 122 2 11 4 -11 2 22 4 23 4 4B.rheadB.cheadAB1 2 2hl1hl3hl4hl2pbPa=NULL5.4 5.4 广义表的定义广义表的定义广义表是线性表的推行，也称为列表广义表是线性表的推行，也称为列表lists广义表中元素既广义表中元素既可以是原子类型，也可以是列表。可以是原子类型，也可以是列表。记为：记为： LS = ( a1 , a2 , ， an ) 广义表名广义表名 a1是表头是表头(Head a2 ,an 是表尾是表尾

50、(Tail)1、定义：、定义：n n是表长是表长 第一个元素是表头，而其他元素组成的表称为表尾；第一个元素是表头，而其他元素组成的表称为表尾； 所以任何一个非空表，表头能够是原子，也能够是所以任何一个非空表，表头能够是原子，也能够是 列表；但表尾一定是列表。列表；但表尾一定是列表。 商定：用小写字母表示原子类型，用大写字母表示商定：用小写字母表示原子类型，用大写字母表示 列表。列表。在广义表中商定：在广义表中商定：2、特点：1次序性：一个直接前驱和一个直接后继次序性：一个直接前驱和一个直接后继2长度：表中最外层包含元素个数长度：表中最外层包含元素个数3深度：当广义表全部用原子替代后，表中括号的

51、最大重数深度：当广义表全部用原子替代后，表中括号的最大重数 空表空表 的深度为的深度为1，长度为，长度为0 ，原子的深度为，原子的深度为0.4可递归：本人可以作为本人的子表。可递归：本人可以作为本人的子表。 例例E=(a, E) 递归表的深度是无穷值，长度是递归表的深度是无穷值，长度是2。5可共享可共享: 可以为其它广义表所共享的表。可以为其它广义表所共享的表。6任何一个非空广义表任何一个非空广义表 LS = ( 1, 2, , n) 均可分解为均可分解为 表头表头 GetHead(LS) = 1 和和 表尾表尾 GetTail(LS) = ( 2, , n) 两部两部分分E=(a,E)=(a

52、,(a,E)= (a,(a,(a,.)，E为递归表为递归表1A =( )2B = ( e ) 3C =( a ,( b , c , d ) ) 4D=( A , B ,C )5E=(a, 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)，共享表，共享表6)F=( ) n=1Gethead(B)= GetTail(B)=GetHea

53、d(C)= GetTail(C)=GetHead(D)= GetTail(D)=GetHead(E)= GetTail(E)=GetHead( )= GetTail( )=B = ( e ) C =( a ,( b , c , d ) ) D=( A , B ,C ) E=(a, E)e( )a(b,c,d)A(B,C)a(E)例例2：求以下广义表的表头和表尾。：求以下广义表的表头和表尾。GetTail( GetHead (a,b),(c,d)b( )( )DABCeabcd A=( a , (b, A) )例例3 3：试用图形表示以下广义表：试用图形表示以下广义表. .设设 代表原子，代表原

54、子， 代表子表代表子表 e D=(A,B,C)=( ( ),(e),( a, (b,c,d) ) )Aab的长度为的长度为3，深度为，深度为3的长度为的长度为2，深度为，深度为深度括号的重数深度括号的重数 结点的最大层数结点的最大层数广义表的笼统数据类型定义广义表的笼统数据类型定义ADT GList 数据对象：数据对象：D= ei|i=1，2，n； n0； ei AtomSet或或 ei Glist, AtomSet为某个数据对象为某个数据对象 数据关系：数据关系：R1=| ei-l，ei D， 2in 根本操作：根本操作： InitGList(&L) 操作结果：创建空的广义表操作结果：创建空的广义表L CreateGList(&L，S) 初始条件：初始条件：s是广义表的书写方式串是广义表的书写方式串 操作结果：由操作结果：由s创建广义表创建广义表L DestroyGL