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

《数据结构数组和广义表.ppt》由会员分享，可在线阅读，更多相关《数据结构数组和广义表.ppt（46页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、关于数据结构数组与关于数据结构数组与广义表广义表第一张，PPT共四十六页，创作于2022年6月第五章第五章 数组和广义表数组和广义表l本章前讨论的线性结构数据元素都是非结构的本章前讨论的线性结构数据元素都是非结构的原子原子类型类型，元素值不可再分。本章讨论了两种数据，元素值不可再分。本章讨论了两种数据结构结构数组和广义表。作为线性表的扩展，表中数组和广义表。作为线性表的扩展，表中的数据元素也是一种数据结构。的数据元素也是一种数据结构。l数组数组这种数据结构可以看成这种数据结构可以看成是线性表的推广是线性表的推广。l广义表广义表是另一种推广形式的线性表，是一种灵活的是另一种推广形式的线性表，是一

2、种灵活的数据结构，在许多方面有广泛的应用。数据结构，在许多方面有广泛的应用。第二张，PPT共四十六页，创作于2022年6月2知识结构图知识结构图数组与广义表数组与广义表 数数 组组广义表广义表类类型型定定义义表表示示方方法法稀稀疏疏矩矩阵阵特特殊殊矩矩阵阵存存储储结结构构逻逻辑辑结结构构 应应用用压压缩缩存存储储各各种种运运算算第三张，PPT共四十六页，创作于2022年6月35.1 数组数组数组数组是是n(n1)个相同数据类型的数据元素个相同数据类型的数据元素a0,a1,a2,.,an-1构成的构成的占用一块地址连续的内存单元的有限序列。占用一块地址连续的内存单元的有限序列。数组中任意一个元素

3、可以用该元素在数组中的位置来表示，数组元数组中任意一个元素可以用该元素在数组中的位置来表示，数组元素的位置通常称作素的位置通常称作数组的下标数组的下标。第四张，PPT共四十六页，创作于2022年6月45.1.1 数组的概念及其与线性表的关系数组的概念及其与线性表的关系 由定义知由定义知，n维数组中有维数组中有b1 b2 bn个数据元素个数据元素，每个数据元素都受每个数据元素都受到到n维关系的约束维关系的约束。直观的直观的n维数组维数组 以二维数组为例讨论。以二维数组为例讨论。将二维数组看成是一个定长的线性表，其每个将二维数组看成是一个定长的线性表，其每个元素又是一个定长的线性表元素又是一个定长

4、的线性表。设二维数组设二维数组A=(aij)m n，则，则 A=(1，2，p)(p=m或或n)其中每个数据元素其中每个数据元素j是一个列向量是一个列向量(线性表线性表)：j=(a1j，a2j，amj)1jn或或是一个行向量是一个行向量：i=(ai1，ai2，ain)1 i m如图如图5-1所示。所示。第五张，PPT共四十六页，创作于2022年6月5 a11 a12 a1n a21 a22 a2n am1 am2 amnA=A=a11 a12 a1na21 a22 a2nam1 am2 amna11 a21 am1a12 a22 am2a1n a2n amnA=图图5-1 二维数组图二维数组图例

5、形式例形式(a)矩阵矩阵表示形式表示形式(b)行行向量的一维数组形式向量的一维数组形式(c)列向量的一维数组形式列向量的一维数组形式第六张，PPT共四十六页，创作于2022年6月6n维数组的特点维数组的特点l每个数据元素都受着每个数据元素都受着n n个关系的约束；个关系的约束；l在每个关系中，元素在每个关系中，元素 (0=j(0=ji i=b=bi i-2)-2)都有一个直接后继都有一个直接后继;l数据元素都必须属于同一数据类型数据元素都必须属于同一数据类型;ln=1n=1时，退化为定长的线性表；时，退化为定长的线性表；ln n维数组可以看成是线性表的推广。维数组可以看成是线性表的推广。l数组

