数据结构第五章数组和广义表幻灯片.ppt

《数据结构第五章数组和广义表幻灯片.ppt》由会员分享，可在线阅读，更多相关《数据结构第五章数组和广义表幻灯片.ppt（48页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构第五章数组和数据结构第五章数组和广义表广义表第1页，共48页，编辑于2022年，星期六第五章第五章数组和广义表数组和广义表5.1数组的定义数组的定义5.2数组的顺序存储结构数组的顺序存储结构5.3矩阵的压缩存储矩阵的压缩存储5.4广义表的定义广义表的定义5.5 5.5 广义表的存储结构广义表的存储结构第2页，共48页，编辑于2022年，星期六3 前前4 4章介章介绍的数据的数据结构共同特点：构共同特点：都属于都属于线性数据性数据结构；构；每种数据每种数据结构中的数据元素，都作构中的数据元素，都作为原子数据，原子数据，不再不再进行分解；行分解；本章本章讨论的两种数据的两种数据结构：数构：

2、数组和广和广义表，其共同特点表，其共同特点是：是：从从逻辑结构上看它构上看它们，可看成是，可看成是线性性结构的一种构的一种扩展；展；数据元素本身也是一个数据数据元素本身也是一个数据结构；构；第五章第五章数组和广义表数组和广义表第3页，共48页，编辑于2022年，星期六4 一一、数数组的定的定义(1)(1)数数组的抽象数据的抽象数据类型定型定义 ADT Array ADT Array 数据数据对象：象：D aj1,j2,ji,jn|ji=0,bi-1,i=1,2,n(n0)称为数组的维数,bi是数组第i维的长度，ji是数组元素的第i维下标 5 51 1 数组的定义数组的定义 数据关系：数据关系：

3、R R1,R2,Rn 第4页，共48页，编辑于2022年，星期六6 (2)(2)二二维数数组的解的解释a00 a01 a0 n-1 a10 a11 a1 n-1 am-1 0 am-1 1 am-1 n-1 二二维数数组中的每个元素都受两个中的每个元素都受两个线性关系的性关系的约束，即行关系和列关系，在束，即行关系和列关系，在每个关系中，每个元素每个关系中，每个元素a aijij都有且都有且仅有一个有一个直接前直接前趋，都有且，都有且仅有一个直接后有一个直接后继。在行关系中在行关系中 aijaij直接前趋是直接前趋是 aij-1 aijaij-1 aij直接后继是直接后继是 aij+1aij+

4、1在列关系中在列关系中 a aijij直接前趋是直接前趋是 a ai-1j i-1j a aijij直接后继是直接后继是 a ai+1ji+1j第6页，共48页，编辑于2022年，星期六7 A=(A=(0 0,1 1 ,2 2,3 3,4 4,p)p)p p=m-1=m-1 或或 n-1 n-1 其中每一个数据元素其中每一个数据元素 j j 是一个列向量的是一个列向量的线性表性表 j j=（a a0j 0j,a a1j 1j ,a,a2j 2j,a a3j 3j,a,am-1j m-1j)0 0jjn-1n-1 二二维数数组也可看作也可看作这样的的线性表：其性表：其每一个数据元每一个数据元素也

