数据结构数组与广义表.ppt

《数据结构数组与广义表.ppt》由会员分享，可在线阅读，更多相关《数据结构数组与广义表.ppt（46页珍藏版）》请在课桌文档上搜索。

1、第五章 数组和广义表,1,第五章 数组和广义表,本章前讨论的线性结构数据元素都是非结构的原子类型，元素值不可再分。本章讨论了两种数据结构数组和广义表。作为线性表的扩展，表中的数据元素也是一种数据结构。数组这种数据结构可以看成是线性表的推广。广义表是另一种推广形式的线性表，是一种灵活的数据结构，在许多方面有广泛的应用。,2,知识结构图,数组与广义表,数 组,广义表,类型定义,表示方法,稀疏矩阵,特殊矩阵,存储结构,逻辑结构,应用,压缩存储,各种运算,3,5.1 数组,数组是n(n1)个相同数据类型的数据元素a0,a1,a2,.,an-1构成的占用一块地址连续的内存单元的有限序列。,数组中任意一个

2、元素可以用该元素在数组中的位置来表示，数组元素的位置通常称作数组的下标。,4,5.1.1 数组的概念及其与线性表的关系,由定义知，n维数组中有b1b2 bn个数据元素，每个数据元素都受到n维关系的约束。直观的n维数组 以二维数组为例讨论。将二维数组看成是一个定长的线性表，其每个元素又是一个定长的线性表。设二维数组A=(aij)mn，则 A=(1，2，p)(p=m或n)其中每个数据元素j是一个列向量(线性表)：j=(a1j，a2j，amj)1jn或是一个行向量：i=(ai1，ai2，ain)1im如图5-1所示。,5,6,n维数组的特点,每个数据元素都受着n个关系的约束；在每个关系中，元素(0=

3、ji=bi-2)都有一个直接后继;数据元素都必须属于同一数据类型;n=1时，退化为定长的线性表；n维数组可以看成是线性表的推广。数组一旦被定义，则维数已定，对于数组的操作只有存取元素和修改元素。(一旦建立了数组，数组中的元素个数和元素之间的关系就不再发生变动)数组是多维的结构，而存储空间是一个一维的结构。（存储时需要一个次序约定）,7,5.1.2 数组的顺序存储结构,数组的实现机制,8,行向量 下标 i 页向量 下标 i列向量 下标 j 行向量 下标 j 列向量 下标 k二维数组 三维数组,9,数组的顺序表示-小结,n维数组的特点:数据元素同属于一种数据类型；数组一旦被定义，则维数和各维长度不

4、能改变；数组操作只有引用型操作，没有加工型操作；数组是多维结构，但存储空间是一维结构。数组顺序表示的特点存储单元地址连续（需要一段连续空间）存储规则（以行（列）为主序）决定元素实际存储位置随机存取存储密度最大（100%）,10,5.2 矩阵的压缩存储,在科学与工程计算问题中，矩阵是一种常用的数学对象，在高级语言编程时，通常将一个矩阵描述为一个二维数组。这样，可以对其元素进行随机存取，各种矩阵运算也非常简单。对于高阶矩阵，若其中非零元素呈某种规律分布或者矩阵中有大量的零元素，若仍然用常规方法存储，可能存储重复的非零元素或零元素，将造成存储空间的大量浪费。对这类矩阵进行压缩存储：多个相同的非零元素

5、只分配一个存储空间；零元素不分配空间。,11,5.2.1 特殊矩阵的压缩存储,1.对称矩阵n阶矩阵A中元素满足性质aij=aji(1i,jn)。,（即aij=aji,1=i,j=n）,LTA0.n(n+1)/2-1,k=0 1 2 n(n+1)/2-1,12,13,k的含义：按行优先，是第k个（从0开始）,i=3,j=2,k=4,公式的推导（下三角）i=3，j=2则前面有一个i-1行的完整三角形，共有元素(1+i-1)(i-1)/2=i(i-1)/2个另外，同一行，前面还有j-1个元素所以，k=i(i-1)/2+j-1,14/50,2、三角矩阵,以主对角线划分，n阶三角矩阵有n阶上三角矩阵和n

