文本编辑器的数据结构

Question

这是一个面试问题。您将使用什么数据结构在文本编辑器中存储文本？

Answer 1

关于好旧的ZX-Spectrum一个(或多个，我不知道)文本编辑程序使用了非常简单的结构。

有一个很大的缓冲区，它占用了所有空闲的RAM。文本在光标处被分成两部分。部分放在缓冲区的开头，其余部分放在缓冲区的末尾。输入文本时，只需将数据添加到第一部分的末尾，当光标移动时，文本就会来回复制。

缓冲区布局：

Hello, World!
        ^------Cursor here

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|H|e|l|l|o|,| |W| <free>  |o|r|l|d|!|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                ^         ^        |
begin           cur1      cur2    end

这就是一些编辑操作是如何进行的：

Type a char:    buffer[cur1++] = character

Backspace:      cur1--

Cursor left:    buffer[--cur2] = buffer[--cur1]

Cursor right:   buffer[cur1++] = buffer[cur2++]

操作中的缓冲区：

             Hello, W..............orld!
Press right          ^             ^
             Hello, Wo..............rld!
Press backspace       ^             ^
             Hello, W...............rld!
Press 0              ^              ^
             Hello, W0..............rld!
                      ^             ^

Answer 2

Rope

绳索本质上是一个二叉树，它的叶子是字符的数组。树中的节点有一个左子节点和一个右子节点--左子节点是字符串的第一部分，而右子节点是字符串的最后一部分。两条绳的连接只涉及创建一个新的树节点，并将两条绳作为子节点。为了确保对数时间索引和子字符串操作，可能需要平衡得到的字符串。各种平衡策略都是可能的。

与将字符串存储为字符数组相比，ropes的主要优点是它们支持比普通字符串更快的连接，并且不需要大量连续的内存空间来存储大型字符串。主要缺点是更大的总体空间使用量和更慢的索引速度，随着树结构变得更大和更深，这两个问题都变得更加严重。然而，索引的许多实际应用只涉及对字符串的迭代，只要叶节点足够大，就可以保持较快的速度，从而受益于缓存效应。

Answer 3

我知道现在回答已经太晚了，但我发现The Craft of Text Editing这本书真的很有用。它包含了几种缓冲区模型的描述，以及它们的优缺点。不幸的是，它没有提到Ropes数据结构。