Операция разделения на структурах данных веревки - PullRequest
Новая
       28

Операция разделения на структурах данных веревки

3 голосов
/ 12 ноября 2011

Я работаю над реализацией структуры данных Rope в C ++ для полностью абстрактных объектов. Проблема, с которой я сталкиваюсь, заключается в том, что я не могу понять реализацию критической операции «split». Страница Википедии полезна, но расплывчата и очень теоретична, а изображения, прикрепленные к тексту, не помогают мне понять алгоритм. Есть ли хорошая реализация или документ, содержащий пример кода? Я пробовал читать оригинальные статьи, но они тоже не очень помогают.

1 Ответ

4 голосов
/ 12 ноября 2011

Предположим, у нас есть структура веревки, как 

struct Rope {
    Rope *left;
    union {
        Rope *right;
        const char *string;
    };
    size_t length;
};

Если left равно нулю, то символы string[0], ..., string[length - 1]. В противном случае, символы - это left, за которыми следуют символы right. Оставляя в стороне вопросы управления хранилищем, операция подстроки составляет 

Rope *substring(const Rope *r, size_t start, size_t length) {
    if (!r->left) {
        Rope *s = new Rope;
        s->left = 0;
        s->string = r->string + start;
        s->length = length;
        return s;
    } else if (start + length <= r->left->length) {
        return substring(r->left, start, length);
    } else if (r->left->length <= start) {
        return substring(r->right, start - r->left->length, length - r->left->length);
    } else {
        Rope *s = new Rope;
        s->left = substring(r->left, start, r->left->length - start);
        s->right = substring(r->right, 0, length - (r->left->length - start));
        s->length = length;
        return s;
    }
}
...