高级数据结构及其应用ppt课件

1、高级数据构造及其运用高级数据构造及其运用福建师大附中周成C内容提要内容提要l一个简单的例子块链l检索树？及其运用再做8数码l并查集及其运用l二叉排序树及其运用圆桌问题菜鸟级问题l圆桌上围坐着2n个人其中n个人是好人，另外n个人是坏人。假设从第一个人开场数数数到第m个人，那么立刻处死该人，然后从被处死的人之后开场数数，再将数到的第m个人处死依此方法不断处死围坐在圆桌上的人。试问预先应如何安排这些好人与坏人的座位，能使得在处死n个人之后，圆桌上围坐的剩余的n个人全是好人。输入格式：输入文件中的仅一行都有两个数依次为n和m，表示一个问题的描画信息，n32767，m3276

2、7。输出格式：输出问题的解，问题的解可以用延续的假设干行字符来表示，每行的字符数量不超越50，但是在问题的解中不允许出现空白字符和空行，用大写字母G表示好人大写字母B表示坏人。输入输出2 3 GBBG顺序表和块链顺序表和块链1234567891012345678910Head顺序表、链表的时间复杂度均约为On2)1238910两种数据构造下时间效率的比较两种数据构造下时间效率的比较编号NM算法一用时算法二用时1500004001.10s0.44s2327673276746.92s0.33s3327673276546.32s0.33s4500004000093.96s0.60s算法一：顺序表算法

3、二：块链结论：随着问题规模的进一步扩展，算法二与一相比，时间效率会更明显！检索树检索树l检索树是一种简单但用途广的数据构造。l有时可替代哈希表l它可以用来储存各种元素类型范围一定的串，例如字符串，数串等。l例如用检索树来储存abc,abd,bca,bcb,bcd这个字符串集合，可表示为：检索树检索树l由图可知，在一棵检索树中查找一个目的只需求OL的时间，L为目的的串长度，比盲目比较要快得多。在空间上，由于检索树是动态创建的，防止了不用要的浪费。 检索树检索树8数码问题中的运用数码问题中的运用l八数码问题是一题经典的广度搜索问题。l问题1：简单地采用广度搜索对步数较多和无解的情况就无法得出结果。

4、l可以运用双向搜索进展优化。l问题2：但在判重时仍需求很大的复杂度导致了整个算法的复杂度很大。l处理方法：可以运用检索树来存储一切已扩展的形状进展判重，复杂度为O(8)，大大提高了算法的效率。l8数码的检索树只用到了8层，但不用把最后一层开出来，所以在实践内存中之开了7层的空间。形状在检索树的表示形状在检索树的表示检索树数据构造的表示：检索树数据构造的表示：Type Ttree = ty; ty = array0.9of Ttree;Var Tree : Ttree;检索某形状能否出现的函数检索某形状能否出现的函数oklfunction ok(t:longint;s:string):longi

5、nt;l判别形状s能否在检索树中出现，假设出现，那么前往相应1或2(分别代表正向和反向搜索时产生),否那么在检索树并建立该形状l var p:Ttree;l i:integer;l 函数函数okl beginl p:=tree;l for i:=1 to 7 dol beginl if psi=nil then 该形状末出现，那么建立l beginl new(psi); fillchar(psi,sizeof(psi),0);l end;l p:=psi;指针下移到下一层l end; 函数函数oklif ps8=nil then 第8个数码所指的指针为空，表示该形状末出现lbeginl ok:

6、=0;前往0l ps8:=pointer(t); 将搜索的方向值(1或2)强迫转换成指针存入该指针域l endl else否那么，表示该形状出现过l ok:=longint(ps8);将第8个数码所对应的指针值强迫转换生长整数，并做为前往值l end;8数码中运用检索树的效果数码中运用检索树的效果编编号号初始形状初始形状目的形状目的形状步数步数算法一用时算法一用时检索树检索树算法二用时算法二用时普通普通1123456780123087654150.00s0.00s2123456780087654321280.00s6.5s3876543210132745608310.05s46s4876543

7、210123804765无解无解1.9s并查集l竞赛中会经常遇到这样的标题：给出各个元素之间的联络，要求将这些竞赛中会经常遇到这样的标题：给出各个元素之间的联络，要求将这些元素分成几个集合，每个集合中的元素直接或间接有联络。在这类问题元素分成几个集合，每个集合中的元素直接或间接有联络。在这类问题中主要涉及的是对集合的合并和查找，因此将这种集合称为并查集。中主要涉及的是对集合的合并和查找，因此将这种集合称为并查集。l链构造的并查集链构造的并查集l树构造的并查集树构造的并查集ll链构造的并查集l链表被普通用来计算并查集：表中的每个元素设两个指针：一个指向同链表被普通用来计算并查集：表中的每个元素设

8、两个指针：一个指向同一集合中的下一个元素；另一个指向表首元素。采用链式存储构造，在一集合中的下一个元素；另一个指向表首元素。采用链式存储构造，在进展集合的查找时的算法复杂度仅为进展集合的查找时的算法复杂度仅为O O1 1；但合并集合时的算法复杂；但合并集合时的算法复杂度却到达了度却到达了O On n。假设我们希望两种根本操作的时间效率都比较高的。假设我们希望两种根本操作的时间效率都比较高的话，链式存储方式就话，链式存储方式就“力不从心了。力不从心了。l 前往前往树构造的并查集l采用树构造支持并查集的计算可以满足我们的要求。并查集与普采用树构造支持并查集的计算可以满足我们的要求。并查集与普通的树

9、构造不同，每个顶点纪录的不是它的子结点，而是将它的通的树构造不同，每个顶点纪录的不是它的子结点，而是将它的父结点记录下来。下面我引见一下树构造的并查集的两种运算方父结点记录下来。下面我引见一下树构造的并查集的两种运算方式式l直接在树中查询直接在树中查询l边查询边边查询边“途径紧缩途径紧缩l对应与前面的链式存储构造，树状构造的优势非常明显：编程复杂度低；时间效率高。 前往直接在树中查询集合的合并算法很简单，只需将两棵树的根结点相连即可，这步操集合的合并算法很简单，只需将两棵树的根结点相连即可，这步操作只需作只需O O1 1时间复杂度。所以算法的时间效率取决于集合查找的快慢。时间复杂度。所以算法的

10、时间效率取决于集合查找的快慢。而集合的查找效率与树的深度呈线性关系。因此直接查询所需求的时间复而集合的查找效率与树的深度呈线性关系。因此直接查询所需求的时间复杂度平均为杂度平均为O OlogNlogN。但在最坏情况下，树退化成为一条链，使得每一。但在最坏情况下，树退化成为一条链，使得每一次查询的算法复杂度为次查询的算法复杂度为O ON N。边查询边“途径紧缩 其实，我们还能将集合查找的算法复杂度进一步降低：采用其实，我们还能将集合查找的算法复杂度进一步降低：采用“途径途径紧缩算法。它的想法很简单：在集合的查找过程中顺便将树的深度紧缩算法。它的想法很简单：在集合的查找过程中顺便将树的深度降低。采用途径紧缩后，每一次查询所用的时间复