【题目】有一个整数数组，现要求实现这个整数数组的循环右移。如：1，2，3，4，5 则循
环右移两位后结果是：4，5，1，2，3。
方法一：(最最容易想到的办法)
void RightCircleShift_00(int buffer[],int shift)
{
int i,j,tt;
for(i=0;i
{
tt = buffer[ARRSIZE-1];
for(j=ARRSIZE-1;j>0;j--)
buffer[j] = buffer[j-1];
buffer[0] = tt;
}
}
这个办法是用两个循环来控制，内循环每次向右移动一位，外循环则用来限制移动的位数。
算法需要执行 ARRSIZE * ShiftValue次，时间复杂度是O( N2 )。
方法二：(由方法一得到的递归程序)
void RightCircleShift_01(int buffer[],int shift)
{
int *p,tt;
tt = *(buffer+ARRSIZE-1);
for(p = buffer+ARRSIZE-1;p > buffer;p--)
*p = *(p-1);
*buffer = tt;
shift--;
if(shift > 0)
RightCircleShift_00(buffer,shift);
}
这个程序跟方法一类似，区别就是它是用递归来实现的。同样需要执行ARRSIZE *
ShiftValue次，时间复杂度也是O( N2 )。
方法三：
void RightCircleShift_02(int buffer[],int shift)
{
int *title,*r,*p;
if(shift == 0)
return;
shift = shift % ARRSIZE;
title = (int *)malloc(sizeof(int)*shift);
if( title == NULL )
return;
r = buffer + (ARRSIZE - shift);
memcpy(title, r, shift * sizeof(int));
p = buffer + shift;
memmove(p, buffer, (ARRSIZE - shift) * sizeof(int));
memcpy(buffer, title, shift * sizeof(int));
free(title);
}
这个算法需要移动位数大小的临时辅助空间。如需移动两位，则申请两个的空间，然后把从
右边起的两个元素拷贝的临时辅助空间，然后前面的元素向后移动两位，最后再把临时空间
里面的两个元素拷贝到前面的两位即可完成循环右移。需要执行 ARRSIZE次，时间复杂度是
O( N )。
方法四：从内存模型上出发。
#include
#include
#include
void Rotate(int* beg, int* newBeg, int* end)
{
int numElems = end - newBeg;
int* temp = (int*)malloc(sizeof(int)*(end - newBeg));
memcpy(temp, newBeg, (end - newBeg)*sizeof(int));
memmove(beg + numElems, beg, (newBeg - beg)*sizeof(int));
memcpy(beg, temp, (end - newBeg)*sizeof(int));
free(temp);
}
int main()
{
int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
for(int i = 0; i < 10; ++i)
{
Rotate(a, a + 1, a + 10);
for(int j = 0; j < 10; ++j)
printf("%d ", a[j]);
printf("\n");
}
}
方法五：先把N个字符逆序，再把前M个字符逆序，最后再把这N － M个字符逆序，即得到最
终结果。
代码实现如下：
/******************************************************************
* Copyright (c) 2005-2007 CUG-CS
* All rights reserved
*
* 文件名称：StringShift.c
* 简要描述：字符串循环左移
*
* 当前版本：1.0
* 作 者：raincatss
* 完成日期：2007-11-18
* 开发环境：Windows XP Sp2 + VC6.0
* 个人博客：http://raincatss.cublog.cn/
******************************************************************/
#include
#include
static void Swap(char *p, char *q);
static void Reverse(char *str, int i, int n);
void String_Shift_Reverse(char *str, int n)
{
int len;
assert(NULL != str);
len = strlen(str);
if (n = len) {
return;
}
Reverse(str, 0, n - 1);
Reverse(str, n, len - 1);
Reverse(str, 0, len - 1);
}
static void Swap(char *p, char *q)
{
char tmp;
tmp = *p;
*p = *q;
*q = tmp;
}
static void Reverse(char *str, int i, int n)
{
int l, r;
for (l = i, r = n; l < r; l++, r--) {
Swap(&str[l], &str[r]);
}
}
#include
#include
using namespace std;
int main()
{
int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
rotate(a, a + 10 - 4, a + 10);
for(int i = 0; i < 10; ++i)
cout
move(ptr,n,m-1);
move(ptr,n,1);
return;
}
int pos=0;
int i=0;
while(++i
{
pos=(pos+m)%n;
int tmp=*ptr;
*ptr=*(ptr+pos);
*(ptr+pos)=tmp;
}
}
void main()
{
int a[]={1,2,3,4,5,6,7,8,9,10};
move(a,10,7);
for(int i=0;i
move(ptr,n,m-1);
move(ptr,n,1);
return;
}
int pos=0;
int i=0;
while(++i
{
pos=(pos+m)%n;
*ptr^=*(ptr+pos);
*(ptr+pos)^=*ptr;
*ptr^=*(ptr+pos);
}
}
再优化：
void move(int * ptr, int n, int m)
{
if(m
pos=(pos+m)%n;
*ptr^=*(ptr+pos)^=*ptr^=*(ptr+pos);
}
}
再用逗号表达式优化：
void move(int * ptr, int n, int m)
{
if(m
if(m
int i, j, len;
char tmp;
assert(NULL != str);
len = strlen(str);
if (n = len) {
return;
}
for (i = 0; i < gcd(len, n); i++) {
j = i;
tmp = str[j];
do {
str[j] = str[(j + n) % len];
j = (j + n) % len;
} while (j != i);
str[(j + len - n) % len] = tmp;
}
}
static int gcd(int m, int n)
{
int tmp;
while (n != 0) {
tmp = m % n;
m = n;
n = tmp;
}
return m;
}
在do{}while()循环中，如果k每次加n后不与len取模，可以发现k - i最后等于M、N的最小公倍数，这样保证在循环过程中无重复下标(为什么？请自己想一下)。之所以让for()循环做gcd(M, N)次，是因为每次do{}while()循环做M * N / (N * gcd(M, N)) = M / gcd(M, N)次，for()循环做gcd(M, N)次正好可以保证移动M次，即所有元素移动一次。(如果谁有此法的精确且清楚的数学证明，请发Email:raincatss#gmail.com)
方案二
把原字符串分成三部分ABlBr(Br与A长度相同)，循环左移后为BlBrA。可以先把A与Br互换位置，变为BrBlA，然后再把Br与Bl互换，由此可以递归求解。
递归实现代码如下：
/******************************************************************
* Copyright (c) 2005-2007 CUG-CS
* All rights reserved
*
* 文件名称：StringShift.c
* 简要描述：字符串循环左移
*
* 当前版本：1.0
* 作 者：raincatss
* 完成日期：2007-11-18
* 开发环境：Windows XP Sp2 + VC6.0
* 个人博客：http://raincatss.cublog.cn/
******************************************************************/
#include
#include
static void Swap(char *p, char *q);
void StringShift(char *str, int len, int n)
{
int i;
assert(NULL != str);
if (len
for (i=0; i
Swap(&str[i], &str[len - n + i]);
}
StringShift(str, len - n, n);
} else if (n > len - n) {
for (i=len-1; i>n-1; i--) {
Swap(&str[i], &str[i - n]);
}
StringShift(str + len - n, n, n + n - len);
} else {
for (i=0; i
Swap(&str[i], &str[n + i]);
}
}
}
static void Swap(char *p, char *q)
{
char tmp = *p;
*p = *q;
*q = tmp;
}
为提高效率，可以把递归转换为迭代，实现代码如下：
/******************************************************************
* Copyright (c) 2005-2007 CUG-CS
* All rights reserved
*
* 文件名称：StringShift.c
* 简要描述：字符串循环左移
*
* 当前版本：1.0
* 作 者：raincatss
* 完成日期：2007-11-18
* 开发环境：Windows XP Sp2 + VC6.0
* 个人博客：http://raincatss.cublog.cn/
******************************************************************/
#include
#include
static void Swap(char *p, char *q);
void StringShift(char *str, int len, int n)
{
int i, tmp;
char *s = str;
assert(NULL != str);
if (len
if (n < len - n) {
for (i=0; i
Swap(&s[i], &s[len - n + i]);
}
len -=n;
} else {
for (i=len-1; i>n-1; i--) {
Swap(&s[i], &s[i - n]);
}
s += len - n;
tmp = n;
n = n + n - len;
len = tmp;
}
}
for (i=0; i
Swap(&s[i], &s[n + i]);
}
}
static void Swap(char *p, char *q)
{
char tmp = *p;
*p = *q;
*q = tmp;
}