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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,传统的,FAT,文件系统将磁盘空间分簇，并使用,FAT,表,(File Allocation Table),索引每一个簇。,数据（文件）,以簇链式结构储存。,引子,对块状链表的一点研究,山西大学附属中学,苏煜,2008,年,1,月,NOI2003 editor,操作名称,输入文件中的格式,功能,INSERT(n,s),Insert n,S,在光标处插入长度为,n,的字符串,s,，光标位置不变，,n,1,DELETE(n,),Delete n,删除光标后的,n,个字符，光标位置不变，,n,1,GET(n,),Get n,输出光标后的,n,个字符，光标位置不变，,n,1,MOVE(k,),Move k,将光标移动到第,k,个字符之后，如果,k,=0,，将光标移到文本开头,PREV(),Prev,光标前移一个字符,NEXT(),Next,光标后移一个字符,数组模拟,定位很快,插入删除慢，数据大会超时,链表模拟,插入删除很快,定位非常慢，数据大会超时,数据结构的结合,整体使用链表,单个节点使用小数组存储比较多的信息,所谓的“块状”链表,基本操作,定位,分裂,Insert,Delete,及时合并小分块,分块大小的选择,sqrt(n,),与,2sqrt(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,表示空位置）。,0,0,0,0,0,0,0,0,0,0,0,6,0,0,5,8,0,3,1,0,0,7,6,0,0,5,2,3,1,4,0,0,7,用块状链表解法很简单,“正规”解法比较复杂，请参考,05,年龙凡的论文,序的应用,。,其实就是把,L,之后的第一个空位置删掉，再在,L,处插入一个新元素。,CERC2007 sort,在一个车间里有,N,（,1=N=100000,）个零件排成一列，它们的高度各不相同，现在要使用如下方法将它们按高度排序：,找到最低的零件的位置,P1,，将区间,1,P1,反转，再找到第二低的零件的位置,P2,，将区间,2,P2,反转,要求你的程序输出,P1,P2,P3,（有改动）,Reverse,用块状链表解法很简单,Minimum in block,NOI2005,维护序列,维护多种序列！,NOI2007,项链工厂,NOI2006,生日快乐,链式,环式,平衡树,总结,1,时间复杂度高,代码较长,空间利用率高,直观维护多种序列,优点：,缺点：,总结,2,“弱弱结合”,追求平衡,整体处理,块状链表的特点：,谢谢,