幻灯片1
块状链表
幻灯片2
文本编辑器
l 问题描述
l 文本编辑器为一个可以对一段文本和该文本中的一个光标进行如右六条操作的程序。
|
操作名称 |
输入文件中的格式 |
功能 |
|
MOVE(k) |
Move k |
将光标移动到第k个字符之后 |
|
INSERT(n, s) |
Insert n S |
在光标后插入长度为n的字符串s，光标位置不变 |
|
DELETE(n) |
Delete n |
删除光标后的n个字符，光标位置不变 |
|
GET(n) |
Get n |
输出光标后的n个字符，光标位置不变 |
|
PREV() |
Prev |
光标前移一个字符 |
|
NEXT() |
Next |
光标后移一个字符 |
幻灯片3
文本编辑器
l 例子（ □ 表示空格； | 表示光标 ）
l INSERT(13, “Balanced□tree”)
l MOVE(2)
l DELETE(5)
l NEXT()
l INSERT(7, “□editor”)
l MOVE(0)
l GET(15)
幻灯片4
文本编辑器
l 例子（ □ 表示空格； | 表示光标 ）
l INSERT(13, “Balanced□tree”)
l MOVE(2)
l DELETE(5)
l NEXT()
l INSERT(7, “□editor”)
l MOVE(0)
l GET(15)
l 文本内容：|
l 输出：
幻灯片5
文本编辑器
l 例子（ □ 表示空格； | 表示光标 ）
l INSERT(13, “Balanced□tree”) ←
l MOVE(2)
l DELETE(5)
l NEXT()
l INSERT(7, “□editor”)
l MOVE(0)
l GET(15)
l 文本内容：| Balanced□tree
l 输出：
幻灯片6
文本编辑器
l 例子（ □ 表示空格； | 表示光标 ）
l INSERT(13, “Balanced□tree”)
l MOVE(2) ←
l DELETE(5)
l NEXT()
l INSERT(7, “□editor”)
l MOVE(0)
l GET(15)
l 文本内容：Ba | lanced□tree
l 输出：
幻灯片7
文本编辑器
l 例子（ □ 表示空格； | 表示光标 ）
l INSERT(13, “Balanced□tree”)
l MOVE(2)
l DELETE(5) ←
l NEXT()
l INSERT(7, “□editor”)
l MOVE(0)
l GET(15)
l 文本内容：Ba | d□tree
l 输出：
幻灯片8
文本编辑器
l 例子（ □ 表示空格； | 表示光标 ）
l INSERT(13, “Balanced□tree”)
l MOVE(2)
l DELETE(5)
l NEXT() ←
l INSERT(7, “□editor”)
l MOVE(0)
l GET(15)
l 文本内容：Bad | □tree
l 输出：
幻灯片9
文本编辑器
l 例子（ □ 表示空格； | 表示光标 ）
l INSERT(13, “Balanced□tree”)
l MOVE(2)
l DELETE(5)
l NEXT()
l INSERT(7, “□editor”) ←
l MOVE(0)
l GET(15)
l 文本内容：Bad | □editor□tree
l 输出：
幻灯片10
文本编辑器
l 例子（ □ 表示空格； | 表示光标 ）
l INSERT(13, “Balanced□tree”)
l MOVE(2)
l DELETE(5)
l NEXT()
l INSERT(7, “□editor”)
l MOVE(0) ←
l GET(15)
l 文本内容：| Bad□editor□tree
l 输出：
幻灯片11
文本编辑器
l 例子（ □ 表示空格； | 表示光标 ）
l INSERT(13, “Balanced□tree”)
l MOVE(2)
l DELETE(5)
l NEXT()
l INSERT(7, “□editor”)
l MOVE(0)
l GET(15) ←
l 文本内容：| Bad□editor□tree
l 输出： Bad□editor□tree
幻灯片12
文本编辑器
l 你的任务是：
l 1.建立一个空的文本编辑器。
l 2.从输入文件中读入一些操作指令并执行。
l 3.对所有执行过的GET操作，将指定的内容写入输出文件。
幻灯片13
文本编辑器
l 数据规模
l 1.MOVE操作不超过50000个，INSERT和DELETE操作的总个数不超过4000，PREV和NEXT操作的总个数不超过200000。
l 2.所有INSERT插入的字符数之和不超过2M（1M=1024*1024），正确的输出文件长度不超过3M字节。
幻灯片14
文本编辑器
l 题目分析
l 这道题只有四类命令：
l 1.定位（ MOVE(k) PREV() NEXT() ）
l 2.添加（ INSERT(n，s) ）
l 3.删除（ DELETE(n) ）
l 4.读取（ GET(n) ）
幻灯片15
文本编辑器
l 题目分析
l 两种做法：
l 1.数组
l 2.链表
幻灯片16
文本编辑器
l 题目分析
l 时间效率：
|
数组 |
链表 |
|
|
定位 |
O(1)/次 |
O(N)/次 |
|
添加或删除 |
O(N)/次 |
总共2M |
|
读取 |
总共3M |
总共3M |
|
总时间 |
O(4000 * N) |
O(50000 * N) |
题目时间限制：2s~4s
幻灯片17
文本编辑器
l 题目分析
l 时间效率：
|
数组 |
链表 |
|
|
定位 |
O(1)/次 |
O(N)/次 |
|
添加或删除 |
O(N)/次 |
总共2M |
|
读取 |
总共3M |
总共3M |
|
总时间 |
O(4000 * N) |
O(50000 * N) |
题目时间限制：2s~4s
无法通过
幻灯片18
块状链表引入
l 数组添加、删除慢，链表定位慢（缺点）
l 数组定位快，链表添加删除快（优点）
能否将各自的优点结合创建出一种新的数据结构呢？
幻灯片19
块状链表引入
l 数组添加、删除慢，链表定位慢（缺点）
l 数组定位快，链表添加删除快（优点）
能否将各自的优点结合创建出一种新的数据结构呢？
能
幻灯片20
块状链表定义
l 描述性定义
l 块状链表就是节点为数组的链表。（如下图）
幻灯片21
用块状链表的文本编辑器
l 题目分析
l 如果用一个整数记录当前位置，那么我们需要一个支持以下操作的数据结构：
l 1.Insert在指定位置添加指定长度信息；
l 2.delete从指定位置开始删除指定长度的信息；
l 3.Get得到指定位置开始指定长度的信息。
幻灯片22
用块状链表的文本编辑器
l 具体实现
l 1.内部操作
l 2.外部操作
幻灯片23
用块状链表的文本编辑器
l 具体实现
l 1.内部操作
l a.定位：从第一个分块开始向后直到找到指定位置所在的分块和他在分块内的位置。
l b.分裂：将指定分块从指定位置分裂成为两个分块。
l
幻灯片24
用块状链表的文本编辑器
l 具体实现
l 2.外部操作
l a.Inset
l b.Delete
l c.get
幻灯片25
用块状链表的文本编辑器
l 具体实现
l 2.外部操作
l a.Insert：找到指定位置，分裂块，添加新块直到添加完成。从这里开始插入分裂
幻灯片26
用块状链表的文本编辑器
l 具体实现
l 2.外部操作
l b.Delete
幻灯片27
用块状链表的文本编辑器
l 具体实现
l 2.外部操作
l c.Get：找到指定位置，向后扫描直到找完所需数目。
幻灯片28
用块状链表的文本编辑器
l 遗留问题
l 频繁的分裂操作可能会导致很多连续的块实际储存的数据都很少，大大降低了块状链表的效率，我们可以在每次操作后把过于小的连续分块合并起来。
幻灯片29
用块状链表的文本编辑器
l 遗留问题
l 频繁的分裂操作可能会导致很多连续的块实际储存的数据都很少，大大降低了块状链表的效率，我们可以在每次操作后把过于小的连续分块合并起来。
幻灯片30
用块状链表的文本编辑器
l 时间效率分析
幻灯片31
块状链表的扩展
维基百科：对于链表的一些解释
http://zh.wikipedia.org/wiki/%E9%93%BE%E8%A1%A8
http://dongxicheng.org/structure/blocklink/
http://blog.sina.com.cn/s/blog_6466e8320100gxwr.html
http://blog.csdn.net/w397090770/article/details/8299895
http://starforever.blog.hexun.com/3184024_d.html
http://www.nocow.cn/index.php/%E5%9D%97%E7%8A%B6%E9%93%BE%E8%A1%A8
http://blog.csdn.net/bin314/article/details/7899934
http://blog.csdn.net/bin314/article/details/7900427
未完待续。。。