C語言實現字符串左旋轉的兩種經典算法詳解

編輯：關於C語言

C語言實現字符串左旋轉的兩種經典算法詳解

字符串左旋轉是指將字符串前面的若干字符移動到字符串末尾。例如，字符串 "AABCD" 左旋 1 位得到 "ABCDA"，左旋 2 位得到 "BCDAA"。本文介紹兩種常見的 C 語言實現方法，並提供完整代碼示例。

方法一：輔助數組法

最直觀的思路是開闢一個臨時數組，先將第 k+1 個字符及之後的字符複製到臨時數組，再將前 k 個字符追加到臨時數組末尾，最後加上結束符 '\0'。此法時間複雜度 O(n)，空間複雜度 O(n)。

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

void left_Rotate(char *str, char *arr, int k) {
    char *pcur = str + k;          // 指向第 k+1 個字符
    assert(str && arr);            // 斷言指針非空
    while (*pcur) {                // 複製後半部分
        *arr++ = *pcur++;
    }
    pcur = str;                    // 重置指針到字符串開頭
    while (k--) {                  // 複製前 k 個字符
        *arr++ = *pcur++;
    }
    *arr = '\0';                   // 添加結束符
}

int main() {
    int k;
    char str[10] = {0};
    char arr[10] = {0};
    scanf("%d", &k);
    scanf("%s", str);
    left_Rotate(str, arr, k);
    printf("%s\n", arr);
    return 0;
}

方法二：三步反轉法（原地算法）

此法無需額外空間，利用字符串反轉特性：先反轉前 k 個字符，再反轉剩餘字符，最後整體反轉整個字符串。時間複雜度 O(n)，空間複雜度 O(1)。

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

void reverse(char *left, char *right) {
    while (left < right) {
        char tmp = *left;
        *left = *right;
        *right = tmp;
        left++;
        right--;
    }
}

int main() {
    char arr[10] = "AABCD";
    int len = strlen(arr) - 1;
    int k = 0;
    char *pstart = &arr[0];
    char *pend = arr + len;
    scanf("%d", &k);
    reverse(pstart, pstart + k - 1);     // 反轉前 k 個字符
    reverse(pstart + k, pend);           // 反轉剩餘字符
    reverse(pstart, pend);               // 整體反轉
    printf("%s\n", arr);
    system("pause");
    return 0;
}