数组循环移位

时间：2010-11-08 来源：guocai_yao

「方法1」利用memcpy函数，需开辟临时空间。先把从a+n-k到a+n-1这k个字符，存到tmp中；然后，把以a开始的地址空间中的字符复制到a+k开始的地址空间中去；最后，把tmp的k个字符放回以a开始的地址空间中去。

...

a+n-k-1

a+n-k

...

a+n-1

void loopRightShiftV2(char a[], int n, int k)
{
    char *tmp = (char *)malloc(sizeof(char)*k);

    k %= n;
    memcpy(tmp, a+n-k, k);
    memcpy(a+k, a, n-k);
    memcpy(a, tmp, k);
}

「方法2」先看循环右移一个字符的思路：首先，保存最有一个非'\0'字符；然后将字符数组从最后一个非'\0'字符开始，依次后移；最后将已保存的最后一个字符放到第一字符所在位置处。循环右移k个字符，只需将上述过程重复k次即可。

void loopRightShift(char a[], int n, int k)
{
    int tmp;
    int i;

    k %= n;
    while(k--){
        tmp = a[n-1];
        for(i = n-1; i >0; i--){
            a[i] = a[i-1];
        }
        a[0] = tmp;
    }
}

「方法3」初始状态

...

cn-k-1

cn-k

cn-k+1

cn-k+2

...

cn-1

逆序一次后 |

cn-k

cn-k-1

...

cn-1

...

cn-k+2

cn-k+1

再整体逆序，循环右移完成。

cn-k+1

cn-k+2

...

cn-1

...

cn-k-1

cn-k

/* 不用临时变量交换a[begin]和a[end]两内存单元的内容 */
void stringReverse(char a[], int begin, int end)
{
    for(; begin < end; begin++, end--){
        a[begin] ^= a[end];
        a[end] ^= a[begin];
        a[begin] ^= a[end];
    }
}

void loopRightShift(char a[], int n, int k)
{
    k %= n;

    stringReverse(a, 0, n-k-1); /* 先对a[0...n-k-1]这(n-k)个字符逆序 */
    stringReverse(a, n-k, n-1); /* 再对a[n-k...n-1]这k个字符逆序 */
    stringReverse(a, 0, n-1);   /* 最后对整个字符串逆序 */
}

参考文章： 1. http://www.cppblog.com/yuanyuelang/archive/2009/09/12/96023.aspx