6、一旦被定义，则维数已定，对于数组的操作只有存取元素和修数组一旦被定义，则维数已定，对于数组的操作只有存取元素和修改元素。改元素。(一旦建立了数组，数组中的元素个数和元素之间的关系就不再一旦建立了数组，数组中的元素个数和元素之间的关系就不再发生变动发生变动)l数组是多维的结构，而存储空间是一个一维的结构。（存储时需要一个次数组是多维的结构，而存储空间是一个一维的结构。（存储时需要一个次序约定）序约定）第七张，PPT共四十六页，创作于2022年6月75.1.2 数组的顺序存储结构数组的顺序存储结构数组的实现机制数组的实现机制a的内存单元地址的内存单元地址每个元素所需的字节个数每个元素所需的字节个数

7、第八张，PPT共四十六页，创作于2022年6月8行向量行向量行向量行向量 下标下标下标下标 i i 页向量页向量页向量页向量 下标下标下标下标 i i列向量列向量列向量列向量 下标下标下标下标 j j 行向量行向量行向量行向量 下标下标下标下标 j j 列向量列向量列向量列向量 下标下标下标下标 k k二维数组二维数组二维数组二维数组 三维数组三维数组三维数组三维数组第九张，PPT共四十六页，创作于2022年6月9数组的顺序表示数组的顺序表示-小结小结ln维数组的特点维数组的特点:l数据元素同属于一种数据类型；数据元素同属于一种数据类型；l数组一旦被定义，则维数和各维长度不能改变；数组一旦被定

8、义，则维数和各维长度不能改变；l数组操作只有引用型操作，没有加工型操作；数组操作只有引用型操作，没有加工型操作；l数组是多维结构，但存储空间是一维结构。数组是多维结构，但存储空间是一维结构。l数组顺序表示的特点数组顺序表示的特点l存储单元地址连续（需要一段连续空间）存储单元地址连续（需要一段连续空间）l存储规则（以行（列）为主序）决定元素实际存储位置存储规则（以行（列）为主序）决定元素实际存储位置l随机存取随机存取l存储密度最大（存储密度最大（100%100%）第十张，PPT共四十六页，创作于2022年6月105.2 矩阵的压缩存储矩阵的压缩存储 在科学与工程计算问题中，矩阵是一种常用的数学对

9、象，在科学与工程计算问题中，矩阵是一种常用的数学对象，在高级语言编程时，通常将一个矩阵描述为一个二维数组。在高级语言编程时，通常将一个矩阵描述为一个二维数组。这样，可以对其元素进行随机存取，各种矩阵运算也非常简这样，可以对其元素进行随机存取，各种矩阵运算也非常简单。单。对于对于高阶矩阵高阶矩阵，若其中，若其中非零元素呈某种规律分布非零元素呈某种规律分布或者或者矩阵中有大量的零元素矩阵中有大量的零元素，若仍然用常规方法存储，可能存，若仍然用常规方法存储，可能存储重复的非零元素或零元素，将造成存储空间的大量浪费。储重复的非零元素或零元素，将造成存储空间的大量浪费。对这类矩阵进行压缩存储：对这类矩阵

10、进行压缩存储：多个相同的非零元素只分配一个存储空间多个相同的非零元素只分配一个存储空间；零元素不分配空间。零元素不分配空间。第十一张，PPT共四十六页，创作于2022年6月115.2.1 5.2.1 特殊矩阵的压缩存储特殊矩阵的压缩存储l1.对称矩阵对称矩阵n阶矩阵阶矩阵A中元素满足性质中元素满足性质aij=aji(1i,jn)。（即aij=aji,1=i,j=n）a11a21a22aijannLTA0.n(n+1)/2-1k=0 1 2 n(n+1)/2-1第十二张，PPT共四十六页，创作于2022年6月12lk的含义：按行优先，是第k个（从0开始）156752896830790415268

11、37904i=3j=2k=4l公式的推导（下三角）li=3，j=2l则前面有一个i-1行的完整三角形，共有元素 (1+i-1)(i-1)/2=i(i-1)/2个l另外，同一行，前面还有j-1个元素l所以，k=i(i-1)/2+j-1第十三张，PPT共四十六页，创作于2022年6月132 2、三角矩阵、三角矩阵 以主对角线划分，以主对角线划分，n阶三角矩阵有阶三角矩阵有n阶上三角矩阵和阶上三角矩阵和n阶下三角矩阵两种。阶下三角矩阵两种。n阶上三角矩阵的下三角（不包括主对角线）中的元素均为阶上三角矩阵的下三角（不包括主对角线）中的元素均为0（或常数）。（或常数）。n阶下三角矩阶下三角矩阵正好相反，

