用于移动不起作用的数组元素的函数

Question

我有一个以null结尾的字符数组。也称为c字符串。我写了一个函数，它会将每个索引处的元素向左移动，<----通过给定数量的索引。例如，当将"hello-world"的char数组传递给shiftBy值为3的函数时，它应该将char数组转换为："lo worldhel"。

目前，此函数适用于<=11个元素。任何超过这一点的东西和阵列中的最后三个点都不会移动。请记住，最后一个索引包含null终止符！

这是一个棘手的问题，我已经被困了好几个小时了。我也不能使用任何标准的函数或向量，我只能使用这些不推荐使用的数组和简单的循环。所以，请不要用"为什么不使用空白功能"。。。。因为相信我，如果可以的话，我就不会在这里了。

这是代码，位于：

    void shiftLeft (char szString[], int size, int shiftBy)
{
    if(shiftBy > size){
        shiftBy = shiftBy - size;
    }
    if(size == 1){
        //do nothing, do nothing, exit function with no change made to myarray
    }
    else{
        char temp;
        //for loop to print the array with indexes moved up (to the left) <-- by 2
        for (int i = 0; i <= size-shiftBy; i++)//size = 11
        {//EXAMPLE shift by 3  for a c-string of `hello world`
            if(i < size-shiftBy){
                temp = szString[shiftBy + i];//temp = h
                szString[shiftBy + i] = szString[i];//d becomes l
                szString[i] = temp;//h becomes l
            }
            else{//it will run once while i=8
                temp = szString[i];//temp = l
                szString[i] = szString[i+1];//8th element becomes h
                szString[i+1] = szString[size-1];//9th element becomes e
                szString[size-1] = temp;//last element becomes l
            }
        }
    }
}

Answer 1

如果您试图实现的唯一目的是将终止字符串中的字符向左移动并旋转（根据您的"helloworld"样本在3次移动后产生"loworldhel"来判断，情况似乎就是这样），那么您会使比需要的更难

在没有临时空间要求的O（N）时间内这样做的传统算法是从序列开始反转移位的左侧，然后反转整个序列，然后反转移位的右侧，所有。例如，假设我们想左移以下字符串3个插槽：

1234567890

首先，反转第一个移位按时隙

1234567890
^-^
3214567890

第二，反转整个序列

3214567890
^--------^
0987654123

最后，反转（length shiftBy）时隙：

0987654123
^-----^
4567890123

使用标准库会使变得微不足道，但显然您是教授，认为。。。作弊。在不使用任何库api的情况下，上述算法都不是很难：

#include <iostream>
void shiftLeft(char sz[], size_t shiftBy)
{
    const char *p = sz;
    while (*p) ++p;
    std::size_t len = p - sz;
    if (len > 1 && (shiftBy %= len))
    {
        char *ends[] = { sz+shiftBy, sz+len, sz+(len - shiftBy) };
        for (std::size_t i=0; i<3; ++i)
        {
            char *start = sz, *end = ends[i];
            while (start < --end)
            {
                char ch = *start;
                *start++ = *end;
                *end = ch;
            }
        }
    }
}
int main()
{
    char sz[] = "1234567890";
    std::cout << sz << 'n';
    shiftLeft(sz, 11);
    std::cout << sz << 'n';
    shiftLeft(sz, 4);
    std::cout << sz << 'n';
    shiftLeft(sz, 1);
    std::cout << sz << 'n';
    shiftLeft(sz, 20);
    std::cout << sz << 'n';
}

输出

1234567890
2345678901
6789012345
7890123456
7890123456

如果你真的打算在临时空间里做这件事，那就顺其自然吧，但我不可能理解你为什么会这么做

祝你好运。

Answer 2

来自azillionmonkeys.com/qed/case8.html

void shiftLeft(char szString[], int size, int shiftBy) {
            int c, tmp, v;
            if (size <= 0) return;
            if (shiftBy < 0 || shiftBy >= size) {
                shiftBy %= size;
                if (shiftBy < 0) shiftBy += size;
            }
            if (shiftBy == 0) return;
            c = 0;
            for (v = 0; c < size; v++) {
                int t = v, tp = v + shiftBy;
                char tmp = szString[v];
                c++;
                while (tp != v) {
                    szString[t] = szString[tp];
                    t = tp;
                    tp += shiftBy;
                    if (tp >= size) tp -= size;
                    c++;
                }
                szString[t] = tmp;
            }
        }