第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个下标，个下标，每个元素每个元素aij受到两个关系受到两个关系（行关系和列关系）的约束：（行关系和列关系）的约束：一个一个m mn n的二维数组可以的二维数组可以看成是由看成是由m m行的一维数组组行的一维数组组成或由成或由n n列的一维数组组成。列的一维数组组成。a0a1.am-1ai=(ai0, ai1, , ai,n-1) i=0,1,2,m-11n1,m1,1m1,0m1n1,1110

4、1n0,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 两个后继两个后继结点结点ai,j+1和和 ai+1,jqa00没有前驱结点没有前驱结点,称之为开始结点称

5、之为开始结点. 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)同理，三维数组同理，三维数组amn l中每个元素属于三个线性表，每个元素中每个元素

6、属于三个线性表，每个元素最多有三个前驱和三个后继。最多有三个前驱和三个后继。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 n维数组可以看成是维数组可以看成是由若干个由若干个n1维数组组成的线维数组组成的线性表性表，在，在n维数组维数组ab1 b2 bn中中, 每个元素每个元素ai1,i2,in(0 ij bi-1,j=1,2,n)属于属于n个线性表个线性表, 每个元素每个元素最多有最多有n个前驱和个前驱和n个后

7、继。个后继。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 elemset ，0ib1-1, 0 jb2-1数据关系数据关系: : r = row, col row = | 0ib1-1, 0jb2-2 col = | 0ib1-2, 0jb2-1二维数组的二维数组的 定义定义:2b1ba initarray(&a, n, bound1, ., boundn) 操作结果：操作结果：若维数若维

8、数 n 和各维长度合法，则构造相应和各维长度合法，则构造相应 的数组的数组a，并返回，并返回ok。基本操作：基本操作： destroyarray(&a) 操作结果：操作结果：销毁数组销毁数组a。value(a, &e, index1, ., indexn)/取数组元素取数组元素 初始条件：初始条件：a是是n维数组，维数组，e为元素变量，随后是为元素变量，随后是n 个下标值。个下标值。 操作结果：操作结果：若各下标不超界，则若各下标不超界，则e赋值为所指定的赋值为所指定的 a 的元素值，并返回的元素值，并返回ok。基本操作：基本操作：assign(&a, e, index

9、1, ., indexn)/修改数组元素修改数组元素 初始条件：初始条件：a是是n维数组，维数组，e为元素变量，随后是为元素变量，随后是 n 个下标值。个下标值。 操作结果：操作结果：若下标不超界，则将若下标不超界，则将e的值赋给所指的值赋给所指 定的定的a的元素，并返回的元素，并返回ok。5.2 数组的顺序存储表示和实现问题：问题：计算机的存储结构一般是一维的，而计算机的存储结构一般是一维的，而n n维数组维数组(n2)(n2)一般是多维的，怎样存放？一般是多维的，怎样存放？解决办法：解决办法：事先约定按某种次序将数组元素排成一序事先约定按某种次序将数组元素排成一序 列，然后将这个线性序列存

10、入存储器中。列，然后将这个线性序列存入存储器中。例如：例如：在二维数组中，我们既可以规定按在二维数组中，我们既可以规定按行行存储，也存储，也可以规定按可以规定按列列存储存储。若规定好了次序，则数组中任意一个元素的存放地址便有若规定好了次序，则数组中任意一个元素的存放地址便有规律可寻，可形成地址计算公式；规律可寻，可形成地址计算公式；约定的次序不同，则计算元素地址的公式也有所不同；约定的次序不同，则计算元素地址的公式也有所不同；c c和和pascalpascal中一般采用行优先顺序；中一般采用行优先顺序；fortranfortran采用列优先。采用列优先。 按行序为主序存放按行序为主序存放 am

11、-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 a01 . a0n-1 a10 a11 . a1n-1 am-10 am-11 . am-1n-1 . 按列序为主序存放按列序为主序存放01m*n-1m-1m计算二维数组元素地址的通式计算二维数组元素地址的通式二维

