树结构综合版1——7数据结构ch5数组和广义表

数 据 结 构 Data Structure,主讲人： 刘 玮,第五章 数组和广义表,数组的定义,5.1,数组的顺序表示和实现,5.2,矩阵的压缩存储,5.3,广义表的基本概念和存储结构,5.4,5.1 数组的定义,数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表。,5.1.1 什么是数组,数组是n（n0）个相同数据类型数据元素构成的有限序列。,( ),( ),( ),( ),( ),( ),( ),( ),( ),二维数组同样满足数组的定义。二维数组可以看成一个特殊的一维数组，其中的每个元素又是一个一维数组。,5.1.2 数组的抽象数据类型ADT,Value(A, &e, index1,indexn),初始条件：A是n维数组，e为元素变量， 随后是n个下标值。,操作结果：若各下标不超界，则e赋值为 所指定的A的元素值，并返回OK。,Assign(&A, e, index1,indexn),初始条件：A是n维数组，e为元素变量， 随后是n个下标值。,操作结果：若各下标不超界，则e的值赋给 所指定的A的元素值，并返回OK。,数组的特点：,数组中的数据元素数目固定(结构固定)；,数组中的数据元素具有相同的数据类型(元素同构)；,数组中的每个数据元素都与一组唯一的下标值相对应；,数组是一种随机存取结构。,5.2 数组的顺序表示和实现,在数组中插入或者删除一个元素有意义吗？,数组应该采用何种方式存储？,顺序存储方式,5.2 数组的顺序表示和实现,用一组连续的存储单元来表示数组。 有两种存储方式,以行为主:对二维数组进行“按行切分”，即将数组中的数据元素“按行依次排放”在存储器中； 以列为主：对二维数组进行“按列切分”，即将数组中的数据元素“按列依次排放”在存储器中。,每个数据元素占L个存储单元； LOC(0,0)表示数据元素a00的存储地址，是数组的起始地址（基地址）； LOC(i,j)表示下标为(i,j)的数据元素aij的存储地址。,按行序为主序存放,LOC(i,j)=LOC(0,0)+(i*n+j)*L,“行序为主序” 二维数组中任一元素aij的存储位置：,推广到一般情况，可得到n维数组数据元素存储位置：,n维数组的映像函数，数组元素的存储位置是其下标的线性函数。,每个数据元素占L个存储单元； LOC(0,0)表示数据元素a00的存储地址，是数组的起始地址（基地址）； LOC(i,j)表示下标为(i,j)的数据元素aij的存储地址。,按列序为主序存放,LOC(i,j)=LOC(0,0)+(J*m+I)*L,数组的C语言表示,5.3 矩阵的压缩存储,压缩存储,为多个值相同的矩阵只分配一个存储空间； 对零元不分配空间。,值相同的元素或者0元素在矩阵中的分布有一定规律。,5.3.1 特殊矩阵,特殊矩阵,特殊矩阵的压缩存储,仅存储下三角,对称矩阵,下三角矩阵,对角矩阵,非零元较零元少，且分布没有一定规律的矩阵。,5.3.2 稀疏矩阵,稀疏矩阵,压缩原则：尽量少存或不存0元；尽量减少没有意义的运算；运算要方便。,压缩存储方法：三元组顺序表、行逻辑连接和十字链表。,存储特点,三元组顺序表,对于矩阵中每个非0元素，用它的行号、列号、元素值，即（i, j, aij）表示。 将表示稀疏矩阵的所有非0元素的三元组按行优先（列优先）顺序排列，则可得到一个其结点均是三元组的线性表，称为三元组表。 以顺序存储结构来表示三元组。 要唯一确定一个稀疏矩阵，还必须存储该矩阵的行数和列数。,数据类型定义,# define MAXSIZE 12500 三元组结点： typedef struct int i, j; ElemType e; Triple; 稀疏矩阵： typedef struct Triple dataMAXSIZE+1 ; int mu, nu, tu; /*行、列、非零元素个数*/ TSMatrix ;,问题描述：,已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表。,常规算法： for(col=1;col=nu;col+) for(row=1;row=mu;row+) Tcolrow=Mrowcol;,例子:求转置矩阵,解决思路：,将矩阵行、列维数互换； 将每个三元组中的i和j相互调换； 重排三元组次序；,方法一:按矩阵的列序转置,按T.data中三元组次序依次在M.data中找到相应的三元组元素进行转置。,方法二:按矩阵的行序转置,按M.data中三元组次序转置，将转置结果放入T.data中适当位置。,优点：,非零元在表中按行序有序存储，便于进行依行序处理的矩阵运算。,缺点：,若需按行号存取某一行的非零元，则需从头开始查找。,为了便于随机存储任意一行的非零元，需要知道每一行的第一个非零元在三元组表中的位置。,行逻辑连接的顺序表,# define MAXSIZE 12500 三元组结点： typedef struct int i, j; ElemType e; Triple; 稀疏矩阵： typedef struct Triple dataMAXSIZE+1 ; int rposMAXRC+1; /*各行第一个非零元的位置表 int mu, nu, tu; /*行、列、非零元素个数*/ TSMatrix ;,问题描述：,已知两个稀疏矩阵M和N的三元组表，求两个矩阵相乘的结果矩阵Q。,常规算法： for(i=1;i=m1;i+) for(j=1;j=n2;j+) Qij=0; for(k=1;k=n1;k+) Qij += Mik* Nkj;,例子:求矩阵乘法,1、只对M和N的非零元进行计算；,2、M中列号与N中行号相等的非零元相乘即可；,3、Q与M的行号对齐的，且Qij是累加的结果。,Q初始化； if （Q是非零矩阵） for(arrow=1;arrow=M.mu;arrow+) ctemp=0; 计算Q中第arrow行的积并存入ctemp中； 将ctemp中非零元压缩存储到Q.data； ,分析上述算法的时间复杂度,例子:求矩阵乘法,1、累加器ctemp初始化的时间复杂度为O(M.mu×N.nu) 2、求Q的所有非零元的时间复杂度为O(M.tu×N.tu/N.mu) 3、进行压缩存储的时间复杂度为O(M.mu×N.nu),总的时间复杂度O(M.mu×N.nu+M.tu×N.tu/N.mu),若M是m行n列的稀疏矩阵，N是n行p列的稀疏矩阵，则： M中非零元的个数：M.tu=M ×m1×n1 N中非零元的个数： M.tu=N ×m2×n2 (m2=n1) 相乘算法的时间复杂度就是O(m1×n2×(1+n1MN)，当： M 0.05和N 0.05及n11000时， 算法的时间复杂度相当于O(m1×n2)。,引入原因,十字链表,当矩阵的非零元的个数发生变化时，不宜采用三元组表。如A=A+B，非零元的插入或删除将会引起A.data中的数据移动，这是顺序结构三元组的弱势。,数据类型定义,结点： typedef struct OLNode int i, j; ElemType e; struct OLNode *right， *down；/*该非零元所在行的后继链域*/ OLNode; *OLink； 稀疏矩阵： typedef struct OLink *rhead，*chead； int mu，nu，tu； Crosslist;,down,right,5.4 广义表的基本概念和存储结构,1） 广义表的定义,是线性表的推广，广泛的应用于人工智能等领域。 一般记作LS=（1， 2，, n）(n0)其中i即可以为单个元素也可以为广义表。,名称：LS； 长度：n； 原子： i是单个元素（一般用小写字母）； 子表： i是广义表(一般用大写字母)； 表头(Head)：非空广义表LS的第一个数据元素 1； 表尾(Tail)：非空广义表除第一个数据元素外的其余数据元素构成的广义表( 2，, n）,2） 广义表的抽象数据类型,ADT GList 数据对象: D ei | eiAtomSet 或 eiGList i=1,2,.,n, n0 数据关系：R1 |ei-1 ,eiD, i=2,.,n 基本操作： InitGList ( &L) : 广义表的初始化 CreateList ( &L，S) ：广义表的创建 DestoryGList(&L) : 销毁广义表 CopyGList ( &T, L) :复制广义表L到广义表T GetHead (&L ) : 取广义表L的表头 GetTail (L ): 取广义表L的表尾 GListEmpty (L): 判断广义表L空否 ,广义表的特点：,广义表中的数据元素有相对次序；,任何非空广义表均可分解为表头和表尾两部分；,广义表可以为其他列表共享；,广义表可以是一个递归的表。,广义表的长度定义为最外层包含元素个数；,广义表的深度定义为所含括弧的重数；,广义表是一个多层次的线性结构；,3） 广义表的存储结构,广义表的表示有两种结构形式,表结点 原子结点,广义表的采用链式存储结构,第一种结构形式,LS,表头,表尾,LS = NULL,广义表的链式表示,Typedef enum ATOM, LIST ElemTag； Typedef struct GLNode ElemTag tag; union AtomType atom; struct struct GLNode *hp, *tp; ptr; ; *GList;,另一种结构形式,表结点 原子结点,LS,本章小结,数组 数组的定义和特点 数组的顺序存储（行优先，列优先） 逻辑地址 物理地址的计算； 矩阵的压缩存储 对称矩阵、上三角或下三角等特殊矩阵压缩存储时的地址转换公式 稀疏矩阵的压缩存储：存储特点、三元组表表示 稀疏矩阵压缩存储相关算法的思想 广义表 广义表的定义、特点 广义表的链式存储结构（两种形式掌握一种）,第五章 作业,一个稀疏矩阵如下，写出稀疏矩阵对应的三元组表的表示法、行逻辑连接的顺序表表示法和十字链表的表示法。,按照广义表存储结构的第一种结点结构，画出下面广义表的存储结构图。 (a),b),(),d),(e,f),