数据机构第5章描述课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,整理ppt,*,第,5,章 数组和广义表,5.1,数组的定义和运算,5.2,数组的顺序存储和实现,5.3,特殊矩阵的压缩存储,5.4,广义表,1,整理ppt,数组是,n(n,1),个相同类型数据元素,a,0,a,1,a,n-1,构成的有限序列,且该有限序列存储在一块地址连续的内存单元中。,数组的定义类似于采用顺序存储结构的线性表，是线性表在维数上的扩张，也就是线性表中的元素又是一个线性表。,n,维数组，,b,i,是第,i,维的长度，则,n,维数组共有 个数据元素，每个元素受,n,个关系的制约，就单个关系而言，这,n,个关系仍然是线性的。,1.,数组的定义和运算,2,整理ppt,数组具有以下性质：,(1),数组中的数据元素数目固定。一旦定义了一个,数组,其数据元素数目不再有增减变化。,(2),数组中的数据元素具有相同的数据类型。,(3),数组中的每个数据元素都和一组惟一的下标值对,应。,(4),数组是一种随机存储结构。可随机存取数组中的,任意数据元素。,数组的基本操作,(1),取值,Value(A,&e,index1,.,indexn),(2),赋值,Assign(&A,e,index1,indexn),3,整理ppt,2.,数组的存储结构,一维数组中,LOC(a,0,),确定,每个数据元素占用,L,个存储单元,则任一数据元素,a,i,的存储地址,LOC(a,i,),就可由以下公式求出：,LOC(a,i,)=LOC(a,0,)+i*L(0in-1),二维数组,由于计算机的存储结构是线性的,如何用线性的存储结构存放二维数组元素就有一个行列次序排放问题。,4,整理ppt,二维数组通常可以描述为两种形式,:,以,行序,为主序,:PASCAL,、,C,可以看成,A,=(,0,，,1,，,m,-1,),.,其中,i,是一个行向量形式的线性表，,0im,-1,i,=(a,i0,，,a,i1,，,a,i n,-1,),.,a,00,a,01,a,02,a,0,n,-1,a,10,a,11,a,12,a,1,n,-1,a,m,-1,0,a,m,-1,1,a,m,-1,2,a,m,-1,n,-1,.,.,.,.,.,.,.,A,mn,=,5,整理ppt,可以看成,A,=(,0,，,1,，,n,-1,),.,其中,j,是一个列向量形式的线性表，,0jn,-1,j,=(a,0j,，,a,1j,，,a,m,-1,j,),.,a,00,a,01,a,02,a,0,n,-1,a,10,a,11,a,12,a,1,n,-1,a,m,-1,0,a,m,-1,1,a,m,-1,2,a,m,-1,n,-1,.,.,.,.,.,.,.,A,mn,=,以,列序,为主序,:FORTRAN,6,整理ppt,对于数组，一旦规定了维数和维界，如何计算数组元素的存储位置。,a,00,a,01,a,0,n,-1,a,10,a,11,a,1,n,-1,a,m,-1,0,a,m,-1,n,-1,a,m,-1,1,0,1,m,-1,设数组以,行序,为主序。,设二维数组,A(mn),其数组元素,a,ij,的存储位置为,LOC(i,，,j)=LOC(0,，,0),其中，,LOC(0,，,0),是,a,00,的存储位置；,L,是每个数组元素占用的存储单元数；,L,例，,LOC(1,，,1)=LOC(0,，,0)+(,n1+1,),L,+(ni+j),L,7,整理ppt,n,维数组,每一元素对应下标,(j,1,j,2,j,n,),，,0j,i,b,i,-1,，,b,i,为第,i,维的长度。以行序为主序。,LOC(j,1,j,2,j,n,)=LOC(0,0,0)+,(b,n,b,2,j,1,+b,n,b,3,j,2,+b,n,j,n-1,+j,n,)L,8,整理ppt,例,:,对二维数组,float a54,计算：,(1),数组,a,中的数组元素数目；,(2),若数组,a,的起始地址为,2000,且每个数组元素长度为,32,位,(,即,4,个字节,),数组元素,a32,的内存地址。,元素数目共有,5*4=20,个。,C,语言采用行序为主序的存储方式,则有：,LOC(a,3,2,)=LOC(a,0,0,)+(i*n+j)*k,=2000+(3*4+2)*4=2056,。,9,整理ppt,3.,矩阵的压缩存储,特殊矩阵（对称矩阵、三角矩阵、对角矩阵）,特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵,为了节省存储空间,特别是在高阶矩阵的情况下,可以利用特殊矩阵的规律,对它们进行压缩存储,也就是说,使多个相同的非零元素共享同一个存储单元,对零元素不分配存储空间。,10,整理ppt,对称矩阵的压缩存储,若一个,n,阶方阵,A,中的元素满足,a,i,j,=a,j,i,(1i,jn),则称其为,n,阶,对称矩阵,。,（,1,）只存储对称矩阵中上三角或下三角中的元素,（,2,）将,n,2,个元素压缩存储到,n(n+1)/2,个元素的空间中，以一个一维数组作为,A,的存储空间。,11,整理ppt,n,2,个元素,n(n+1)/2,个元素,a,ij,(,1i,jn),Bn(n+1)/2,1+2+(i-1),+j,-1,；,a,ij,a,ji,a,11,a,21,a,22,a,31,a,nn,a,12,=,a,13,=,k=,0,1,2,3,n(n+1),2,-,1,12,整理ppt,下三角矩阵的压缩存储,Bn(n+1)/2+1,C,k=,0,1,2,3,n(n+1),2,-,1,a,11,a,21,a,22,a,31,a,nn,c,a,12,a,13,13,整理ppt,对角矩阵：所有的非零元都集中在以主对角线为中心,的带状区域内。,半带宽为,b,的对角矩阵,14,整理ppt,共有,3n-2,个非零元。,主对角线左下方的元素下标有关系式：,i=j+1,k=3(i-1)-1+,1,-1=3(i-1)-1=2(i-1)+i-2=2(i-1)+j-1.,主对角线上的元素下标有关系式：,i=j,k=3(i-1)-1+,2,-1=3(i-1)=2(i-1)+i-1=2(i-1)+j-1.,主对角线右上方的元素下标有关系式：,i=j-1,k=3(i-1)-1+,3,-1=3(i-1)+1=2(i-1)+i=2(i-1)+j-1.,三对角矩阵,B3n-2;,k=2(i-1)+j-1;,15,整理ppt,稀疏矩阵,非零元较零元少，且没有一定规律。,mn,的矩阵，有,t,个非零元，,矩阵的稀疏因子,：,=t/(m*n),，当,0.05,时为稀疏矩阵。,压缩存储，只存储非零元,三元组顺序表,(i,，,j,，,a,i,j,),行逻辑链接的顺序表,十字链表,(1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7),16,整理ppt,#define MaxSize 100 /*,矩阵中非零元素最多个数*,/,typedef struct,int i;/*,行号*,/,int j;/*,列号*,/,ElemType e;/*,元素值*,/,Triple;/*,三元组定义*,/,typedef struct,int rows;/*,行数*,/,int cols;/*,列数*,/,int nums;/*,非零元素个数*,/,Triple dataMaxSize+1;/*data0,未用*,/,TSMatrix;/*,三元组顺序表定义*,/,17,整理ppt,用三元组表实现稀疏矩阵的转置运算,一个,6*7,的矩阵,A,，以行序为主序顺序排列,18,整理ppt,矩阵的转置，方法一：,19,整理ppt,Status TransposeSMatrix(TSMatrix A,TSMatrix&B),B.rows=A.cols;B.cols=A.rows;B.nums=A.nums;,if(B.nums!=0),q=1;/*q,为,B.data,的下标*,/,for(col=1;col=A.cols;col+),for(p=1;p=A.nums;p+)/*p,为,A.data,的下标*,/,if(A.datap.j=col),B.dataq.i=A.datap.j;,B.dataq.j=A.datap.i;,B.dataq.e=A.datap.e;,q+;,return OK;,20,整理ppt,方法,1,时间复杂度：,O(cols*nums),当非零元个数,nums,和,cols*rows,同数量级时，,O(rows*cols,2,),仅适用于,numsrows*cols.,常规存储方式时，实现矩阵转置的经典算法如下：,for(i=0;im;i+),for(j=0;j n;j+),Ti j=Mji;,O(cols*rows),21,整理ppt,方法二：,依次按三元组表,A(6*7),的次序进行转置，转置后直接放到三元组表,B,的正确位置上。这种转置算法称为快速转置算法。,col 1 2 3 4 5 6 7,numcol,cpotcol,2,2,2,1,0,1,0,1,3,5,7,8,8,9,numcol:A,中第,col,列非零元的个数。,cpotcol:B,中第,col,行第一个非零元,在,B,中的位置,22,整理ppt,Status FastTranSMatrix(TSMatrix A,TSMatrix&B),B.rows=A.cols;B.cols=A.rows;B.nums=A.nums;,if(B.nums),for(col=1;col=A.cols;+col)numcol=0;,for(t=1;t=A.nums;+t)+numA.datat.j;,cpot1=1;,for(col=2;col=A.cols;+col),cpotcol=cpotcol-1+numcol-1;,for(p=1;p=A.nums;+p),col=A.datap.j;q=cpotcol;,B.dataq.i=A.datap.j;B.dataq.j=A.datap.i;,B.dataq.e=A.datap.e;+cpotcol;,return OK;,O(cols+nums),当,nums,和,cols*rows,同数量级时,O(rows*cols),23,整理ppt,row col e,1,2,3,4,5,6,7,8,1 3 -3,3 1 9,2 1 12,cpot1,cpot2,cpot2,cpot3,cpot3,cpot4,cpot6,6 3 14,3 4 24,2 5 18,1 6 15,4 6 -7,24,整理ppt,小结,基本学习要点如下：,(1),理解数组和一般线性表之间的差异。,(2),重点掌握数组的顺序存储结构和元素地址计算方法。,(3),掌握各种特殊矩阵如对称矩阵、上、下三角矩阵和对角矩阵的压缩存储方法。,(4),掌握稀疏矩阵的各种存储结构以及基本运算实现算法。,(5),灵活运用数组这种数据结构解决一些综合应用问题。,25,整理ppt,练习：,将一个,A1.100,1.100,的三对角矩阵，按行优先存入一维数组,B1.298,，,A,中元素,a,66,65,在,B,数组中的位置,k=?,。,在主对角线左下方，,65*3-1+1=195,。,26,整理ppt,作业：,5.2,5.25,27,整理ppt,1.,广义表的定义（列表）,广义表是线性表的推广，是由零个或多个单元素或子表所,组成的有限序列。,LS=(a,1,a,2,a,i,a,n,),a,i,：是单个数据元素,则,a,i,是广义表的,原子,；如果,a,i,是一个广义表,则,a,i,是广义表的,子表,。,规定用小写字母表示原子,用大写字母表示广义表的 表名。,广义表与线性表的区别：,线性表的成份都是结构上不可分的单个数据元素，而广,义表的成份即可以是单元素，也可以是有结构的表，其定义,是递归的定义。,5.4,广义表