12、数组二维数组列优先列优先存储的通式为：存储的通式为：loc(aij)=loc(a00)+(b1*j+i)*l则则行优先行优先存储时的地址公式为：存储时的地址公式为：loc(aij)=loc(a00)+(b2*i+j)*l设一般的二维数组是设一般的二维数组是a0.ba0.b1 1-1, 0.b-1, 0.b2 2-1-11b21,b11,0b11b2i,iji01b20,00mna.a.a.a.a.a.aa计算三维数组元素地址的通式计算三维数组元素地址的通式设一般的设一般的三维数组是维数组是a0.ba0.b1 1-1, 0.b-1, 0.b2 2-1-1，0.b0.b3 3-1-1按按“行优先顺

13、序行优先顺序”存储，其任一元素存储，其任一元素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若是若是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)niii1jc5.3 矩阵的压缩存储矩阵的压缩存储 在科学与工程计算问题中，矩阵是一种常用在科学与工程计算问题中，矩阵是一种常用的数学对象，在高级语言编制程序时，将一个矩的数学对象，在高级语言编制程序时，将一个矩阵描述为一个二维数组。矩阵在这种存储表示之阵描述为一个二维数组。矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵运算下，可以对其

15、元素进行随机存取，各种矩阵运算也非常简单。也非常简单。 但是在矩阵但是在矩阵中非零元素呈某种规律分布中非零元素呈某种规律分布或者或者矩阵中出现大量的零元素矩阵中出现大量的零元素的情况下，占用了许多的情况下，占用了许多单元去存储重复的非零元素或零元素，这对高阶单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪费，为了节省存储空间，矩阵会造成极大的浪费，为了节省存储空间， 我们可以对这类矩阵进行我们可以对这类矩阵进行压缩存储压缩存储：即为多个相即为多个相同的非零元素只分配一个存储空间；对零元素不同的非零元素只分配一个存储空间；对零元素不分配空间分配空间。并非所有的矩阵都可以压缩并非所有的

16、矩阵都可以压缩对称矩阵对称矩阵三角矩阵三角矩阵稀疏矩阵稀疏矩阵5.3.1 5.3.1 特殊矩阵特殊矩阵在一个在一个n n阶方阵阶方阵a a中，若元素满足下述性质：中，若元素满足下述性质： a aijij=a=ajiji 0i,jn-1 0i,jn-1 1 5 1 3 7 a00 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