12、它的主对角线上方均为阵正好相反，它的主对角线上方均为0（或常数）。（或常数）。注：在大多数情况下，注：在大多数情况下，n阶三角矩阵常数为零。阶三角矩阵常数为零。第十四张，PPT共四十六页，创作于2022年6月14 下三角矩阵元素下三角矩阵元素ai j保存保存在向量在向量sa中时的中时的下标值下标值k与（与（i,j）之间的对应关系之间的对应关系是：是：i(i-1)/2+j 当当ij时时n(n+1)/2 当当ij 时时K=1i,jn (5-5)第十五张，PPT共四十六页，创作于2022年6月155.2.2 稀疏矩阵的压缩存储稀疏矩阵的压缩存储l稀稀疏疏矩矩阵阵：设设m行行n列列的的矩矩阵阵含含t个

13、个非非零零元元素素，则则=t/(m*n)称称为为稀稀疏疏因因子子，通常认为通常认为 0.05 的矩阵为稀疏矩阵。的矩阵为稀疏矩阵。(1)、稀疏矩阵、稀疏矩阵矩阵中非零元素的个数远远小于矩阵元素个数。矩阵中非零元素的个数远远小于矩阵元素个数。(2)、稠密矩阵、稠密矩阵 一个不稀疏的矩阵。一个不稀疏的矩阵。(3)、稀疏矩阵压缩存储方法、稀疏矩阵压缩存储方法 只存储稀疏矩阵中的非零元素，只存储稀疏矩阵中的非零元素，实现方法是实现方法是:将每个非零元将每个非零元素用一个素用一个三元组（三元组（i，j，aij）来表示，则每个稀疏矩阵可用一个来表示，则每个稀疏矩阵可用一个三元组线性表三元组线性表三元组线性

14、表三元组线性表来表示。来表示。第十六张，PPT共四十六页，创作于2022年6月161、三元组顺序表、三元组顺序表稀疏矩阵和对应的三元组线性表稀疏矩阵和对应的三元组线性表 若把稀疏矩阵的三元组线性表按顺序存储结构存储，则称为稀疏矩阵的三元组顺序表。若把稀疏矩阵的三元组线性表按顺序存储结构存储，则称为稀疏矩阵的三元组顺序表。第十七张，PPT共四十六页，创作于2022年6月17三元组表表示的稀疏矩阵转置三元组表表示的稀疏矩阵转置18稀疏矩阵的转置 Tij=Mji 0 12 9 0 0 0 0 0 0 0 0 0-3 0 0 0 0 14 0 0 24 0 0 0 0 18 0 0 0 0 0 0-3

15、 0 012 0 0 0 18 9 0 0 24 0 0 0 0 0 0 0 18 0 0 0 0 0 14 0 0566121213931-336144324521865613-32112251831934246314第十八张，PPT共四十六页，创作于2022年6月18稀疏矩阵用三元组表示的转置l行数和列数交换li、j的值相互交换l重排三元组之间的次序566121213931-336144324521865613-32112251831934246314656211231913-3631434242518第十九张，PPT共四十六页，创作于2022年6月19用三元组表示，求稀疏矩阵M的转置矩阵

16、TM566121213931-3361443245218T1.行数和列数交换，总个数不变:T.m=M.n;T.n=M.m;T.t=M.t;2.让q定位T中的第一条记录:q=1;6 5 6q第二十张，PPT共四十六页，创作于2022年6月20M566121213931-3361443245218T3.让col取M的每一列:for(col=1;col=M.n;col+)4.让p扫描三元组M的每一条记录:for(p=1;p=M.t;p+)6 5 6qcol=1p第二十一张，PPT共四十六页，创作于2022年6月21M566121213931-3361443245218T6 5 6qcol=1p5.如

