《数组和广义表数据结构》由会员分享，可在线阅读，更多相关《数组和广义表数据结构（37页珍藏版）》请在金锄头文库上搜索。
1、第五章 数组和广义表,一、基本概念,1、数组的定义：n（n1）个相同数据类型的数据元素a0,a1,an-1有限序列，且该序列存储在一块地址连续的内存单元中。数组的定义类同于采用顺序存储结构的线性表。 在一维数组中，一旦a0的存储地址确定，每个数据元素的存储单元k就确定，ai的存储地址LOC(ai)就可以由以下公式求出： LOC(ai) =LOC(a0)+i*k (0 i n) 一维数组的任一数据元素的存储地址可直接计算得到，所以一维数组中的任一数据元素可直接存取，故一维数组是一种随机存储结构。 对于一个m行n列的二维数组Amn，有,可以认为Amn=A，A是这样的一维数组：A=(a0,a1,ai
2、,am-1), 其中，ai=(ai,0,ai,1,ai,n-1) (0jm) 一个二维数组可以看做是每个数据元素都是相同类型的一维数组的一维数组。依此类推，任何多维数组都可以看成是一个线性表，这时线性表中的每个数据元素也是一个线性表。多维数组是线性表的推广。 推广到d维数组，不妨将其看作是一个由d-1维数组作为数据元素的线性表。,数组的性质： 数组中的数据元素数目固定。一旦定义了一个数组，其数据元素不再有增减变化。 数组中的数据元素具有相同的数据类型。 数组中的每个数据元素都和一组唯一的下标值对应。 数组是一种随机存储结构。可随机存取数组中的任意数据元素。,2、数组的基本操作,一旦建立了数组，
3、结构中的数据元素个数和元素之间的关系就不再发生改变，所以不会有元素的插入和删除操作，其基本运算主要是元素的取值和复制操作。,二、数组的存储结构,对于一维数组来说，其存储结构是线性的，关系式为 。 对二维数组来说，由于计算机的存储结构是线性的，如何用线性结构存放二维数组元素就有一个行/列问题。对于式的m行n列的二维数组Amn ，当满足式时，我们说是以行为主序的存储方式，即先存储第0行，然后紧接着存储第1行，最后是m-1行。此时，二维数组的线性排列次序为：a0,0,a0,1,a0,n-1,a1,0,a1,n-1,am-1,0,am-1,n-1。 在C、Pascal和BASIC等大多数程序设计语言中
4、采用的是以行序为主序的存储方式。在ForTran等少数语言中采用的是以列序为主序的存储方式。 二维数组中任一数据元素ai,j的存储地址： LOC( ai,j )=LOC(a0,0)+(i*n+j) （其中n为列数） ,【例1】对二维数组float a54，计算： （1）数组a中的数组元素数目； （2）若数组a中的起始地址为2000，且每个数组元素的长度为32位，数组元素a32的内存地址。 【例2】有m名学生，每人考n门功课，试写出求任一课程总分数的数据结构和算法。,三、特殊矩阵的压缩,特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。为节省空间，特别是在高阶矩阵的情况下，可以利用特殊矩阵的规
5、律，对它们进行压缩，即，使多个相同的非零元素共享一个存储单元，对零元素不分配存储空间。 特殊矩阵的主要形式：对称矩阵、对角矩阵等，它们都是方阵。 1、对称矩阵的压缩 如果一个n阶方阵A中的元素关于对角线对称ai,j=aj,I (0=n-1) 存储时可只存储对称矩阵中上三角和下三角中的元素，使得对称矩阵的元素共享一个存储空间。这样就可以把n2个元素压缩到n(n+1)/2个元素的空间中。,以行序为主序存储其下三角（包括对角线）的元素。假设一维数组sa0n(n+1)/2作为n阶矩阵A的存储结构，在sa中只存储对称矩阵A的下三角元素，则A中任一元素Aij和sak之间存在着如下对应关系：,由此称一维数组
6、sa0n(n+1)/2为n阶对称矩阵A的压缩存储。其存储关系如下表：该压缩形式只需按上式作一映射即可实现矩阵的随机存储。,有些非对称矩阵也可以借用此方法存储，如n阶下（上）三角矩阵。 所谓n阶下（上）三角矩阵，是指矩阵的上（下）三角（不包括对角线）中的元素均为常数C或0的n阶方阵。设以一维数组sb0n(n+1)/2作为n阶三角矩阵B的存储结构，则B中任一元素bij和sbk之间存在如下对应关系：,2、对角矩阵的压缩 若一个n阶方阵满足其所有非零元素都集中在以主对角线为中心的带状区域中，则则称其为n阶对角矩阵。一个m（1=mn）条非零元素的n阶对角矩阵如下图所示：,一个有m条非零元素的n阶对角矩阵
7、A的非零元素总数u为：,一个有m条非零元素的n阶对角矩阵A的上对角矩阵（i=j）：,四、稀疏矩阵,一个阶数较大的矩阵中的非零元素的个数s相对于矩阵元素总个数t十分小时，即st时，称该矩阵为稀疏矩阵。 特点：非零元素的分布没有任何规律。,稀疏矩阵的三元组表示：,稀疏矩阵的十字链表表示,十字链表为稀疏矩阵的每一行设置一个单独链表，同时也为每一列设置一个单独链表。矩阵中的每一个非零元素就同时包含在两个链表中，即每一个非零元素同时包含在所在行的行链表和所在列的列链表中。 优点：大大降低了链表的长度，方便了算法中行方向和列方向的搜索，因而大大降低了算法的时间复杂度。,数组的基础要点,1、设二维数组A-2
8、030,-3020，每个元素占4个存储单元，存储起始地址为200，若按行优先顺序存储，则元素A25,18的存储地址为（ ），若按列优先顺序存储，则元素A-18,-25的存储地址为（ ）。 2、将一个A11000，11000的三对角矩阵，按行优先存入一维数组B1298中，A中元素a66,65（即该元素下标i=66,j=65）在数组B中的位置K为（ ）。 3、数组A110，110的每个元素占5个单元，将其按列优先顺序存储在起始地址为1000的连续存储单元中，则元素A6,5的地址为（ ）。 4、已知二维数组Amn采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC(A00)
9、，则Aij的地址是（ ）。 5、有一个10阶对称矩阵A，采用压缩方式存以行序为主序存储，且A00的地址为1，则A85的地址为（ ）。,6、若对n阶对称矩阵以行序为主序存储其下三角的元素（包括对角线的所有元素）依次存放在一维数组B1n(n+1)/2中，则B中确定aij（i=j），在数组B中的下标位置是（ ）。 8、将下三角矩阵A18,18的下三角部分逐行存储到起始地址为1000的内存单元中，已知每个元素占4个单元，则A7，5的地址为（ ）。 9、对矩阵采用压缩存储是为了节省存储空间。,广义表,简称表，是线性表的推广。 一个广义表是n（n0）个元素的一个序列。若n=0时称为空表。 设ai为广义表中
10、的第i个元素，则广义表GL的一般表示与线性表相同： GL=(a1,a2,ai,ai+1,an) 其中n为广义表的长度，即广义表中所含元素的个数。 广义表的定义是递归的，是一种递归的数据结构。,【例】下列广义表的长度分别是多少？ A=() B=(e) C=(a,(b,c,d) D=(A,B,C)=(), (e), (a,(b,c,d) E=(a,(a,b),(a,b),c),广义表的图形表示,若用圆圈和方框分别表示表和单元素，并用线段把表和它的元素(元素结点应在其表结点的下方)连接起来，则可得到一个广义表的图形表示。 广义表的图形表示像倒着画的一棵树，树根结点代表整个广义表各层树枝结点代表相应的
11、子表，树叶结点代表单元素或空表。,广义表的图形表示,表头、表尾深度,表的第一个元素ai为广义表GL的表头，其余部分(a2，aj, aj+1,，an)为GL的表尾，分别记作head(GL)=a1和tail(GL)=(a2,，aj, aj+1,，an)。 显然，一个广义表的表尾始终是一个广义表。空表无表头表尾。 【例】 A无表头表尾 head(B)=e, tail(B)=0 head(C)=a, tail(C)=(b, c, d) head(D)=0，tail(D)=(e)，(a, (b，c d) head(E)=(a, (a, b), (a, b), c), tail(E)=(),广义表的深度,
12、一个广义表中括号嵌套的最大次数为它的深度。在图形表示中，广义表深度是指从树根结点到每个树枝结点所经过的结点个数的最大值。如广义表A和B的深度为1（注意广义表A和广义表B的深度相同，因它们均只有一重括号），广义表C、D、E的深度分别为2，3和4。,广义表的存储结构,广义表是一种递归的数据结构，因此很难为每个广义表分配固定大小的存储空间，所以其存储结构只好釆用动态链式结构。 我们将一个广义表看成一棵树，为了方便存储，将其转换成一棵二叉树。其转换过程将在第6章中介绍，这里以示例中的广义表C说明其转换过程。如图所示，左边的图表示转换的中间状态，右边的图表示转换的最终状态，即一棵二叉树。从二叉树中看到，
13、有两类结点：一类为圆圈结点，在这里对应子表；另一类为方形结点，在这里对应原子。,广义表的转换过程,为了使子表和原子两类结点既能在形式上保持一致，又能进行区别，可采用如下结构形式：,其中，tag域为标志字段，用于区分两类结点。sublist或data域由tag决定。若tag=0，表示该结点为原子结点，则第二个域为data，存放相应原子元素的信息；若tag=l，表示该结点为表结点，则第二个域为sublist，存放相应子表第一个元素对应结点的地址。link域存放与本元素同一层的下一个元素所在结点的地址，当本元素是所在层的最后一个元素时，link域为NULL。 例：前面的广义表C的存储结构如下图所示(
14、很多数据结构公教科书上称之为带表头结点的广义表的链表存储结构,C语言描述结点的类型，可用如下定义：,广义表的运算,广义表的运算主要有求广义表的长度和深度，向广义表插入元素和从广义表中查找或删除元素，建立广义表的存储结构，输出广义表和复制广义表等。由于广义表是一种递归的数据结构，所以对广义表的运算一般釆用递归的算法。 1.求广义表的长度 在广义表中，同一层次的每个结点是通过link域链接起来的，所以可把它看做是由link域链接起来的单链表。这样，求广义表的长度就是求单链表的长度，可以釆用以前介绍过的求单链表长度的方法求其长度。 2.求广义表的深度 广义表深度的递归定义是它等于所有子表中表的最大深
15、度加1，若一个表为空或仅由单元素所组成，则深度为1。,3.建立广义表的存储结构 假定广义表中的元素类型ElemType为chai类型，每个原子的值被限定为英文字母。并假定广义表是一个表达式，其格式为：元素之间用一个逗号分隔，表元素的起止符号分别为左、右圆括号，空表在其圆括号内不包含任何字符。例如“(a，(b, c, d)”就是一个符合上述规定的广义表格式。 建立广义表存储结构的算法同样是一个递归算法。该算法使用一个具有广义表格式的字符串参数s,返回由它生成的广义表存储结构的头结点指针h。在算法的执行过程中，需要从头到尾扫描s的每一个字符。当碰到左括号时，表明它是一个表元素的开始，则应建立一个由
16、h指向的表结点，并用它的sublist域作为子表的表头指针进行递归调用，来建立子表的存储结构；当碰到一个英文字母时，表明它是一个原子，则应建立一个由h指向的原子结点；当碰到一个“）”字符时，表明它是一个空表，则应置h为空。当建立了一个由h指向的结点后，接着碰到逗号字符时，表明存在后继结点，需要建立当前结点(即由h指向的结点）的后继表；当碰到右括号或分号字符时，表明当前所处理的表已结束，应该置当前结点的link域为空。 4.输出广义表 5.广义表的复制,广义表的基础要点,(1) 广义表的深度定义为广义表中括弧的重数。 (2)设广义表L=(),()，则head(L)是(), tail是();L的长度是2. (3)对于广义表L=(
