《第5章数组与广义表》由会员分享，可在线阅读，更多相关《第5章数组与广义表（10页珍藏版）》请在金锄头文库上搜索。
1、第 5 章数组和广义表（4 学时）（一）教学目的： 掌握数组的定义及顺序表示与实现；掌握矩阵的压缩存储；广义表的定义及存储结构。（二）教学重点：1、数组的定义及其存储2、特殊矩阵的压缩存储3、稀疏矩阵逻辑结构和存储结构4、广义表的逻辑结构和存储结构5、数组和广义表的操作应用举例（三）教学难点：1、矩阵的压缩存储2、广义表的存储结构51 数组的定义一、数组的抽象类型定义：数据对象：D= |n(0)称为数组的维数，bi 是数组第 i 维的长度，ji 是数njja21组元素的第 i 维下标， ElemSetnjj21数据关系：R=R1，R2 ， ，Rn Ri= nini jjjja 111,0jkb
2、k-1，1 kn 且 k i，0jibi-2， D，I=2,nnini jjjja 111,二、数组基本操作：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 维
3、数组，e 为元素变量，随后是 n 个下标值。操作结果：若下标不超界，则将 e 的值赋给所指定的 A 的元素，并返回 OK。三、数组与线性表的关系：1、二维数组与线性表的关系：以把二维数组看成是这样一具定长线性表：它的每个数据元素也是一个定长线性表。A=(a0,a1,ap) (p=m-1 或 n-1)其中每个数据元素 aj 是一个列向量形式的线性表aj=(a0j,aij,am-1j) 0 jn-1ai=(ai0,ai1,ai,n-1) 0 im-1在 C 语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型，也就是说，typedef ElemType Array2mn;等价于
4、 typedef ElemType Array1n;typedef Array1 Array2m;01020,1 0,101, 1,1,01,0,1, 1,.n nmnmmn mnaaaaAnA (a) (b)010,101,1,0,1,()()()nnn naaa (C )图 51 二维数组图例（a）矩阵形式表示；（b ）列向量的一维数组；（c）行向量的一维数组2、n 维数组与线性表的关系：同理，一个 n 维数组类型可以定义为其数据元素为 n-1 维数组类型的一维数组类型。四、数组的基本操作数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素
5、值的操作。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)式中，L
6、OC（i,j ）是 aij 的存储位置； LOC（0，0）是 a00 的存储位置，即二维数组A 的起始存储位置，也称为基地址或基址。2、n 维数组地址计算：LOC(j1,j2,jn)=LOC(0,0,0)(b2bnj1 b3bn j2bnjn-1jn)L=LOC(0,0,0)( )L1niknjbj或缩写成LOC（j1,j2,jn ）=LOC(0,0,0)+ (52)1nicj其中 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
7、;（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 语言，把广义表作为基本的数据结构，就连程序也表示为一系列的广义表。一、广
8、义表的定义：1、抽象数据类型定义：ADT GList 数据对象：D=,;0;,21为 某 个 数 据 对 象 或AtomSe GlisteAtomSeni ii 数据关系：R1= ei-1,ei| ei-1, ei D, 2in2、广义表的表示：广义表一般记作 LS=（1，2，n）其中，LS 是广义表（1，2，n ）的名称，n 是它的长度。 可以是单个元素，i也可是广义表，分别称为广义表 LS 的原子和子表。习惯上，用大写字母表示广义表的名称，用小写字母表示原子。当广义表 LS 非空时，称第一个元素 为 LS 的表头（Head） ，称其余元素组成的表1（2，3，n ）是 LS 的表尾（Tail
9、 ） 。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()：根据前述对表头、表尾的定义可知：任何一个非空列表其表头可能是原子，也可能
10、是列表，而其表尾必定为列表。例如：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 广义表的存储结构一、广义表结点的设定：两种结构的结点：（1）一种是表结点，用以表示列表；一个表结点可由 3 个域组成：标示域、指示表头的指针域和指示表尾的指针域；（2）一种是原子结点，用以表示原子。而原子结点只需两个域：标志域和值域（如图 5.8 所示） 。其形式定义说明如下：二、广义表的存储结构图：图 5.9 广义表的存储结构示例
