文本编辑器的数据结构

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

Rope

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

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

Answer 3

我知道答案已经太迟了，但我发现The Craft of Text Editing书非常有用。它包含几种缓冲模型的描述及其优缺点。不幸的是，它没有提到Ropes数据结构。

Answer 4

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

Most efficient data structure to add styles to text

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

Answer 5

由于@Vovanium已经提到了如何使用间隙缓冲区的基本理论，我已经实现了一个C / C ++版本。

码：

#include <stdio.h>
#define SZ 1000

char leftArray[SZ], rightArray[SZ];
int leftCount, rightCount;
int cursorPos;

/*
 * Private APIs
 */

void printArray(){

    for(register int i = 0; i < leftCount; i++){
        printf("%c", leftArray[i]);
    }

    for(register int i = rightCount - 1; i >= 0; i--){
        printf("%c", rightArray[i]);
    }
    printf("\n");
}

void adjust(int pos){

    while(leftCount > pos){
        rightArray[rightCount++] = leftArray[--leftCount];
    }

    while(leftCount < pos){
        leftArray[leftCount++] = rightArray[--rightCount];
    }
}


/*
 * Public APIs for Text Editor
 */

void init(){

    cursorPos = leftCount = rightCount = 0;
}

void addWord(char word[], int len){

    adjust(cursorPos);

    for(register int i = 0; i < len; i++){
        leftArray[leftCount++] = word[i];
    }
    leftArray[leftCount] = 0;
}

void addBackSpace(){

    adjust(cursorPos);
    leftCount--;
}

void moveCurson(int newPosition){

    cursorPos = newPosition;
}

void subString(int pos, int length, char result[]){

        adjust(cursorPos);

    int k = 0;
        int l = 0;
    while(k + pos < leftCount && k < length){
        result[k] = leftArray[pos + k];
        k++;
    }

    length -= k;
    while( l < length){
        result[k++] = rightArray[rightCount - 1 - l];
        l++;
    }
}