ch5数组和广义表(冲突STEVEN–PC2006–08–2517–10–14).ppt

第五章 数组和广义表 目 录 5.1 数组的定义和特点 定义:数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表. 数组的抽象数据类型 ADT Array { 数据对象：D = {aj1j2...jn | n(0)称为数组的维数,bi是数组第i维的长度, ji是数组元素的第i维下标, aj1j2...jn属于Elemset} 数据关系： R={R1 , R2 ... Rn} Ri = {＜ aj1...ji...jn, aj1...ji+1...jn ＞|0 ? jk? bk-1, 1 ? k ? n, aj1...ji...jn, aj1...ji+1...jn 属于D}。 基本操作： InitArray(A,n,bound1,bound2,...,boundn); DestroyArray (A); Value(A,e,index1,index2,...,indexn); Assign(A,e, index1,index2,...,indexn) }ADT Array 5.2 数组的顺序表示和实现 通常有两种顺序存储方式： 以行序为主序 以列序为主序 数组的应用 生命细胞游戏 魔术方阵 5.3 矩阵的压缩存储 矩阵: 二维数组 特殊矩阵: 大量重复元素或大量0元素 稀疏矩阵: 大量0元素 压缩存储: 重复元素只分配一个存储空间,0元素不分配存储空间 5.3.1 特殊矩阵 1.对称矩阵: aij = aji (1=i,j=n) 2.下三角矩阵: 当ij时, aij = 0, (0=i,j=n-1) 稀疏矩阵转置算法思想 显然，一个稀疏矩阵的转置仍然是一个稀疏矩阵，方法是：设将矩阵M转置为矩阵T （1）将矩阵的行列值交换 （2）将每一个三元组的i和j相互调换 （3）重排三元组之间的次序 可以有两种处理方法： 该算法主要工作是在p*col的两重循环中做的，所以时间复杂度是O(nu*tu)。而一般矩阵的转置算法是在nu*mu的两重循环中做的，时间复杂度是O(nu*mu)。当稀疏矩阵的非零元个数tu=nu*mu时，其时间复杂度O(nu*tu)=O(nu*nu*mu)=O(nu2*mu)大大高于一般矩阵的时间复杂度，所以该算法仅适用于tunu*mu的稀疏矩阵。 5.4 广义表 5.4.1 基本概念 5.4.2 广义表的存储结构 5.4.3 广义表的运算 5.4.1 基本概念 广义表（简称表）：是n（n≥0）个元素的一个序列，若n=0时则称为空表。设ai为广义表的第i个元素，则广义表GL一般表示为： GL=（a1，a2，…，ai，ai+1，…，an） n表示广义表的长度，即广义表中所含元素的个数，n≥0。如果ai是单个数据元素，则称ai是广义表GL的原子；如果ai是一个广义表，则ai是广义表GL的子表。 当GL非空时，第一个元素a1称为该广义表的表头（head），除第一个元素外所有元素构成的表（a2，…，ai，ai+1，…，an）称为该广义表的表尾（tail）。显然，一个广义表的表头可以是原子或子表，但表尾始终是一个广义表。括号嵌套的最大次数称为广义表的深度。 A=( ); //A是一个空表 B=(e); //表B有一个原子 C=(a,(b,c,d)); //两个元素为原子a和子表 (b,c,d) D=(A,B,C); //有三个元素均为列表 E=(a,E); //递归的列表,包含两个元素,一个是单元素a,另一个是子表,但该子表是其自身.所以,E相当于一个无限的广义表( a,(a,(a,…))). 5.4.2 广义表的存储结构 通常采用链式存储结构。在广义表中原子和子表所含的信息不同，所以在存储时也有原子和子表之分。 广义表的头尾链接存储定义： 5.4.3 广义表的运算 求广义表的长度 求广义表的深度 建立广义表 输出广义表 求广义表的长度 分析：由于广义表中同一层的结点都是通过next指针域链接起来的，所以，可采用求单链表长度的方法。 实现算法：（略，可编写递归和非递归两种算法） 注意：广义表采用带有附加结点的链式存储结构。 两种算法的时间复杂度都是O（n）。由于在递归算法中需要为值参GL分配空间，用来存储指针值，所以其空间复杂度为O（n）。非递归算法的空间复杂度为O（1）。 求广义表的深度 分析：广义表深度的递归定义是它等于所有子表中表的最大深度加1，若一个表为空或仅由单元素所组成，则深度为1。递归函数如下：