数据结构完整第5章数组和广义表ppt课件

1,第,5,章,数,组,和,广,义,表,5.1数组的逻辑结构,5.2数组的顺序存储结构5.3矩阵的压缩存储5.4广义表,数组(array)是最常用的数据结构之一。几乎所有的程序设计语言都把数组类型设定为固有类型。,数组的定义,线性结构中的数据都是非结构的原子类型，元素的值是不再分解的。而数组可以看成是线性表在下述含义上的扩展：,2,数组的基本操作,表中的数据元素本身也是一种数据结构。,数组是由下标和值组成的序对集合。在数组中，一旦给定下标，都存在一个与其相对应的值，这个值就称为数组元素。,也可以说，数组中的每个数据元素都对应于一组下标（j1,j2,jn），每个下标取值范围是1jibi，bi称为第i维的长度（i=1,2,n）。显然，当n=1时，n维数组就退化为定长的线性表。反之，n维数组也可以看成是线性表的推广。,3,5.1.1数组的定义,可以把二维数组看成是这样一个定长线性表：它的每个数据元素也是一个定长线性表。,Amn=,4,例如，下面是一个二维数组，且以m行n列的矩阵形式表示。,每个数据元素j是一个列向量形式的线性表,Amn=,二维数组A还可以看成是一个线性表：,A=(1,2,n),j=(a1j,a2j,am,j)1jn,每个数据元素是一个行向量形式的线性表B=(123,m),Amn=(a11a12a1,n),(am,1am,2am,n),(a21a22a2,n),i=(ai1,ai2,ai,n)1im,5,6,5.1.2数组的抽象类型定义,ADTArrayD=aj1j2j3.jn|n0,称为数组的维数,ji是数组的第i维下标,1jibi,bi为数组第i维的长度，aj1j2j3.jnElementSet数据关系：=R1,R2,.RnRi=|1jkbk,1kn且ki,1jibi-1,aj1j2.jn,aj1ji+1jnD,i=1,n,8,5.1.2数组的抽象类型定义,由于内存储器的结构是一维的。一维数组可直接采用顺序存储。用一维的内存存储表示多维数组时，需按某种次序将数组中元素排成一线性序列，再将这个线性序列存放在一维的内存中，即数组的顺序存储结构表示。,顺序存储的定位公式,9,数组的顺序存储表示,基本操作的算法描述,用顺序存储结构来存储数组中的元素，一定要按照某种次序将元素排成一个线性序列。有两种存储方式：,(1)以列为主序(columnmajororder)的存储方式，即按列优先，逐列顺序存储。,(2)以行为主序(rowmajororder)的存储方式，即按行优先，逐行顺序存储。,10,5.2.1顺序存储的定位公式,11,列主次序存放,12,行主次序存放,13,（）一维数组的地址计算：设一维数组为：=(a1,a2,ai,an),数组中每个元素占size个存储单元，则元素ai的存储地址为：Loc(Ai)=Loc(A1)+(i-1)*size。,数组的地址计算,14,二维数组的地址计算假设每个数据元素占1个存储单元，且以行序为主序的进行存储，则二维数组A中任一元素aij的存储位置可以由下面定位公式确定LOC(Ai,j)=LOC(A1,1)+n*(i-1)+(j-1),其中：,LOC(Ai,j)是aij的存储位置；,LOC(A1,1)是a11的存储位置，即二维数组A的起始存储位置，也称为基地址或基址；,n是数组第二维的长度。,15,假设每个数据元素占size个存储单元，则二维数组A中任一元素aij的存储位置可以由下面定位公式确定LOC(Ai,j)=LOC(A1,1)+(n*(i-1)+(j-1)*size,三维数组的地址计算三维数组A(1:r,1:m,1:n)。假设每个数据元素占size个存储单元，且以行序为主序的进行存储，首元素a111的地址为Loc(A111),求任意元素aijk的地址。显然，ai11地址为oc(Ai11)=Loc(A111)+(i-1)*m*n,因为在该元素之前有i-1个m*n的二维数组。,16,不难得到三维数组任意元素aijk的地址：Loc(Aijk)=Loc(A111)+(i-1)*m*n+(j-1)*n+(k-1)*size,其中：ir,jm,kn。,矩阵(matrix)是很多科学与工程计算问题中研究的数学对象。在数据结构中，我们感兴趣的不是矩阵本身，而是如何存储矩阵的元素而使矩阵的各种运算能够有效地进行。,特殊矩阵包括两个部份：元素分布有特殊规律的矩阵,找到规律对应的公式，实现压缩存储。非零元素很少的稀疏矩阵，可采用只存非零元素的方法实现压缩存储。,17,特殊矩阵的压缩存储,所谓压缩存储是指：为多个值相同的元素只分配一个存储空间；对零元不分配空间。,18,稀疏矩阵的逻辑结构,稀疏矩阵的存储结构,假若相同的元素或者零元素在矩阵中的分布有一定规律，则称特殊矩阵。特殊矩阵主要有3种：对称矩阵、三角矩阵、带状矩阵。,在所有这些统称为“特殊矩阵”的矩阵中，非零元的分布都有一个明显的规律，从而都可以将其压缩存储到一维数组中，并且找到每个非零元在一维数组中的对应关系。,19,5.3.1特殊矩阵的压缩存储,若一个n阶矩阵M中的元素满足下述性质,1.对称矩阵,aij=aji1i，jn,则称为n阶对称矩阵。,20,对于对称矩阵，可以为每一对对称元只分配一个存储空间，这样就可以将n2个元压缩存储到n(n+1)/2个元的空间中。,假设以行序为主序存储对称矩阵的下三角（包括对角线）中的元。以一维数组Bn(n+1)/2作为n阶对称矩阵M的存储结构，,21,B,Loc(Aij=1,2,3,4,Loc(Aij)=Loc(A11)+i*(i-1)/2+j-1(ij),三角矩阵分为下三角矩阵和上三角矩阵。所谓下(上)三角矩阵是指矩阵的上(下)三角(不包括对角线)中的元均为常数c或为零的n阶矩阵。,2.三角矩阵,22,三角矩阵除了和对称矩阵一样，只存储矩阵的下(上)三角中的元之外，再加上一个存储常数c的存储空间即可。,一个n阶方阵，若它的全部非零元素落在一个以对角线为中心的带状区域中，则称该矩阵为带状矩阵，或对角矩阵。这个带状区域若包含主对角线上下各b条对角线道上元素，那么，b称为该带状矩阵的半带宽，或称该带状矩阵的带宽为(2b+1)。,3.带状矩阵,b条,b条,23,在带状矩阵中，当|i-j|b时，aij=0。该方阵共有(2b+1)n-(b+1)b个非零元素。,D矩阵是一个5阶、半带宽为2的带状矩阵，在其主对角线a11、a22、a33、a44、a55上下各有2条对角线，共有(2b+1)n-(b+1)b=19个非零元素。,24,例如：,带状矩阵中最常见的是三对角带状矩阵。,25,特点：当i=1j=1,21data中三元组的序号，/i指示A.data中三元组的序号，/k指示A的列号（即B的行号）,B-m=A.n;/将稀疏矩阵A的列数值作为其转置矩阵B的行数值B-n=A.m;/将稀疏矩阵A的行数值作为其转置矩阵B的列数值B-len=A.len;/转置矩阵B与稀疏矩阵A的非零元个数相等,算法编(稀疏矩阵“列序”递增转置算法),if(B-len0)j=1;,37,for(k=1;kdataj.col=A.datai.row;/稀疏矩阵A的行域值成为其转置矩阵M的列域值,B-dataj.e=A.datai.e;/将稀疏矩阵M的非零元值赋给其转置矩阵T,j+;/B-data中三元组的序号加1,/if(A.data)结束/if(B-len0)结束,38,算法分析,一般矩阵的转置算法（经典算法）为：,39,for(col=0;colcol_head=(Olink*)malloc(n+1)*sizeof(Olink)exit(OVERFLOW);,if(M)free(M);scanf(,45,算法编写,for(scanf(,p-row=i;/生成新结点的行号域p-col=j;/生成新结点的列号域p-value=e;/生成新结点的值域,46,M-row_head=NULL;/初始化行头指针向量；令各行链表为空链表M-col_head=NULL;/初始化列头指针向量；令各列链表为空链表,if(M-row_headi=NULL)M-row_headi=p;p-right=NULL;,elsefor(q=M-row_headi;(q-right)/完成行插入,elseif(M-row_headi-colj)/寻找在行表中的插入位置p-right=M-row_headi;M-row_headi=p;,47,if(M-col_headj=NULL)M_col_headj=p;p-down=NULL;,elsefor(q=M-col_headj;(q-down)/完成列插入,elseif(M-col_headj-rowi)/寻找在列表中的插入位置p-down=M-row_headj;M-col_headj=p;,/for结束returnOK;/CreateSMatrix_OL,48,M-col_head,M-row_head,(1)输入(1,1,3),1,1,3,p,(2)输入(1,3,5),p,1,3,5,q,(3)输入(1,4,9),1,4,9,p,q,(4)输入(3,1,2),3,1,2,p,q,49,(5)输入(2,3,4),2,3,4,q,(6)输入(2,2,8),q,创建稀疏矩阵M的十字链表,if(M.rheadi=NULL)M.rheadi=p;p-right=NULL;,for(q=M-col_headi;(q-down),if(M-row_headi-jj)p-right=M-row_headi;M-row_headi=p;,if(M-col_headj=NULL)M-col_headj=p;p-down=NULL;,p,q,p,2,2,8,if(M-col_headj=NULL)M-col_headj=p;p-down=NULL;,for(q=M-row_headi;(q-right),if(M-col_headj=NULL)M-col_headj=p;p-down=NULL;,for(q=M-row_headi;(q-right),if(M-col_headj=NULL)M-col_headj=p;p-down=NULL;,if(M-row_headi=NULL)M-row_headi=p;p-right=NULL;,for(q=M-col_headi;(q-down),if(M-row_headi=NULL)M-row_headi=p;p-right=NULL;,对于一个m行n列，并且有t个非零元的稀疏矩阵，CreateSMatrix_OL算法执行时间为O(ts)，其中s=maxm,n。,这是因为：每建立一个非零元的结点时都需要寻查它在行表和列表中的插入位置，此算法对非零元输入的先后次序没有任何要求。,反之，若按以行序为主序的次序依次输入三元组，即可以将建立十字链表表示的算法改写成O(t)数量级的（t为非零元个数）的算法。,算法分析,50,广义表(generalizedlist)是线性表的推广，有时也称为列表（lists，用复数形式以示与统称的表list的区别）。广泛地应用于人工智能等领域的LISP（表处理语言），把广义表作为基本的数据结构，就连程序也表示为一系列的广义表。,51,广义表的逻辑结构,和数组一样，广义表也可以看成是线性表在下述含义上的扩展：表中的数据元素本身也是一种数据结构。,52,广义表的存储结构,53,5.4.1广义表的逻辑结构,广义表一般记作：GL=(a1,a2,an),其中：,n是广义表GL的长度；,ai可以是单个元素，也可以是广义表，分别称为广义表GL的原子和子表，习惯上用大写字母表示广义表的名称，用小写字母表示原子的名称。,GL是广义表(a1,a2,an)的名称；,1.广义表的定义,54,例5-1A=()，A是一个空表，它的长度为零。,例5-2B=(e)，B只有一个原子e，它的长度为1。,例5-3C=(a,(b,c,d)，C的长度为2，两个元素分别为原子a和子表(b,c,d)。,例5-4D=(A,B,C)，D的长度为3，三个元素分别为A、B和C，都是广义表。显然，将上面所述三个子表的值代入以后，则有D=(),(e),(a,(b,c,d)。,例5-5E=(a,E)，这是一个递归表，它的长度为2，E相当于一个无限的广义表E=(a,(a,(a,)。,55,2.广义表的三个重要结论,从上述定义和例子推出如下广义表的三个重要结论,(1)广义表的元素可以是子表，而子表的元素还可以是子表，。由此，广义表是一个多层次结构。,(2)广义表可以为其他广义表所共享。例如在上述例子中，广义表A、B和C为D的子表，则在D中可以不必列出广义表的值，而是通过子表的名称引用。,(3)广义表可以是一个递归表，即广义表也可以是其本身的一个子表。例如广义表E就是一个递归的表。,56,表示广义表,表示原子,57,和线性表相类似，可以对广义表进行的操作有查找、插入、删除和取表元素等。由于广义表在结构上较线性表复杂的多，因此，广义表操作的实现也不如线性表简单。在这些操作中，最重要的两个基本操作是：,(1)取广义表表头GetHead：表中的第一个元素为此表的表头。(2)取广义表表尾GetTail：表中除第一个元素外的其余元素组成的表为此表的表尾。,58,3.广义表的两个基本操作,(1)A=()(2)B=(e)(3)C=(a,(b,c,d)(4)D=(A,B,C)(5)E=(a,E),GetHead(B)=eGetTail(B)=()GetHead(C)=aGetTail(C)=(b,c,d)GetHead(D)=AGetTail(D)=(B,C)由于(B,C)为非空广义表，令F=(B,C)，则可以继续分解得到：GetHead(F)=BGetTail(F)