左旋字符串的三种算法

一时失言乱红尘 2022-06-06 13:20 244阅读 0赞

abcd1234 左旋4个字符 —–> 1234abcd

方法一：循环移动

这里先把’a’右移7个单位，得到bcd1234a，然后再把’b’右移7个单位>>得到cd1234ab。按这个步骤循环四次后得到1234abcd。

代码如下：

void left_rotate(char *str, int len, int k)
    {
        if (str ！= NULL && len > 0)
        {
            k %=len;//去除无效的左旋次数
            int step = len - k; //移动的步数
            while (k)
            {
                {            //一个字符完整的移动过程
                    int i = 0;
                    char tem = str[k - 1 + i];
                    for (i = 0; i < step; i++)
                    {
                        str[k - 1 + i] = str[k + i];
                    }
                    str[k - 1 + i] = tem;
                }
    
                k--; //开始移动另一个字符
            }
        }
    
        else
        {
            return;
        }
    }

方法二：逆序（推荐使用）

要把abcd1234左旋4个字符变成1234abcd，这里分三步  
①把abcd逆序 —–> dcba  
②把1234逆序 —-> 4321  
③此时字符串变成dcba4321，然后把整个字符串逆序—> 1234abcd  
代码如下：

void reverse(char *start, char *end)  //左旋——逆序法
    {
        if (start != NULL && end != NULL)
        {
            while (start < end)
            {
                *start ^= *end;
                *end ^= *start;
                *start ^= *end;
                start++;
                end--;
            }
    
        }
    
        else
        {
            return;
        }
    
    }
    
    void left_rotate(char *str, int len, int k)
    {
        if (str != NULL && len > 0)
        {
            k %= len;
            reverse(str + 0, str + k - 1);  //步骤①
            reverse(str + k, str + len - 1);//步骤②
            reverse(str, str + len - 1);    //步骤③
        }
        else
        {
            return;
        }
    }

方法三：双倍字符串——穷举法（用空间换取时间）

①创建一个空间，里面存”abcd1234abcd1234”  
②把这个字符串从第5个字符’1’到第12个字符’d’依次拷贝到原字符串数组里。  
代码如下：

void left_rotate(char *str, int len, int k)
    {
        if (str != NULL && len > 0)
        {
            k %= len;
            char *mem = (char *)malloc(2 * len + 1);
            strcpy(mem, str);
            strcat(mem, str);
            strncpy(str, mem + k, len);
        }
        else
        {
            return;
        }
    }

![这里写图片描述][SouthEast]

转自：[http://blog.csdn.net/Tianzez/article/details/78416768][http_blog.csdn.net_Tianzez_article_details_78416768]

[SouthEast]: /images/20220606/5ca264a89f8d4799b180015edcbcd683.png
[http_blog.csdn.net_Tianzez_article_details_78416768]: http://blog.csdn.net/Tianzez/article/details/78416768