17、果p指向的记录的j下标与col相等:if(M.datap.j=col)ije第二十二张，PPT共四十六页，创作于2022年6月22M566121213931-3361443245218T6 5 6qcol=1p6.把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第二十三张，PPT共四十六页，创作于2022年6月23M566121213931-3361443245218T6 5 6qcol=2p1 3 -32 1 122 5 18第二十四张，PPT共四十六页，

18、创作于2022年6月24M566121213931-3361443245218T6 5 6qcol=3p1 3 -32 1 122 5 183 1 93 4 24第二十五张，PPT共四十六页，创作于2022年6月25M566121213931-3361443245218T6 5 6qcol=6p1 3 -32 1 122 5 183 1 93 4 246 3 14第二十六张，PPT共四十六页，创作于2022年6月26（1）稀疏矩阵的转置：“按需查找”法l简单算法的分析l稀疏矩阵转置算法复杂度=O(n*t)l比较一般矩阵的转置算法：l其复杂度=O(m*n)l如果t和m*n一个数量级，则稀疏矩阵转

19、置算法复杂度=O(m*n2)l所以此算法只适用于tm*n时for(col=1;col=nu;col+)for(row=1;row 00时时,表的第一个表元素表的第一个表元素l表尾表尾(tailtail):):其它表元素组成的其它表元素组成的表表l空表空表:n n=0 =0 的广义表。的广义表。l广义表的特性：广义表的特性：l l有长度：有长度：有长度：有长度：n nl l有深度：广义表中括号的重数有深度：广义表中括号的重数有深度：广义表中括号的重数有深度：广义表中括号的重数l l可递归可递归可递归可递归l l可共享可共享可共享可共享表名表名表元素表元素 表长表长非空列表表头可是原子或非空列表表

20、头可是原子或列表列表,表尾必定是列表表尾必定是列表第三十二张，PPT共四十六页，创作于2022年6月32广义表的图形表示广义表的图形表示 1、A=(/)2、B=(e)3、C=(a,(b,c,d)4、D=(A，B，C)注：注：表：表：原子：原子第三十三张，PPT共四十六页，创作于2022年6月335.3.1广义表的定义广义表的定义GetHead(L):GetHead(L):在广义表在广义表L L存在的条件下，取存在的条件下，取L L的表头。的表头。GetTail(L):GetTail(L):在广义表在广义表L L存在的条件下，取存在的条件下，取L L的表尾。的表尾。举例：举例：1 A=()Get

21、Head(A)=NULL,GetTail(A)=NULL2 B=(e)GetHead(B)=e,GetTail(B)=()3 C=(a,(b,c,d)GetHead(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)=()第三十四张，PPT共四十六页，创作于2022

22、年6月345.3.2 广义表的存储结构广义表的存储结构l采用链式存储结构，元素包括原子和子表，结点结构：采用链式存储结构，元素包括原子和子表，结点结构：表结点：表结点：表示列表表示列表 原子结点：原子结点：表示原子表示原子l1、广义表的、广义表的头尾链表头尾链表存储表示：存储表示：typedef enum ATOM,LISTElemTag;/ATOM=0:原子原子,LIST=1:子表子表 typedef struct GLNode ElemTag tag;/公共部分，用来区分原子结点和表结点公共部分，用来区分原子结点和表结点 Union/原子结点和表结点的联合部分原子结点和表结点的联合部分 A

23、tomType atom;Structstruct GLNode*hp,*tp;ptr;/hp指向表头指向表头,tp指向表尾指向表尾 ;*Glist;tag=1 hp tptag=0 atom第三十五张，PPT共四十六页，创作于2022年6月35A=(/)B=(e)C=(a,(b,c,d)D=(A，B，C)E=(a，E)5.5 广义表的存储结构广义表的存储结构示例示例B0 e1C110 a1110 b0 d0 cD1 11E110 aA=NIL表结点：表结点：原子结点：原子结点：tag=1 hp tptag=0 atom第三十六张，PPT共四十六页，创作于2022年6月365.5 广义表的存储

24、结构广义表的存储结构示例示例对广义表：C=(a,(b,c,d)，其头尾链表为：1C 0a11 0b1 0c1 0d第三十七张，PPT共四十六页，创作于2022年6月375.3.3 广义表的基本操作与实现广义表的基本操作与实现 下面讨论头链和尾链存储结构下和原子和子表存储结构下一些典型操作的算法实现。下面讨论头链和尾链存储结构下和原子和子表存储结构下一些典型操作的算法实现。/-广义表的头尾链表存储表示广义表的头尾链表存储表示typedef enum ATOM,LIST ElemTag;/ATOM=0原子，原子，LIST=1子表子表typedef struct GLNode ElemTag tag

25、;/公共部分，用于区分原子结点和表结点公共部分，用于区分原子结点和表结点 union AtomType atom;/atom是原子结点的值域是原子结点的值域 struct struct GLNode*hp,*tp;ptr;/ptr是表结点的指针域，是表结点的指针域，ptr.hp和和ptr.tp分别指向表头和表尾分别指向表头和表尾 ;*GList;/广义表类型广义表类型第四十张，PPT共四十六页，创作于2022年6月40第五章第五章 数组和广义表数组和广义表1、求广义表深度算法、求广义表深度算法 广义表的深度是广义表中所有原子数据元素到达根结点的最大值。广义表的深度是广义表中所有原子数据元素到达

26、根结点的最大值。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第四十一张，PPT共四十六页，创作于2022年6月41第五章第五章

27、 数组和广义表数组和广义表2、求广义表的长度算法、求广义表的长度算法 在头链和尾链存储结构中，广义表的长度就是表尾指针构成的单链表的长度。在头链和尾链存储结构中，广义表的长度就是表尾指针构成的单链表的长度。int GListLength(GList LS)for(p=L;p!=NULL;p=p-ptr.tp)number+;return number;第四十二张，PPT共四十六页，创作于2022年6月42第五章第五章 数组和广义表数组和广义表3、复制广义表算法、复制广义表算法任何非空广义表都由表头和表尾构成，故可将广义表分解成表头和表尾两部分，分别递归复制求得新的表头和表尾。Status Co

28、pyLS(GList&T,GList LS)/采用头尾链表存储结构，由广义表采用头尾链表存储结构，由广义表L复制得到广义表复制得到广义表T if(!L)T=NULL;/复制空表复制空表 else if(!(T=(GList)malloc(sizeof(GLNode)exit(OVERFLOW);T-tag=L-tag;if(L-tag=ATOM)T-atom=L-atom;elseCopyGList(T-ptr.hp,L-ptr.hp);CopyGList(T-ptr.tp;L-ptr.tp);/else /else return OK;/CopyGList第四十三张，PPT共四十六页，创作于

29、2022年6月43第五章第五章 数组和广义表数组和广义表4、广义表的输出、广义表的输出根据广义表的递归的定义，可利用递归算法根据广义表的递归的定义，可利用递归算法 来实现广义表输出。来实现广义表输出。void printLS(Glist LS)第四十四张，PPT共四十六页，创作于2022年6月44第五章第五章 数组和广义表数组和广义表5、创建广义表、创建广义表 创建广义表就是按照所给的表示具体广义表的字符串创建广义表就是按照所给的表示具体广义表的字符串S创建一个广义表创建一个广义表L。对一个广义表的任何操作都可以分解为对表头的操作和对表尾的操作。同样，创建对一个广义表的任何操作都可以分解为对表

30、头的操作和对表尾的操作。同样，创建广义表操作可以分解为创建表头广义表和创建表尾广义表。因此，创建广义表函数广义表操作可以分解为创建表头广义表和创建表尾广义表。因此，创建广义表函数CreatGList(&L,SString S)只要递归完成对表头广义表的创建和对表尾广义表的创只要递归完成对表头广义表的创建和对表尾广义表的创建即可。建即可。这样，还需要设计一个把表示广义表的字符串这样，还需要设计一个把表示广义表的字符串str分解成表头字符串分解成表头字符串hstr和表尾字和表尾字符串符串str的函数的函数sever(&str,&hstr)。void CreatGList(GList&LS,StrType&S)第四十五张，PPT共四十六页，创作于2022年6月45感感谢谢大大家家观观看看第四十六张，PPT共四十六页，创作于2022年6月