JAVA数据结构第五章数组和广义表.ppt

,第五章数组和广义表,线性表具有相同类型的数据元素的有限序列。,限制插入、删除位置,线性表具有相同类型的数据元素的有限序列。,限制元素类型为字符,串零个或多个字符组成的有限序列。,线性表具有相同类型的数据元素的有限序列。,将元素的类型进行扩充,4.2数组,数组（array）：是n(n=0)个相同数据类型的数据元素（a1,a2,a3,an）构成的有限线性序列。n为数组长度或数组大小。n=0为空数组。多维数组：一个m(m=2)维数组，其每个数据元素是一个m-1维的数组。且每个元素都对应于一组下标（j1,j2,jm）,每个下标的取值范围是cijidi,di-ci+1称为第i维的长度(i=1,2,n),m为数组的维数。,数组的特点：数组中各元素具有统一的类型；数组元素的下标一般具有固定的上界和下界。数组的基本操作比较简单，除了结构的初始化和销毁之外，只有存取元素和修改元素值的操作。数组有顺序存储和链式存储两种方式。,一维数组的特点：,1个下标，a2是a3的直接前驱，a4是a3的直接后继。注：一维数组的顺序存储常称为向量。,一维数组存储结构与寻址设一维数组的下标的范围为闭区间l，h，每个数组元素占用c个存储单元，则其任一元素ai的存储地址可由下式确定：Loc(ai)Loc(al)(il)c,二维数组的特点：,2个下标，每个元素ai,j受到两个关系（行关系和列关系）的约束：,一个mn的二维数组可以看成是m行的一维数组，或者n列的一维数组。,例如，元素a22受两个线性关系的约束，在行上有一个行前驱a21和一个行后继a23，在列上有一个列前驱a12和和一个列后继a32。,a11a12a1na21a22a2nam1am2amn,A=,二维数组是数据元素为一维数组（线性表）的线性表。,m维数组的特点：,m个下标，每个元素受到m个关系约束。,一个m维数组可以看成是由若干个m1维数组组成的线性表。,问题：计算机的存储结构是一维的，而数组一般是多维的，怎样存放？解决办法：事先约定按某种次序将数组元素排成一列序列，然后将这个线性序列存入存储器中。例如：在二维数组中，我们既可以规定按行存储，也可以规定按列存储。,注意：若规定好了次序，则数组中任意一个元素的存放地址便有规律可寻，可形成地址计算公式；约定的次序不同，则计算元素地址的公式也有所不同；,常用的映射方法有两种：按行优先：先行后列，先存储行号较小的元素，行号相同者先存储列号较小的元素。按列优先：先列后行，先存储列号较小的元素，列号相同者先存储行号较小的元素。,2、二维数组的存储结构与寻址,0,n-1,0,m-1,(a)二维数组,按行优先存储的寻址,数组大小：（m-1-0+1）*（n-1-0+1）=m*n;,设二维数组Amn的首地址A00为p,每个元素占L个存储单元。若已知aij是数组的第k个元素，则可得：Loc(i,j)=p+k*L;目标：求aij是数组的第几个元素。,0,n-1,0,m-1,(a)二维数组,按行优先存储的寻址,aij前面的元素个数=阴影部分的面积=整行数每行元素个数+本行中aij前面的元素个数=(i-0)(n-1-01)(j-0),LOC(aij)=LOC(a00)+i*n+j*L,c2,b2,c1,b1,(a)二维数组,aij前面的元素个数=阴影部分的面积=整行数每行元素个数+本行中aij前面的元素个数=(i-c1)(b2-c21)(j-c2),通用按行优先存储的寻址公式：,数组大小：（b1-c1+1）*（b2-c2+1）;,计算二维数组元素地址的通式设一般的二维数组是Ac1.d1,c2.d2，这里c1,c2不一定是从0开始。每个元素占L个存储单位。,二维数组列优先存储的通式为：LOC(aij)=LOC(ac1，c2)+(j-c2)*(d1-c1+1)+i-c1*L数组的大小:(d1-c1+1)*(d2-c2+1),单个元素长度,aij之前的行数,数组基址,总列数，即第2维长度,aij本行前面的元素个数,则行优先存储时的地址公式为：LOC(aij)=LOC(ac1，c2)+(i-c1)*(d2-c2+1)+j-c2*L,例2、已知二维数组Am,m按行存储的元素地址公式是：Loc(aij)=Loc(a11)+(i-1)*m+(j-1)*K,按列存储的公式是？,Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*K（尽管是方阵，但公式仍不同）,例1、一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是个字节。,288,例3、设数组a160,170的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a32,58的存储地址为。,8950,答：LOC(aij)=LOC(ac1，c2)+(j-c2)*(d1-c1+1)+i-c1)*L得：LOC(a32,58)=2048+(58-1)*(60-1+1)+32-1)*28950,答：Volume=m*n*L=(6-1+1)*(7-0+1)*6=48*6=288,Loc(aijk)=Loc(a000)+(im2m3+jm3+k)L,若三维数组am1m2m3中，总共有m1*m2*m3个数组元素。求aijk存储地址。若按先页、再行后列。,多维数组的存储结构与寻址,链式存储顺序存储方式：按低地址优先（或高地址优先）顺序存入一维数组。（难点是多维数组与一维数组的地址映射关系）,行指针向量,链式存储方式：用带行指针向量的单链表来表示。,矩阵类。,矩阵运算主要有矩阵加、矩阵减、矩阵乘、矩阵转置等。矩阵加（C=A+B）定义为publicclassMatrixprivateintvalue;,5.2矩阵的压缩存储,讨论：1.矩阵是很多科学与工程计算问题中研究的数学对象.如何存储矩阵中的元素,使对矩阵的各种操作更方便、效率更高。2.在实际问题中，常遇到一些矩阵，其元素有许多值相同或大量元素值为零。如何节省空间。,.什么是压缩存储？多个值相同的元素，只分配一个元素值的存储空间，且零元素不占存储空间。.所有二维数组（矩阵）都能压缩吗？未必，要看矩阵是否具备以上压缩条件。.什么样的矩阵具备以上压缩条件？一些特殊矩阵（如：对称矩阵，三角矩阵，对角矩阵）和稀疏矩阵等。,.什么叫特殊矩阵？若值相同的元素或者零元素在矩阵中的分布有一定规律，则该类矩阵称为特殊矩阵。.什么叫稀疏矩阵？（重点）若值相同的元素或者零元素在矩阵中的分布不具有规律，且矩阵中非零元素的个数较少（一般小于5%）时。（无确切定义）,一、特殊矩阵、n阶对称矩阵：若n阶矩阵中的元素满足如下条件：aij=aji1i,jn。如：压缩存储方案：为每一对对称元素分配一个存储空间，则可将n*n个元素压缩存储到n(n+1)/2个元素的空间中。,方法：）按行序为主序存储其下三角（含对角线元素）（以此为例）按行序为主序存储其上三角（含对角线元素）按列序为主序存储其下三角（含对角线元素）按列序为主序存储其上三角（含对角线元素）,aij在一维数组中的序号=阴影部分的面积一维数组下标从0开始aij在一维数组中的下标k=i(i+1)/2+j,0in-1,0jn-1,aij,对称矩阵的压缩存储（存储下三角）,(c)计算方法,(b)存储说明,下三角矩阵,问：如何获取矩阵中的元素（或赋值）？关键：找到该元素在一维数组sa中的位置k。即确定sak与矩阵元素aij之间存在的一一对应关系。,（可获得下三角元素）（可获得上三角元素（不含主对角线）,注：我们将sa就称为n阶对称矩阵的压缩存储。若计算aij存放地址，则可以利用以下公式获得：LOCaij=LOCa00+（i(i+1)/2+j）*L,i=j，L为每个元素的存储单元大小。,2、三角矩阵：（）上三角矩阵：是指矩阵的下三角（不包括对角线）中的元均为常数或零的n阶矩阵。（）下三角矩阵：是指矩阵的上三角（不包括对角线）中的元均为常数或零的n阶矩阵。压缩存储方案：只存储其下（上）三角中的元素之外，需加一个存储常数c的存储空间即可。,特殊矩阵的压缩存储三角矩阵,3cccc62ccc481cc7460c82957,(a)下三角矩阵,34810c2946cc57ccc08cccc7,(b)上三角矩阵,矩阵中任一元素aij在数组中的下标k与i、j的对应关系：,矩阵中任一元素aij在数组中的下标k与i、j的对应关系：,上三角矩阵的压缩存储,如何只存储非零元素？,注意：稀疏矩阵中的非零元素的分布没有规律。,二、稀疏矩阵、稀疏矩阵的压缩存储,问题：如果只存储稀疏矩阵中的非零元素，那这些元素的位置信息该如何表示？解决思路：对每个非零元素增开若干存储单元，例如存放其所在的行号和列号，便可准确反映该元素所在位置。实现方法：1)三元组法2)十字链表法如:将每个非零元素用一个三元组（i，j，aij）来表示，则每个稀疏矩阵可用一个三元组表来表示。,方法一:三元组将稀疏矩阵中的每个非零元素表示为：(行号，列号，非零元素值)三元组,(0,2,11)，(0,4,17)，(1,1,20)，(3,0,19)，(3,5,28)，(4,4,50),可还原吗？,不可以，须再加一行“总体”信息：即总行数、总列数、非零元素总个数。,三元组单链表行/列的单链表,方法二：用三元组链表表示,方法三：用十字链表表示,用途：方便稀疏矩阵的加减运算；方法：每个非0元素占用5个域。row：存储非零元素的行号col：存储非零元素的列号item：存储非零元素的值right：指针域，指向同一行中的下一个三元组down：指针域，指向同一列中的下一个三元组,十字链表的特点：每行非零元素链接成带表头结点的链表(或循环链表)；每列非零元素也链接成带表头结点的链表(或循环链表)。则每个非零元素既是行链表中的一个结点；又是列链表中的一个结点，即呈十字链状。,稀疏矩阵的压缩存储十字链表(实例),rhead,chead,三、广义表,1、广义表的定义,广义表是线性表的推广，也称为列表（lists）记为：LS=(a1,a2,，an),广义表名表头(Head）表尾(Tail),第一个元素是表头，而其余元素组成的表称为表尾；用小写字母表示原子类型，用大写字母表示列表。,n是表长,在广义表中约定：,讨论：广义表与线性表的区别和联系？广义表中元素既可以是原子类型，也可以是列表；当每个元素都为原子且类型相同时，就是线性表。,广义表的逻辑结构：直接元素之间是线性关系，1对1。常用术语：长度：广义表LS中的直接元素的个数；深度：广义表LS中括号的最大嵌套层数。表头：广义表LS非空时，称第一个元素为LS的表头；表尾：广义表LS中除表头外其余元素组成的广义表。,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=3，3个元素都是子表n=2，a为原子，E为子表,D=(A,B,C)=(),(e),(a,(b,c,d)，共享表,A=(a,(b,A),实训2：试用图形表示下列广义表。（设代表原子，代表子表）,D=(A,B,C)=(),(e),(a,(b,c,d),的长度为3，深度为3,的长度为2，深度为,两种特殊的基本操作：GetHead(L)取表头(可能是原子或列表);GetTail(L)取表尾(一定是列表)。,广义表()和广义表()不同？,():长度为0，深度为1;():长度为1,深度为2;,1.GetTail【(b,k,p,h)】;2.GetHead【(a,b),(c,d)】;3.GetTail【(a,b),(c,d)】;4.GetTail【GetHead【(a,b),(c,d)】;,实训3：求下列广义表操作的结果,(k,p,h),（b）,(a,b),5.GetTail【（e）】;6.GetHead【()】.7.GetTail【()】.,(),(a,b),(),(),(c,d),2、广义表的存储结构,广义表可以采用顺序存储结构吗？,由于广义表中的数据元素的类型不统一（原子或广义表），因此难以采用顺序存储结构来存储。,若广义表不空，则可分解为表头和表尾；反之，一对确定的表头和表尾可唯一地确定一个广义表。注：采用头尾表示法存储广义表,如何采用链接存储结构存储广义表？,广义表的存储结构头尾表示法,广义表中的数据元素既可以是广义表也可以是单元素,头尾表示法中的结点结构？,表结点存储广义表；元素结点存储单元素,tag：区分表结点和元素结点的标志；hp：指向表头结点的指针；tp：指向表尾结点的指针；data：数据域，存放单元素。,结点结构,A()B(e)C(a,(b，c，d),实例如下：,C=(a,(b,c,d),B=(e),E(a,E)F(),扩展表示：三个域结点结构,指向下一结点,原子结点,表结点,如:C=(a,(b,c,d),