17、-1012345n(n-1)n(n+1)/2-11）对称矩阵的存储方式）对称矩阵的存储方式在对称矩阵中，第在对称矩阵中，第i i行恰有行恰有i+1i+1个元素，元素总数为：个元素，元素总数为： 可以将这些元素存放在一个向量可以将这些元素存放在一个向量 中中1 1、对称矩阵、对称矩阵1n0i21)n(n1)(i 12/ ) 1(.0nnsa2）为了便于访问对称矩阵为了便于访问对称矩阵a a中的元素，我们必须在中的元素，我们必须在a aijij和和saksak之间找一个对应关系之间找一个对应关系。v若若ijij，则，则a aijij在下三角形中。在下三角形中。a aijij之前的之前的i i行（从

18、第行（从第0 0行行到第到第i-1i-1行）一共有行）一共有1+2+1+2+i=i+i=i* *(i+1)/2(i+1)/2个元素，在第个元素，在第i i行上，行上，a aijij之前恰有之前恰有j j个元素（即个元素（即a ai0i0,a,ai1i1,a,ai2i2, ,a,aij-1ij-1），），因此有：因此有： k=ik=i* *(i+1)/2+j(i+1)/2+j 0kn(n+1)/2-10kn(n+1)/2-1 v若若ijij，则，则a aijij是在上三角矩阵中。因为是在上三角矩阵中。因为a aijij=a=ajiji，所以只，所以只要交换上述对应关系式中的要交换上述对应关系式中

19、的i i和和j j即可得到：即可得到： k=jk=j* *(j+1)/2+i(j+1)/2+i 0kn(n+1)/2-10kn(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-1 (a) 上三角矩阵上三角矩阵

20、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=s/(mn)n)，称，称e e为

21、矩阵为矩阵的的稀疏因子稀疏因子。通常认为。通常认为e0.05e0.05时为稀疏矩时为稀疏矩阵。阵。稀疏矩阵的压缩存储方法稀疏矩阵的压缩存储方法一、三元组顺序表一、三元组顺序表二、行逻辑联接的顺序表二、行逻辑联接的顺序表三、三、 十字链表十字链表存储稀疏矩阵时，为了节省存储单元，使用存储稀疏矩阵时，为了节省存储单元，使用压缩压缩 存储方法。存储方法。非零元素的分布一般是没有规律的，因此在存储非零元素的分布一般是没有规律的，因此在存储 非零元素的同时，还必须同时记下它所在的非零元素的同时，还必须同时记下它所在的行和行和 列的位置（列的位置（i,j)i,j)。一个一个三元组三元组(i,j,a(i,j

22、,aijij) )唯一确定了矩阵唯一确定了矩阵a a的一个非零的一个非零 元。因此，稀疏矩阵可由元。因此，稀疏矩阵可由表示非零元的三元组表示非零元的三元组及及 其其行列数行列数唯一确定。唯一确定。一、三元组顺序表一、三元组顺序表例如，下列稀疏矩阵例如，下列稀疏矩阵 5.3.2 5.3.2 稀疏矩阵稀疏矩阵可由三元组表可由三元组表(1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7)和矩阵和矩阵维数（维数（6,7）唯一确定）唯一确定 760007001500000180000024000140000300000

23、0000009120m=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, tu; (mu行数行数,nu列数列数,tu非零元个数非零元个数) tsmatrix; / 稀疏矩阵类型稀疏矩阵类型三元组表表示法：三元组表表示法：12121393

24、1-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求转置矩阵算法求转置矩阵算法028003600070500140m005280000007143600t用常规的二维数组表示时的算法用常规的二维数组表示时的算法 其时间复杂度为其时间复杂度为: o(munu) for (c=1;

25、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三三元元组组表表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

26、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 2）t t的总行数的总行数mumu和总列数和总列数nunu与与m m值不同值不同（互换）；互换）；（3 3）重排重排三元组内元素顺序三元组内元素顺序，使转置后的三元组也按行，使转置后的三元组也按行 （或列）为主序有规律的排列。（或列）为主序有规律的排列。上述（上述

27、（1 1）和（）和（2 2）容易实现，难点在）容易实现，难点在（3 3）。提问：提问：若采用三元组压缩技术存储稀疏矩阵，只要把每个若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的元素的行下标和列下标互换行下标和列下标互换，就完成了对该矩阵的转置运，就完成了对该矩阵的转置运算，这种说法正确吗？算，这种说法正确吗？ 有两种实现方法有两种实现方法压缩转置压缩转置( (压缩压缩) )快速转置快速转置方法方法1 1：压缩转置压缩转置思路：思路：反复扫描反复扫描m.datam.data中的中的列序列序，从小到大依次进行转置。，从小到大依次进行转置。6 7 8 1 2 12 1 3 9 3 1 -3 3

28、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)/用三元组表存放稀疏矩阵用三元组表存放稀疏矩阵m m，求，求m m的转置矩阵的转置矩阵t tt.mu=m.nu; t.nu=m.mu; t.tu=m

29、.tu; /nu/nu是列数是列数,mu,mu是行数是行数,tu,tu是非零元素个数是非零元素个数if (t.tu) q=1; /q/q是转置矩阵是转置矩阵t t的结点编号的结点编号 for(col=1; col=m.nu; col+) for(p=1; p=m.tu; p+) /p/p是是m 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; /tranposesmatrix压缩转置算法描述压缩转置算法描述：1 1、

