算法合集之《对块状链表的一点研究》.ppt
《算法合集之《对块状链表的一点研究》.ppt》由会员分享,可在线阅读,更多相关《算法合集之《对块状链表的一点研究》.ppt(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,“弱弱结合” 追求平衡 整体处理,块状链表的特点:,谢谢,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 对块状链表的一点研究 算法 块状 一点 研究
链接地址:https://www.31doc.com/p-2158892.html