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