我正在实现几个数据结构，我想要使用的一个原语如下：我有一个内存块 A[N] （它的长度可变，但我在示例中使用 100），在这个块内，有一个较小的部分C 长度为 K（假设为 30），我想在不使用任何额外内存的情况下移动它。
额外的困难是，A“换行”，即C可以从A[80]开始，然后C的前20个元素是元素A[80..100]，最后10个元素是元素A[ 0..10]。此外，目标范围还可以以任何可能的方式“环绕”并与C重叠。此外，我不想使用超过恒定量的额外内存，一切都应该就位。另外，A 中既不在目标范围内也不在源范围内的部分可能包含重要的内容，因此也不能使用。因此，一种情况如下：
A 看起来像这样：
|456789ABCDEF0123456789AB|-----|0123|
并且应该改成这样：
|89AB|-----|0123456789ABCDEF01234567|
仅仅将其委托给库或使用库中的另一个数据结构在这里不是一个选择，我想自己理解这个问题。乍一看，我认为这可能不是什么小事，但只要你区分几个案例，就清楚了，但现在我遇到了严重的麻烦。当然，如果它们不重叠或不环绕，也会有一些微不足道的情况，但至少如果两者同时发生，就会变得混乱。您可以从一个空闲位置开始，然后移动属于该位置的部件，但是随后您在其他地方创建另一个空闲部件，并且很难跟踪您仍然可以使用哪些部件。
也许我完全遗漏了一些东西，但即使是我的特殊情况，如果目标范围没有换行，也有近 100 行（不过其中一半是断言和注释），我可以更新它，以便它还可以通过一些额外的处理处理一般情况索引计算，但如果有人有一个优雅而简短的解决方案，我将不胜感激。直觉上我认为这应该是微不足道的，但我只是还没有看到最好的解决方案。
注意：有趣的情况当然是，如果 C 几乎与 A 一样大。如果 |C|
编辑：使用超过恒定数量的附加标志/索引算作附加内存，如果可能的话我想避免这种情况。
编辑：有些人想看看我的代码。我的问题相当抽象，所以我不想发布它，但也许有人看到如何改进它。这很糟糕，它只适用于目标从头开始（但是，很容易改变）并且非常长的情况，但它在 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;
}
