打消与重做 | 模子实现
文章目次
一. 打消与重做
打消（Undo）与重做（Redo）利用在日常工作中的使用，想必各人是非常熟悉的。打消与重做给用户带来更高的容错率，其重要水平可以说仅亚于复制粘贴。也正是因为打消与重做利用的实用性与重要性，当我举行一个软件项目的开辟时，也希望给用户实现这两项利用。
那么在开辟者的角度，如作甚用户实现打消与重做的功能呢。颠末我自己的思考，本文提供两个模子思路，来实现打消与重做利用。
二. 打消与重做功能的需求形貌
1. 打消 Undo
打消利用需要完成的是：在用户对被利用对象完成有限次利用后。用户的利用使对象到达某状态。此时再执行打消利用，使得用户可以举行有限次的打消利用后回到先前被利用对象的所有状态。
上述形貌是一个非常抽象的概念。我们接下来举行详细表明。
设用户对被利用对象 O b j Obj Obj，执行了 n n n 次利用为 o i , ( i = 1 , 2 , 3 , . . . , n ) o_i,(i=1,2,3,...,n) oi,(i=1,2,3,...,n)。每次利用前，被利用对象处于状态 s i , ( i = 0 , 1 , 2 , 3 , . . . , n ) s_i,(i=0,1,2,3,...,n) si,(i=0,1,2,3,...,n)，此中 s 0 s_0 s0 为初始状态，即一开始用户尚未做任何利用时备利用对象的状态。基于上述形貌我们可以得到以下图示，体现用户利用的过程。
图1. 用户利用改变被利用对象的状态
由上图可知，用户对 O b j Obj Obj 举行了 3 次利用，使得 O b j Obj Obj 的状态从 s 0 s_0 s0 转换到了 s 3 s_3 s3。此时若用户在 s 3 s_3 s3 状态举行打消，应当使得用户执行有限次打消，使得用户可以使 O b j Obj Obj 回到 s 1 , s 2 , s 3 s_1,s_2,s_3 s1,s2,s3 中的任意状态（如图2所示）。 这就是打消功能要实现的需求。
图2. 用户执行打消利用，回到先前被利用对象的状态
2. 重做 Redo
重做则是在上述打消的根本上再举行的利用。若用户已经执行了有限次打消利用，使得 O b j Obj Obj 从状态 s k , ( 0 ≤ k ≤ n ) s_k,(0\leq k\leq n) sk,(0≤k≤n) 到达了状态 s j , ( 0 ≤ j ≤ k ) s_j,(0\leq j\leq k) sj,(0≤j≤k)，此时可执行有限次重做，可使得 O b j Obj Obj 到达 s j s_j sj 至 s k s_k sk 之间的任意状态。
比方，若在图2所示的情况下。用户在 O b j Obj Obj 的 s 3 s_3 s3 状态下，执行了 3 次打消利用，回到了状态 s 0 s_0 s0。此时用户应当可以执行有限次重做使得 O b j Obj Obj 可以回到 s 3 , s 2 , s 1 s_3,s_2,s_1 s3,s2,s1 的任意状态。
图3. 在图 2 的根本上举行重做利用
3. 综合情况
- 用户举行多次利用后，再举行一定次数的打消，再举行利用时，会对被利用对象产生新的状态覆盖原来的状态。如图 4 所示。
图4. 利用 - 撤回 - 利用的情况
在这种情况下，新利用产生的状态 s k + 4 s_{k+4} sk+4 会覆盖原有的状态 s k + 3 s_{k+3} sk+3，且原 s k + 3 s_{k+3} sk+3 状态的数据会被清除。所以在这种情况下，是不能举行重做的，且无法再通过打消或重做再得到被清除的状态。
为了实现打消与清除，可以使用两种较为简朴的数据结构举行实现。
三. 双栈法实现
所谓双栈法，顾名思义就是使用两个栈结构来实现模子。根本实现规则有以下几点
- 模子分为两个栈，一个为利用栈，一个为打消栈。
- 每一个状态都为一个栈元素。
- 每一个利用都产生一个状态栈元素并入栈。
- 利用栈初始含有被利用对象的初始状态 s 0 s_0 s0，打消栈初始为空。
- 被利用对象的当前状态为栈顶元素元素。
图5. 双栈模子的初始状态
假设我们已经举行了两次利用，在利用栈中压入了三个状态。蓝色的为栈顶元素，是被利用对象的当前状态。
图6. 举行了两次利用后的模子
现在我们举行一次打消利用。在利用栈中弹出栈顶元素 s 2 s_2 s2，将弹出的 s 2 s_2 s2 再压入到打消栈中。此时完成一次打消。此时被利用对象的状态转变为了栈顶的 s 1 s_1 s1，完成了打消。
图6. 举行了一次打消利用
我们继续举行打消。在利用栈中弹出栈顶元素 s 1 s_1 s1，将弹出的 s 1 s_1 s1 压入打消栈。此时被利用对象的状态转变为了栈顶的 s 0 s_0 s0。此时不能再继续举行打消了，因为利用栈不能为空（被利用对象必须拥有一个状态， s 0 s_0 s0已为初始状态）。
图7. 再次打消，被利用对象回到初始状态
此时举行重做测试。举行一次重做，在打消栈中弹出栈顶元素 s 1 s_1 s1 ，并将 s 1 s_1 s1 压入利用栈。此时被利用对象的状态重新指向 s 1 s_1 s1。完成重做利用。
图8. 重做利用
我们接下来再举行一次利用，产生状态 s 3 s_3 s3。此时，如上文综合情况一致。先将新利用产生的状态 s 3 s_3 s3 压入利用栈，然后将打消栈清空。
图9. 再利用时打消栈将会清空
上述形貌了一系列利用下双栈模子的情况。对于双栈模子的优缺点有以下几点
- 优点
- 实现简朴，可以大概快速创建模子并实现。
- 可以通过打消利用回溯到初始状态。
- 缺点
- 无论执行多声步利用都会将状态对象缓存进栈，利用数大的情况下，非常淹灭内存空间。
比方，不撤回重做的举行 10000 次利用，每个 s i , ( i = 1 , . . . , 10000 ) s_i,(i=1,...,10000) si,(i=1,...,10000) 用状态类的对象体现，每个对象需要 64 B 的内存，则双栈模子要为该被利用对象缓存 625 Kb 的数据。
- 大多数时候并不需要回溯到初始状态。为了生存足够的状态以包管可以大概回溯到初始状态非常浪费内存资源。
- 要通过打消或重做回退 n 步，就需要举行 n 次打消或重做。（如果使用链栈可以制止该缺点）
为相识决以上缺点，我们可以使用双链表模子。接下来先容用双链表法优化打消重做算法。
四. 链表法实现
和双栈法相比，在双链表模子下的打消和重做更符合许多软件中的设计。我们以 Photoshop 中的汗青记载功能为例，来形貌。
可见，Ps 的汗青记载栏与双栈模子中的初始情况是相似的，都先生存了一个初始状态，Ps 中是新建状态，在双栈中是 s 0 s_0 s0。
图10. Photoshop 中的汗青记载栏，可用于撤回与重做
我们若执行多步利用，情况如下。注意，在该汗青记载栏中显示的利用名称，而不是状态！其步伐背后生存的依然为图像（被利用对象）的状态。
图11. 执行多次利用的汗青栏
此时我们可以直接通过选择撤回到特定的位置完成多步打消。而且打消颠末的步调（灰色的利用名称）也是可以被选择，从而实现重做的。
图12. 通过选择撤回多步
接着，若我们举行新利用，先前的打消颠末的步调都消失了。这与双栈模子中综合情况相同，会删除用于重做的状态，并使得无法举行重做。
图13. 举行新利用 "橡皮擦"后，无法再重做
Ps 的汗青记载有一个特点，与双栈模子差别，汗青记载中不会无休止的将用户的利用记载下去。双栈模子也正是因为会一直将用户利用产生的状态对象举行缓存，所以存在浪费内存资源的缺点。在我们对图像使用许多次画笔工具后，可以发现原来的初始状态利用 “新建” 已经不在了。汗青记载栏只缓存特定命量的利用状态，一旦到达数量上限，尚有新利用发生，则从最早的利用状态开始删除，同时到场新利用状态到汗青记载栏中。这使得内存的消耗是可控的，由状态对象的巨细和最大缓存多少状态对象决定。
图14. 多次画笔工具利用后，在汗青记载栏最顶部已经找不到 "新建"。
注意右侧的滑动条滑到了最顶部的位置
从以上形貌的汗青记载栏来说，我们可以使用链表来举行打消与重组的模子设计。下图为在链表模子中执行各种利用的情况，读者可以按顺序阅览，明确模子的运行情况。
- 此中蓝色的箭头是一个指针，其作用是标识被利用对象当前的状态，因此要举行打消与重做只需要移动该指针并取出指针所指的状态并以此刷新被利用对象就可以完成。
- 涉及到删除状态时，也只需将指针指向的状态对象的下一节点（链表数据结构的特点）直接置空就可以完成。这一特点接下来有更详细的表明说明。
- 下列图示中的链表规定最大容纳 4 个状态对象。
图15. 链表模子下的各种利用
在上图中的 f 情况下，如果我们直接举行新利用，那么缓存的状态 x 1 x_1 x1、 x 2 x_2 x2、 x 4 x_4 x4 都要删除，此时链表的优势就体现出来了。只需要将指针指向的 s 0 s_0 s0 的下一个节点置为新利用产生的状态，就同时完成了删除三个状态与到场新状态了。
图16. 该模子使用链表数据结构的优势
问题
图15 中的不都是线性存储的列表吗，而且使用线性表就可以完成模子功能无论是顺序存储照旧链式存储。为什么要用链表呢？
实际上，确实只要使用线性表就可以完成该模子，但是使用链式存储的链表效率更高。在该模子中，不强调对表中元素的检索，更强调在表的首尾增加元素和删除元素，所以使用链式存储的表会更高效。
五. 竣事语
实在这篇博客并欠好写，原来是计划草草的随便写一下。但是最后照旧因为比力重视数据结构与算法的部门，照旧做了许多图，只管做成教学级别的博客。博客中大概还存在一些语句不通顺大概谬误，欢迎在批评区指出，我会尽快改正。
其次，关于代码。原来是计划附上 Java 实现的代码的。但是由于大学期末，事情比力繁重，先搁置一段时间。后续会在本博客更新实现代码。如果喜欢博客的内容，渴望得到代码的话，欢迎收藏关注。
六. 提示
可以学习设计模式中的备忘录模式。其与本博客讨论的打消与重做非常相似，大概说完全相同，只是更详细的设计实现。
文章内容来自个人学习总结 欢迎指出本文中存在的问题 未经本人同意克制转载，不得用于商业用途
来源：https://blog.csdn.net/weixin_43095238/article/details/111475741
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ |
