Я работаю над реализацией структуры данных Rope на C++ для полностью абстрактных объектов. Проблема, с которой я сталкиваюсь, заключается в том, что я не могу понять реализацию критической операции «разделить». Страница Википедии полезна, но расплывчата и весьма теоретична, а изображения, прикрепленные к тексту, не помогают мне понять алгоритм. Есть ли хорошая реализация или документ с примером кода? Я пробовал читать оригинальные статьи, но они тоже не очень помогают.
Операция разделения на структурах данных веревки
Ответы (1)
Предположим, у нас есть структура веревки, такая как
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;
}
}
person
Per
schedule
12.11.2011
Большое спасибо, это именно то, что мне было нужно.
- person lushr; 12.11.2011