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

传统的FAT文件系统将磁盘空间分簇，并使用FAT表(File Allocation Table)索引每一个簇。 数据（文件） 以簇链式结构储存。 对块状链表的一点研究 山西大学附属中学 苏煜 2008年1月 NOI2003 editor 数组模拟 定位很快 插入删除慢，数据大会超时 数据结构的结合 整体使用链表 单个节点使用小数组存储比较多的信息 基本操作 定位 Insert Delete 分块大小的选择 sqrt(n)与2×sqrt(n)之间。 NEERC2003,KeyInsertion N(1 = N = 131 072)个士兵在进行队列训练，从左至右有M（1 = M = 131 072）个位置。每次将军可以下达一个命令，表示为Goto(L,S)。 若队列L位置上为空，那么士兵S站在L上。 若队列L位置上有士兵K，那么士兵S站在L上，执行Goto（L+1，K）。 将军对N个士兵依次下达N个命令，每个士兵被下达命令一次且仅一次。要你求出最后队列的状态。（有可能在命令执行过程中，士兵站的位置标号超过M，所以你最后首先要求出最终的队列长度。0表示空位置）。 用块状链表解法很简单 “正规”解法比较复杂，请参考05年龙凡的论文《序的应用》。 其实就是把L之后的第一个空位置删掉，再在L处插入一个新元素。 CERC2007 sort 在一个车间里有N（1=N=100000）个零件排成一列，它们的高度各不相同，现在要使用如下方法将它们按高度排序： 找到最低的零件的位置P1，将区间[1,P1]反转，再找到第二低的零件的位置P2，将区间[2,P2]反转…… 要求你的程序输出P1,P2,P3… NOI2005 维护序列 总结1 总结2 “弱弱结合” 追求平衡 整体处理 * * 引子 将光标移动到第k个字符之后，如果k=0，将光标移到文本开头 Move k MOVE(k) 光标后移一个字符 Next NEXT() 光标前移一个字符 Prev PREV() 输出光标后的n个字符，光标位置不变，n ? 1 Get n GET(n) 删除光标后的n个字符，光标位置不变，n ? 1 Delete n DELETE(n) 在光标处插入长度为n的字符串s，光标位置不变，n ? 1 Insert n? S INSERT(n, s) 功能 输入文件中的格式 操作名称 链表模拟 插入删除很快 定位非常慢，数据大会超时 所谓的“块状”链表 分裂 及时合并小分块 0 0 0 0 0 0 0 0 0 0 0 8 0 3 1 0 0 0 6 7 0 5 2 3 1 4 0 0 0 6 7 0 5 （有改动） Reverse 用块状链表解法很简单 Minimum in block NOI2007 项链工厂 NOI2006 生日快乐 时间复杂度高 代码较长 空间利用率高 直观维护多种序列 优点： 缺点： 块状链表的特点： * * *