字符串的循环移位

问题描述:

　　将一个字符串a像左旋转i个位置。例如，当n=8且i=3时(n为字符串有效长度)，向量abcdefgh旋转为defghabc。要求时间复杂度O(n)，空间复杂度为O(1)

问题求解:

      直接将前i个数组复制到一个临时数组，将余下的元素左移，再将临时数组中的i个元素复制到末尾的方法可得正确解，但空间复杂度为O(n)。每次移动一个到末尾，剩余的前移也能得正确解，但时间复杂度为O（n^2）。显然，我们需要新的想法。

     解法一：

　　　　移动a[0]到临时变量t，然后移动a[i]到a[0],a[2i]到x[i]，依次类推（将a中所有下标对n取模）,直至返回到取x[0]中的元素，此时改为从t取值然后终止过程。

　　代码如下：

　　

#include <stdio.h>
#include <string.h>

//求最大公约数
int gcd(int i,int j)
{
    while(i != j )
    {
        if(i > j)
            i = i - j;
        else
            j = j - i;
    }
    return i;
}

void turnleft(char *a,int i,int n)
{
     int left = i % n;
  
     if(left == 0)
          return ;

     int gcdnum = gcd(left,n);
     int j,k,t,m;
    
     for(j=0;j<gcdnum;j++)
     {
        t = a[j];     
         m = j;
         k = m + left;
         while(1)
        {
            k = m + left;
            if(k >= n)
                k = k - n;
            if(k == j)
                break;
            a[m] = a[k];
            m = k;
        }
        
        a[m] = t;

     }

}

int main()
{
    char a[1024];
    int i;
    printf("请输入字符串: ");
    //fgets(a,1024,stdin);//fgets会将结尾的回车换行符也记录下
    scanf("%s",a);
    printf("请输入左移位数：");
    scanf("%d",&i);
    int n = strlen(a);
    turnleft(a,i,n);
    printf("%s\n",a);

}

 

 解法二：

　　　解法一满足了我们的要求，但看起来仍然没那么直观，有没有更清晰移动的方法呢？ 答案就是有。

　　   首先将字符串a分为两段,要移动的前i位为b，剩余部分为c，则字符串可表示为bc，左移i位的结果其实就是cb，则算法的目的就是将bc转换为cb。首先将b逆序为b'，再将c逆序为c'，最后将(b'c')'整体逆序即得到cb。 

　　  代码如下：

 

#include <stdio.h>
#include <string.h>

//将a中从start到end翻转
void reverse(char *a,int start, int end)
{
    int i ,j,temp;
    for(i = start,j = end; i < j; i++,j--)
    {
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    
}


//a为原数据，i为要左翼的位数，n为总长度
void turnleft(char *a,int i,int n)
{
    int left = i % n;

    if(left == 0)
        return ;

    reverse(a,0,left-1);
    reverse(a,left,n-1);
    reverse(a,0,n-1);
    return ;

}

int main()
{
    char a[1024];
    int i;
    printf("请输入字符串: ");
    //fgets(a,1024,stdin);//fgets会将结尾的回车换行符也记录下
    scanf("%s",a);
    printf("请输入左移位数：");
    scanf("%d",&i);
    int n = strlen(a);
    turnleft(a,i,n);
    printf("%s\n",a);
}

 

      以上两种算法均可以在O(n),O(1)内完成字符串的循环移位。也许有看观会问，这里说的都是循环左移，那循环又移怎么办呢？ 呵，事实上，循环左移和循环右移本质上是一模一样的，循环右移i位其实就是循环左移n-i位而已。