什么是拉链数据结构,我应该使用它吗?

让我们从列表的拉链模拟开始。如果要修改列表的第n个元素,则需要O(n),因为必须首先复制n-1个元素。相反,您可以将列表保持为一个结构(颠倒前n-1个元素)n个元素(其余元素))。例如,列表 (1 2 3 4 5 6) 在3处可修改的将表示为 ((2 1) 3 (4 5 6)) . 现在,您可以轻松地将3更改为其他内容。您还可以轻松地将焦点向左移动 ((1) 2 (3 4 5 6)) 正确 ((3 2 1) 4 (5 6)) .

拉链同样适用于树木。你在树中表示一个特定的焦点,加上一个上下文(向上到父,向下到子),它以一种形式给你整棵树,在焦点处它很容易修改,并且很容易上下移动焦点。

这是一篇很好的文章解释 using the zipper for a tiling window manager in Haskell . 维基百科的文章不是很好的参考资料。

简而言之,拉链是指向树或列表结构中特定节点的指针或手柄。拉链提供了一种自然的方式来获取树结构,并将其视为被焦点节点“拾取”的树-实际上,您可以获得第二棵树,而无需额外复制原始树或影响树的其他用户。

给出的示例显示了如何按照屏幕上的位置对窗口进行原始排序,然后使用指向焦点窗口的拉链对焦点进行建模。您可以得到一组很好的O(1)操作,例如插入和删除,而无需对焦点窗口进行特殊设置或编写额外的代码。

了解你一个哈斯克尔也有 a great chapter about zippers .

This article 与haskell有关,但它也很好地解释了拉链,应该很容易从haskell的细节中抽象出来。