C语言实现字符串旋转的两种方法详解

????????处理字符串旋转问题时可以采用不同的策略。以下代码片段展示了两种方法：一种是直接移动字符的暴力求解法，另一种则是通过反转子串实现的高效三步法。

方法一：暴力求解（left_move函数）

// 定义一个函数，用于将字符串向左移动指定数量的字符
void left_move(char* p, int k) {
    assert(p != NULL); // 检查输入的字符串指针是否有效
    int len = strlen(p); // 获取字符串长度

    // 遍历k次，每次将第一个字符移到末尾
    for (int i = 0; i < k; ++i) {
        char tmp = *p; // 存储首个字符
        
        // 将除首字符外的所有字符依次前移一位
        for (int j = 0; j < len - 1; ++j) {//len - 1 =>防止*(p+1+j)越界.带数字5进去 5-1=4  p+1+4=p+5 
            *(p + j) = *(p + j + 1);
        }

        // 最后，将临时变量tmp赋值给原字符串的末尾位置
        *(p + len - 1) = tmp;//len - 1就是最后一个元素的位置
    }
}

这种方法直观且易于理解，但效率较低，因为每旋转一次都需要遍历整个字符串，时间复杂度为O(kn)，其中n为字符串长度。

方法二：三步反转法（Reverse_e函数）

//ab cdef => ba cdef =>  ba fedc = cdefab

void Reverse(char* first, char* last) {
    assert(first != NULL && last != NULL);
    
    // 双指针交换字符直到相遇
    while (first < last) {
        char tmp = *first;
        *first++ = *last;
        *last-- = tmp;
    }
}

// 主要函数，通过三次反转实现字符串旋转
void Reverse_e(char* p, int k) {
    assert(p);
    int len = strlen(p);
    assert(k <= len);

    // 第一步：反转字符串前k个字符
    Reverse(p, p + k - 1);

    // 第二步：反转剩余字符
    Reverse(p + k, p + len - 1);

    // 第三步：整体反转整个字符串，完成旋转操作
    Reverse(p, p + len - 1);
}

// 在主函数中获取用户输入并进行字符串旋转操作
int main() {
    char arr[20] = "";
    printf("请输入字符串：\n");
    scanf("%s", arr);
    printf("请输入旋转次数：\n");
    int k = 0;
    scanf("%d", &k);

    // 使用高效方法对字符串进行旋转
    Reverse_e(arr, k);

    printf("旋转后的字符串为：%s\n", arr);
    return 0;
}

三步反转法利用了字符串反转的特性，通过三个步骤将原本位于开头的k个字符巧妙地移动到了末尾，而无需逐个字符移动，因此其时间复杂度仅为O(n)，相比暴力求解法更加高效。

在上述C语言代码中，我们已经详细解释了两种实现字符串旋转的方法。简单回顾一下：

1. 暴力求解方法（left_move函数）： 这个方法通过循环遍历的方式将字符串的前k个字符逐一移动到末尾。每轮循环都将第一个字符存储到临时变量tmp中，然后将剩余字符依次向前移一位，最后再将tmp赋值给原字符串的末尾。这种方法直观易懂，但效率较低，因为每次旋转都需要遍历整个字符串。

2. 三步反转法（Reverse_e函数）： 该方法利用字符串反转的特性，通过三次反转操作高效地实现了字符串旋转。具体步骤如下：

   • 首先，调用Reverse(p, p + k - 1)反转字符串的前k个字符。
   • 然后，调用Reverse(p + k, p + len - 1)反转剩余的字符部分。
   • 最后，再次调用Reverse(p, p + len - 1)整体反转整个字符串。经过这样的处理，原本位于字符串开头的k个字符就会被移到末尾，同时保持其他字符相对顺序不变。

主函数中首先获取用户输入的字符串和要旋转的步数k，然后使用Reverse_e函数进行旋转，并输出旋转后的结果。

????????总结：相较于暴力求解方法，三步反转法在处理字符串旋转问题时表现出更高的效率和更简洁的逻辑，是解决此类问题的一种优秀策略。