首页 > 代码库 > 杂题之循环移动字符串

杂题之循环移动字符串

1.问题:一个m个字符的字符串,‘循环’ 向左或向右移动n(n <= m)位,求移动后的字符串。例如abcdefg 左循环移动3位 -> defgabc, 又循环移动三位 -> efgabcd.

2.实现方法很多,最直接但是效率很低的方法是挨个移动字符元素,类似移动数组。这里介绍一个技巧来实现, 以循环左移n位为例

  1).首先翻转前n位,此时你可以伸出右手,手心对着你自己,假设此时从无名指到大拇指标号为1,2,3,4,5;然后翻转你的右手,让手心对外,则此时为5,4,3,2,1。翻转前n位字符串的过程与此类似。

    那么程序中这个过程如何实现呢,很简单,就是第一位和最后以为对换,第二位和倒数第二位对换,依次类推,实现代码如下:

static void
swap(char &a, char &b)
{
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
}

static void 
move(char *str, int head, int tail)
{
    if (str == NULL || strlen(str) < 2)
    {
        return;
    }

    for (; head < tail; head++, tail--)
    {
        swap(*(str + head), *(str + tail));
    }
}

  2).将n+1到m位翻转,过程与上边类似。当然这两个翻转执行顺序没有先后的区别。

  3).将字符串整体翻转后,便得到循环左移后的字符串。

  循环右移的过程于此类似。

3.下面贴出可以选择循环左移和右移的代码(move.c),读者可以参考这理解:

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

static void
swap(char &a, char &b)
{
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
}

static void 
move(char *str, int head, int tail)
{
    if (str == NULL || strlen(str) < 2)
    {
        return;
    }

    for (; head < tail; head++, tail--)
    {
        swap(*(str + head), *(str + tail));
    }
}

int
main(int argc, char *argv[])
{
    char str[100] = { 0 };
    int movenum;
    char direc;

    while(1)
    {
        printf("Enter a string And move direction(L or R) And a move num\n");
        if (scanf("%s %c %d", str, &direc, &movenum) == 3)
        {
            if (movenum < 0 || movenum > strlen(str))
            {
                printf("error\n");
                continue;
            }

            printf("Before Move: %s \n", str);

            if (R == direc)
            {
                //the sequence of two move op can be changed
                move(str, strlen(str) - movenum, strlen(str) - 1);
                move(str, 0, strlen(str) - movenum - 1);
            }
            else if (L == direc)
            {
                //the sequence of two move op can be changed
                move(str, 0, movenum - 1);
                move(str, movenum, strlen(str) - 1);
            }
            else
            {
                continue;
            }
            move(str, 0, strlen(str) - 1);    
            
            printf("After  Move: %s \n", str);    
        }
        else
        {
            break;
        }
    }

    return 0;
}

  编译命令: g++ -g -o move move.c;,运行: ./move

  部分运行结果:

  技术分享

  当让只是简单的示例程序,如果代码出错,欢迎指正, 同时若有更好的方法,希望不吝赐教。

  

杂题之循环移动字符串