《数组和广义表》PPT课件.ppt

数据结构 第五章 数组与广义表,本章内容 5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.4 广义表的定义 5.5 广义表的存储结构,5-3,通过本章学习，要求掌握如下内容： 1多维数组的定义及在计算机中的存储表示； 2对称矩阵、三角矩阵、对角矩阵等特殊矩阵在计算机中的压缩存储表示及地址计算公式； 3稀疏矩阵的三元组表示及转置算法实现； 4稀疏矩阵的十字链表表示及相加算法实现； 5广义表存储结构表示及基本运算。,重点难点,5-4,数组是我们最熟悉的数据类型，在早期的高级语言中，数组是唯一可供使用的数据类型。由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单。多维数组是向量的推广。例如，二维数组：,5.1 数组的定义,5-5,5.1 数组的定义,数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表。,数组是n（n0）个相同数据类型数据元素构成的有限序列。,( ),( ),( ),( ),( ),( ),( ),( ),( ),二维数组同样满足数组的定义。二维数组可以看成一个特殊的一维数组，其中的每个元素又是一个一维数组。,5.1 数组的定义,5-7,数组的特点：,数组中的数据元素数目固定(结构固定)；,数组中的数据元素具有相同的数据类型(元素同构)；,数组中的每个数据元素都与一组唯一的下标值相对应；,数组是一种随机存取结构。,5.1 数组的定义,5.1 数组的抽象数据类型ADT,5-8,一维数组存储结构示意图,地址映像的计算公式：假设线性表中每个元素占L个单元，第一个元素的地址为loc(a1)，则第i个元素的地址为： loc(ai) =loc(a1)+(i-1)L,5.2 数组的顺序表示和实现,问 题：计算机的存储结构是一维的，而数组一般是多维的，怎样存放？ 解决办法：事先约定按某种次序将数组元素排成一列序列，然后将这个线性序列存入存储器中。 注意： 用一组连续的存储单元来表示数组； 若规定好了次序，则数组中任意一个元素的存放地址便有规律可寻，可形成地址计算公式； 约定的次序不同，则计算元素地址的公式也有所不同； C和PASCAL中一般采用行优先顺序；FORTRAN采用列优先,5-10,5-11,5.2 数组的顺序表示和实现,设一3维数组A423，存贮在一个顺序线性表S中，结构如下所示：,5.2 数组的顺序表示和实现,以行为主:对二维数组进行“按行切分”，即将数组中的数据元素“按行依次排放”在存储器中； 以列为主：对二维数组进行“按列切分”，即将数组中的数据元素“按列依次排放”在存储器中。,5-12,按行序为主序存放,LOC(i,j)=LOC(0,0)+(i*n+j)*L,按列序为主序存放,LOC(i,j)=LOC(0,0)+(j*m+i)*L,例题,无论规定行优先或列优先，只要知道以下三要素便可随时求出任一元素的地址： 开始结点的存放地址（即基地址） 维数和每维的上、下界； 每个数组元素所占用的单元数,5-15,例题,【例5-1】对于给定的二维数组float a34，计算： (1) 数组a中的数组元素上界、下界、元素数目； (2) 若数组a的起始地址为1000，且每个数组元素长度为32位(即4个字节)，数组元素a23的内存地址。 【解】(1)由于C语言中数组的行、列下标值的下界均为0，该数组行上界为3-1=2，列上界为4-1=3，所以该数组的元素数目共有3*4=12个。 (2)由于C语言采用行序为主序的存储方式，有： LOC(a2,3)=LOC(a0,0)+(i*n+j)*L =1000+(2*4+3)*4 =1044,5-16,例题,【例5-2】一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是 个字节。 【解】 Volume=m*n*L=(6-1+1)*(7- 0 +1)*6=48*6=288 【例5-3】 设数组a160, 170的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a32,58的存储地址为 。,5-17,根据列优先公式 Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*L 得：LOC(a32,58)=2048+(58-1)*60+(32-1)*28950,想一想：若数组是a059, 069，结果是否仍为8950？,5-18,5.3 矩阵的压缩存储,在高级语言编制程序时，将一个矩阵描述为一个二维数组。 矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵运算也非常简单，并且存储的密度为1。但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，看起来存储密度仍为1，但实际上占用了许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪费.,5.3 矩阵的压缩存储,5-19,压缩存储,为多个值相同的矩阵只分配一个存储空间； 对零元不分配空间。,5-20,5.3 矩阵的压缩存储,5.3.1 特殊矩阵,值相同的元素或者0元素在矩阵中的分布有一定规律。,5-21,5.3 矩阵的压缩存储,对称矩阵,仅存储下三角,下三角矩阵,5.3 矩阵的压缩存储,5.3 矩阵的压缩存储,对角矩阵,5-24,5.3 矩阵的压缩存储,5.3.2 稀疏矩阵 定义：设矩阵A中有t个非零元素，若s远远小于矩阵元素的总数（即smn），则称A为稀疏矩阵。 设在的矩阵A中，有t个非零元素。令 e=t/(m*n)，称e为矩阵的稀疏因子。通常认为e0.05时称之为稀疏矩阵。 以常规方法，即以二维数组表示的高阶的稀疏矩阵时产生的问题： 1.零值元素占的空间很大； 2.计算中进行了很多和零值的运算；,5.3 矩阵的压缩存储,解决问题的原则 1. 尽量少存或不存0元； 2. 尽量减少没有意义的运算； 3. 运算要方便。 能尽可能快地找到与下标值（i，j）对应的运算； 能尽可能快地找到同一行或同一列的非0值元。 压缩存储方法：三元组顺序表、行逻辑连接和十字链表。,5-25,存储特点,三元组顺序表,对于矩阵中每个非0元素，用它的行号、列号、元素值，即（i, j, aij）表示。 将表示稀疏矩阵的所有非0元素的三元组按行优先顺序排列，则可得到一个其结点均是三元组的线性表，称为三元组表。 以顺序存储结构来表示三元组。 要唯一确定一个稀疏矩阵，还必须存储该矩阵的行数和列数。,5-27,三元组法存储,（( 1,2,12) ，(1,3,9)， (3,1,-3)， (3,5,14)， (4,3,24)， (5,2,18) ，(6,1,15)， (6,4,-7) 6行6列，8个非零元,三元组顺序表,三元组法存储,5-28,三元组顺序表,数据类型定义,# define MAXSIZE 12500 三元组结点： typedef struct int i, j; /行号，列号 ElemType e; Triple; 稀疏矩阵： typedef struct Triple dataMAXSIZE+1 ; int mu, nu, tu; /*行、列、非零元素个数*/ TSMatrix ;,三元组顺序表,5-30,例子：三元组法表示的矩阵转置 M T,已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表。,常规算法： for(col=1;col=nu;col+) for(row=1;row=mu;row+) Tcolrow=Mrowcol;,时间复杂度： O(munu),三元组顺序表,5-31,解决思路：,将矩阵行、列维数互换； 将每个三元组中的i和j相互调换； 重排三元组次序；,三元组顺序表,5-32,2 1 3,5 1 -5,2 2 -1,1 3 6,4 3 8,1 4 -4,5 4 7,2 1 3,5 1 -5,2 2 -1,5 1 -5,三元组顺序表,5-33,2 1 3,5 1 -5,2 2 -1,1 3 6,4 3 8,1 4 -4,5 4 7,三元组顺序表,5-34,2 1 3,5 1 -5,2 2 -1,1 3 6,4 3 8,1 4 -4,5 4 7,0,0,0,0,0,+1,+1,+1,+1,+1,+1,+1,三元组顺序表,5-35,2 1 3,5 1 -5,2 2 -1,1 3 6,4 3 8,1 4 -4,5 4 7,1,2,3,4,5,5,6,7,三元组顺序表,5-36,三元组顺序表,优点：,非零元在表中按行序有序存储，便于进行依行序处理的矩阵运算。,缺点：,若需按行号存取某一行的非零元，则需从头开始查找。,三元组顺序表,为了便于随机存储任意一行的非零元，需要知道每一行的第一个非零元在三元组表中的位置。,3.行逻辑连接的顺序表,# define MAXSIZE 12500 三元组结点： typedef struct int i, j; ElemType e; Triple; 稀疏矩阵： typedef struct Triple dataMAXSIZE+1 ; int rposMAXRC+1; /*各行第一个非零元的位置表 int mu, nu, tu; /*行、列、非零元素个数*/ TSMatrix ;,5-39,3.行逻辑连接的顺序表,带行向量的三元组法的矩阵乘法,5-40,3.行逻辑连接的顺序表,=,问题描述：,已知两个稀疏矩阵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是累加的结果。,3.行逻辑连接的顺序表,3.行逻辑连接的顺序表,Q初始化； if （Q是非零矩阵） for(arrow=1;arrow=M.mu;arrow+) ctemp=0; 计算Q中第arrow行的积并存入ctemp中； 将ctemp中非零元压缩存储到Q.data； ,5-42,处理M的每一行,分析上述算法的时间复杂度,例子:求矩阵乘法,1、累加器ctemp初始化的时间复杂度为O(M.muN.nu) 2、求Q的所有非零元的时间复杂度为O(M.tuN.tu/N.mu) 3、进行压缩存储的时间复杂度为O(M.muN.nu),总的时间复杂度O(M.muN.nu+M.tuN.tu/N.mu),若M是m行n列的稀疏矩阵，N是n行p列的稀疏矩阵，则： M中非零元的个数：M.tu=M mn N中非零元的个数： M.tu=N np 相乘算法的时间复杂度就是O(mn(1+nMN)，当： M 1000时， 算法的时间复杂度相当于O(mp)。,引入原因,十字链表,当矩阵的非零元的个数发生变化时，不宜采用三元组表。如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-46,4. 十字链表,十字链表结点定义：每一个非零元用一个结点表示，结点包括五个域：除了表示非零元所在的行、列和值的三元组（i, j, v）外，还需增加两个链域：行指针域（right），用来指向本行中下一个非零元素；列指针域（down），用来指向本列中下一个非零元素。,5-47,4. 十字链表,十字链表法：为稀疏矩阵中的链接存储中的一种较好的存储方法,5-48,4. 十字链表,十字链表类型定义 稀疏矩阵中同一行的非零元通过向右的right指针链接成一个带表头结点的线性链表。同一列的非零元也通过down指针链接成一个带表头结点的线性链表。 因此，每个非零元既是第i行循环链表中的一个结点，又是第j列循环链表中的一个结点，相当于处在一个十字交叉路口，故称链表为十字链表。可用两个分别存储行链表的头指针和列链表的头指针的一维数组表示之。,5-49,是线性表的推广，广泛的应用于人工智能等领域。 一般记作LS=（1， 2，, n）(n0)其中i既可以为单个元素也可以为广义表。,名称：LS； 长度：n； 原子： i是单个元素； 子表： i是广义表； 表头(Head)：非空广义表LS的第一个数据元素 1； 表尾(Tail)：非空广义表除第一个数据元素外的其余数据元素构成的广义表( 2，, n）,5.4 广义表,5-50,5.4 广义表,任意一个非空广义表，均可分解为表头和表尾。 对于一个非空广义表，其表头可能是原子，也可能是子表；而表尾一定是子表。 广义表举例 A=（） / 空表，长度n = 0 B=（e） / n=1, 只有一个原子e C=（a, (b, c, d) ) / n=2, 有两个元素，分别为原子a和子表(b,c,d) D=（A，B，C） / n=3,有3个元素 E= (a , E） / n=2,无限循环列表（递归）,5-51,5.4 广义表,性质 广义表是一个多层次结构; 广义表的深度 d 定义为所含括弧的重数（展开后所含括号的层数）; “原子”的深度为0 ; “空表”的深度为1 广义表可以共享;也可以是一个递归的表;,广义表有两个重要的基本操作，即取头操作（Head）和取尾操作（Tail）。 根据广义表的表头、表尾的定义可知，对于任意一个非空的列表，其表头可能是单元素也可能是列表，而表尾必为列表。例如： B=（e） Head（B） e Tail（B）（） C=（a, (b, c, d) ) Head（C） a Tail（C）（b，c，d） D=（A，B，C） Head（D） A Tail（D）（B，C） E= (a , E）Head（E） a Tail（E）（E） F=() Head（F）（） Tail（F）（） LS= ( (a, b), (a, b), (u, (x, y, z), ( ) ) )，求LS的深度,5.4 广义表,5-53,5.5 广义表的存储结构,广义表的表示有两种结构形式,表结点 原子结点,第一种结构形式,LS,表头,表尾,LS = NULL,5-54,5.5 广义表的存储结构,5-55,5.5 广义表的存储结构,typedef enumatom,listelemtag; typedef struct GLnode Elemtag tag; union AtomType atom; struct GLnode *hp; /表结点的表头指针 ; struct GLnode *tp; / 指向下一个元素结点 *GList;,5-56,5.5 广义表的存储结构,广义表的运算 创建空的广义表: initGList(,5-57,5.5 广义表的存储结构,广义表作为ADT,ADT Glist 数据对象: D=ei |i=1,2, n; n0, ei AtomSet 或ei Glist 数据关系: R=(ei-1 , ei ) | ei D 基本操作: initGList(,5-58,5.5 广义表的存储结构,求广义表的深度 设：LS = (a1, a2, , an)， 例如，对于广义表 E ( B (a, b), D ( B (a, b), C (u, (x, y, z), A ( ) ) ) 按递归算法分析： Depth (E) = 1+Max Depth (B), Depth (D) Depth (B) = 1+Max Depth (a), Depth (b) = 1 Depth (D) = 1+Max Depth (B), Depth (C), Depth (A),5-59,5.5 广义表的存储结构,Depth (C) = 1+Ma