30、主要时间消耗在主要时间消耗在查找查找m.datap.j=colm.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中非零元素的个数之中非零元素的个数之积积最坏情况最坏情况：m m中全是非零元素，此时中全是非零元素，此时tu=mutu=mu* *nunu， 时间复杂度为时间复杂度为 o(o(nu2 2*mu ) )注：注：若

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

32、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.datat.data的的“恰当恰当”位置？位置？ p1234 q 3 5如果能预知如果能预知m矩阵中每一列矩阵中每一列( (即即t的每一行的每一行) )的非零元的非零元素个数，又能预知每一列

33、第一个非零元素在素个数，又能预知每一列第一个非零元素在t.datat.data中中的位置的位置, ,则扫描则扫描m.data时便可以将每个元素准确定位。时便可以将每个元素准确定位。设计思路：设计思路：注意：注意：根据根据m.datam.data的特征，每列第一个非零元素必的特征，每列第一个非零元素必 定先被扫描到。定先被扫描到。令令：m中的列变量用中的列变量用col表示；表示； num col ：存放存放m中第中第col 列中非列中非0 0元素个数，元素个数， cpot col ：存放存放m中第中第col列的第一个非列的第一个非0 0元素的位置，元素的位置， （即（即t.data中待计算的中待

34、计算的“恰当恰当”位置所需参考点位置所需参考点）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 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

35、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 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.da

36、ta 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.dataq. e = m.datap.e; /for /if return ok; /fasttranposesmatrix;快速转置算法描述快速转置算法描述：/m/m用顺序存储表示，求用顺序存储

