我正在实现几个数据结构，我想使用的一个原语如下：我有一个内存块 A[N]（它有一个可变长度，但我的例子是 100），在这个块内，有一个较小的部分我想在不使用任何额外内存的情况下移动长度为 K（比如说 30）的 C。
额外的困难是，A“换行”，即 C 可以从 A[80] 开始，然后 C 的前 20 个元素是元素 A[80..100]，最后 10 个元素是元素 A[ 0..10]。此外，目标范围也可以以任何可能的方式与C“环绕”和重叠。此外，我不想使用超过恒定数量的额外内存，一切都应该发生。此外，A 中既不在目标范围内也不在源范围内的部分可能包含一些重要的东西，因此也不能使用它。因此，一种情况如下：
A 看起来像这样：
|456789ABCDEF0123456789AB|-----|0123|
并且应该转化为：
|89AB|-----|0123456789ABCDEF01234567|
只是将它委托给一个库或使用库中的另一个数据结构不是一个选择，我想自己理解这个问题。乍一看，我认为这可能不是一件小事，但只要你区分几个案例，就清楚了，但现在我遇到了严重的麻烦。当然，如果它们不重叠或不换行，也有一些微不足道的情况，但至少如果两者同时发生，它就会变得混乱。您可以从一个空闲位置开始并移动属于该位置的部分，但随后您在其他位置创建另一个空闲部分，并且很难跟踪您仍然可以使用哪些部分。
也许我完全遗漏了一些东西，但即使是我的特殊情况，如果目标范围没有换行，也有近 100 行（其中一半是断言和注释），我可以更新它，以便它也可以处理一般情况，并添加一些额外的索引计算，但如果有人有一个优雅而简短的解决方案，我将不胜感激。直觉上我认为这应该是微不足道的，但我还没有看到最好的解决方案。
注意：有趣的情况当然是，如果 C 几乎和 A 一样大。如果 |C| < N/2，这是微不足道的。
编辑：使用超过恒定数量的附加标志/索引算作附加内存，如果可能的话，我想避免这种情况。
编辑：有些人想看我的代码。我的问题相当抽象，所以我不想发布它，但也许有人看到如何改进它。这很糟糕，它只适用于目标从头开始（但是，可以很容易地改变）并且非常长的情况，但是它在 O(n) 中没有额外内存的情况下完成了这项工作。
#include <stddef.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
void move_part(int* A, size_t N, size_t target, size_t source, size_t size, int show_steps)
{
assert(source + size <= N);
assert(target + size <= N);
if (show_steps) {
printf("Moving size %d from %d to %d.\n", size, source, target);
}
memmove(A + target, A + source, size * sizeof(int));
}
void swap_parts(int* A, size_t N, size_t first_begin, size_t second_begin, size_t size, int show_steps)
{
if (show_steps) {
printf("Swapping size %d at %d and %d.\n", size, first_begin, second_begin);
}
assert(first_begin + size <= N);
assert(second_begin + size <= N);
size_t i;
for (i = 0; i < size; ++i) {
int x = A[first_begin + i];
A[first_begin + i] = A[second_begin + i];
A[second_begin + i] = x;
}
}
void move_to_beginning(int* A, size_t N, size_t begin, size_t size, int show_steps)
{
assert(begin <= N);
assert(size <= N);
// Denotes the start of our "working range". Increases during
// the algorithm and becomes N
size_t part_start = 0;
// Note: Keeping the size is crucial since begin == end could
// mean that the range is empty or full.
size_t end = (begin + size) % N;
while (part_start != N) {
size_t i;
if (show_steps) {
for (i = 0; i < N; ++i) {
printf("%d ", A[i]);
}
printf("\n");
printf("part_start %d begin %d end %d size %d\n", part_start, begin, end, size);
}
// loop invariants
assert(part_start < N);
// The two pointers are in our range
assert(part_start <= begin && begin <= N);
assert(part_start <= end && end <= N);
// size is valid (wrapped case, non-empty, non-full case)
assert(begin <= end || (N - begin) + (end - part_start) == size);
// size is valid (non wrapped case, non-empty, non-full case)
assert(begin >= end || end - begin == size);
// size is valid (working range is full or empty case)
assert(begin != end || size == 0 || part_start + size == N);
if (size == 0 || begin == N || begin == part_start) {
// ##|1234|# -> 1234### ||
if (show_steps) {
printf("Case 1:\nTerminating\n");
}
// #||# -> ## ||
// 12|##| -> 12## ||
// |12|## -> 12## ||
break;
/* Not necessary any more, but would be the correct transformation:
part_start = N;
begin = N;
end = N;
size = 0;*/
} else if (end == part_start) {
// |##|123 -> ##|123|
if (show_steps) {
printf("Case 2:\n");
printf("Setting end to %d.\n", N);
}
end = N;
} else if (begin < end) {
// ##|1234|# -> 1234### ||
if (show_steps) {
printf("Case 3:\n");
}
move_part(A, N, part_start, begin, size, show_steps);
break;
/* Not necessary any more, but would be the correct transformation:
part_start = N;
begin = N;
end = N;
size = 0;*/
} else {
size_t end_size = end - part_start;
size_t begin_size = N - begin;
assert(begin_size + end_size == size);
if (end_size >= begin_size) {
// 345|#|12 -> 12 5|#|34
if (show_steps) {
printf("Case 4:\n");
}
swap_parts(A, N, part_start, begin, begin_size, show_steps);
assert(begin_size > 0); // Necessary for progress
part_start += begin_size;
size = end_size;
// begin, end remain unchanged
} else if (begin - part_start <= begin_size) {
// 56|#|1234 -> 123 56|#|4
size_t size_moved = begin - part_start;
assert(size_moved >= end_size); // else the next step would be more efficient
if (show_steps) {
printf("Case 5\n");
}
swap_parts(A, N, part_start, begin, end_size, show_steps);
move_part(A, N, end, begin + end_size, begin - end, show_steps);
assert(end_size + (begin - end) == size_moved);
size -= size_moved;
part_start = begin;
begin += size_moved;
end += size_moved;
} else if (end_size <= begin_size) {
// 45|##|123 -> 123 #|45|#
if (show_steps) {
printf("Case 6\n");
}
swap_parts(A, N, part_start, begin, end_size, show_steps);
move_part(A, N, end, begin + end_size, begin_size - end_size, show_steps);
part_start += begin_size;
size = end_size;
end = begin + end_size;
// begin remains unchanged
} else {
// No case applies, this should never happen
assert(0);
}
}
}
}
int main()
{
int N = 20;
int A[20];
size_t size = 17;
size_t begin = 15;
size_t i;
for (i = 0; i < size; ++i) {
A[(begin + i) % N] = i;
}
move_to_beginning(A, N, begin, size, 0);
for (i = 0; i < size; ++i) {
printf("%d ", A[i]);
}
printf("\n");
return 0;
}