6、阶下三角矩阵两种。n阶上三角矩阵的下三角（不包括主对角线）中的元素均为0（或常数）。n阶下三角矩阵正好相反，它的主对角线上方均为0（或常数）。注：在大多数情况下，n阶三角矩阵常数为零。,下三角矩阵元素ai j保存在向量sa中时的下标值k与（i,j）之间的对应关系是：,15,5.2.2 稀疏矩阵的压缩存储,稀疏矩阵：设m行n列的矩阵含t个非零元素，则=t/(m*n)称为稀疏因子，通常认为 0.05 的矩阵为稀疏矩阵。,(1)、稀疏矩阵矩阵中非零元素的个数远远小于矩阵元素个数。(2)、稠密矩阵 一个不稀疏的矩阵。(3)、稀疏矩阵压缩存储方法 只存储稀疏矩阵中的非零元素，实现方法是:将每个非零元素用

7、一个三元组（i，j，aij）来表示，则每个稀疏矩阵可用一个三元组线性表来表示。,16,1、三元组顺序表稀疏矩阵和对应的三元组线性表,若把稀疏矩阵的三元组线性表按顺序存储结构存储，则称为稀疏矩阵的三元组顺序表。,17,三元组表表示的稀疏矩阵转置,18,18,稀疏矩阵的转置 Tij=Mji,19,稀疏矩阵用三元组表示的转置,行数和列数交换i、j的值相互交换重排三元组之间的次序,20,用三元组表示，求稀疏矩阵M的转置矩阵T,M,T,1.行数和列数交换，总个数不变:T.m=M.n;T.n=M.m;T.t=M.t;2.让q定位T中的第一条记录:q=1;,6 5 6,21,M,T,3.让col取M的每一列

8、:for(col=1;col=M.n;col+)4.让p扫描三元组M的每一条记录:for(p=1;p=M.t;p+),6 5 6,col=1,22,M,T,6 5 6,col=1,5.如果p指向的记录的j下标与col相等:if(M.datap.j=col),23,M,T,6 5 6,col=1,6.把M中的记录p复制到T中的记录q:T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.v=M.datap.v;7.让q下移:q+;,1 3-3,24,M,T,6 5 6,col=2,1 3-3,2 1 12,2 5 18,25,M,T,6 5 6,col=

9、3,1 3-3,2 1 12,2 5 18,3 1 9,3 4 24,26,M,T,6 5 6,col=6,1 3-3,2 1 12,2 5 18,3 1 9,3 4 24,6 3 14,27,（1）稀疏矩阵的转置：“按需查找”法,简单算法的分析稀疏矩阵转置算法复杂度=O(n*t)比较一般矩阵的转置算法：其复杂度=O(m*n)如果t和m*n一个数量级，则稀疏矩阵转置算法复杂度=O(m*n2)所以此算法只适用于tm*n时,for(col=1;col=nu;col+)for(row=1;row=mu;row+)Tcolrow=Mrowcol;,28,算法的实现附设两个辅助向量num 和cpot。n

10、umcol：统计A中第col列中非0元素的个数；cpotcol：指示A中第一个非0元素在b.data中的恰当位置。数组numcol：原矩阵第col列中，非零元素的个数数组cpotcol：原矩阵第col列中，第1个非零元素在结果三元组表中的位置显然有：,（2）稀疏矩阵的转置：“按位就坐”算法,29,（2）稀疏矩阵的转置：“按位就坐”算法,2.十字链表,十字链表的定义稀疏矩阵的每个非零元素用一个含五个域的结点表示:i:非零元素所在行;j:非零元素所在列 e:非零元素值;right域:链接同一行下一非零元素 down域:链接同一列下一非零元素；存储结构的C语言描述 typedef struct OL

11、Node int i,j;ElemType e;Struct OLNode*right,*down;OLNode,*OLink;typedef struct OLink*rhead,*chead;int mu,nu,tu;CrossLink;,结点结构：,30,十字链表表示的稀疏矩阵举例,结点结构：,稀疏矩阵M：,M的十字链表：,采用十字链表存储稀疏矩阵，创建稀疏矩阵、稀疏矩阵的运算见教材P104106,31,5.3 广义表(General Lists),广义表(列表):n(0)个表元素组成的有限序列，记作 LS=(a1,a2,an)表头(head):n0时,表的第一个表元素表尾(tail):