37、表示，求m m的转置矩阵的转置矩阵t t/先统计每列非零元素个数先统计每列非零元素个数/再生成每列首元位置辅助向量表再生成每列首元位置辅助向量表/p/p指向指向a.dataa.data，循环次数为非，循环次数为非0 0元素总个数元素总个数tutu/查辅助向量表得查辅助向量表得q q，即，即t t中位置中位置/修改向量表中列坐标值，供同一列下一修改向量表中列坐标值，供同一列下一非零元素定位之用！非零元素定位之用！1.1. 与常规算法相比，增加了与常规算法相比，增加了2 2个长度为列长的辅助数个长度为列长的辅助数组组( (num 和和cpot ）。快速转置算法的效率分析快速转置算法的效率分析：2.

38、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; 该算法的时间复杂度该算法的时间复杂度(nu(nu* *2)+(tu2)+(tu*

39、 *2)=o(2)=o(nu+tunu+tu） 传统转置：传统转置：o(o(mumu* *nunu) ) 压缩转置：压缩转置：o(o(mumu* *tutu) ) 压缩快速转置：压缩快速转置：o(o(nu+tunu+tu) )牺牲空间效率换时牺牲空间效率换时 间效率。间效率。小结：小结：讨论：讨论：最坏情况是最坏情况是tu=nutu=nu* *mumu( (即矩阵中全部是非零元即矩阵中全部是非零元素），而此时的时间复杂度也只是素），而此时的时间复杂度也只是o(o(mumu* *nunu) )，并未超，并未超过传统转置算法的时间复杂度。过传统转置算法的时间复杂度。 三元组顺序表又称有序的双下标法

40、，它的特点三元组顺序表又称有序的双下标法，它的特点是，非零元在表中按行序有序存储，因此是，非零元在表中按行序有序存储，因此便于进行便于进行依行顺序处理的矩阵运算。依行顺序处理的矩阵运算。然而，然而，若需随机存取某若需随机存取某一行中的非零元，则需从头开始进行查找一行中的非零元，则需从头开始进行查找。二、行逻辑联接的顺序表二、行逻辑联接的顺序表 #define maxsize 500 typedef struct triple datamaxsize + 1; /三元组表三元组表 int rposmaxmn + 1; /每一行非零元的位置表每一行非零元的位置表 int mu, nu, tu; r

41、lsmatrix; / 行逻辑链接顺序表类型行逻辑链接顺序表类型二、行逻辑联接的顺序表二、行逻辑联接的顺序表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=121213931-3351443245218611564-7668ijerow123456numrow202112rposrow133567例如：给定一组下标，求矩阵的元素值例如：给定一组下标，求矩阵的元素值elemtype value(rlsmatrix m, int r, int c) p=m.rposr;/第第r行第一个非零值的位

42、置行第一个非零值的位置 while (m.datap.i=r &m.datap.j i=i; p-j=j; p-e=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;(

43、q-down)& q-down-idown); p-down=q-down;q-down=p;/end forreturn 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.rh

44、ead1131 452 2 -13 122 2 11 4 -11 2 22 4 23 4 4b.rheadb.cheadabpa=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;

45、pre=p; pb=pb-right;paa.cheada.rhead1131 4522 -13 122 2 11 4 -11 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.che

46、adabpapb1 2 2prehl1hl3hl4hl2a.cheada.rhead1131 4522 -13 122 2 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 2hl1hl3

47、hl4hl2prepb=nulla.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 2hl1hl3hl4hl2papba.cheada.rhead1131 4422 -13 122 2 11 4 -11 2 22 4 23 4 4b.rheadb.cheadab1 2 2hl1hl3hl4hl2ppbpa=nul

48、la.cheada.rhead1131 4422 -13 122 2 11 4 -11 2 22 4 23 4 4b.rheadb.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）广义表中元素既）广义表中元素既可以是原子类型，也可以是列表。可以是原子类型，也可以是列表。记为

49、：记为： ls = ( a1 , a2 , ， an ) 广义表名广义表名 a1是表头是表头(head） （ a2 ,an ）是表尾）是表尾 (tail)1、定义：、定义：n n是表长是表长 第一个第一个元素是表头元素是表头，而其余元素组成的，而其余元素组成的表表称为表称为表尾尾； 所以任何一个非空表，表头可能是原子，也可能是所以任何一个非空表，表头可能是原子，也可能是 列表；但列表；但表尾一定是列表。表尾一定是列表。 约定：用小写字母表示原子类型，用约定：用小写字母表示原子类型，用大写字母大写字母表示表示 列表。列表。在广义表中约定：在广义表中约定：2、特点：、特点：1）次序性：）次序性：一

50、个直接前驱和一个直接后继一个直接前驱和一个直接后继2）长度：）长度：表中表中最外层最外层包含元素个数包含元素个数3）深度：）深度：当广义表全部用原子代替后，表中括号的最大重数当广义表全部用原子代替后，表中括号的最大重数 空表（空表（ ）的深度为）的深度为1，长度为，长度为0 ，原子的深度为，原子的深度为0.4）可递归：）可递归：自己可以作为自己的子表。自己可以作为自己的子表。 例例e=(a, e) 递归表的深度是无穷值，长度是递归表的深度是无穷值，长度是2。5）可共享）可共享: 可以为其它广义表所共享的表。可以为其它广义表所共享的表。6 6）任何一个非空广义表）任何一个非空广义表 ls = (

51、 ls = ( 1, 1, 2, 2, , , n)n) 均可分解为均可分解为 表头表头 gethead(ls) = 1 和和 表尾表尾 gettail(ls) = ( 2, , n) 两部分两部分e=(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,c,d)为子表为子表n=3，

52、3个元素都是子表个元素都是子表n=2，a 为原子，为原子，e为子表为子表d=(a,b,c)=( ),(e),(a,(b,c,d)，共享表共享表6)f=( ) n=1gethead(b)= gettail(b)=gethead(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：求下列广义表的表头和表尾。求下列广义表的

53、表头和表尾。gettail( gethead (a,b),(c,d)（b）( )( )dabceabcd a=( a , (b, a) )例例3 3：试用图形表示下列广义表试用图形表示下列广义表. .（设设 代表原子，代表原子， 代表子表）代表子表） 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 destroyglist(&l) 初始条件初始条