第27章字符串的循环移位

课程目录第27章字符串的循环移位

第27章字符串的循环移位：左移、右移的实现

字符串的循环移位，说白了就是把字符串当成一个环，往左或者往右转几格。比如"abcde"左移2位变成"cdeab"，右移2位变成"deabc"。这玩意儿在密码学、数据加密、文本处理里经常碰到。我当年做嵌入式通信协议解析时，就遇到过需要循环移位来对齐数据帧的场景——嗯，那时候踩了不少坑。

27.1 什么是循环移位？

先明确概念。给定一个字符串 s 和一个整数 k，循环左移 k 位，就是把前 k 个字符挪到末尾；循环右移 k 位，就是把后 k 个字符挪到开头。

举个例子：

s = "abcdefg"，k = 3
左移3位：前3个"abc"移到末尾 → "defgabc"
右移3位：后3个"efg"移到开头 → "efgabcd"

你可能会问：左移和右移有关系吗？当然有。左移 k 位等价于右移 n - k 位（n是字符串长度）。这个对称性很重要，后面写代码时能省不少事。

核心公式：

左移 k 位 = 右移 (n - k % n) 位

右移 k 位 = 左移 (n - k % n) 位

27.2 三种实现方法

实现循环移位，我见过不下五种写法。但最实用的就三种：暴力法、三次反转法、以及用库函数拼接法。咱们一个一个聊。

27.2.1 方法一：暴力法（直接移动）

最直观的思路：每次移动一位，循环 k 次。左移一位就是把第一个字符存起来，剩下的往前挪，最后把存起来的字符放到末尾。右移同理。

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

// 循环左移一位
void left_shift_one(char *s, int n) {
    char temp = s[0];
    for (int i = 0; i < n - 1; i++) {
        s[i] = s[i + 1];
    }
    s[n - 1] = temp;
}

// 循环左移 k 位（暴力法）
void left_rotate_brute(char *s, int k) {
    int n = strlen(s);
    if (n == 0) return;
    k = k % n;  // 取模，避免多余移动
    for (int i = 0; i < k; i++) {
        left_shift_one(s, n);
    }
}

int main() {
    char s[] = "abcdefg";
    left_rotate_brute(s, 3);
    printf("%s\n", s);  // 输出: defgabc
    return 0;
}

这个方法时间复杂度 O(n*k)，空间复杂度 O(1)。k 很大的时候效率很低。我记得有一次在嵌入式设备上处理几百字节的缓冲区，k 值接近 n，结果循环了 n 次，每次移动 n 个字节——那叫一个慢。后来果断换了方法。

避坑指南： 我曾经犯过一个低级错误——没对 k 取模。如果 k 大于 n，就会多移动很多次，甚至数组越界。记住：k = k % n 是必须的。

27.2.2 方法二：三次反转法（最优解）

这个方法是我最喜欢的。它利用了反转操作的特性，时间复杂度 O(n)，空间复杂度 O(1)。

原理很简单：

反转整个字符串
反转前 k 个字符
反转后 n-k 个字符

左移 k 位的步骤：

原串: "abcdefg", k=3
反转整个: "gfedcba"
反转前3个: "efgdcba"
反转后4个: "efgabcd" → 得到左移3位结果

右移 k 位呢？其实一样，只是反转的边界不同。或者直接用左移 n-k 位代替。

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

// 反转区间 [start, end]
void reverse(char *s, int start, int end) {
    while (start < end) {
        char temp = s[start];
        s[start] = s[end];
        s[end] = temp;
        start++;
        end--;
    }
}

// 循环左移 k 位（三次反转法）
void left_rotate(char *s, int k) {
    int n = strlen(s);
    if (n == 0) return;
    k = k % n;
    if (k == 0) return;  // 不需要移动

    reverse(s, 0, n - 1);      // 反转整个字符串
    reverse(s, 0, n - k - 1);  // 反转前 n-k 个
    reverse(s, n - k, n - 1);  // 反转后 k 个
}

