C語言字符串反轉：非遞歸、遞歸、遞歸無庫函數三種實現全解析

編輯：關於C語言

C語言字符串反轉：非遞歸、遞歸、遞歸無庫函數三種實現全解析

字符串反轉是基礎操作，本文展示三種不同思路的實現，涵蓋指針交換、遞歸棧特性、純遞歸無庫函數版本。

方法一：雙指針迭代交換（標準庫風格）

char *reverse_iter(char *str) {
    if (!str) return NULL;
    int len = strlen(str);
    for (int i = 0, j = len - 1; i < j; i++, j--) {
        char tmp = str[i];
        str[i] = str[j];
        str[j] = tmp;
    }
    return str;
}

時間 O(n)，空間 O(1)，修改原字符串。

方法二：遞歸打印（利用調用棧）

#include <assert.h>

void reverse_print(const char *str) {
    assert(str);
    if (*str == '\0') return;
    reverse_print(str + 1);  // 先遞歸到末尾
    putchar(*str);           // 回溯時打印，實現反序
}

int main() {
    char s[20];
    scanf("%[^\n]", s);  // 讀取含空格行
    reverse_print(s);
    putchar('\n');
    return 0;
}

不修改原串，僅反序輸出。空間 O(n) 棧深度。

方法三：純遞歸原地反轉（無庫函數，面試高頻）

int my_strlen(const char *s) {
    return *s ? 1 + my_strlen(s + 1) : 0;
}

char *reverse_recursive(char *str, int len) {
    if (!str || len <= 1) return str;
    
    char tmp = str[0];
    str[0] = str[len - 1];
    str[len - 1] = '\0';  // 臨時截斷，避免下層處理已換位字符
    
    reverse_recursive(str + 1, len - 2);  // 遞歸處理中間段
    
    str[len - 1] = tmp;  // 恢復末尾字符
    return str;
}

int main() {
    char s[20];
    scanf("%s", s);
    int len = my_strlen(s);
    reverse_recursive(s, len);
    printf("%s\n", s);
    return 0;
}

三種方法對比

方法	修改原串	空間複雜度	適用場景
雙指針迭代	是	O(1)	通用、高效、標準實現
遞歸打印	否	O(n) 棧	只需輸出、教學演示棧
純遞歸反轉	是	O(n) 棧	面試考察遞歸思維、受限環境