数据结构演示文稿精品文稿.ppt

数据结构演示文稿第1页，本讲稿共53页第2页，本讲稿共53页 5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.3.1 特殊矩阵 5.3.2 稀疏矩阵 5.4 广义表的定义。5.5 广义表的存储结构第3页，本讲稿共53页 5.1 数组的定义数组的定义 例如，二维数组：|a11 a12 a1n|AmXn =|a21 a22 a2n|am1 am2 amn|可以看成是由m个行向量组成的向量，也可以看成是n个列向量组成的向量。由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单。多维数组是向量的推广。1、类型相同的有限个元素的序列，叫数组。第4页，本讲稿共53页在C语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型，也就是说，typedef elemtype array2mn;等价于：typedef elemtype array1n;typedef array1 array2m;同理，一个维数组类型可以定义为其数据元素为维数组类型的一维序组类型。数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。第5页，本讲稿共53页 5.2 数组的顺序表式和实现数组的顺序表式和实现1、数组是采用顺序方式存贮设第 0 号元组的地址为 a，元素的长度为 L l0 1 2 i n-2 n-1(长度为n)一维数组任一元素的地址LOC(i)ail行号：0 1 j n-1l列号：0 1 2 k m-1二维数组任一元素的地址LOC(j,k)a(jmk)l通常有两种顺序存储方式：1、行优先顺序2、列优先顺序第6页，本讲稿共53页1、行优先顺序 将数组元素按行排列，第i+1个行向量紧接在第i个行向量后面。以二维数组为例，按行优先顺序存储的线性序列为：a11,a12,a1n,a21,a22,a2n,am1,am2,amn在PASCAL、C语言中，数组就是按行优先顺序存储的。列优先顺序将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后，A的m*n个元素按列优先顺序存储的线性序列为：a11,a21,am1,a12,a22,am2,an1,an2,anm在FORTRAN语言中，数组就是按列优先顺序存储的。第7页，本讲稿共53页5.3 矩阵的压缩存储1.压缩存储：为多个值相同的元素只分配一个存储空间；对0元素不分配空间。2.特殊矩阵假若值相同的元素或者0元素在矩阵中的分布有一定的规律，既为特殊矩阵。反之，称为稀疏矩阵。第8页，本讲稿共53页1、对称矩阵在一个n阶方阵A中，若元素满足下述性质：aij=aji 0i,jn-1则称A为对称矩阵。5.3 矩阵的压缩存储5.3.1特殊矩阵若所有元素都保存，则需要n2个存储空间。若采用压缩存储只需n(n+1)/2个元素的存储空间。1 5 1 3 7 a00 5 0 8 0 0 a10 a 11 1 8 9 2 6 a20 a21 a23 3 0 2 5 1 .7 0 6 1 3 an-1 0 a n-1 1 a n-1 2 a n-1 n-1 图 5.1 对称矩阵第9页，本讲稿共53页an-1 0an-1 1an-1 2 an-1 n-1 480963lastn=8n(n-1)/2 .n(n+1)/2a00a10a11a20a21a22a30 0 1 2 3 4 5 6 在这个下三角矩阵中，第i行恰有i+1个元素，元素总数为：1+2+3+(i+1)+n=n(n+1)/2因此，我们可以按图中箭头所指的次序将这些元素存放在一个向量sa0.n(n+1)/2-1中。为了便于访问对称矩阵A中的元素，我们必须在aij和sak之间找一个对应关系。若ij，则ai j在下三角形中。ai j之前的i行（从第0行到第i-1行）一共有1+2+i=i(i+1)/2个元素，在第i行上，ai j之前恰有j个元素（即ai0,ai1,ai2,aij-1），因此有：k=i*(i+1)/2+j 0kn(n+1)/2 第10页，本讲稿共53页 若ij，则aij是在上三角矩阵中。因为aij=aji，所以只要交换上述对应关系式中的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 因此，aij的地址可用下列式计算：LOC(aij)=LOC(sak)=LOC(sa0)+k*d=LOC(sa0+I*(I+1)/2+J*d 有了上述的下标交换关系，对于任意给定一组下标(i，j)，均可在sak中找到矩阵元素aij，反之，对所有的k=0,1,2,n(n-1)/2-1，都能确定sak中的元素在矩阵中的位置(I,j)。由此，称san(n+1)/2为阶对称矩阵A的压缩存储，第11页，本讲稿共53页例如a21和a12均存储在 sa4中，这是因为 k=I*(I+1)/2+J=2*(2+1)/2+1=42、三角矩阵|a00 a01 a 0 n-1|a00 c c|c a11 a 1 n-1|a10 a11 c|.|.|c c a n-1 n-1|an-1 0 an-1 1 an-1 n-1|(a)上三角矩阵 (b)下三角矩阵 图5.2 三角矩阵三角矩阵中的重复元素c可共享一个存储空间第12页，本讲稿共53页其余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到向量sa0.n(n+1)/2中，其中c存放在向量的最后一个分量中.上三角矩阵中，主对角线之上的第p行(0pj第13页，本讲稿共53页下三角矩阵的存储和对称矩阵类似，sak和aij对应关系是：k=i(i+1)/2+j ij k=n(n+1)/2 ij3、对角矩阵对角矩阵中，所有的非零元素集中在以主对角线为了中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。下图给出了一个三对角矩阵，a00 a01 a10 a11 a12 a21 a22 a23 .图5.3 对角矩阵 an-2 n-3 an-2 n-2 an-2 n-1 an-1 n-2 an-1 n-1第14页，本讲稿共53页非零元素仅出现在主对角(aii,0in-1上，紧邻主对角线上面的那条对角线上(aii+1,0in-2)和紧邻主对角线下面的那条对角线上(ai+1 i,0in-2)。显然，当i-j1时，元素aij=0。由此可知，一个k对角矩阵(k为奇数)A是满足下述条件的矩阵：若i-j(k-1)/2，则元素 aij=0。对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。在三对角矩阵里附满足条件i=0，j=0、1，或i=n-1j=n-2、n-1或1i求矩阵转置若MmXn转置 NnXm 且 Ni,j=Mj,i 1=i =n 1=j =m显然一个稀疏矩阵的转置仍是稀疏矩阵假设M和T是tripletabletripletable型变量，如何由型变量，如何由M M求求T T从分析可知：（1）将矩阵的行列值交换；（2）将每个三元组中的I和J交换；（3）重排三元组之间的次序以便可实现矩阵转置；有两种处理方法：一种按T.DATA中的三元组转置；另一种按M.DATA中的三元组的次序转置；第22页，本讲稿共53页void transmatrix(tripletable M,tripletable T)T.mu=M.nu;T.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.v=M.datap.e;q+;return OK;1.按T.DATA转置第23页，本讲稿共53页分析这个算法，主要的工作是在p和col的两个循环中完成的，故算法的时间复杂度为O(n*t)，即矩阵的列数和非零元的个数的乘积成正比。而一般传统矩阵的转置算法为：for(col=0;col=n-1;+col)for(row=0;row=m;+row)tcolrow=mrowcol;其时间复杂度为O(n*m)。当非零元素的个数t和m*n同数量级时，算法transmatrix的时间复杂度为O(n*nu2)。第24页，本讲稿共53页因此，此算法仅适用于t=m*n的情况。2.2.另外一种称之为快速转置的算法另外一种称之为快速转置的算法 其算法思想为：对A扫描一次，按A第二列提供的列号一次确定位置装入B的一个三元组。具体实施如下：一遍扫描先确定三元组的位置关系，二次扫描由位置关系装入三元组。可见，位置关系是此种算法的关键。第25页，本讲稿共53页为了预先确定矩阵M中的每一列的第一个非零元素在数组B中应有的位置，需要先求得矩阵M中的每一列中非零元素的个数。因为：矩阵M中第一列的第一个非零元素在数组B中应有的位置等于前一列第一个非零元素的位置加上前列非零元素的个数。为此，需要设置两个一维数组num0.n和cpot0.n num0.n：统计M中每列非零元素的个数，numcol的值可以由A的第二列求得。第26页，本讲稿共53页 1 2 vqA i j v第一列元素个数 第二列元素个数 第三列元素个数numcpotq=cpotcol2 1 vpp第27页，本讲稿共53页cpot0.n：由递推关系得出M中的每列第一个非零元素在B中的位置。算法通过cpot数组建立位置对应关系：cpot1=1 cpotcol=cpotcol-1+numcol-1 2=cpl=a.n 例如：图5.4中的矩阵M和相应的三元组A可以求得numcol和 cpotcol的值如下：col 1 2 3 4 5 6 7 numcol 2 2 2 1 0 1 0 cpotcol 1 3 5 7 8 8 9第28页，本讲稿共53页快速转置算法如下：void fasttranstri(tritupletable M,tritupletable&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(t=1;t=M.tu;+t)+numM.datat.j;cpot1=1;for(col=2;col=M.nu;+col)cpotcol=cpotcol-1+numcol-1;for(p=1;p=M.tu;+p)col=M.datap.j;q=cpotcol;T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.e=M.datap.e;+cpotcol;return OK;第29页，本讲稿共53页二、带行表的三元组 有时为了方便某些矩阵运算，我们在按行优先存储的三元组中，加入一个行表来记录稀疏矩阵中每行的非零元素在三元组表中的起始位置。当将行表作为三元组表的一个新增属性加以描述时，我们就得到了稀疏矩阵的另一种顺序存储结构：带行表的三元组表。其类型描述如下：第30页，本讲稿共53页#define maxrow 100 typedef struct triple datamaxsize+1;int rposmaxrow+1;int nu,mu,tu;rtripletable 下面讨论两个稀疏矩阵相乘的例子，容易看出这种表示方法的优越性。第31页，本讲稿共53页两个矩阵相乘的经典算法也是大家所熟悉的。若设 Q=M*N 其中，M是m1*n1矩阵，N是m2*n2矩阵。当n1=m2时有：for(i=1;i=m1;+i)for(j=1;j=n2;+j)qij=0 for(k=1;k=n1;+k)qij+=mik*nkj;此算法的复杂度为O(m1*n1*n2)。第32页，本讲稿共53页当M和N是稀疏矩阵并用三元组表存储结构时，就不能套用上述算法。假设M和N分别为：30 0 50 -1 0 02 0 0 0M=0 2 1 0-2 4 0 0N=则Q=M*N为：0 6-1 0 0 4Q=第33页，本讲稿共53页 它们的三元组、和分别为：i j v i j v i j v 1 1 3 1 2 2 1 2 6 1 4 5 2 1 1 2 1 -1 3 2 -1 3 1 -2 3 2 4 3 1 2 3 2 4 q.data m.data n.data 矩阵可相乘的条件为：m.datap.j=n.datat.i 的所有t，将m.datap.v与n.datat.v乘积加到 ctempccol中，这里arow=m.datap.i ,ccol=n.datat.jpqtQ.tu第34页，本讲稿共53页稀疏矩阵相乘的基本思想是稀疏矩阵相乘的基本思想是：对于M中每个元素M，找到N中所有满足条件的元素，求得和的乘积，而从式得知，乘积矩阵Q中每个元素的值是个累加和，这个乘积只是中的一部分。为了便于操作，应对每个元素设一累加和的变量，其初值为零，然后扫描数组M，求得相应元素的乘积并累加到适当的求累计和的变量上。结论：两个稀疏矩阵相乘的乘积不一定是稀疏矩阵例如：0 0 1 0 0 0 1 1 1 0 0 1 *0 0 0 =1 1 1 0 0 1 1 1 1 1 1 1第35页，本讲稿共53页 Status MultSMatrix(rtripletable M,rtripletable N,rtripletable Q)if(M.nu!=N.mu)return ERROR;Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;if(M.tu*N.tu!=0)for(arow=1;arow=M.mu;+arow)ctemparow=0;/当前行各各累加器清零 Q.rposarow=Q.tu+1;for(p=M.rposarow;pM.rposarow+1;+p)brow=M.datap.j ;if(browN.nu)t=N.rposbrow+1;第36页，本讲稿共53页else t=N.tu+1;for(q=N.rposbrow;qt;+q)ccol=N.dataq.j;ctempccol+=M.datap.v*N.dataq.v;For(ccol=1;ccolMAXSIZE)return ERROR;Q.dataQ.tu=arow,ccol,ctempccol;/for arow return OK;第37页，本讲稿共53页稀疏矩阵的加、减时，用三元组（row,col,val）会产生大量的数据元素的移动。因此，要用十字链表来表示稀疏矩阵。十字链表的表结点存储结构：十字链表的表结点存储结构：其中：row:行；col：列 val：值；down：向下指针 right：向右指针；三、十字链表三、十字链表 所以其存储结构为：Typedef struct OLNode int i ,j;Struct OLNode *right,*down;OLNode,*Olink;rowcolvaldown right第38页，本讲稿共53页例如：3 0 0 5A=0 -1 0 0 2 0 0 022-1145113312M.cheadM.rheadmunuturhead chead十字链表头结点结构：mu:行数；nu:列数 tu:非零元个数 rhead：存各行表的指针的地址 chead：存各列表的指针的地址 3 4 4rhead cheadM第39页，本讲稿共53页讨论用十字链表表示的稀疏矩阵时，如何实现矩阵加法运算：A=A+B 例如：3 0 0 5 7 0 4 0A=0 -1 0 0 B=0 1 0 2 0 0 0 0 0 0 3 0 10 0 4 5A+B=0 0 0 2 0 0 3 0第40页，本讲稿共53页14511322-1 A.rheadA.chead第41页，本讲稿共53页221134117333 B.rheadB.chead242第42页，本讲稿共53页1341110333 (A+B).rhead(A+B).chead242145第43页，本讲稿共53页Status CreateSMatrix_OL(CrossList&M)/创建稀疏矩阵Mif(M)free(M);scanf(&m,&n,&t);M.mu=m;M.nu=n ;M.tu=t;if(!(M.chead=(Olink*)maloc(m+1)*sizeof(Olink)exit(OVFLOW);if(!(M.rhead=(Olink*)maloc(n+1)*sizeof(Olink)exit(OVFLOW);M.rhead =M.chead =NULL;for(scanf(&I,&j,&e);I!=0;scanf(&I,&j,&e)if(!(p=(OLNod*)maloc(sizeof(OLNod)exit(OVERFLOW);第44页，本讲稿共53页p-i=i ;p-j=j;p-e=e;if(M.rheadi=NULL)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=p;elsefor(q=M.cheadj;(q-down)&q-down-idown)p-down=q-down;q-down=p;return OK;第45页，本讲稿共53页假设C=A+B，则和矩阵C中的非零元素cij只可能有三种情况。(注：在A上加B）aij+bij 当 aij+bij0 只改变值Cij=aij 当bij=0 不变 bij 当aij=0 插入新结点 0 当 aij+bij=0 删除aij 结点整个的运算可从矩阵的第一行起逐行进行。假设指针pa和pb分别指向A和B的十字链表中行值相同的两个结点，若1）pa-j=pb-j 且 pa-e+pb-e 0，则只要将aij+bij的值送到pa 所指结点的值域中即可，其他不变第46页，本讲稿共53页2)pa-j=pb-j 且 pa-e+pb-e=0，则需要在A链表中删除pa所指的结点，此时需改变 right 和down域3)p-jj 且 pa-j0，则只要将pa指针往后推进一步，并重新加以比较。4)pa-jpb-j 且 pa-j=0，则只需在A的链表中插入一个值为bij的结点，需改变相应的指针，并重新加以比较。第47页，本讲稿共53页一、定义一、定义 1、表中的元素即可以是数据元素（又名原子）也可以是表的表，叫做广义表（General List）。2、一般表示：gl=(a0,a1,a2,an-1)3、a0 称为广义表 gl 的表头，其余称为表尾。5.2 5.2 广义表的概念广义表的概念第48页，本讲稿共53页A空表B62线性表Ca53x纯表二、二、GL的图形表示的图形表示DABC62a53x共享表D=(B,C,A)A=()B=(6,2)C=(a,(5,3,x)第49页，本讲稿共53页三、性质三、性质 1、有次序性最多只有一个前驱（后继），元素位置不能交换。2、有长度3、有深度圆括弧层数，或具有“”结点的层数。4、可共享5、可递归广义表本身又可以是自己的子表。第50页，本讲稿共53页四、广义表的链接存贮表示四、广义表的链接存贮表示1、结点结构utype=0/1/2/3 ref/intinof/charinof/hlinktlink标志域：值域：尾指针0123ref(表头结点的引用计数)intinof(整数原子结点)charinof(字符型原子结点)hlink(子表结点)指向同一层下一个结点第51页，本讲稿共53页2、带表头结点的链式存贮表示举例D=(B,C,A)=(6,2),(a,(5,3,x),()四、广义表的链接存贮表示四、广义表的链接存贮表示0 1 0 1 1 6 1 2 0 0 3 3 3 0 1 3 2 a 0 1 5 1 3 2 xABDC第52页，本讲稿共53页 第二章作业 1、假定数组 AarrySize 中有多个零元素，试写出一个函数，将 A 中所有的非零元素依次移到数组的前端 Ai（0iarrySize）。2、字符串替换操作 replace（String&s，String&t，String&v）是指：若 t 是 s 子串，则用 v 替换串 s 中所有与 t 相同的子串。试利用串的基本运算实现这个操作。第53页，本讲稿共53页