《算法合集之《对块状链表的一点研究》》由会员分享，可在线阅读，更多相关《算法合集之《对块状链表的一点研究》（19页珍藏版）》请在金锄头文库上搜索。
1、传统的FAT文件系统将磁盘空间分簇，并使用FAT表(File Allocation Table)索引每一个簇。 数据（文件） 以簇链式结构储存。,引子,对块状链表的一点研究,山西大学附属中学 苏煜 2008年1月,NOI2003 editor,数组模拟,定位很快 插入删除慢，数据大会超时,链表模拟,插入删除很快 定位非常慢，数据大会超时,数据结构的结合,整体使用链表 单个节点使用小数组存储比较多的信息,所谓的“块状”链表,基本操作,定位,分裂,Insert,Delete,及时合并小分块,分块大小的选择,sqrt(n)与2sqrt(n)之间。,NEERC2003,KeyInsertion,N(1
2、 = 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处插入一个新元素
3、。,CERC2007 sort,在一个车间里有N（1=N=100000）个零件排成一列，它们的高度各不相同，现在要使用如下方法将它们按高度排序： 找到最低的零件的位置P1，将区间1,P1反转，再找到第二低的零件的位置P2，将区间2,P2反转 要求你的程序输出P1,P2,P3,（有改动）,Reverse,用块状链表解法很简单,Minimum in block,NOI2005 维护序列,维护多种序列！,NOI2007 项链工厂,NOI2006 生日快乐,链式,环式,平衡树,总结1,时间复杂度高代码较长,空间利用率高直观维护多种序列,优点：,缺点：,总结2,“弱弱结合”追求平衡整体处理,块状链表的特点：,谢谢,
