ch5数组和广义表.ppt

第五章 数组和广义表,一、教学内容： 1、数组的定义和运算 2、数组的顺序存储结构 3、矩阵的压缩存储 4、广义表的定义 5、广义表的存储结构,二、教学要求： 了解稀疏矩阵的三元组和十字链表存储结构和基本运算； 理解稀疏矩阵和特殊矩阵进行压缩存储的方法及下标变换； 理解广义表的基本概念，掌握广义表的特点及存储结构； 掌握数组的两种存储表示方法，特别是以行为主的存储结构中的地址计算方法；,目 录,5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.4 广义表的定义 本章总结,5.1 数组的定义和特点,定义:数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表.,数组特点 数组结构固定(具有固定的上界和下界) 数据元素同构(元素类型相同) 数组运算 给定一组下标，存取相应的数据元素 给定一组下标，修改数据元素的值,在C语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型 typedef ElemType Array2mn; 等价于 typedef ElemType Array1n; typedef Array1 Array2m; 如:Array2 A;/数组一旦被定义，它的维数和维界就不再改变。 二维的数组 = 定长的线性表 a11 a12 a13 . a1n a21 a22 a23 . a2n Amxn= am1 am2 am3 . amn Am*n= (a11,a12,a13,.a1n),(a21,a22,a23,.a2n),.,(am1,am2,am3,.amn),数组的抽象数据类型,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( 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),每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。,对称矩阵顺序存储实例: 1 5 1 3 7 a00 5 0 8 0 0 a10 a 11 1 8 9 2 6 a20 a21 a23 3 0 2 5 1 7 0 6 1 3 an-1 0 a n-1 1 a n-1 2 a n-1 n-1 在这个下三角矩阵中，元素总数为：n(n+1)/2 因此，我们可以按从上到下、从左到右访问对称矩阵A中的元素，若ij，则ai j在下三角形中。 ai j之前的i行一共有1+2+i=i(i-1)/2个元素，在第i行上， ai j之前恰有j-1个元素（即ai0,ai1,ai2,aij-1），因此有： k=i*(i-1)/2+j-1 ( 0kn(n+1)/2) 若ij，则aij是在上三角矩阵中。因为aij=aji，所以只要交换上述对应关系式中的i和j即可得到： k=j*(j-1)/2+i-1 ( 0 kn(n+1)/2 ),2.下三角矩阵: 当ij时, aij = 0, (0=i,j=n-1),按行序为主序的顺序存储：,计算:若 i j, 数组元素Aij在数组B中的存放位置为 1 + 2 + + i + j = (i + 1)* i / 2 + j,地址:,3.三对角矩阵: 当|i-j| 1时, aij = 0, (1=i,j=n),Loc(aij)=Loc(a11)+2(i-1)+(j-1),地址计算:,M由(1,2,12), (1,3,9), (3,1,-3), (3,6,14), (4,3,24), (5,2,18), (6,1,15), (6,4,-7) 和矩阵维数（6,7）唯一确定,定义：非零元较零元少，且分布没有一定规律的矩阵 压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标及其值.,5.3.2 稀疏矩阵,稀疏矩阵的三元组线性表表示： 记录每个非零元素的行下标、列下标和元素值，这样稀疏矩阵中的每一个非零元素需要由一个三元组（i，j，ai，j）来唯一确定。记录稀疏矩阵中所有非零元素的三元组构成三元组线性表。,#define MAXSIZE 12500 /假设非零元个数的最大值 typedef struct int i,j; /非零元素行号/列号 ElemType e; /非零元素的值 Triple; /三元组 typedef union Triple dataMAXSIZE+1; /非零元三元组表,data0未用 int mu,nu,tu; /矩阵行数、列数、非零元个数 TSMatrix;/稀疏矩阵类定义,稀疏矩阵的抽象数据类型(三元组顺序表）,稀疏矩阵转置算法思想,显然，一个稀疏矩阵的转置仍然是一个稀疏矩阵，方法是：设将矩阵M转置为矩阵T （1）将矩阵的行列值交换 （2）将每一个三元组的i和j相互调换 （3）重排三元组之间的次序 可以有两种处理方法：,方法一：按照M(m*n)的列序来进行转置 设矩阵列数为nu，对矩阵三元组表扫描nu次。第k次检测列号为k的项。 第k次扫描找寻所有列号为k的项，将其行号变列号、列号变行号，顺次存于转置矩阵三元组表。,Status TransposeSMatrix(TSMatrix M, TSMatrix /TransposeSMatrix,算法 稀疏矩阵的转置,该算法主要工作是在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的稀疏矩阵。,算法分析：,方法二：快速转置 按ma中三元组次序转置，转置结果放入b中恰当位置.此法关键是要预先确定M中每一列第一个非零元在mb中位置，为确定这些位置，转置前应先求得M的每一列中非零元个数.,实现：设两个数组 numcol：表示矩阵M中第col列中非零元个数 cpotcol：指示M中第col列第一个非零元在mb中位置 显然有：,示例：,算法分析：T(n)=O(M的列数n+非零元个数t) 若 t 与mn同数量级，则T(n)=O(mn),算法描述：(略),7 6 8,1 3 -3,1 6 15,2 1 12,2 5 18,3 1 9,3 4 24,4 6 -7,6 3 14,4,6,2,9,7,5,3,5.4 广义表,5.4.1 基本概念 5.4.2 广义表的存储结构 5.4.3 广义表的运算,5.4.1 基本概念,广义表（简称表）：是n（n0）个元素的一个序列，若n=0时则称为空表。设ai为广义表的第i个元素，则广义表GL一般表示为： GL=（a1，a2，ai，ai+1，an） n表示广义表的长度，即广义表中所含元素的个数，n0。如果ai是单个数据元素，则称ai是广义表GL的原子；如果ai是一个广义表，则ai是广义表GL的子表。 当GL非空时，第一个元素a1称为该广义表的表头（head），除第一个元素外所有元素构成的表（a2，ai，ai+1，an）称为该广义表的表尾（tail）。显然，一个广义表的表头可以是原子或子表，但表尾始终是一个广义表。括号嵌套的最大次数称为广义表的深度。,广义表的图形表示法：用圆圈和方框分别表示原子和子表，并用线段把表和它的元素（元素结点应在其表结点的下方）连接起来。 注意： 1 习惯上，用大写字母表示广义表的名称，用小写字母表示原子。 2 广义表的定义是一种递归定义。 3 （）和（）不同，前者为空表，长度为0；后者为包含一个空表的广义表，长度为1，可分解得到其表头、表尾均为空表（）。,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 广义表的存储结构,通常采用链式存储结构。在广义表中原子和子表所含的信息不同，所以在存储时也有原子和子表之分。 广义表的头尾链接存储定义：,包括值域和指向其后继结点的指针域,包括指向子表中第一个结点的指针域和指向其后继结点的指针域,typedef struct GLNode int tag; union char atom; struct GLNode *hp; ; struct GLNode *tp; *GList;,表结点,原子结点,示例,5.4.3 广义表的运算,求广义表的长度 求广义表的深度 建立广义表 输出广义表,求广义表的长度,分析：由于广义表中同一层的结点都是通过next指针域链接起来的，所以，可采用求单链表长度的方法。 实现算法：（略，可编写递归和非递归两种算法） 注意：广义表采用带有附加结点的链式存储结构。 两种算法的时间复杂度都是O（n）。由于在递归算法中需要为值参GL分配空间，用来存储指针值，所以其空间复杂度为O（n）。非递归算法的空间复杂度为O（1）。,求广义表的深度,分析：广义表深度的递归定义是它等于所有子表中表的最大深度加1，若一个表为空或仅由单元素所组成，则深度为1。递归函数如下： 1 GL为空或只有一个单元素 depth（GL）= maxdepth(GL-sublist)+1 其它情况 实现算法： （略）,时间复杂度为O（n），其中n为广义表中所有结点的个数。该算法的空间复杂度为O（m），m为广义表的深度。,建立广义表,分析：建立广义表过程可以通过递归实现。将广义表分解成表头和表尾，而表头和表尾若仍是广义表，则继续分解为表头和表尾。创建过程就是建立表头和建立表尾。 区分表头和表尾中的元素是单元素还是表元素的方法： （1）如果 i为“（）”，表示这是一个空的表元素，字符串长度为2； （2）如果 i长度为1，表明它是一个单元素； （3）如果长度1，这是一个表元素。 前两种情况就可作为递归过程的结束条件。 实现算法： （略） 时间复杂度和空间复杂度：0（n），n广义表中字符个数,输出广义表,分析：设GL为表头指针，则输出时，需要对子表进行递归调用。当GL结点为表结点时，应首先输出作为一个表的起始符号“（”。然后再输出以sublist为表头指针的表；当GL结点为原子结点时，则应输出该元素的值。当以sublist为表头指针的表输出结束后，应在其最后输出一个作为表终止符的“）”。当GL结点输出结束后，若存在后继结点，则应首先输出一个逗号作为分隔符，然后再递归输出由next指针所指向的后继表。 实现算法： （略） 时间复杂度和空间复杂度：0（n），n广义表中结点个数。,本章总结：,一维数组在内存中开辟一块连续的存储单元存储数据，适合于随机查找。多维数组可以看成是一维数组的推广，也是一个线性表，表