// 循环右移 k 位（三次反转法）
void right_rotate(char *s, int k) {
    int n = strlen(s);
    if (n == 0) return;
    k = k % n;
    if (k == 0) return;

    reverse(s, 0, n - 1);      // 反转整个字符串
    reverse(s, 0, k - 1);      // 反转前 k 个
    reverse(s, k, n - 1);      // 反转后 n-k 个
}

int main() {
    char s1[] = "abcdefg";
    left_rotate(s1, 3);
    printf("左移3位: %s\n", s1);  // defgabc

    char s2[] = "abcdefg";
    right_rotate(s2, 3);
    printf("右移3位: %s\n", s2);  // efgabcd
    return 0;
}

你看，代码很简洁。三次反转，每次都是 O(n/2) 的操作，总体 O(n)。而且不需要额外空间。我在项目中处理网络数据包时，经常用这个方法来调整字节序。

个人习惯： 我一般把左移和右移封装成同一个函数，加一个方向参数。比如 rotate(s, k, direction)，direction 为 0 表示左移，1 表示右移。这样调用起来更统一。

27.2.3 方法三：库函数拼接法

如果允许使用临时空间，可以用 strcpy 和 strcat 来拼接。这个方法简单，但需要额外 O(n) 空间。

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

// 循环左移 k 位（拼接法）
void left_rotate_str(char *s, int k) {
    int n = strlen(s);
    if (n == 0) return;
    k = k % n;
    if (k == 0) return;

    char *temp = (char *)malloc(n + 1);
    if (!temp) return;

    // 把前 k 个字符放到临时串末尾
    strcpy(temp, s + k);      // 复制后半部分
    strncat(temp, s, k);      // 拼接前半部分
    strcpy(s, temp);          // 复制回原串

    free(temp);
}

int main() {
    char s[] = "abcdefg";
    left_rotate_str(s, 3);
    printf("%s\n", s);  // defgabc
    return 0;
}

这个方法适合快速原型开发，或者对性能要求不高的场景。但要注意：strncat 需要确保目标缓冲区够大，否则会溢出。我见过有人直接用 strcat 拼接，结果缓冲区溢出，程序崩溃——嗯，血的教训。

27.3 三种方法对比

方法	时间复杂度	空间复杂度	适用场景
暴力法	O(n*k)	O(1)	k 很小，n 很小
三次反转法	O(n)	O(1)	通用，推荐
拼接法	O(n)	O(n)	快速实现，不介意空间

我个人强烈推荐三次反转法。它优雅、高效、省空间。你想想看，面试的时候写出三次反转法，面试官一般都会点头。而暴力法嘛……可能会被追问“能不能优化？”

27.4 知识体系图

下面这张图总结了字符串循环移位的核心逻辑和三种实现路径：

27.5 避坑指南与实战经验

最后，我把自己踩过的坑总结一下，希望能帮你少走弯路。

坑1：k 取模问题

我曾经在写一个字符串加密模块时，忘了对 k 取模。结果 k 传进来是 100，字符串长度才 10，直接数组越界，程序崩溃。排查了半天才发现。记住：k = k % n 是第一步。

坑2：空字符串和 k=0 的情况

如果字符串长度为 0，或者 k 取模后为 0，直接返回。否则反转函数会操作空区间，虽然不会崩溃，但逻辑上没必要。我习惯在函数开头加两个 if 判断：if (n == 0) return; if (k == 0) return;

坑3：反转函数的边界

三次反转法里，反转的边界很容易搞错。左移和右移的边界不一样。我建议你写一个辅助函数 reverse(s, start, end)，然后每次调用时仔细核对 start 和 end 的值。我当年写左移时把前 n-k 个和后 k 个搞反了，结果移出来的字符串完全不对。

我的调试技巧： 写完后用几个简单例子测试：

k = 0 → 字符串不变
k = n → 字符串不变
k = 1 → 左移一位
k = n-1 → 左移 n-1 位
k = n+1 → 等价于 k=1

这几个例子能覆盖大部分边界情况。我每次写完都会跑一遍，确保没问题。

好了，字符串循环移位就讲到这里。三种方法各有优劣，但三次反转法是我最推荐的。它简洁、高效、省空间，而且面试时很加分。你可以在自己的项目里试试，看看能不能一次写对。

📚 课程目录