文本编辑器的数据结构

Question

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

Answer 1

在好的旧ZX-Spectrum上(或者更多,我不知道)文本exditor使用非常简单的结构.

有一个大缓冲区占用了所有空闲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

绳

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

与将字符串存储为字符数组相比,绳索的主要优点是它们比普通字符串实现更快的连接,并且不需要大的连续内存空间来存储大字符串.主要缺点是更大的整体空间使用和更慢的索引,随着树结构变得越来越大,这两者都变得更加严重.然而,索引的许多实际应用仅涉及对字符串的迭代,只要叶节点足够大以受益于缓存效果,该字符串就保持快速.

Answer 3

我知道答案已经太晚了,但我发现"文本编辑工艺"一书非常有用.它包含几种缓冲模型的描述及其优缺点.不幸的是,它没有提到Ropes数据结构.

Answer 4

您可能会觉得这很有趣,即使它没有完全回答您的问题:

最有效的数据结构,为文本添加样式

我希望讨论能够进入迷人的地方:-)