5、是一个素也是一个线性表。性表。a00 a01 a0 n-1 a10 a11 a1 n-1 am-1 0 am-1 1 am-1 n-1A Am m n=a00 a10 am-1 0A Am m n=第7页，共48页，编辑于2022年，星期六8 或或 i i 是一个行向量的是一个行向量的线性表性表 i i=（a ai0 i0 ,a,ai1 i1 ,a,ai2 i2,a ai3 i3,a,ain-1 in-1)0 0i im-1 m-1 A Am m n n=(a(a00 00 a a0101 a a0 n-1 0 n-1),(a),(a10 10 a a1111 a a1 n-11 n-1),(

6、a),(am-1 0 m-1 0 a am-1 1m-1 1 a am-1 n-1m-1 n-1)(3)(3)C C语言中二言中二维数数组类型的一种定型的一种定义 typedef elemtype Array2mn;typedef elemtype Array2mn;等价于等价于 typedef elemtype Array1n;typedef elemtype Array1n;typedef Array1 Array2m;typedef Array1 Array2m;同理，可以用同理，可以用 n-1 n-1 维数数组的数据的数据类型来定型来定义 n n 维数数组。第8页，共48页，编辑于20

7、22年，星期六9一、一、数组的顺序表示和实现数组的顺序表示和实现(1)(1)类型特点类型特点 只有引用型操作，一般不作插入或删除操作；数组是多维的结构，而存储空间是一个一维的结构。(2)(2)两个两个策略策略-两种顺序映象的方式两种顺序映象的方式 以行序为主序以行序为主序(低下标优先低下标优先)；以列序为主序以列序为主序(高下标优先高下标优先)。5 52 2 数组的顺序存贮结构数组的顺序存贮结构第9页，共48页，编辑于2022年，星期六10a00 a01 a0 n-1 a10 a11 a1 n-1 am-1 0 am-1 1 am-1 n-1A Am m n=以行以行为主序的方式：主序的方式：

8、a00 a01 a0n-1 a10 a11 a1n-1 a(m-1)n-1 amn-10 1 n-1 n n+1 2n-1 mn-1第10页，共48页，编辑于2022年，星期六110 1 m-1 m m+1 2m-1 nm-1a00 a10 am-10 a01 a11 am-11 a0n-1 a1n-1 amn-1以列以列为主序的方式：主序的方式：第11页，共48页，编辑于2022年，星期六1212(4)(4)存存储位置的公式位置的公式 假假设二二维数数组A A每个元素每个元素占用占用L个存个存储单元，若以行序元，若以行序为主序的主序的方式存方式存储二二维数数组，二二维数数组A A中任一元素中

9、任一元素a ai,ji,j的存的存储位置位置为：LOC(i,j)=LOC(0,0)+(b2ij)L 三三维数数组A A中任一元素中任一元素a ai,j,ki,j,k的存的存储位置位置为：LOC(i,j,k)=LOC(0,0,0)+(bLOC(i,j,k)=LOC(0,0,0)+(b2 2bb3 3iib b3 3j+k)Lj+k)L若以列序为主序的方式存储二维数组，则元素若以列序为主序的方式存储二维数组，则元素a aijij的存储位置可由的存储位置可由下式确定：下式确定：Loc(a aijij)=Loc(a a0000)+（b1 j+i)L第12页，共48页，编辑于2022年，星期六1313三

10、三维二二维一一维123123412a111a121a131a141a211a231a241a221a331a341a321a311a142a132a122a112a242a342第13页，共48页，编辑于2022年，星期六151515(5)(5)结构定构定义#define maxarraydim 8 define maxarraydim 8 typedef struct typedef struct elemtype*base;/elemtype*base;/数数组元素基址元素基址 int dim;/int dim;/数数组维数数 int*bounds;/int*bounds;/数数组维界基址

11、界基址(各各维容量容量)int*constants;/int*constants;/数数组映象函数常量基址映象函数常量基址 array;array;第15页，共48页，编辑于2022年，星期六5.3矩阵的压缩存储矩阵的压缩存储 一一 特殊矩阵的压缩存储特殊矩阵的压缩存储二二 稀疏矩阵的压缩存储稀疏矩阵的压缩存储 1 1 三元组表的存储结构三元组表的存储结构 2 2 十字链表的存储结构十字链表的存储结构第16页，共48页，编辑于2022年，星期六(1)(1)矩矩阵压缩存存储的必要性的必要性 矩阵是许多科学与工程计算问题中常常涉及到的一种运算对象。通常程序员是用二维数组存储矩阵。由于这种存储方法可

12、以随机地访问矩阵的每个元素，因而能较为容易地实现矩阵的各种运算。应用中常遇到一些阶数很高的矩阵，矩阵中有许多值相同的元素或零元素。二维数组存储矩阵会浪费很多的存储单元。例如，设一个1000 1000的矩阵中有800个非零元素，若用二维数组存储需要106个存储单元。因此，需要使用高效的存储方法，减少数据的存储量，即对原矩阵，根据数据分布特征进行压缩存存储。1 1、矩阵的压缩存储矩阵的压缩存储5 53 3 矩阵的压缩存储矩阵的压缩存储第17页，共48页，编辑于2022年，星期六(2)(2)压缩存存储的有关概念的有关概念 压缩存存储：为多个多个值相同的元素分配一个存相同的元素分配一个存储空空间，对零

