代码之家 › 专栏 › 技术社区 › serhio

使用memento撤消/重做:堆栈、队列还是只使用LinkedList?

collections design-patterns .net

serhio · 技术社区 · 16 年前

实施时最好拥有什么 Memento pattern (撤销/重做)

在女巫收藏中保存纪念品?

基本上,我需要这个(c=更改,u=撤消,r=重做):

                  0
                  *c
            -1    0
                  *c
      -2    -1    0
                  *c
-3    -2    -1    0
                  <u
      -2    -1    0    1
                  *c
-3    -2    -1    0

变体:

链表 -原则上是可能的,可能没有优化。
排队 -我不适应这个任务。
栈 -不适用于撤消和重做;
双栈 -可能是最佳的,但无法控制撤消最大大小。

5 回复 | 直到 7 年前

serhio 16 年前

最后,我使用了LinkedList

Public Sub Add(ByVal item As T)
  If _list.Count > 0 Then
    If Me.IsFull Then
      ' we forgot (delete) the oldest state '
      _list.RemoveFirst()
    End If
    ' remove all the following the current items objects '
    Dim lastNode As LinkedListNode(Of T) = _list.Last
    While Not Object.ReferenceEquals(_currentNode, lastNode)
      _list.RemoveLast()
      lastNode = _list.Last
    End While
  End If

  ' add the new item and point current to it '
  _currentNode = _list.AddLast(item)
End Sub

sfg 16 年前

撤消时,您将希望恢复到最近覆盖的数据。所以您要使用的纪念品将是最后一个添加到收藏中的。由于堆栈是后进先出(后进先出)的,因此它们对于您的意图应该是理想的。

注意:您可能希望了解命令模式,因为它对于实现撤消功能非常有用。

编辑:没有注意到你想要重做。从你的堆栈中弹出一些东西会把它去掉,这样对你的目的就没有多大用处了。链接列表应该有效。

Doug Ferguson 16 年前

是否希望用户能够选择多个项目进行撤消或重做?

如果是这种情况,那么您将希望使用通用列表或可观察集合(如果是WPF/Silverlight),以便项目可以显示在UI中。您可以使用两个列表:一个用于撤消,另一个用于重做。

adam 16 年前

使用双重链接列表。当用户使用撤消/重做时,他们可能会多次索引状态(例如,执行4次撤消,然后意识到自己做得太远并执行重做)。单个堆栈或队列将不支持这一点。

两个堆栈支持撤消和重做,但我认为使用它们有点浪费。所有重做备忘将在用户执行编辑(创建新的备忘)时被删除。因此,大多数情况下,应用程序运行时都不会有“重做”的内存。

假设您在标记它.net之后有垃圾收集: 当一个用户进行编辑时,你所要做的就是将链接列表的头引用设置为当前的备忘录。如果您使用一个栈,那么您将不得不创建一个新的栈或者从中弹出所有东西,以便GC释放重做内存。

user3623182 7 年前

A 双端队列 最好用于有效支持撤消重做操作。当用户输入单词时,节点将插入队列,头部指针指向当前位置。当一个撤消操作被触发时,只需将头部移动到上一个节点,在重做操作时,将头部指针移动到列表中的下一个位置。在执行编辑操作时,删除头部右侧的所有节点,并在头部末端插入。这样我们就可以在 O(1) 时间复杂性。