12、其它表元素组成的表空表:n=0 的广义表。广义表的特性：有长度：n有深度：广义表中括号的重数可递归可共享,非空列表表头可是原子或列表,表尾必定是列表,32,广义表的图形表示,1、A=(/)2、B=(e)3、C=(a,(b,c,d)4、D=(A，B，C)注：表：原子,33,5.3.1广义表的定义,GetHead(L):在广义表L存在的条件下，取L的表头。GetTail(L):在广义表L存在的条件下，取L的表尾。举例：1 A=()GetHead(A)=NULL,GetTail(A)=NULL2 B=(e)GetHead(B)=e,GetTail(B)=()3 C=(a,(b,c,d)GetHead

13、(C)=a,GetTail(C)=(b,c,d)GetHead(b,c,d)=b,GetTail(b,c,d)=(c,d)GetHead(c,d)=c,GetTail(c,d)=(d)4 D=(A,B,C)GetHead(D)=A,GetTail(D)=(B,C)GetHead(B,C)=B,GetTail(B,C)=(C)5 E=()GetHead(B)=(),GetTail(B)=(),34,5.3.2 广义表的存储结构,采用链式存储结构，元素包括原子和子表，结点结构：表结点：表示列表 原子结点：表示原子1、广义表的头尾链表存储表示：typedef enum ATOM,LISTElemTa

14、g;/ATOM=0:原子,LIST=1:子表 typedef struct GLNode ElemTag tag;/公共部分，用来区分原子结点和表结点 Union/原子结点和表结点的联合部分 AtomType atom;Structstruct GLNode*hp,*tp;ptr;/hp指向表头,tp指向表尾;*Glist;,35,A=(/)B=(e)C=(a,(b,c,d)D=(A，B，C)E=(a，E),5.5 广义表的存储结构示例,A=NIL,表结点：,原子结点：,36,5.5 广义表的存储结构示例,对广义表：C=(a,(b,c,d)，其头尾链表为：,37,2、广义表的扩展线性链表存储表

15、示：typedef enum ATOM,LISTElemTag;/ATOM=0:原子，LIST=1：子表 typedef struct GLNode ElemTag tag;/公共部分，用来区分原子结点和表结点 Union/原子结点和表结点的联合部分 AtomType atom;/原子结点的值域 Struct GLNode*hp/表结点的头指针;GLNode*tp;/指向下一个结点*Glist;,38,广义表的另一种存储结构示例,A=(/)B=(e)C=(a,(b,c,d)D=(A，B，C)E=(a，E),表结点：,原子结点：,39,40/50,5.3.3 广义表的基本操作与实现,下面讨论头链

16、和尾链存储结构下和原子和子表存储结构下一些典型操作的算法实现。,/-广义表的头尾链表存储表示typedef enum ATOM,LIST ElemTag;/ATOM=0原子，LIST=1子表typedef struct GLNode ElemTag tag;/公共部分，用于区分原子结点和表结点 union AtomType atom;/atom是原子结点的值域 struct struct GLNode*hp,*tp;ptr;/ptr是表结点的指针域，ptr.hp和ptr.tp分别指向表头和表尾;*GList;/广义表类型,41/50,第五章 数组和广义表,1、求广义表深度算法,广义表的深度是广

17、义表中所有原子数据元素到达根结点的最大值。,int GListDepth(GList LS)/采用头尾链表存储结构，求广义表L的深度 if(!L)return 1;/空表深度为1 if(L-tag=ATOM)return 0;/原子深度为0 for(max=0,pp=L;pp;pp=pp-ptr.tp)/求以pp-ptr.hp为头指针的子表深度 dep=GListDepth(pp-ptr.hp);if(depmax)max=dep;return max+1;/GListDepth,42/50,第五章 数组和广义表,2、求广义表的长度算法,在头链和尾链存储结构中，广义表的长度就是表尾指针构成的单

18、链表的长度。,int GListLength(GList LS)for(p=L;p!=NULL;p=p-ptr.tp)number+;return number;,43/50,第五章 数组和广义表,3、复制广义表算法任何非空广义表都由表头和表尾构成，故可将广义表分解成表头和表尾两部分，分别递归复制求得新的表头和表尾。,Status CopyLS(GList/CopyGList,44/50,第五章 数组和广义表,4、广义表的输出根据广义表的递归的定义，可利用递归算法 来实现广义表输出。void printLS(Glist LS),2023/3/2,45/50,第五章 数组和广义表,5、创建广义表

19、 创建广义表就是按照所给的表示具体广义表的字符串S创建一个广义表L。对一个广义表的任何操作都可以分解为对表头的操作和对表尾的操作。同样，创建广义表操作可以分解为创建表头广义表和创建表尾广义表。因此，创建广义表函数CreatGList(&L,SString S)只要递归完成对表头广义表的创建和对表尾广义表的创建即可。这样，还需要设计一个把表示广义表的字符串str分解成表头字符串hstr和表尾字符串str的函数sever(&str,&hstr)。void CreatGList(GList&LS,StrType&S),2023/3/2,46/50,第五章 数组和广义表,void destroyGList(GList LS),6、销毁广义表,