13、元零元不分配空不分配空间。特殊矩特殊矩阵：值相同的元素或零元素在矩相同的元素或零元素在矩阵中的分布有一定中的分布有一定规律。律。稀疏矩稀疏矩阵：值相同的元素或者零元素在矩相同的元素或者零元素在矩阵中的分布无中的分布无规律。律。第18页，共48页，编辑于2022年，星期六a11 a11 a1na21 a22 a2nan1 an2 anna11 a21 a22 a31 a32 a33 an1 an2 an3 ann 压缩存存储方法方法 为每每一一对对称称元元分分配配一一个个存存储空空间，则可可将将n n2 2个个元元压缩存存储到到n(n+1)/2n(n+1)/2个元的空个元的空间中。中。(3)(3

14、)特殊矩特殊矩阵 概概念念：若若n n阶矩矩阵 A A 中中的的元元满足足：a aijij=a=ajiji 1 1i,ji,jn n，则称称为n n 阶对称矩称矩阵。a11a21 a22 a31 a32 a33 an1 an2 annk=0 1 2 3 4 5 n(n+1)/2-1 第19页，共48页，编辑于2022年，星期六 下下标对应关系关系k=k=当 i j当当 i i j j 矩矩阵的上的上(下下)三角三角(不含不含对角角线)中的元均中的元均为常数常数C C或或0 0的的n n阶矩矩阵(三角三角矩矩阵)，其存，其存储方法相同。方法相同。例如，a a32 32 在 sa 中的存储位置是：

15、k=3*(3-1)/2+2-1=4 sa4=a a32 32 (4)(4)对角矩角矩阵 概念：概念：非零元都集中在以主非零元都集中在以主对角角线为中心的中心的带状区域中。状区域中。存存储：这种种矩矩阵可可以以某某个个原原则(以以行行为主主，或或以以对角角线的的顺序序)将将其其压缩存存储到一到一维数数组上。上。第20页，共48页，编辑于2022年，星期六 压缩存储的对称矩阵的取值算法压缩存储的对称矩阵的取值算法intget_M(inti,intj)if(i=j)return(sai*(i+1)/2+j)elsereturn(saj*(j+1)/2+i);压缩存储的对称矩阵的压缩存储的对称矩阵的赋

16、值算法赋值算法voidassign_M(inti,intj,intvalue)if(i=j)sai*(i+1)/2+j=value;elsesaj*(j+1)/2+i=value;第21页，共48页，编辑于2022年，星期六 带状矩阵带状矩阵 所有非0元素都集中在以主对角线为中心的带状区域，半带宽为d时,非0元素有(2d+1)*n-(1+d)*d个a a00 00 a a01 01 a a 02 02 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 a a10 10 a a11 11 a a12 12 a a13 13 0 0 0 0 0 0 0 0 0 0 0 0 0

17、 0 0 0a a20 20 a a21 21 a a22 22 a a23 23 a a24 24 0 0 00 0 0 0 0 0 0 0 0 0 00 0 a a31 31 a a32 32 a a33 33 a a34 34 a a35 35 0 00 0 0 0 0 0 0 0 0 00 0 0 0 a a42 42 a a43 43 a a44 44 a a45 45 a a46 46 0 0 0 0 0 0 0 0 0 00 0 0 0 0 a0 a53 53 a a54 54 a a55 55 a a56 56 a a57 57 0 00 0 0 0 0 0 0 0 0 0 0

18、 00 0 a a64 64 a a65 65 a a66 66 a a67 67 a a68 68 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 a a75 75 a a76 76 a a77 77 a a78 78 a a79 79 0 0 0 0 0 00 0 0 0 0 0 0 0 0 a0 a86 86 a a87 87 a a88 88 a a89 89 a a810810 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 a a9797 a a98 98 a a99 99 a a910 910 a a911 911 0 00 0 0 0 0 0 0 0

19、 0 0 0 0 0 0 a a108 108 a a109 109 a a1010 1010 a a1011 1011 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 a a119 119 a a1110 1110 a a11111111d第22页，共48页，编辑于2022年，星期六a 00 a01 0 0 0 a10 a11 a12 0 0 0 a21 a22 a23 00 0 a32 a33 a34 0 0 0 a43 a44 为计算方便，认为每一行都有2d+1个非0元素，若少则用0补足，所以，存放矩阵的数组sa 有n(2d+1)个元素 数组元素sak与矩阵元素ai

