第五章-数组及广义表--WL.ppt

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第五章 数组和广义表,5.1 数组的定义,5.2 数组的顺序表示和实现,5.3 矩阵的压缩存储,5.3.1 特殊矩阵,5.3.2 稀疏矩阵,5.4 广义表的定义,5.5 广义表的存储结构,数组和广义表可看成是一种,特殊的线性表,:表中的数据元素本身也是一种线性表。,一、多维数组,1、多维数组是线性表的推广。例如，二维数组：,5.1 数组的定义,a,00,a,01,.,a,0m-1,a,10,a,11,a,1m-1,a,20,a,21,a,2m-1,.,.,.,.,.,.,.,.,a,n-10,a,n-11,a,n-12,.,a,n-1m-1,A,数组,A,可以看成是由,n,个行线性表组成的线性表，也可以看成是,m,个列线性表组成的线性表。,2、设二维数组的每行为一个数据元素，可用,A,i,表示,则二维数组可以表示为：,D=（A,1,，A,2,，A,3,，.，A,i,，.，A,n,),其中每个数据元素,A,i,可以表示成一个线性表,A,i,=(a,i-10,a,i-11,a,i-12,.,a,i-1j,a,i-1m,),设二维数组的每列为一个数据元素，可用,Bi,表示，则二维数组可以表示为：,D=（B,1,，B,2,，B,3,，B,i,，B,m,),其中每个数据元素,B,i,可以表示成一个线性表,Bi=(a,0i-1,a,1i-1,a,2i-1,，a,ji-1,，a,ni-1,),3、二维数组在,C,语言中的表示,一个二维数组类型可以定义为一维数组类型，但一维数组的每个数据元素也一个一维数组，就是说，,typedef,elemtype,array2mn;,等价于：,typedef elemtype,array1n;,typedef,array1 array2m;,同理，一个,n,维数组类型可以定义为其数据元素为,n-1,维数组类型的一维序组类型。,数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有,存取元素,和,修改元素值,的操作。,二、数组的抽象类型定义(,P90),ADT Array,数据对象：.,数据关系：,数据操作：,.,.,ADT Array,一、内存结构,由于计算机的,内存结构是一维,的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。,又由于对数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采,用顺序存储的方法来表示数组,。,5.2 数组的顺序表示和实现,二、多维数组的顺序存储方式,按行顺序,将数组元素按行排列，第,i+1,个行线性表紧接在第,i,个行线性表后面。以二维数组为例，按行优先顺序存储的线性序列为：,a,11,a,12,a,1n,a,21,a,22,a,2n,a,m1,a,m2,a,mn,在,PASCAL、C,语言中，数组按行顺序存储。,按列顺序,将数组元素按列向量排列，第,j+1,个列线性表紧接在第,j,个列性线表之后，,A,的,m*n,个元素按列优先顺序存储的线性序列为：,a,11,a,21,a,m1,a,12,a,22,a,m2,a,nm,a,nm,a,n,m,在,FORTRAN,语言中，数组就是按列顺序存储的。,内存单元,数组元素,地址,10,A00,F000,20,A01,F002,40,A02,F004,45,A03,F006,67,A04,F008,66,A10,F00A,78,A11,F00C,。,。,。,89,A23,F01C,98,A24,F01E,66,A30,F020,68,A31,F022,56,A32,F024,34,A33,F026,25,A34,F028,0行,1行,2行,3行,二维数组,A45,的物理存储,以上规则可以推广到多维数组的情况：按行存储可规定为先排,最右,的下标，从右到左，最后排最左下标：按列存储与此相反，先排,最左,下标，从左向右，最后排最右下标。,只要知道,开始结点,的存放地址（即基地址），维数和每维的,上、下界,，以及每个数组元素所占用的单元数，就可以将数组元素的存放地址表示为其下标的线性函数。数组是一个随机存取结构。,二、数组元素地址的计算,设二维数组,A,mn,按“,行优先顺序,”存储在内存中，假设每个元素占用,d,个存储单元。,a,00,a,01,.,a,0m-1,a,10,a,11,a,1m-1,a,20,a,21,a,2m-1,.,.,.,.,.,a,ij,.,.,.,.,.,.,.,a,n-10,a,n-11,.,.,a,n-1m,i-1,i,j-1,j,m*d,i*m*d,j*d,loc(a,ij,)=loc(a,00,)+i*m*d+j*d,说明：,元素,a,ij,的存储地址应是数组的基地址加上排在,a,ij,前面的元素所占用的单元数。,因为,a,ij,位于第,i,行、第,j,列，前面,i-1,行一共有,im,个元素，第,i,行上,a,ij,前面又有,j,个元素，故它前面一共有,im+j,个元素，因此，,a,ij,的地址计算函数为：,LOC(a,ij,)=LOC(a,00,)+(i*m+j)*d,同样，三维数组,A,mnp,按“行”存储，其地址计算函数为：,LOC(a,ijk,)=LOC(a,000,)+(i*n*p+j*p+k)*d,i*n*k,前,i,面的元素个数,j*p,第,i,面前,j,行元素,更一般的二维数组是,Ac,1,.d,1,c,2,.d,2,，,这里,c,1,c,2,不一定是1。,a,ij,前一共有,i-c,1,行，二维数组一共有,d2-c2+1,列，故这,i-c,1,行共有,(,i-c,1,)*(d,2,-c,2,+1),个元素，第,i,行上,a,ij,前一共有,j-c,2,个元素，因此，,a,ij,的地址计算函数为：,LOC(,a,ij,)=,LOC(a,c,1,c,2,)+(i-c,1,)*(d,2,-c,2,+1)+j-c,2,)*d,设数组各维下标的下界是0，则，二维数组的地址计算公式为：,LOC(,a,ij,)=LOC(a,00,)+(i*(d,2,+1)+j)*d,矩阵是数学问题中常研究的数学对象。常用二,维数组表示矩阵。此时，,可以对矩阵元素进行随机存取，各种矩阵运算也非常简单，并且存储的密度为1,。,但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下。许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪费，为了节省存储空间，我们可以对这类矩阵进行压缩存储：,即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。,5.3 矩阵的压缩存储,所谓,特殊矩阵,是指非零元素或零元素的分布有一定规律的矩阵，下面我们讨论几种特殊矩阵的压缩存储。,1、对称矩阵,在一个,n,阶方阵,A,中，若元素满足下述性质：,a,ij,=,a,ji,0i,jn-1,则称,A,为,对称矩阵,。如图5.1便是一个5阶对称矩阵。,对称矩阵中的元素关于,主对角线,对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。,5.3.1特殊矩阵,可以“,按行存储,”主对角线（包括对角线）以下的元素，其存储形式如图所示：,1 5 1 3 7,a,00,5 0 8 0 0 a,10,a,11,1 8 9 2 6 a,20,a,21,a,22,3 0 2 5 1 .,7 0 6 1 3 a,n-1 0,a,n-1 1,a,n-1 2,a,n-1 n-1,图 5.1 对称矩阵,在这个下三角矩阵中，第,i,行恰有,i+1,个元素，元素总数为：,(,i+1)=n(n+1)/2,因此，我们可以按图中箭头所指的次序将这些元素存放在一个向量,sa,0.n(n+1)/2-1,中。为了便于访问对称矩阵,A,中的元素，我们必须在,a,ij,和,sa,k,之间找一个对应关系。,若,ij，,则,a,i,j,在下三角形中。,a,i,j,之前的,i,行（从第0行到第,i-1,行）一共有1+2+,i=i(i+1)/2,个元素，在第,i,行上，,a,i,j,之前恰有,j,个元素（即,a,i0,a,i1,a,i2,a,ij,-1,），,因此有：,k=i*(i+1)/2+j 0kn(n+1)/2,若,ij，,则,a,ij,是在上三角矩阵中。因为,a,ij,=,a,ji,，,所以只要交换上述对应关系式中的,i,和,j,即可得到：,k=j*(j+1)/2+i 0 kn(n+1)/2,令,I=max(i,j)，J=min(i,j)，,则,k,和,i,j,的对应关系可统一为：,k=I*(I+1)/2+J 0 kn(n+1)/2,因此，,a,ij,的地址可用下列式计算：,LOC(,a,ij,)=LOC(,sa,k),=LOC(,sa,0)+k*d=LOC(,sa,0)+I*(I+1)/2+J*d,有了上述的下标交换关系，对于任意给定一组下标,(,i，j)，,均可在,sa,k,中找到矩阵元素,a,ij,，,反之，对所有,的,k=0,1,2,n(n-1)/2-1，,都能确定,sa,k,中的元素在矩阵中的位置(,i,j)。,由此，称,sa,n(n+1)/2,为阶对称矩阵,A,的压缩存储，见下图：,k=0 1 2 3 n(n-1)/2 n(n-1)/2-1,例如,a,21,和,a,12,均存储在,sa,4,中，这是因为,k=I*(I+1)/2+J=2*(2+1)/2+1=4,a,00,a,10,a,11,a,20,a,n-1 0,a,n-1,n-1,2、三角矩阵,以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵如图所示，它的下三角（不包括主对角线）中的元素均为常数。下三角矩阵正好相反，它的主对角线上方均为常数，如图所示。在大多数情况下，三角矩阵常数为零。,a,00,a,01,a,0 n-1,a,00,c c,c a,11,a,1 n-1,a,10,a,11,c,.,c c a,n-1 n-1,a,n-1 0,a,n-1 1,a,n-1 n-1,(a),上三角矩阵 (,b),下三角矩阵,图5.2 三角矩阵,三角矩阵中的重复元素,c,可共享一个存储空间，其余的元素正好有,n(n+1)/2,个，因此，三角矩阵可压缩存储到向量,sa,0.n(n+1)/2,中，其中,c,存放在向量的最后一个分量中，,上三角矩阵中，主对角线之上的第,p,行(0,pj,k=,下三角矩阵的存储和对称矩阵类似，,sa,k,和,a,ij,对应关系是：,i(i+1)/2+j ij,n(n+1)/2 ij,3、,对角矩阵,对角矩阵中，所有的非零元素集中在以主对角线为了中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。下图给出了一个三对角矩阵，,a,00,a,01,a,10,a,11,a,12,a,21,a,22,a,23,.,图5.3 对角矩阵,a,n-2 n-3,a,n-2 n-2,a,n-2 n-1,a,n-1 n-2,a,n-1 n-1,k=,非零元素仅出现在主对角,(,a,ii,0in-1),上，紧邻主对角线上面的那条对角线上,(,a,ii,+1,0in-2),和紧邻主对角线下面的那条对角线上,(,a,i,+1i,0in-2)。,显然，当,i-j1,时，元素,a,ij,=0。,由此可知，一个,k,对角矩阵(,k,为奇数),A,是满足下述条件的矩阵：若,i-j(k-1)/2，,则元素,a,ij,=0。,对角矩阵可,按行优先顺序,或,对角线的顺序,，将其压缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。,数组,sa,中的元素,sa,k,与三对角带状矩阵中的元素,a,ij,存在一一对应关系，在,a,ij,之前有,i,行,共有,3*,i-1,个非零元素，在第,i,行，有,j-i+1,个非零元素，这样，非零元素,a,ij,的地址为：,在三对角矩阵里附满足条件,i=0，j=0、1,，,或,i=n-1,j=n-2、n-1,或,1,in-1,j=i-1、i、i+1,的元素,a,ij,外，其余元素都是零。,对这种矩阵，我们也可,按行优序,为主序来存储。除第0行和第,n-1,行是2个元素外，每行的非零元素都要是3个，因此，需存储的元素个数为3,n-2。,a,n-1 n-1,a,n-1 n-2,a,21,a,12,a,11,a,10,a,01,a,00,K=0 1 2 3 4 5 3n-4 3n-3,LOC(i,j)=LOC(0,0)+3*i-1+(j-i+1)*d,=LOC(0,0)+(2i+j)*d,上例中，,a,34,对应着,sa,10。,k=2*i+j=2*3+4=10,a,21,对应着,sa,5,k=2*2+1=5,由此，我们称,sa,0.3*n-3,是阶三对角带状矩阵,A,的压缩存储表示。,前面提到的矩中，其非零元素的分布都是有规律的，因此总能,找到一种方法将它们压缩存储到一个向量中,，并且一般都能,找到矩阵中的元素与该向量的对应关系,，通过这个关系，仍能对矩阵的元素进行随机存取。,5.3.2 稀疏矩阵,什么是,稀疏矩阵,？简单说，设矩阵,A,中有,s,个非零元素，若,s,远远小于矩阵元素的总数（即,smn），,则称,A,为,稀疏矩阵,。,0,0,1,0,0,0,-1,0,0,0,0,3,0,0,0,2,0,0,0,0,4,0,0,0,1,0,0,0,0,3,0,0,0,1,2,0,设在的矩阵,A,中，有,s,个非零元素。令,e=s/(m*n)，,称,e,为矩阵的,稀疏因子,。通常认为,e0.05,时称之为稀疏矩阵。在存储稀疏矩阵时，为了节省存储单元，很自然地想到使用,压缩存储方法,在存储稀疏矩阵时：,由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须同时记下它所在的,行和列的位置（,i,j),。,这样，一个,三元组,(,i,j,a,ij,),唯一确定了矩阵,A,的一个非零元。因此，稀疏矩阵可由表示,非零元、行和列的三元组及其行数与列数,唯一确定。,0,0,1,0,0,0,-1,0,0,0,0,3,0,0,0,2,0,0,0,0,4,0,0,0,1,0,0,0,0,3,0,0,0,1,2,0,如以下矩阵的三元组表示为：,（0,2,1),(1,0,-1),(1,5,3),(2,3,2),(3,2,4),(4,0,1),(4,5,3),(5,3,1),(5,4,2),假设以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方法,三元顺序表,。,#,define,MaxSize,10000,typedef int DataType,;,typedef struct,/,一个元素,int,i,j;,DataType,v;,triple;,typedef struct /,一个稀疏矩阵,triple dataMaxSize;,int m,n,t;,TripleTable;,一、三元组顺序表,0,0,1,0,0,0,-1,0,0,0,0,3,0,0,0,2,0,0,0,0,4,0,0,0,1,0,0,0,0,3,0,0,0,1,2,0,如以下矩阵的三元组表示为：,0,2,1,1,0,-1,1,5,3,2,3,2,3,2,4,4,1,1,4,5,3,5,3,1,5,4,2,实例：矩阵转置,一个,mn,的矩阵,A，,它的转置,B,是一个,nm,的矩阵，且,aij=bji，0im，0jn，,即,A,的行是,B,的列，,A,的列是,B,的行。,将,A,转置为,B，,就是将,A,的三元组表,a.data,置换为表,B,的三元组表,b.data，,如果只是简单地交换,a.data,中,i,和,j,的内容，那么得到的,b.data,将是一个按,列优先顺序存储,的稀疏矩阵,B，,要得到按行优先顺序存储的,b.data，,就必须,重新排列,三元组的顺序。,由于,A,的列是,B,的行，因此，,按,a.data,的列序转置，所得到的转置矩阵,B,的三元组表,b.data,必定是按行优先存放的。,算法基本思想是,：,对,A,中的,每一列,col,(0,col,n-1)，,通过从头至尾扫描三元表,a.data，,找出所有列号等于,col,的那些三元组，将它们的行号和列号互换后依次放入,b.data,中，即可得到,B,的按行优先的压缩存储表示。,0,2,1,1,0,-1,1,5,3,2,3,2,3,2,4,4,1,1,4,5,3,5,3,1,5,4,2,0,1,1,1,4,1,2,0,1,2,3,4,3,2,2,3,5,1,4,5,2,5,1,3,5,4,3,void,transmatrix,(,TripleTable,a,TripleTable,b),int,p,q,col,;,b.m=a.n;b.n=a.m;/b,的行列即是,a,列行,b.t=a.t;/,非0元个数,if(b.t=0),printf,(“A=0n”);/,显示矩阵为0矩阵,q=0;/b,中的第一个非零元的下标,for(col=0;cola.n;col+),for(p=0;pa.t;p+)/,在线性表中扫描,if(a.datap.j=col)/,如果找到相应列,b.dataq.i=a.datap.j;/,得到,b,的一个元素,b.dataq.j=a.datap.i;,b.dataq.v=a.datap.v;,q+;/,准备下一个元素,分析这个算法的效率：,由于主要的工作是在,p,和,col,的两个循环中完成的，故算法的时间复杂度为,O(n*t),，,即矩阵的列数和非零元的个数的乘积成正比。而一般传统矩阵的转置算法为：,for(,col,=0;,col,n;+,col,),for(row=0;rowm;+row),t,col,row=mrow,col,;,其时间复杂度为,O(n*m)。,当非零元素的个数,t,和,m*n,同数量级时，算法,transmatrix,的时间复杂度为,O(n*n,2,)。,注,：三元组顺序表虽然,节省了存储空间,，但时间复杂度比一般矩阵转置的算法还要复杂，同时还有可能增加算法的难度。因此，此算法仅适用于,t=m*n,的情况。,改进：,快速转置的算法,，其算法思想为：对,A,扫描一次，按,A,第二列提供的列号一次确定位置装入,B,的一个三元组。具体实施如下：,一遍扫描先确定三元组的位置关系，二次扫描由位置关系装入三元组,。可见，位置关系是此种算法的关键。,（1）需要先求得矩阵,M,中的,每一列,中非零元素的个数。因为：矩阵,M,中,第,i,列,的第一个非零元素在数组,B,中序号(,X,i1,),等于,第,i-1,列,第一个非零元素的序号(,X,i-11,加上该列非零元素的个数（,n,i-1,)。,即:,X,i1,=X,i-11,+n,i-1,为此，需要设置两个一维数组,num0.n,:,统计,M,中每列非零元素的个数，,numcol,的值可以由,A,的第二列求得。,cpot0.n,:,由递推关系得出,M,中的每列第一个非零元素在,B,中的位置。即：,cpotcol=cpotcol-1+numcol-1,算法通过,cpot,数组建立位置对应关系：,cpot,1=1,cpot,col,=,cpot,col,-1+num,col,-1,2=,cpl,=a.n,例如：上例中的矩阵,M,和相应的三元组,A,可以求得,num,col,和,cpot,col,的值如下：,col 0,1 2 3 4 5,num,col,1 1 2 2 1 2,cpot,col,1 2 3 5 7 8,0,2,1,1,0,-1,1,5,3,2,3,2,3,2,4,4,1,1,4,5,3,5,3,1,5,4,2,i,0,1,2,3,4,5,num(i),1,1,2,2,1,2,cpot(i),0,1,2,4,6,7,3,1,0,2,-1,1,0,5,1,3,1,5,8,2,2,3,4,3,2,4,1,4,1,2,3,4,5,9,1,5,3,6,2,5,4,7,快速转置算法如下：,void,fasttranstri,(,TritupleTable&b,TritupleTable,a),int,p,q,col,k;,int,num0.a.n,cpot,0.a.n;,b.m=a.n;b.n=a.m;b.t=a.t;/,得,b,中的列,m,行,n,即元素个数,if(b.t=0),printf,(a=0n);/,是0矩阵,for(,col,=0;,col,a.n;+,col,)/,初始化,col,列的非0元个数,num,col,=0;,for(k=0;ka.t;+k)/,计算每列的元素个数,+numa.datak.j;,cpot0=0;/,第0个元素的位置从0开始,for(col=1;cola.n;+col)/,计算每列的1个非0元的位置,cpotcol=cpotcol-1+numcol-1;,for(p=0;pa.t;+p),col=a.datap.j;q=cpotcol;/q,为第,col,列的首序号,b.dataq.i=a.datap.j;,b.dataq.j=a.datap.i;,b.dataq.v=a.datap.v;,+cpotcol;/col,列的下一个元素的位置,/for,/end,有时为了方便某些矩阵运算，我们在,按行优先,存储的三元组中，加入一个行表来记录稀疏矩阵中每行的非零元素在三元组表中的起始位置。当将行表作为三元组表的一个新增属性加以描述时，我们就得到了稀疏矩阵的另一种顺序存储结构：,带行表的三元组表,。其类型描述如下：,二、带行表的三元组,#,define,MaxRow,100,typedef struct,triple data,MaxSize,;,int rpos,MaxRow,;,/,某行第一个非0元的位置,int,n,m,t;,RtripleTable,下面,讨论两个稀疏矩阵相乘的例子，容易看出这种表示方法的优越性。,两个矩阵相乘：,若设,Q=M*N,其中，,M,是,m,1,*n,1,矩阵，,N,是,m2*n,2,矩阵。,当,n,1,=m,2,时有：,for(i=1;i=m1;+i),for(j=1;j=n2;+j),qij=0;,for(k=1;k=n1;+k),qij+=mik*nkj;,此算法的复杂度为,O(m,1,*n,1,*n,2,)。,当,M,和,N,是稀疏矩阵并用三元组表存储结构时，就不能套用上述算法。假设,M,和,N,分别为：,0 0 5,0 -1 0 0,2 0 0 0,M=,0 2,1 0,-2 4,0 0,N=,则,Q=M*N,为：,0 6,-1 0,0 4,Q=,它们的三元组、和分别为：,2,0,2,-1,1,1,5,3,0,3,0,0,M,4,1,2,-2,0,2,1,0,1,2,1,0,N,4,1,2,-1,0,1,6,1,0,Q,稀疏矩阵相乘的基本思想,：,对于,M,中每个元素,M,ik,，,找到,N,中所有满足条件的元素,N,kj,，,求得和的乘积，而乘积矩阵,Q,中每个元素的值是个累加和，这个乘积只是其中的一部分。,为了便于操作，应对每个元素设一累加和的变量，其初值为零，然后扫描数组,M，,求得相应元素的乘积并累加到适当的求累计和的变量上。,稀疏矩阵相乘算法,设,CTemp0.n-1,用来存储,结果矩阵,C,中某行所有元素计算相乘相结果，如当计算,C,的第,i,行时，,CTemp,的值为,0，0，10，0，0，20,表示计算出的,C,中第,i,行有,Ci2,与,Ci5,两个非0元素。,（1）初始化,CTemp,为0值,（2）计算,C,的第,i,行的值并放到,CTemp,中,i),在,A,中找第,i,行的一个元素，下标,p=,rpos i,ii),B,中可与之相乘的行号为,Ap,的列号，即,k=Ap.j,iii),对于,Ap，,按,k,在,B,中找到所有可以相乘的元素,Bj，,把乘积加到,Ctempi,中,即：,Ctempj+=Ap.data*Bj.data,iV),如果第,i,行未处理(,irposi+1，,转,i),（3）把,CTemp,中的非0元素写入到,C,中,(4)如果,I,的值不超过,m-1,则,i+1,i,转（1）,（5）,算法结束,2,0,2,-1,1,1,5,3,0,3,0,0,M,4,1,2,-2,0,2,1,0,1,2,1,0,N,0,0,ctemp,Q,0,0,ctemp,0,ctemp,6,-1,1,0,-1,0,1,6,0,4,2,1,4,i=0,i=1,i=2,void,MultsMatrix,(,RtripleTable,a,RtripleTable,b,RtripleTable,c),if(a.n!=b.m)/,不能相乘,printf,(errorn);exit(0);,c.m=a.m;c.n=b.n;c.t=0;,if(a.t*b.t!=0)/if-1,for(,arow,=0;,arow,a.m;+,arow,)/for-1,ctemp,arow,=0;,c.rposarow=c.t+1;,for(p=a.rposarow;pa.rposarow+1;+p)/for-2,brow=a.datap.j;/a,的第,p,行的元素的列坐标对应,b,的行,if(browb.t)t=b.rposbrow+1;/t,为,b,中第,brow+1,首元地址,else t=b.t+1;,for(q=b.rposbrow;qt;+q)/for-3，b,中的,brow,行,ccol=b.dataq.j;/b,中,brow,行中元素的坐标,ctempccol+=a.datap.v*b.dataq.v;/,计算,/for-3,/for-2,for(,ccol,=0;,ccol,MaxSize,)/if-3,下标越界,exit(0);,c.datac.t=,arow,ccol,ctemp,ccol,;,/if-2,/for-1,/if-1,/end,typedef struct,node,int,col,;,int val,;,struct,node *next;,TNode;,typedef struct,node *TD;,1 3,5 7,3 -1,1 -1,2 -2,4 2,需存储单元个数为3,t+m,四、链式存储结构,（1）带行指针向量的单链表表示,（2）每行的非零元用一个单链表存放,（3）设置一个行指针数组，指向本行第一个非零元结点；若本行无非零元，则指针为空,表头结点与单链表结点类型定义,tpedef struct,node,int,row,col,val,;,struct,node *down,*right;,TNode;,row,col,val,down,right,1,1,3,4,1,8,2,2,5,2,3,4,五、十字链表,设行指针数组和列指针数组，分别指向每行、列第一个非零元结点定义。,算法分析：,T(n)=o(t,s),其中：,t,非零元个数,s=max(m,n),r,个表示行，,c,表示列,令,q=NULL,p=,rh,r-1,q,总是在,p,之前,（1）,寻找插入位置：,当,p!=NULL,且,cp-,col,时，,p,和,q,右移,（2）插入：,a、,若,p=NULL,且,q=NULL，,即本行空,，则,rh,r-1=s;,b、,若,p=NULL,q!=NULL，,即走到行末，则,q-right=s,c、,若,c=p-,col,，,则修改,p-,val,d、,若,c,col,且,q=NULL，,则在,p,之前插入,s，,即,s,是行链表中,第一个结点，令,rh,r-1=s;s-right=p;,e、,若,c,col,且,q!=NULL，,则在,p,之前,q之后,插入,s，,即,s-right=p;q-right=s;,从键盘接收信息建立十字链表算法,4,1,8,2,3,4,m=4,n=3,1,1,3,2,2,5,2,3,4,4,1,8,2,1,7,1,1,3,2,1,7,2,2,5,5.4 广义表的定义,一、基本概念,广义表是,n(n=0),个元素,a,1,a,2,a,3,a,n,的有限序列，,其中,a,i,或者是原子项，或者是一个广义表,。通常记作,LS=（a,1,a,2,a,3,a,n,)。LS,是广义表的名字，,n,为它的长度。若,a,i,是广义表，则称它为,LS,的子表。,如：广义表,LS,LS=(a1,a2,a3,a4,an),a1=(b1,b2,b3),a4=(k1,k2,k3),表头：,若广义表,LS,非空，则,a,1,是,LS,的表头。,表尾：,其余元素组成的表,（,a,1,a,2,a,n,）,称为,LS,的表尾。,例：,head(L)=a tail(L)=(b),head(B)=A tail(B)=(y),head(tail(L)=b tail(tail(L)=(),注:()和()不同,前者是空表,长度为0;后者是有一个,元素的空表,长度为1,表的深度:,是指表展开后所含号的层次.,例如,表,A,的深度为2,表,D,的深度为.,例：,E=(),长度为0，空表,L=(a,b),长度为2，两个原子,A=(x,L)=(x,(a,b),长度为2，一个原子，一个子表,B=(A,y)=(x,(a,b),y),长度为2，一个子表，一个原子,C=(A,B)=(x,(a,b),(x,(a,b),y),长度为2，两个列表,D=(a,D)=(a,(a,(a,(),长度为2，是无限列表,三个重要结论：,（1）列表的元素可以是子表，而列表的元素还可以是子表，。,（2）列表可为其它列表所共享。,（3）列表可以是一个递归的表，即列表也可以是其本身的一个子表。,各种广义表的例子,二、广义表的表示,只包括整数和字符型数据的广义表链表表示,表中套表情形下的广义表链表表示,1、广义表结点定义,（1）标志域,utype,表明结点类型。,0,为表头结点，,1,为整型原子结点，,2,为字符型原子结点，,3,为子表结点。,（2）值域,value,。,当,utype,=0,时为,表引用计数,，=1时为,整数值,，=2 时为,字符值,，=3 时为,指向子表的表头结点的指针,。,（3）尾指针域,tlink,。,当,utype,=0,时为指向该表表头元素的指针；当,utype,0,时为指向同一层下一个表结点的指针。,utype,=0/1/2/3,value=ref,/,intgrinfo,/,charinfo,/,hlink,tlink,2、广义表的带表头结点的存储表示,3.广义表的数据类型,typedef struct GListNode,int,utype,;,struct GListNode*tlink,;,union,int,ref,;/,utype,=0,表头结点,int,intgrinfo,;/,utype,=1,整型,char,charinfo,;/,utype,=2,字符型,struct GListNode*hlink,;,/,utype,=3,子表结点,value;,GenListNode;,GenLiistNode *first;/,定义广义表首指针,4.广义表的访问算法,（2）,提取广义表中指定表元素,elem,的值,GenListNode,Info,(,GenListNode,*,elem,),GenListNode*,pitem,;,pitem=(,GenListNode*)malloc(sizeof(GenListNode),;,pitem,utype,=,elem,utype,;,pitem,value,=,elem,value,;,return,*,pitem,;,(1),广义表的初始化,InitGenList,(),GenListNode,*,first,；,first=(,GenListNode,*)malloc(sizeof(GenListNode);,first,utype,=0,;,first,ref,=1,;,first,tlink,=,NULL,;/,仅建立表头结点,(3)将表元素,elem,中的值修改为,x,void,setInfo,(,GenListNode,*,elem,GenListNode,*,x,),elem,utype,=,x,utype,;,elem,value,=,x,value,;,(4)返回表的表头元素的指针,GenListNode,*GetHead,(,),if,(,first,tlink,=NULL,),/,空表,cout,“,无效的,head,操作.”,endl,;,exit,(1),;,else,GenListNode,*,temp,;,temp=(,GenListNode*)malloc(sizeof(GenListNode),;,temp,utype,=,frist,tlink,utype,;,temp,value,=,frist,tlink,value,;,return,temp,;,(5),取表尾,GenListNode,*,Tail,(,),/,若广义表非空，返回广义表除表头元素外其,/它元素组成的表，否则函数没有定义,if,(,first,tlink,=NULL,),/,空表,cout,“,无效的,Tail,操作.”,endl,;,exit,(1),;,else,GenListNode,*,temp,；,temp=(,GenListNode,*)malloc(sizeof(GenListNode);,temp,frist,tlink,=,frist,tlink,tlink,;,return,*,temp,;,（6）将表结点,x,加到表的最前端,void,Push,(,GenListNode,*,x,),if,(,first,tlink,=NULL,),first,tlink,=,x,;,else,x,tlink,=,first,tlink,;,first,tlink,=,x,;,