《第5部分数组和广义表》由会员分享，可在线阅读，更多相关《第5部分数组和广义表（80页珍藏版）》请在金锄头文库上搜索。
1、第第5章章 数组和广义表数组和广义表 元素的值并非原子类型，可以再分解，表中元素的值并非原子类型，可以再分解，表中 元素也是一个线性表（即线性表的推广）。元素也是一个线性表（即线性表的推广）。数组和广义表的特点：数组和广义表的特点：特殊的线性表特殊的线性表5.1 数组的定义数组的定义5.2 数组的顺序表示和实现数组的顺序表示和实现5.3 矩阵的压缩存储矩阵的压缩存储5.4 广义表的定义广义表的定义5.5 广义表的存储结构广义表的存储结构第第5章章 数组和广义表数组和广义表5.1 数组的定义 数组：数组： 由一组名字相同、下标不同的同类型的元素由一组名字相同、下标不同的同类型的元素 组成组成数组
2、特点数组特点数组结构固定,下标一般具有下标一般具有固定的上界和下界固定的上界和下界数据元素具有具有统一的类型统一的类型数组运算数组运算给定一组下标，取取相应的数据元素.给定一组下标，修修改数据元素的值.数组的处理比其它复杂的结构要简单数组的处理比其它复杂的结构要简单与高级语言中数组的区别：与高级语言中数组的区别： 1、本章所讨论的数组是一种、本章所讨论的数组是一种数据结构数据结构，而高级语言，而高级语言中数组是一种中数组是一种数据类型数据类型。2、高级语言高级语言中的数组是中的数组是顺序结构顺序结构；而本章的数组；而本章的数组 既可以是既可以是顺序的，顺序的，也可以是也可以是链式结构链式结构，
3、用户可根，用户可根 据需要选择。据需要选择。二维数组的特点：二维数组的特点：一维数组的特点：一维数组的特点： 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-15.1 数组的定义 B0B1Bn-1二维数组是一个数据元素为线性表的线性表二维数组是一
4、个数据元素为线性表的线性表j=0,1,n-1qaij(1im-2，1jn-2)有有两个前驱两个前驱结点结点ai,j-1和和ai-1,j两个后继两个后继结点结点ai,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行的线性表行的线性表A
5、i和和第第j列的线性表列的线性表Bjq第第m-1行的元素行的元素am-1,j(j=1,n-2)q第第n-1列的元素列的元素ai,n-1(i=1,m-2)同理，三维数组同理，三维数组Amnl中每个元素属于三个线性表，每个元素中每个元素属于三个线性表，每个元素最多有三个前驱和三个后继。最多有三个前驱和三个后继。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维数组组成的线维数组组成的
6、线性表性表，在，在n维数组维数组Ab1b2bn中中,每个元素每个元素ai1,i2,in(0ijbi-1,j=1,2,n)属于属于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 ElemSet，0ib1-1,0jb2-1数据关系数据关系: : R=ROW,COLROW=|0ib1-1,0jb2-2COL=|0ib1-2,0jb2-1二
7、维数组的二维数组的定义定义:InitArray(&A,n,bound1,.,boundn)操作结果：操作结果：若维数若维数n和各维长度合法，则构造相应和各维长度合法，则构造相应的数组的数组A，并返回并返回OK。基本操作：基本操作： DestroyArray(&A) 操作结果：操作结果：销毁数组销毁数组A。Value(A,&e,index1,.,indexn)/取数组元素取数组元素初始条件：初始条件：A是是n维数组，维数组，e为元素变量，随后是为元素变量，随后是n个下标值。个下标值。操作结果：操作结果：若各下标不超界，则若各下标不超界，则e赋值为所指定的赋值为所指定的A的元素值，并返回的元素值，
8、并返回OK。基本操作：基本操作：Assign(&A,e,index1,.,indexn)/修改数组元素修改数组元素初始条件：初始条件：A是是n维数组，维数组，e为元素变量，随后是为元素变量，随后是n个下标值。个下标值。操作结果：操作结果：若下标不超界，则将若下标不超界，则将e的值赋给所指的值赋给所指定的定的A的元素，并返回的元素，并返回OK。5.2 数组的顺序存储表示和实现问题：问题：计算机的存储结构一般是一维的，而计算机的存储结构一般是一维的，而n n维数组维数组( (n n22) )一般是多维的，怎样存放？一般是多维的，怎样存放？解决办法：解决办法：事先约定按某种次序将数组元素排成一序事先
9、约定按某种次序将数组元素排成一序 列，然后将这个线性序列存入存储器中。列，然后将这个线性序列存入存储器中。例如：例如：在二维数组中，我们既可以规定按在二维数组中，我们既可以规定按行行存储，也存储，也可以规定按可以规定按列列存储存储。若规定好了次序，则数组中任意一个元素的存放地址便有若规定好了次序，则数组中任意一个元素的存放地址便有规律可寻，可形成地址计算公式；规律可寻，可形成地址计算公式；约定的次序不同，则计算元素地址的公式也有所不同；约定的次序不同，则计算元素地址的公式也有所不同；C C和和PASCALPASCAL中一般采用行优先顺序；中一般采用行优先顺序；FORTRANFORTRAN采用列
10、优先。采用列优先。按行序为主序存放按行序为主序存放 am-1,n-1 . am-1,1 am-1,0 . a1n-1 . a11 a10 a0,n-1 . a01 a00a00a01.a0,n-1a10a11.a1,n-1am-1,0am-1,1am-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 a00a00a01.a0n-1a10a11.a1n-1am-10am-11.am-1n-1.按列序为主序存放按列序为主序存放01m*n-1m-1m计算二维数组元素地址的通式计算二维数组元素地址的通式
11、二维数组二维数组列优先列优先存储的通式为：存储的通式为：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-1计算三维数组元素地址的通式计算三维数组元素地址的通式设一般的设一般的三维数组是维数组是A0.bA0.b1 1-1, 0.b-1, 0.b2 2-1-1，0.b0.b3 3-1-1按按“行优先顺序行优先顺序”存储，其任一元素存储，其任一元素A Aijkijk地地址计算函数为：址
12、计算函数为：LOC(aLOC(aijkijk)=LOC(a)=LOC(a000000)+()+(i*bi*b2 2*b*b3 3+ +j*bj*b3 3+k)*L+k)*L若是若是N N维数组，其中任一元素的地址该如何计算？维数组，其中任一元素的地址该如何计算？开始结点的存放地址（即基地址）开始结点的存放地址（即基地址）维数和每维的上、下界；维数和每维的上、下界；每个数组元素所占用的单元数每个数组元素所占用的单元数其中其中Cn=L,Ci-1=biCi，1in（递归）递归）Loc(jLoc(j1 1,j,j2 2, ,j jn n)=LOC(0,0,)=LOC(0,0,0)0)5.3 矩阵的压缩
13、存储矩阵的压缩存储 在科学与工程计算问题中，矩阵是一种常用在科学与工程计算问题中，矩阵是一种常用的数学对象，在高级语言编制程序时，将一个矩的数学对象，在高级语言编制程序时，将一个矩阵描述为一个二维数组。矩阵在这种存储表示之阵描述为一个二维数组。矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵运算下，可以对其元素进行随机存取，各种矩阵运算也非常简单。也非常简单。 但是在矩阵但是在矩阵中非零元素呈某种规律分布中非零元素呈某种规律分布或者或者矩阵中出现大量的零元素矩阵中出现大量的零元素的情况下，占用了许多的情况下，占用了许多单元去存储重复的非零元素或零元素，这对高阶单元去存储重复的非零元素
14、或零元素，这对高阶矩阵会造成极大的浪费，为了节省存储空间，矩阵会造成极大的浪费，为了节省存储空间， 我们可以对这类矩阵进行我们可以对这类矩阵进行压缩存储压缩存储：即为多个相即为多个相同的非零元素只分配一个存储空间；对零元素不同的非零元素只分配一个存储空间；对零元素不分配空间分配空间。并非所有的矩阵都可以压缩并非所有的矩阵都可以压缩对称矩阵对称矩阵三角矩阵三角矩阵稀疏矩阵稀疏矩阵5 5.3.1 .3.1 特殊矩阵特殊矩阵在一个在一个n n阶方阵阶方阵A A中，若元素满足下述性质：中，若元素满足下述性质： a aijij=a=ajiji 0 0i,ji,jn-1n-115137a0050800a1
15、0a1118926a20a21a2230251.70613an-10an-11an-12an-1n-1对称矩阵对称矩阵1 1、对称矩阵、对称矩阵sak按行序为主序按行序为主序：a00a10a11a20a21a22an-1,0an-1,n-1012345n(n-1)n(n+1)/2-11）对称矩阵的存储方式）对称矩阵的存储方式在对称矩阵中，第在对称矩阵中，第i i行恰有行恰有i+1i+1个元素，元素总数为：个元素，元素总数为： 可以将这些元素存放在一个向量可以将这些元素存放在一个向量 中中1 1、对称矩阵、对称矩阵2）为了便于访问对称矩阵为了便于访问对称矩阵A A中的元素，我们必须在中的元素，我
16、们必须在a aijij和和saksak之间找一个对应关系之间找一个对应关系。v若若i ij j，则则a aijij在下三角形中。在下三角形中。a aijij之前的之前的i i行（从第行（从第0 0行行到第到第i-1i-1行）一共有行）一共有1+2+1+2+ +i=i*(i+1)/2i=i*(i+1)/2个元素，在第个元素，在第i i行上，行上，a aijij之前恰有之前恰有j j个元素（即个元素（即a ai0i0,a,ai1i1,a,ai2i2, ,a,aij-1ij-1），），因此有：因此有： k=i*(i+1)/2+jk=i*(i+1)/2+j 0kn(n+1)/2-10kn(n+1)/2
17、-1 v若若ijij，则则a aijij是在上三角矩阵中。因为是在上三角矩阵中。因为a aijij=a=ajiji，所以只所以只要交换上述对应关系式中的要交换上述对应关系式中的i i和和j j即可得到：即可得到： k=j*(j+1)/2+ik=j*(j+1)/2+i 0kn(n+1)/2-10kn(n+1)/2-1 1 1、对称矩阵、对称矩阵2、三角矩阵、三角矩阵以主对角线划分，三角矩阵有以主对角线划分，三角矩阵有上三角上三角和和下三角下三角两种。两种。上三角矩阵中主对角线以下的元素均为常数上三角矩阵中主对角线以下的元素均为常数(a)。下三角矩阵正好相反，主对角线以上的元素均为常数下三角矩阵正
18、好相反，主对角线以上的元素均为常数(b)。a00a01.a0,n-1ca11.a1,n-1cccam-1,n-1(a)上三角矩阵上三角矩阵a00c.ca10a11c.cam-10am-11am-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
19、A为稀疏矩为稀疏矩阵。阵。有有s s个非零元素。令个非零元素。令e=s/(me=s/(mn)n)，称称e e为矩阵为矩阵的的稀疏因子稀疏因子。通常认为。通常认为e e0.050.05时为稀疏矩时为稀疏矩阵。阵。稀疏矩阵的压缩存储方法稀疏矩阵的压缩存储方法一、三元组顺序表一、三元组顺序表二、行逻辑联接的顺序表二、行逻辑联接的顺序表三、三、十字链表十字链表存储稀疏矩阵时，为了节省存储单元，使用存储稀疏矩阵时，为了节省存储单元，使用压缩压缩 存储方法。存储方法。非零元素的分布一般是没有规律的，因此在存储非零元素的分布一般是没有规律的，因此在存储 非零元素的同时，还必须同时记下它所在的非零元素的同时，
20、还必须同时记下它所在的行和行和 列的位置（列的位置（i,j)i,j)。一个一个三元组三元组( (i,j,ai,j,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)和矩和矩阵阵维数（
21、维数（6,7）唯一确定）唯一确定 M=123456 1234567一、三元组顺序表一、三元组顺序表#defineMAXSIZE12500typedefstructinti,j;/该非零元的行下标和列下标该非零元的行下标和列下标ElemTypee;/该非零元的值该非零元的值Triple;/三元组类型三元组类型typedefstructTripledataMAXSIZE+1;intmu,nu,tu;(mu行数行数,nu列数列数,tu非零元个数非零元个数)TSMatrix;/稀疏矩阵类型稀疏矩阵类型三元组表表示法：三元组表表示法：121213931-3351443245218611564-7注意：注
22、意：三元组表中的三元组表中的元素按行（或列）排元素按行（或列）排列。列。668ije稀疏矩阵压缩存储的稀疏矩阵压缩存储的缺点：将失去随机存取功能缺点：将失去随机存取功能0 01 12 23 34 45 56 67 78 80129000000000-3000140002400001800001500-700求转置矩阵算法求转置矩阵算法用常规的二维数组表示时的算法用常规的二维数组表示时的算法其时间复杂度为其时间复杂度为: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,
23、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转置后转置后0129000000000-3000140002400001800001500-700M=003001512000180900240000000-70014000000000T=?不正确！不正确！（1 1）每个元素的行下标和列下标互换（即三元组中的）每个元素的行下标和列下标互换（即
24、三元组中的i i和和j j 互换互换）；）；（2 2）T T的总行数的总行数mumu和总列数和总列数nunu与与M M值不同值不同（互换）；互换）；（3 3）重排重排三元组内元素顺序三元组内元素顺序，使转置后的三元组也按行，使转置后的三元组也按行 （或列）为主序有规律的排列。（或列）为主序有规律的排列。上述（上述（1 1）和（）和（2 2）容易实现，难点在）容易实现，难点在（3 3）。提问：提问：若采用三元组压缩技术存储稀疏矩阵，只要把每个若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的元素的行下标和列下标互换行下标和列下标互换，就完成了对该矩阵的转置运，就完成了对该矩阵的转置运算，这种说法
25、正确吗？算，这种说法正确吗？ 有两种实现方法有两种实现方法压缩转置压缩转置( (压缩压缩) )快速转置快速转置方法方法1 1：压缩转置压缩转置思路：思路：反复扫描反复扫描M.dataM.data中的中的列序列序，从小到大依次进行转置。，从小到大依次进行转置。678121213931-3361443245218611564-7ije012345678M7 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 ije012345678Tqppppppppqqqqppppppppcol=1col=2qqqStatusTransPoseS
26、Matrix(TSMatrixM,TSMatrix&T)/用三元组表存放稀疏矩阵用三元组表存放稀疏矩阵M M，求求M M的转置矩阵的转置矩阵T TT.mu=M.nu;T.nu=M.mu;T.tu=M.tu;/nu/nu是列数是列数, ,mumu是行数是行数, ,tutu是非零元素个数是非零元素个数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.
27、j=M.datap.i;T.dataq.e=M.datap.e;q+;returnOK;/TranposeSMatrix压缩转置算法描述压缩转置算法描述：1 1、主要时间消耗在主要时间消耗在查找查找M.datap.j=colM.datap.j=col的元素的元素，由两重循，由两重循环完成环完成: : for(col=1;col=M.nu;col+)循环次数循环次数nufor(p=1;p=M.tu;p+)循环次数循环次数tu所以该算法的时间复杂度为所以该算法的时间复杂度为O(O(nu*tu) ) - -即即M M的列数与的列数与M M中非零元素的个数之中非零元素的个数之积积最坏情况最坏情况：M
28、M中全是非零元素，此时中全是非零元素，此时tu=mu*nutu=mu*nu， 时间复杂度为时间复杂度为 O(O(nu2 2*mu ) )注：注：若若M M中基本上是非零元素时，即使用非压缩传统转置算法中基本上是非零元素时，即使用非压缩传统转置算法的时间复杂度也不过是的时间复杂度也不过是O(O(nu*mu) )结论：结论：压缩转置算法不能滥用。压缩转置算法不能滥用。前提前提：仅适用于非零元素个数很少（即仅适用于非零元素个数很少（即tutumu*numu*nu）的情况。的情况。压缩转置算法的效率分析压缩转置算法的效率分析方法方法2 2 快速转置快速转置三三元元组组表表M.data三三元元组组表表T
29、.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.dataT.data的的“恰当恰当”位置位置？p
30、1234q35如果能预知如果能预知M矩阵中每一列矩阵中每一列( (即即T的每一行的每一行) )的非零元素的非零元素个数，又能预知每一列第一个非零元素在个数，又能预知每一列第一个非零元素在T.dataT.data中的中的位置位置, ,则扫描则扫描M.data时便可以将每个元素准确定位。时便可以将每个元素准确定位。设计思路：设计思路：注意：注意：根据根据M.dataM.data的特征，每列第一个非零元素必的特征，每列第一个非零元素必 定先被扫描到。定先被扫描到。令令：M中的列变量用中的列变量用col表示；表示； num col ：存放存放M中第中第col 列中非列中非0 0元素个数，元素个数， c
31、pot col ：存放存放M中第中第col列的第一个非列的第一个非0 0元素的位置，元素的位置， （即（即T.data中待计算的中待计算的“恰当恰当”位置所需参考点）位置所需参考点）col123456numcol222110cpotcol1规律规律:cpot(1)1cpotcolcpotcol-1+numcol-10129000000000-3000140002400001800001500-700M=3col1234565987668121213931-3351443245218611564-7ijv012345678M66813-3161521122518319342446-75314pp
32、pppppp4629753col123456numcol222110cpotcol135789ijv012345678TStatusFastTransposeSMatrix（TSMatirxM,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.datai.j;+numcol;cpot1=1;for(col=2;col=M.nu;col+)cpotcol=cpotcol-1+numcol-1;for(p=1;p=M.tu;p+)col=
33、M.datap.j;q=cpotcol;T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.e=M.datap.e;+cpotcol;+cpotcol;/for/ifreturnOK;/FastTranposeSMatrix;快速转置算法描述快速转置算法描述：/M M用顺序存储表示，求用顺序存储表示，求M M的转置矩阵的转置矩阵T T/先统计每列非零元素个数先统计每列非零元素个数/再生成每列首元位置辅助向量表再生成每列首元位置辅助向量表/p p指向指向a.dataa.data，循环次数为非循环次数为非0 0元素总个数元素总个数tutu/查辅助向量表得
34、查辅助向量表得q q，即即T T中位置中位置/修改向量表中列坐标值，供同一列下一修改向量表中列坐标值，供同一列下一非零元素定位之用！非零元素定位之用！1.1. 与常规算法相比，增加了与常规算法相比，增加了2 2个长度为列长的辅助数个长度为列长的辅助数组组( (num和和cpot）。快速转置算法的效率分析快速转置算法的效率分析：2.2. 从时间上，此算法用了从时间上，此算法用了4 4个并列的单循环，而且其个并列的单循环，而且其中前中前3 3个单循环都是用来产生辅助数组的。个单循环都是用来产生辅助数组的。for(col=1;col=M.nu;col+)循环次数循环次数nu;nu;for(i=1;i
35、=M.tu;i+)循环次数循环次数tu;tu;for(col=2;col=M.nu;col+)循环次数循环次数nu;nu;for(p=1;p=M.tu;p+)循环次数循环次数tu;tu;该算法的时间复杂度该算法的时间复杂度( (nu*2)+(tu*2)=O(nu*2)+(tu*2)=O(nu+tunu+tu） 传统转置：传统转置：O(O(mu*numu*nu) ) 压缩转置：压缩转置：O(O(mu*tumu*tu) ) 压缩快速转置：压缩快速转置：O(O(nu+tunu+tu) )牺牲空间效率换时牺牲空间效率换时 间效率。间效率。小结：小结：讨论：讨论：最坏情况是最坏情况是tu=nu*mutu
36、=nu*mu( (即矩阵中全部是非零元素）即矩阵中全部是非零元素），而此时的时间复杂度也只是，而此时的时间复杂度也只是O(O(mu*numu*nu) )，并未超过传并未超过传统转置算法的时间复杂度。统转置算法的时间复杂度。 三元组顺序表又称有序的双下标法，它的特点是，三元组顺序表又称有序的双下标法，它的特点是，非零元在表中按行序有序存储，因此非零元在表中按行序有序存储，因此便于进行依行顺便于进行依行顺序处理的矩阵运算。序处理的矩阵运算。然而，然而，若需若需随机随机存取某一行中的存取某一行中的非零元，则需从头开始进行查找非零元，则需从头开始进行查找。二、行逻辑联接的顺序表二、行逻辑联接的顺序表#
37、define MAXSIZE 500 typedefstruct Triple dataMAXSIZE + 1; /三元组表三元组表 intrposMAXMN+1; /每一行非零元的位置表每一行非零元的位置表 int mu, nu, tu; RLSMatrix; /行逻辑链接顺序表类型行逻辑链接顺序表类型二、行逻辑联接的顺序表二、行逻辑联接的顺序表0129000000000-3000140002400001800001500-700M=121213931-3351443245218611564-7668ije0 01 12 23 34 45 56 67 78 8row123456numrow2
38、02112rposrow133567例如：给定一组下标，求矩阵的元素值例如：给定一组下标，求矩阵的元素值ElemTypevalue(RLSMatrixM,intr,intc)p=M.rposr;/第第r行第一个非零值的位置行第一个非零值的位置while(M.datap.i=r&M.datap.ji=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-
39、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 forReturn Ok;/CreateSMtrix_OL418234输入：输入：m=4,n=31,1,32,2,52,3,44,1,82,1,7113217225rhead1rhead2rhead3rhead4chead1chead2chead33 0 0 50 -1 0 02 0 0 0矩阵相加
40、算法矩阵相加算法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.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
41、(pa-jpb-j)复制复制pb所指的结点赋值为所指的结点赋值为p；if(pre=NULL)A.rheadp-i=p;elsepre-right=p;p-right=pa;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;Elsep-down=hlp-j-down;hlp-j-down=p;h
42、lp-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 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 4
43、422 -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 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
44、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.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 广义表的定义广义表的定义广义表是线性表的推广，也称为列表（
45、广义表是线性表的推广，也称为列表（lists）广义表中元素既广义表中元素既可以是原子类型，也可以是列表。可以是原子类型，也可以是列表。记为：记为：LS=(a1,a2,，an)广义表名广义表名a1是表头是表头(Head）（a2,an）是表尾是表尾(Tail)1、定义：、定义：n n是表长是表长第一个第一个元素是表头元素是表头，而其余元素组成的，而其余元素组成的表表称为表称为表尾尾；所以任何一个非空表，表头可能是原子，也可能是所以任何一个非空表，表头可能是原子，也可能是列表；但列表；但表尾一定是列表。表尾一定是列表。约定：用小写字母表示原子类型，用约定：用小写字母表示原子类型，用大写字母大写字母表
46、示表示列表。列表。在广义表中约定：在广义表中约定：2、特点：、特点：1）次序性：）次序性：一个直接前驱和一个直接后继一个直接前驱和一个直接后继2）长度：）长度：表中表中最外层最外层包含元素个数包含元素个数3）深度：）深度：当广义表全部用原子代替后，表中括号的最大重数当广义表全部用原子代替后，表中括号的最大重数空表（空表（）的深度为）的深度为1，长度为，长度为0，原子的深度为，原子的深度为0.4）可递归：）可递归：自己可以作为自己的子表。自己可以作为自己的子表。例例E=(a,E)递归表的深度是无穷值，长度是递归表的深度是无穷值，长度是2。5）可共享）可共享: 可以为其它广义表所共享的表。可以为其
47、它广义表所共享的表。6 6）任何一个非空广义表）任何一个非空广义表 LS = ( 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
48、=3，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：求下列广义表的表头和表尾。求下列广义表的表头和表尾。GetTail(GetHead(a,b),(c,d)
49、（b）()()DABCeabcdA=(a,(b,A)例例3 3：试用图形表示下列广义表试用图形表示下列广义表. .（设设 代表原子，代表原子， 代表子表）代表子表） eD=(A,B,C)=(),(e),(a,(b,c,d)Aab的长度为的长度为3，深度为，深度为3的长度为的长度为2，深度为，深度为 深度括号的重数深度括号的重数结点的最大层数结点的最大层数广义表的抽象数据类型定义广义表的抽象数据类型定义ADTGList数据对象：数据对象：D=ei|i=1，2，n；n0；ei AtomSet或或ei Glist,AtomSet为某个数据对象为某个数据对象数据关系数据关系：R1=|ei-l，ei D
50、，2in基本操作：基本操作：InitGList(&L)操作结果操作结果：创建空的广义表：创建空的广义表LCreateGList(&L，S)初始条件初始条件：s是广义表的书写形式串是广义表的书写形式串操作结果操作结果：由：由s创建广义表创建广义表LDestroyGList(&L)初始条件初始条件：广义表：广义表L存在。存在。操作结果操作结果：销毁广义表：销毁广义表LCOpyGList(&T，L)初始条件初始条件：广义表：广义表L存在。存在。操作结果：操作结果：由广义表由广义表L复制得到广义表复制得到广义表TGListLength(L)初始条件初始条件：广义表：广义表L存在。存在。操作结果操作结果
51、：求广义表：求广义表L的长度，即元素个数。的长度，即元素个数。GListDepth(L)初始条件初始条件：广义表：广义表L存在。存在。操作结果操作结果：求广义表：求广义表L的深度。的深度。GListEmpty(L)初始条件初始条件：广义表：广义表L存在。存在。操作结果操作结果：判定广义表：判定广义表L是否为空。是否为空。GetHead(L)初始条件初始条件：广义表：广义表L存在。存在。操作结果操作结果：取广义表：取广义表L的头。的头。GetTail(L)初始条件初始条件：广义表：广义表L存在。存在。操作结果操作结果：取广义表：取广义表L的尾。的尾。InsertFirst_GL(&l，e)初始条
52、件初始条件：广义表：广义表L存在。存在。操作结果操作结果；插入元素；插入元素e作为广义表作为广义表L的第一元素。的第一元素。DeleteFirst_GL(&L，&e)初始条件初始条件：广义表：广义表L存在。存在。操作结果操作结果：删除广义表：删除广义表L的第一元素，并用的第一元素，并用e返回其值返回其值Traverse_GL(L，Visit()初始条件初始条件：广义表：广义表L存在。存在。操作结果操作结果；遍历广义标；遍历广义标L,用函数用函数visit处理每个元素。处理每个元素。ADTGList5.5 广义表的存储结构由于广义表的元素可以是不同结构（原子或列表），由于广义表的元素可以是不同结
53、构（原子或列表），难以用顺序存储结构表示，难以用顺序存储结构表示，通常用链式结构通常用链式结构，每个，每个元素元素用一个结点表示。用一个结点表示。1.1.原子结点原子结点2.2.表结点表结点注意：列表的注意：列表的“元素元素”还可以是列表，所以结点可能还可以是列表，所以结点可能有两种形式有两种形式方法方法1 1：表头、表尾表示法：表头、表尾表示法表结点表结点:原子结点：原子结点：5.5 广义表的存储结构valuetag=0标志域标志域数值域数值域tphptag=1标志域标志域表头指针表头指针表尾指针表尾指针A=()10eC=(a,(b,c,d)1110a0b0d0c11例例：B=(e)A=NU
54、LL15.5 广义表的存储结构E=(a,E)D=(A,B,C)=(),(e),(a,(b,c,d)0a1110e111110a0b0d0c1115.5 广义表的存储结构tpatomtag=0标志域标志域值域值域表尾指针表尾指针方法方法2 2：子表表示法：子表表示法指向下一结点指向下一结点tphptag=1标志域标志域表头指针表头指针表尾指针表尾指针表结点表结点:原子结点：原子结点：5.5 广义表的存储结构A=()1C=(a,(b,c,d)，e)1b00 a c0d0例例：B=(e)A=NULL1e01BCe0本章小结本章小结理解数组的理解数组的逻辑结构是线性结构的推广逻辑结构是线性结构的推广；
55、掌握数组在行优先存储和列优先存储结构中的地址计算掌握数组在行优先存储和列优先存储结构中的地址计算 方法方法( (注意我们所讲的公式前提是在数组各下界为注意我们所讲的公式前提是在数组各下界为0 0）掌握对特殊矩阵进行压缩存储时的下标变换公式；掌握对特殊矩阵进行压缩存储时的下标变换公式；理解理解稀疏矩阵的三种压缩存储方法的特点和适用范围稀疏矩阵的三种压缩存储方法的特点和适用范围，以三元组表示稀疏矩阵时进行矩阵转置所采用的处理方以三元组表示稀疏矩阵时进行矩阵转置所采用的处理方法；法；掌握广义表的定义、存储结构；掌握广义表的定义、存储结构；书面作业书面作业:p32:5.8题题,p33:5.10题，题，5.12题题p35:5.25题题上机作业上机作业:识别广义表的表头和表尾识别广义表的表头和表尾(p138)作作业业