20、j 之间有关系：k=i*(2d+1)+d+(j-i)k=i*(2d+1)+d+(j-i)0 0 a a0000 a a0101 a a1010 a a11 11 a a12 12 a a21 21 a a22 22 a a23 23 a a32 32 a a33 33 a a34 34 a a43 43 a a44 44 0 0K=0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 第23页，共48页，编辑于2022年，星期六 压缩存储的带状矩阵的取值算法压缩存储的带状矩阵的取值算法intget_Md(inti,intj)if(abs(i-j)=d）return(sai*(2

21、*d+1)+d+(j-i)；elsereturn(0);压缩存储的压缩存储的带状矩阵的带状矩阵的赋值算法赋值算法voidassign_Md(inti,intj,intvalue)if(abs(i-j)=d）sai*(i+1)/2+j=value;第24页，共48页，编辑于2022年，星期六(5)(5)稀疏矩稀疏矩阵 含含义：在：在 mn mn 的矩的矩阵中，有中，有t t 个元素不个元素不为零，令：零，令：称称为矩矩阵的的稀稀疏疏因因子子，通通常常认为0.05 0.05 时称稀疏矩称稀疏矩阵 抽象数据抽象数据类型稀疏矩型稀疏矩阵的定的定义 分析分析 按常按常规方法，即以二方法，即以二维数数组表

22、示高表示高阶的稀疏矩的稀疏矩阵时产生的生的问题:I I 零值元素占了很大空间；II II 计算中进行了很多和零值的运算，遇除法，还需判别除数是否为零。第25页，共48页，编辑于2022年，星期六解决解决问题的原的原则:I I 尽可能少存或不存零值元素；IIII 尽可能减少没有实际意义的运算；IIIIII 操作方便。即：能尽可能快地找到与下标值(i，j)对应的元素，能尽可能快地找到同一行或同一列的非零值元。为此提出一种存储方法：为了能找到相应的元素，仅存储非零元素的值是不够的，还要记下它所在的行和列。于是采取将非零元素所在的行、列以及它的值构成一个三元组(i,j,v)，然后再按某种规律存储这些三

23、元组，这种方法可以节约存储空间。第26页，共48页，编辑于2022年，星期六 例如：稀疏矩例如：稀疏矩阵：A=0 12 912 9 0 0 0 0 0 0 0 0 0 0 0-3-3 0 0 0 0 1414 0 0 0 24 24 0 0 0 0 0 1818 0 0 0 0 0 1515 0 0-7-7 0 0 0 可用三元三元组表表(i,j,ai,j,aijij)A=(0,1,12),(0,2,9),A=(0,1,12),(0,2,9),(2,0,-3),(2,5,14),(2,0,-3),(2,5,14),(3,2,24),(4,1,18),(3,2,24),(4,1,18),(5,0

24、,15),(5,3,-7)(5,0,15),(5,3,-7)加上行、列数、非零元个数6 6，7,87,8 表示。用三元用三元组表存表存储稀疏矩稀疏矩阵有三种方法：有三种方法：I I 三元三元组顺序表序表 II II 行行逻辑链接的接的顺序表序表 III III 十字十字链表表 第27页，共48页，编辑于2022年，星期六 三元三元组顺序表序表 I I 概念：概念：以顺序存储结构来表示三元组表，得稀疏矩阵的一种压缩存储方式称之为三元组顺序表。如：如：A=0 12 912 9 0 0 0 0 0 0 0 0 0 0 0-3-3 0 0 0 0 1414 0 0 0 24 24 0 0 0 0 0

25、1818 0 0 0 0 0 1515 0 0-7-7 0 0 0 i i j j V V0 1 2 3 4 5 6 7 8 3 1 -33 1 -36 1 156 1 151 2 121 2 125 2 185 2 181 3 91 3 94 3 244 3 246 4 -76 4 -73 6 143 6 146 7 86 7 8第28页，共48页，编辑于2022年，星期六 如：ma1.row=1,ma1.col=1,ma1.value=12ma1.row=1,ma1.col=1,ma1.value=12 II II 结构定构定义#define maxsize 1024 define max

26、size 1024 typedef struct typedef struct int i,j;int i,j;elemtype v;elemtype v;triple;triple;typedef struct typedef struct triple datamaxsize+1;triple datamaxsize+1;int mu,nu,tu;int mu,nu,tu;tsmatrix;tsmatrix;III III 转置运算算法置运算算法 转置运算是一种最常用的矩阵运算。对于一个 m m 行 n 列的矩阵 A A，它的转置矩阵 B B 是一个 n n 行 m m 列的矩阵。如，下图

27、中的矩阵 A A 和 B B 互为转置矩阵。第29页，共48页，编辑于2022年，星期六 小 结 1 矩阵压缩存储是指为多个值相同的元素分配一个 存储空间，对零元素不分配存储空间；2 特殊矩阵的压缩存储是根据元素的分布规律，确定 元素的存储位置与元素在矩阵中的位置的对应关系；3 稀疏矩阵的压缩存储除了要保存非零元素的值外，还 要保存非零元素在矩阵中的位置；第40页，共48页，编辑于2022年，星期六1 1、广义表的定义广义表的定义(1)(1)广广义表的引入表的引入 线性表是由n个数据元素组成的有限序列。其中每个组成元素被限定为单元素，有时这种限制需要拓宽。例如，中国举办的某体育项目国际邀请赛，

28、参赛队清单可采用如下的表示形式：(俄罗斯，巴西，(国家，河北，四川)，古巴，美国，()，日本)在这个拓宽了的线性表中，韩国队应排在美国队的后面，但由于某种原因未参加，成为空表。国家队、河北队、四川队均作为东道主的参赛队参加，构成一个小的线性表，成为原线性表的一个数据项。这种拓拓宽了的了的线性表性表就是广广义表表。5.4 5.4 广义表广义表第41页，共48页，编辑于2022年，星期六(2)(2)广广义表的定表的定义 广义表（Generalized Lists）是n（n0）个数据元素 a1，a2，ai，an 的有序序列，一般记作：ls（a1，a2，ai，an）其中：ai（1in）是ls的成员，它

29、可以是单个元素，也可以是一个广义表。说明明 ls是广义表的名称，n是它的长度。广义表的定义是一个递归定义，因为在描述广义表时又用到了广义表；第42页，共48页，编辑于2022年，星期六 在线性表中数据元素是单个元素，而在广义表中，元素可以是单个元素,称为单元素(原子原子)，也可以是广义表，称为广义表的子表子表；当广义表ls非空时，称第第一一个个元元素素a1为ls的表头(head)，称其其余余元素组成的表表（a1，a2，ai，an）为ls的表尾(tail)。若广义表不空，则可分成表头和表尾，反之，一对表头和表尾可唯一确定广义表。为书写清楚起见，通常用大写字母表示广义表，用小写字母表示单个数据元素

30、，广义表用括号括起来，括号内的数据元素用逗号分隔开。第43页，共48页，编辑于2022年，星期六 (3)(3)广广义表示例表示例 A=()B=(a,(b,c,d)C=(e)D=(A,B,C,f)(4)(4)广广义表的表的层次关系次关系 广义表的元素之间除了存在次序次序关系外，还存在层次次关系，以圆圈圈表示列表，以方方块表示原子。上面示例的层次关系如下：DABCfa ebcd第44页，共48页，编辑于2022年，星期六 广义表是一种多多层次次的数据结构。广义表的元素可以是单元素，也可以是子表，而子表的元素还可以是子表，。广义表可以是递归的表。广义表的定义并没有限制元素的递归，即广义表也可以是其自

31、身的子表。例如广义表：E（a，E），就是一个递归的表。广义表可以为其他表所共享。例如，表A、表B、表C是表D的共享子表。在D中可以不必列出子表的值，而用子表的名称来引用。(5 5)广广义表的性表的性质第45页，共48页，编辑于2022年，星期六2 2 广义表的存储结构广义表的存储结构 由于广义表中数据元素可以具有不同结构，故难以用顺序结构表示广义表。通常采用链表存储方式 如何设定链表结点？广义表中的数据元素可能为单元素(原子)或子表，由此需要两种结点：一种是表结点，用以表示广义表；一种是单元素结点，用以表示单元素（原子）。tag hp tp表结点1 0 tag atom tp单元素结点第46页，共48页，编辑于2022年，星期六 小 结 1 广义表是数据元素的有限序列。其数据元素 可以单个元素，也可以是广义表；2 广义表，通常采用链式存储结构3 分解非空广义表的方法：将非空广义表分解为表头和表尾两部分；第47页，共48页，编辑于2022年，星期六第48页，共48页，编辑于2022年，星期六