算法合集之《对块状链表的一点研究》

《算法合集之《对块状链表的一点研究》》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、对块状链表的一点研究山西大学附中苏煜对块状链表的一点研究山西大学附中苏煜【摘要】本文主要介绍了块状链表的概念，如何扩展块状链表,讨论了块状链表的性能以及在信息学竞赛中应用块状链表的利与弊，最后简要介绍了块状链表思想在实际生活中的应用。【关键词】块状链表分块大小性能块状链表的扩展模拟骗分一、什么是块状链表我们先从题目入手，看看什么是块状链表：NOI2003editor【题目大意】一些定义：文本：由0个或多个ASCII码在闭区间[32,126]内的字符（即空格和可见字符）构成的序列。光标：在一段文本中用于指示位置的标记，可以位于文本首部，文本尾

2、部或文本的某两个字符之间。文本编辑器：为一个包含一段文本和该文本中的一个光标的，并可以对其进行如下六条操作的程序。如果这段文本为空，我们就说这个文本编辑器是空的。操作名称输入文件中的格式功能MOVE(k)Movek将光标移动到第k个字符之后，如果k=0，将光标移到文本开头INSERT(n,s)Insertn¿S在光标处插入长度为n的字符串s，光标位置不变，n³1DELETE(n)Deleten删除光标后的n个字符，光标位置不变，n³1GET(n)Getn输出光标后的n个字符，光标位置不变，n³1PREV()Prev光标前移一个字符NEXT(

3、)Next光标后移一个字符比如一个空的文本编辑器依次执行操作INSERT(13,“Balancedtree”)，MOVE(2)，DELETE(5)，NEXT()，INSERT(7,“editor”)，MOVE(0)，GET(16)后，会输出“Badeditortree”。你的任务是：建立一个空的文本编辑器。10对块状链表的一点研究山西大学附中苏煜从输入文件中读入一些操作并执行。对所有执行过的GET操作，将指定的内容写入输出文件。【数据范围】lMOVE操作不超过50000个，INSERT和DELETE操作的总个数不超过4000，PREV和NE

4、XT操作的总个数不超过200000。l所有INSERT插入的字符数之和不超过2M（1M=1024*1024），正确的输出文件长度不超过3M字节。lDELETE操作和GET操作执行时光标后必然有足够的字符。MOVE、PREV、NEXT操作必然不会试图把光标移动到非法位置。l输入文件没有错误。首先分析题目：这道题的命令其实只有两类：1.定位；2.添加或删除。这两类操作也正是两种常见顺序表实现方式的主要区别：数组链表定位O(1)O(N)添加或删除O(N)O(1)因为单个操作O(N)复杂度的存在，无论我们用哪一种方法，都不可能AC这个题。但是如果我

5、们将这两种方法结合起来，比如在整体上用链表，具体每一个链表节点改为一个大小适当（比如1000、1500）的数组，那么就可以“优势互补”，得到两种操作更加平衡的数据结构，也就是所谓的“块状链表”。再回到题目，如果用一个整数记录当前位置，那么我们需要一个支持以下操作的数据结构：1、Insert在指定位置添加指定长度信息；2、Erase从指定位置开始删除指定长度的信息；3、Get得到指定位置开始指定长度的信息。具体实现很简单当然有更快的写法，但是这个方法可以省去不少判断，出错概率小一些。：首先我们实现两个内部基本操作：a.定位：从第一个分块开始向

6、后直到找到指定位置所在的分块和他在分块内的位置。b.分裂：将指定分块从指定位置分裂成为两个分块。接下来实现外部基本操作：1、Insert：找到指定位置，分裂块，添加新块直到添加完成。从这里开始插入分裂10对块状链表的一点研究山西大学附中苏煜2、Erase：找到起始位置，分裂首尾块，删掉中间的所有节点。删除虚线之间的文本3、Get：找到指定位置，向后扫描直到找完所需数目。还有一个问题：频繁的分裂操作可能会导致很多连续的块实际储存的数据都很少，大大降低了块状链表的效率，我们可以在每次操作后把过于小的连续分块合并起来。这样就满足了题目的所有要求，

7、同时也完成了一个最基本的块状链表。二、块状链表的简单应用可以感觉到，块状链表其实是对普通模拟操作的一种优化，它将两种并不优秀的方法结合起来，得到了一个比较实用的数据结构。利用它的这种性质，对有些题目，我们可以“强行”模拟地做：NortheasternEurope2003,NorthernSubregion,KeyInsertion【题目大意题目翻译来自05年龙凡的冬令营论文《序的应用》。】N(1<=N<=131072)个士兵在进行队列训练，从左至右有M（1<=M<=131072）个位置。每次将军可以下达一个命令，表示为Goto(L,S)。若

8、队列L位置上为空，那么士兵S站在L上。若队列L位置上有士兵K，那么士兵S站在L上，执行Goto（L+1，K）。将军对N个士兵依次下达N个命令，每个士兵被下达命令一次且仅一次。要你