高级数据结构及其应用.ppt

《高级数据结构及其应用.ppt》由会员分享，可在线阅读，更多相关《高级数据结构及其应用.ppt（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

3、3.96s0.60s算法一：顺序表算法二：块链结论：随着问题规模的进一步扩大，算法二与一相比，时间效率会更明显！检索树检索树l检索树是一种简单但用途广的数据结构。l有时可代替哈希表l它可以用来储存各种元素类型范围一定的串，例如字符串，数串等。l例如用检索树来储存abc,abd,bca,bcb,bcd这个字符串集合，可表示为：检索树检索树l由图可知，在一棵检索树中查找一个目标只需要O（L）的时间，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;

5、s:string):longint;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个数码所指的指针为空，表示该状态末出现lb

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

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

8、个指针：一个指向同一集合中的下一个元素；另一个指向表首元素。采用链式存储结构，在一集合中的下一个元素；另一个指向表首元素。采用链式存储结构，在进行集合的查找时的算法复杂度仅为进行集合的查找时的算法复杂度仅为O O（1 1）；）；但合并集合时的算法复杂但合并集合时的算法复杂度却达到了度却达到了O O（n n）。）。如果我们希望两种基本操作的时间效率都比较高的如果我们希望两种基本操作的时间效率都比较高的话，链式存储方式就话，链式存储方式就“力不从心力不从心”了。了。返回树结构的并查集l采采用用树树结结构构支支持持并并查查集集的的计计算算能能够够满满足足我我们们的的要要求求。并并查查集集与与一一般般

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

10、的查找效率与树的深度呈线性关系。因此直接查询所需要的时间复而集合的查找效率与树的深度呈线性关系。因此直接查询所需要的时间复杂度平均为杂度平均为O O（logNlogN）。）。但在最坏情况下，树退化成为一条链，使得每一但在最坏情况下，树退化成为一条链，使得每一次查询的算法复杂度为次查询的算法复杂度为O O（N N）。）。边查询边“路径压缩”其其实实，我我们们还还能能将将集集合合查查找找的的算算法法复复杂杂度度进进一一步步降降低低：采采用用“路路径径压压缩缩”算算法法。它它的的想想法法很很简简单单：在在集集合合的的查查找找过过程程中中顺顺便便将将树树的的深深度度降降低低。采采用用路路径径压压缩缩后后，每每一一次次查查询询所所用用的的时时间间复复杂杂度度为为增增长长极极为为缓缓慢慢的的ackermanackerman函函数数的的反反函函数数（x x）。对对于于可可以以想想象象到到的的n n，（n n）都都是在是在5 5之内的。之内的。返回并查集的应用并查集的应用l求等价类单词方程相同字符串问题l并查集的变形食物链