字符串循环左转算法实现

把一串字符串“abcdefg”循环左转3个字符，即“defgabc”。

 

一种比较笨的方法是用一个辅助数组保存要旋转的子字符串（比如上例中的“abc”），然后把“defg”在原数组前移3个位置，再把“abc”从辅助数组复制回来。不过这样空间使用为n（n为字符串中字符的多少）。

 

编程珠玑里提到一个方法，只需要一个辅助的变量就可以实现。比如处理a时，先把a赋给辅助变量tmp，d移到a原来的位置，接着g移到d原来的位置，最后tmp（值为a）移动g原来的位置。其它的同理。算法实现如下：

 

/////////////////////////////////////////////////////////////////////////

#include

 

using namespace std;

 

void Rotate(char *array, const int i, const int n);
void Swap(char &a, char &b);

 

int main()
{
 int n = 9, i = 4, j = 0;     // n为字符串字符的个数，i为左转的个数
 char a[9] = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i' };

 cout << "旋转前：";
 
 for (j = 0; j < n; ++j)
  cout << a[j] << "  ";
 
 cout << endl;

 Rotate(a, i, n);
 cout << "旋转后：";
 
 for (j = 0; j < n; ++j)
  cout << a[j] << "  ";

 cout << endl;
 
 return 0;
}

 

void Rotate(char *array, const int i, const int n)
{
 char tmp, index;
 int j, k;

 for (j = 0; j < i; ++j)
 {
  tmp = array[j];

  for (k = 0; (index = j + (k + 1) * i) < n; ++k)
   array[index-i] = array[index];
  
  array[index-i] = tmp;
 }
}

 

void Swap(char &a, char &b)
{
 char tmp = a;
 a = b;
 b = tmp;
}