深圳大学-数据结构-2017数组和广义表演示文档

第5章数组和广义表,5.1.1 数组和数组元素数组: n个相同类型数据元素a1,a2,an 构成的有限序列 该有限序列存储在一块地址连续的内存单元中 数组的定义类似于采用顺序存储结构的线性表,5.1 数 组,数组的特性: 数组中的数据元素数固定 数组中的数据元素具有相同数据类型 数组中的每个数据元素都有一组惟一的下标值。 数组是一种随机存储结构。可随机存取数组中的任意数据元素,5.1.2 数组的定义 ADT array 数据对象D：具有相同类型的数据元素构成的有序集合； 数据关系R：对于n维数组，其每一个元素均位于n个向量中，每个元素最多具有n个前驱结点和n个后继结点； 基本运算: ADT array,5.1.3 数组的顺序存储及实现 数组是线性表的一种存储方式 多维数组数据元素的顺序存储有两种方式： 按行优先存储 按列优先存储,一维数组的存储:若a0的存储地址LOC(a0)确定,每个数据元素占用k个存储单元,则: LOC(ai)=LOC(a0)+i*k (0in)一维数组中任一数据元素的存储地址可直接计算得到(直接存取).一维数组是一种随机存储结构。,二维数组Amn的存储： a00 a01 a0( n-1) a10 a11 a1( n-1) A = a(m-1)0 a(m-1)1 a(m-1) (n-1)按行优先存储顺序：a00， a01， a0(n-1) , a10, a11， a1(n-1) ， a(m-1)0,a(m-1)1,a(m-1) (n-1) 按列优先存储顺序：a00，a10， a(m-1)0 , a01, a11, a(m-1)1， a0(n-1) ,.a1(n-1)，a(m-1) (n-1),二维数组及其顺序存储图例形式,(b) 行优先顺序存储,(c) 列优先顺序存储,设有二维数组A=(aij)mn，若每个元素占用的存储单元数为L(个)，LOCa00表示元素a00的首地址，即数组的首地址。1 以“行优先顺序”存储 第0行中的每个元素对应的(首)地址是：LOCa0j=LOCa00+jL j=0,1,2, ,n(2) 第1行中的每个元素对应的(首)地址是： LOCa1j=LOCa00+nL+jL j=0,1,2, ,n 第m行中的每个元素对应的(首)地址是：LOCamj=LOCa00+mnL+jL j=0,1,2, ,n,aij存储位置按行优先：address(aij )= address ( a00 ) + ( in+j )L 按列优先：address(aij ) = address ( a00 ) + (jm +i )L,二维数组可以看作是每个数据元素都是相同类型的一维数组的一维数组。以此类推,任何多维数组都可以看作一个线性表,这时线性表中的每个数据元素也是一个线性表。多维数组是线性表的推广。,例5.1 有二维数组float a54,计算a32的内存地址.(a起始地址为2000,数组元素长度4字节) LOC(a3,2)=LOC(a0,0)+(i*n+j)*k =2000+(3*4+2)*4=2056,压缩存储：多个相同值的结点只分配一个存储空间，值为零的结点不分配空间。,5.2 矩阵的压缩存储,5.2.1 特殊矩阵主要讨论对称矩阵和三角矩阵的压缩存储,对称矩阵的压缩存储 若该矩阵为方阵。nn阶的方阵A满足： aij=aji (0in-1 , 0jn-1)则A为对称矩阵。 对称矩阵中，几乎有一半元素的值相等。如存储所有元素，浪费空间，且n值越大，浪费越严重。,对称矩阵压缩存储: 只存储对角线以上(或对角线以下)部分，未存储的部分利用元素之间的对称性访问。 存储对称矩阵A(对角线以下部分,下标满足ij的数组元素aij）： a00 a10 a11 A = a20 a21 a22 a(n-1)0 .a(n-1) (n-1),按行优先存储，A压缩存储后元素aij的地址： address(a00)+(i*(i+1)/2+j)L 当ijaddress(aij)= address(a00)+(j*(j+1)/2+i)L 当i j,三角矩阵的压缩存储 1、下三角矩阵 a00 0 0 0 a10 a11 0 . 0 A = a20 a21 a22 . 0 a(n-1)0 a(n-1) (n-1) 按行优先， aij(ij)压缩存储后的地址为： address(aij)= address(a00)+ (i*(i+1)/2+j)L 当ij注: 与对称矩阵不同，当ij时，aij的值为0，其没有对应的存储空间。,稀疏矩阵:矩阵中零元素的个数远远大于非零元素的个数时，称该矩阵为稀疏矩阵。 例如一个100100的矩阵,若其中只有100个非零元素,就可称其为稀疏矩阵。疏矩阵的压缩存储方法是只存储非零元素。,5.2.2 稀疏矩阵,稀疏矩阵的三元组表示 稀疏矩阵中非零元素的分布没有规律,在存储非零元素时必须同时存储该非零元素的行和列下标。这样稀疏矩阵中的每一个非零元素需由一个三元组 (i,j,ai)惟一确定,稀疏矩阵中的所有非零元素构成三元组线性表。,有一个67阶稀疏矩阵A, 对应的三元组线性表为： (0,2,1),(1,1,2),(2,0,3),(3,3,5), (4,4,6),(5,5,7),(5,6,4),5.3 广义表,广义表(简称表)是线性表的推广。广义表是n(n0)个元素的一个序列(n=0,空表)。设ai为广义表的第i个元素,则广义表GL的一般表示与线性表相同： GL=(a1,a2,ai,an)如果ai是单个数据元素,则ai是广义表GL的原子；如果ai是一个广义表,则ai是广义表GL的子表。,广义表的特性： 广义表中的数据元素有相对次序； 广义表的长度为最外层包含的元素个数； 广义表的深度为所含括弧的重数。(原子深度为0,空表深度为1)； 广义表可以共享；称为再入表； 广义表可以是一个递归表。即可以是自已的子表。递归表的深度是无穷值,长度是有限值； 任何一个非空广义表GL均可分解为表头head(GL) = a1和表尾tail(GL) = ( a2,an) 两部分。,广义表的表示下面讨论一般的广义表。小写字母表示原子,大写字母表示广义表的表名。假定广义表中的元素为char类型,每个原子的值被限定为英文字母。假定广义表是表达式,元素之间用逗号分隔,表元素的起止符号分别为左、右圆括号,空表在其圆括号内不包含任何字符。例如“(a,(b,c,d)” 符合广义表格式。,例如： A=() B=(e) C=(a,(b,c,d) D=(A,B,C)=(),(e),(a,(b,c,d) E=(a,(a,b),(a,b),c)如果把表名写在表的前面,广义表可表示如下： A() B(e) C(a, (b,c,d) ) D( A() , B(e) , C( a, ( b,c,d ) ) ) E( ( a, ( a, b ) , ( ( a, b ) , c ) ) ),广义表的图形表示:用圆圈和方框分别表示表和单元素,用线段把表和元素(元素结点应在其表结点的下方)连接起来.例如:A() B(e) C(a,(b,c,d) D(A(),B(e),C(a,(b,c,d) E(a,(a,b),(a,b),c),广义表举例:,广义表的链式存储结构 广义表是递归的数据结构,很难分配固定大小的存储空间,所以采用动态链式结构。 将一个广义表看成一棵树,为了方便存储,将其转换成一棵二叉树。 如下图所示:左边的图表示转换的中间状态,右边的图表示转换的最终状态(一棵二叉树)。从二叉树中看到,有两类结点,一类为圆圈结点,对应子表；另一类为方形结点,对应原子。,广义表的存储结构,下左图表示转换的中间状态,右边的图表示转换的最终状态(一棵二叉树)。从二叉树中看到,有两类结点,一类为圆圈结点,对应子表；另一类为方形结点,对应原子。,广义表的两种基本情况 ：(原子),例：广义表A=(),B=(e),C=(a, (b, c, d) )，D=(A, B, C)，E=(a, E)的存储结构如图所示。,广义表的运算1. 求广义表的长度 在广义表中,同一层次的每个结点是由link域链接起来的单链表。 求广义表的长度就是求单链表的长度.,2. 求广义表的深度 对于带头结点的广义表g ,广义表深度是所有子表中最大深度加1。若g为原子,其深度为0。 求广义表深度的递归模型f()如下：,f(g)=,0 若g为原子,1 若g为空表,MAXf(subg)+1 其他情况,subg为g的子表,4. 输出广义表 打印输出广义表时,需要对子表进行递归调用。,本章小结学习要点： (1)掌握广义表的定义。 (2)掌握广义表的链式存储结构。 (3)掌握广义表的基本运算,包括创建广义表、输出广义表、求广义表的长度和深度。 (4)灵活运用广义表这种数据结构解决一些综合应用问题。,数组习 题,稀疏矩阵常用的压缩存储方法有（）和（）两种。设有一个1010的对称矩阵A采用压缩方式进行存储，存储时以按行优先的顺序存储其下三角阵，假设其起始元素a00的地址为1，每个数据元素占2个字节，则a65的地址为（）。 address(aij)= address(a00)+(i*(i+1)/2+j)L 3.常对数组进行的两种基本操作为（）和（）。4.数组的存储结构采用( )存储方式；对矩阵压缩是为了节省( )。,5.设二维数组Amn（即m行n列）按列存储在数组Bm*n中，则二维数组元素Aij在一维数组B中的下标为（ ） A、i*n+j B、i+j*m C、i*jD、j*n+i6.有二维数组int a56,计算a25的内存地址.(a起始地址为1000,数组元素长度4字节)按行:LOC(a2,5)=LOC(a0,0)+(i*n+j)*k =1000+(2*6+5)*4=1068按列: LOC(a2,5)=LOC(a0,0)+(j*m +i )*k =1000+(5*5+2)*4=1108,1. 求广