使字符数组旋转其单元格 left/right n 次

Question

我在这里是全新的，但我听说过很多关于这个站点的信息，现在我已经接受了为期 7 个月的软件开发 'bootcamp' 我正在为即将到来的测试磨练我的 C 知识。

在我已经通过的测试中，我被分配了一个问题，但我没有完成那个问题，这让我很困扰。

问题是用 C 语言编写一个程序，将字符 (char) 数组的单元格向左移动 1（对我来说向哪个方向移动并不重要，但指定的问题是向左移动）。而且我还承诺在执行期间不要使用临时 array/stack 或任何其他结构来保存整个数组数据。

所以 'string' 或包含 '0' '1' '2' 'A' 'B' 'C' 的字符数组将变为 '1' '2' 'A' 'B' 'C' '0' 使用函数一次后.

写这篇文章没问题，我相信我最终得到的结果类似于：

void ArrayCharMoveLeft(char arr[], int arrsize, int times) {
    int i;
    for (i = 0; i <= arrsize ; i++) {
        ArraySwap2CellsChar(arr, i, i+1);
    }
}

如您所见，该函数有点模块化，因为它允许输入单元格需要移动或向左移动的次数。我没有实现它，但就是这个想法。

据我所知，有 3 种方法可以做到这一点：

循环 ArrayCharMoveLeft 次。这本能地感觉效率低下。
在 ArrayCharMoveLeft 中使用递归。这应该类似于第一个解决方案，但我不是 100% 确定如何实现它。
这就是我想弄清楚的方法：循环中没有循环，没有递归，没有临时数组，程序将知道如何将单元格移动 x 次到 left/right 而没有任何问题.

问题是在交换数组中的单元格 N 次后，剩余的数组大小 - 次有时没有组织。例如：

将 ArrayCharMoveLeft 与我们上面提到的给定数组一起使用 3 次将产生 ABC021 而不是 ABC012 的期望值。

我已经运行为此使用了以下函数：

int i;
char* lastcell;
if (!(times % arrsize))
{
    printf("Nothing to move!\n");
    return;
}
times = times % arrsize;
// Input checking. in case user inputs multiples of the array size, auto reduce to array size reminder
for (i = 0; i < arrsize-times; i++) {
    printf("I = %d ", i);
    PrintArray(arr, arrsize);
    ArraySwap2CellsChar(arr, i, i+times);
}

如您所见，运行s 从 0 到数组大小 - 次。如果使用此函数，例如使用包含 14 个字符的数组。然后使用 times = 5 将使运行从 0 到 9，因此单元格 10 - 14 不按顺序排列（但其余的按顺序排列）。

最糟糕的是，剩余的单元格始终保持顺序，但位置不同。意思不是 0123，它们可能是 3012 或 2301...等等

我运行不同时间值的不同数组，但没有找到特定模式，例如“如果剩余单元格 = 3，则对时间 = 1 的剩余单元格使用 ArrayCharMoveLeft”。

它似乎总是 2 个选项中的 1 个：剩余的单元格按顺序排列，或者移动了不同的值。它似乎与此类似：时间转移+方向对齐 1 0 2 0 3 0 4 1R 5 3R 6 5R 7 3R 8 1R 数字随着时间和数组的不同而变化。有人对此有想法吗？即使您在循环中使用递归或循环，我也想听听可能的解决方案。唯一的固定规则是不要使用临时数组。

提前致谢！

Answer 1

使用标准库函数 memcpy、memmove 等，因为它们针对您的平台进行了非常优化。
使用正确的尺码类型 - size_t 而不是 int

char *ArrayCharMoveLeft(char *arr, const size_t arrsize, size_t ntimes) 
{
    ntimes %= arrsize;
    if(ntimes)
    {
        char temp[ntimes];
        memcpy(temp, arr, ntimes);
        memmove(arr, arr + ntimes, arrsize - ntimes);
        memcpy(arr + arrsize - ntimes, temp, ntimes);
    }
    return arr;
}

但是你想要它没有临时数组（内存效率更高，性能非常差）：

char *ArrayCharMoveLeft(char *arr, size_t arrsize, size_t ntimes) 
{
    ntimes %= arrsize;
    while(ntimes--)
    {
        char temp = arr[0];
        memmove(arr, arr + 1, arrsize - 1);
        arr[arrsize -1] = temp;
    }
    return arr;
}

https://godbolt.org/z/od68dKTWq https://godbolt.org/z/noah9zdYY

Answer 2

如果出于学习的目的，无论效率还是简单性，你只想使用ArraySwap2CellsChar交换两个数组元素，你可以通过一些调整来保持你的循环。正如您所指出的，给定的 for (i = 0; i < arrsize-times; i++) 循环使最后的 times 元素错位。为了正确放置所有元素，循环条件必须是 i < arrsize-1（少一个就足够了，因为如果除了最后一个元素之外的每个元素都是正确的，那么最后一个元素也必须是正确的）。当然，当 i 几乎运行到 arrsize 时，i+times 不能保留为另一个交换索引；相反，必须计算要放在索引 i 处的元素的正确索引 j。由于元素已经从其原始位置交换，因此该计算有些棘手。这是您的循环的修改变体：

for (i = 0; i < arrsize-1; i++)
{
    printf("i = %d ", i);
    int j = i+times;
    while (arrsize <= j) j %= arrsize, j += (i-j+times-1)/times*times;
    printf("j = %d ", j);
    PrintArray(arr, arrsize);
    ArraySwap2CellsChar(arr, i, j);
}

Answer 3

免责声明：我不确定在这里分享完整的工作代码是否常见，因为这实际上是我在这里提出的第一个问题，所以我不会这样做，假设这个想法是在回答具体问题，并且没有提供抓取的示例解决方案（这可能会破坏学习和探索 C 的目的）。这个论点得到了这样一个事实的支持，即这个特定的任务来自编程课程使用的编程测试，其目的是过滤掉不适合参加为期 7 个月的软件开发密集培训的申请人。如果您仍然希望看到我的代码，请私信我。

因此，在@Armali 的大力帮助下，我很高兴地宣布问题已得到解答！我们一起想出了一个函数，它接受 C 中的一个字符数组（字符串），并且不使用任何以前编写的库（例如 strings.h），甚至一个临时数组，它旋转数组中的所有单元格向左N次。

示例：在 N = 5 的以下数组上使用 ArrayCharMoveLeft()：原数组：0123456789ABCDEF 更新数组：56789ABCDEF01234 如您所见，第一个单元格 (0) 现在是第六个单元格 (5)，第二个单元格是第七个单元格，依此类推。所以每个单元格都向左移动了 5 次。前 5 个单元格 'overflow' 到数组末尾，现在显示为最后 5 个单元格，同时保持它们的顺序。该函数适用于各种数组长度和 N 个值。

这不是任何成就，而是尝试用尽可能少的变量执行任务（只有 4 个整数，除了 char 数组，还包括用于交换单元格的子函数）。

它是使用嵌套循环实现的，因此绝不是高效的运行时方式，只是内存方式，同时仍然是自编码函数，没有使用外部库（stdio.h 除外）。

参考 Armali 发布的解决方案，它应该可以为您提供该问题的答案。

使字符数组旋转其单元格 left/right n 次

Making a character array rotate its cells left/right n times

c

arrays

string

char