第5章 数组与广义表.doc

第5章数组和广义表（4学时）（一）教学目的： 掌握数组的定义及顺序表示与实现；掌握矩阵的压缩存储；广义表的定义及存储结构。（二）教学重点：1、数组的定义及其存储2、特殊矩阵的压缩存储3、稀疏矩阵逻辑结构和存储结构4、广义表的逻辑结构和存储结构5、数组和广义表的操作应用举例（三）教学难点：1、矩阵的压缩存储2、广义表的存储结构51数组的定义一、数组的抽象类型定义：数据对象：D= |n(0)称为数组的维数，bi是数组第i维的长度，ji是数组元素的第i维下标，ElemSet数据关系：R=R1，R2，Rn Ri= 0jkbk-1，1kn且ki，0jibi-2，D，I=2,n二、数组基本操作：1、InitArray(&A,n,bound1,boundn)操作结果：若维数n和各维长度合法，则构造相应的数组A，并返回OK。2、DestroyArray（&A）操作结果：销毁数组A。3、Value(A,&e,indeex1,indexn)初始条件：A是n维数组，e为元素变量，随后是n个下标值。操作结果：若各下标不超界，则e赋值为所指定的A的元素值，并返回OK。4、Assign(&A,e,index1,indexn)初始条件：A是n维数组，e为元素变量，随后是n个下标值。操作结果：若下标不超界，则将e的值赋给所指定的A的元素，并返回OK。三、数组与线性表的关系：1、二维数组与线性表的关系：以把二维数组看成是这样一具定长线性表：它的每个数据元素也是一个定长线性表。A=(a0,a1,ap) (p=m-1或n-1)其中每个数据元素aj是一个列向量形式的线性表aj=(a0j,aij,am-1j) 0jn-1ai=(ai0,ai1,ai,n-1) 0im-1在C语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型，也就是说，typedef ElemType Array2mn;等价于 typedef ElemType Array1n;typedef Array1 Array2m;(a) (b) (C )图51二维数组图例（a）矩阵形式表示；（b）列向量的一维数组；（c）行向量的一维数组2、n维数组与线性表的关系：同理，一个n维数组类型可以定义为其数据元素为n-1维数组类型的一维数组类型。四、数组的基本操作数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。52数组的顺序表示和实现一、二维数组的顺序存储：则用一组连续存储单元存放数组的数据元素就有个次序约定问题。对二维数组可有两种存储方式：在扩展BASIC、PL/1、COBOL、PASCAL和C语言中，用的都是以行序为主序的存储结构，而在FORTRAN语言中，用的是以列序为主序的存储结构。（a） 以列序为主序 （b）以行序为主序图5.2 二维数组的两种存储结构二、数组的地址计算：1、二维数组的地址计算：假设每个数据元素占L个存储单元，则二维数组A中任一元素aij的存储位置可由下式确定LOC（i,j）=LOC（0，0）+（b2i+j）L (51)式中，LOC（i,j）是aij的存储位置；LOC（0，0）是a00的存储位置，即二维数组A的起始存储位置，也称为基地址或基址。2、n维数组地址计算：LOC(j1,j2,jn)=LOC(0,0,0)(b2bnj1b3bnj2bnjn-1jn)L=LOC(0,0,0)()L或缩写成LOC（j1,j2,jn）=LOC(0,0,0)+ (52)其中Cn=L,ci-1=bici, 1j=j; p-e=e;if(M.rheadpi=NULLp-right=M.rheadi;M.rheadi=p; else /寻查在行表中的插入位置 for (q=M.rheadi;（q-right）&q-right-jj; q=q-right);else /寻查在列表中的插入位置 for(q=M.cheadj;(q-down)&. Q-down-iI; q=q-down); p-down=q-down; q-=down=p; / 完成列插入 return OK;/CreateSMatrix.OL算法 5.45.4 广义表的定义顾名思议，广义表是线性表的推广。也有人称其为列表（lists，用复数形式以示与统称的表list的区别）。广泛地用于人工智能等领域的表处理语言LISP语言，把广义表作为基本的数据结构，就连程序也表示为一系列的广义表。一、广义表的定义：1、抽象数据类型定义：ADT GList 数据对象：D=数据关系：R1=ei-1,ei| ei-1, ei D, 2in2、广义表的表示：广义表一般记作 LS=（1，2，n）其中，LS是广义表（1，2，n）的名称，n是它的长度。可以是单个元素，也可是广义表，分别称为广义表LS的原子和子表。习惯上，用大写字母表示广义表的名称，用小写字母表示原子。当广义表LS非空时，称第一个元素为LS的表头（Head），称其余元素组成的表（2，3，n）是LS的表尾（Tail）。3、广义表的举例：（1）A=（）A是一个空表，它的长度为零。（2）B=（e）列表B只有一个原子e，B的长度为1。（3）C=（a,(b,c,d)）列表C的长度为2，两个元素分别为原子和子表(b,c,d)。（4）D=（A，B，C）列表D的长度为3，3个元素都是列表。显然，将子表的值代入后，则有D=（），(e),(a,(b,c,d)。（5）E=（a,E）这是一个递归的表，它的长度为2。E相当于一个无限的列表E=(a,(a,a,)）。二、表头函数 head()和表尾函数tail()：根据前述对表头、表尾的定义可知：任何一个非空列表其表头可能是原子，也可能是列表，而其表尾必定为列表。例如：GetHead(B)=e, GetTail(B)=(),GetHead(D)=A, GetHead(D)=(B,C)由于（B，C）为非空列表，则可继续分解得到：GetHead(B,C)=B, GetHead(B,C)=C，值得提醒的是列表（）和（）不同。前者为空表，长度n=0；后者长度n=1，可分解得到其表头、表尾均为空表（）。图5.7 列表的图形表示5.5广义表的存储结构一、广义表结点的设定：两种结构的结