C 語言字串處理 18 大經典演算法實戰：壓縮、解壓、排序、查找、編碼轉換全解析

編輯：關於C語言

前言

字串處理是 C 語言程式設計的核心基本功，也是面試高頻考點。本文精選 18 個經典題目，涵蓋字串壓縮/解壓、IP 校驗、排序去重、子串查找、單詞統計、命名慣例轉換、增刪改查等實戰場景，每題提供標準解法與關鍵技巧解析。

1. 按順序壓縮字串（分組計數）

題目：輸入 SamSameCome，輸出分組後字串 SSaammmeeCo 及計數編碼 S2a2m3e2C1o1。

void compressOrdered(char *in, char *outStr, char *outCnt) {
    int len = strlen(in), k = 0;
    char *visited = calloc(len, 1);
    for (int i = 0; i < len; ++i) if (!visited[i]) {
        char c = in[i];
        int cnt = 0;
        for (int j = 0; j < len; ++j)
            if (in[j] == c) visited[j] = 1, outStr[k++] = c, ++cnt;
        sprintf(outCnt + strlen(outCnt), "%c%d", c, cnt);
    }
    outStr[k] = '\0';
    free(visited);
}

關鍵：雙層迴圈 + 訪問標記陣列，時間 O(n²)，空間 O(n)。

2. IPv4 地址合法性校驗

規則：四段 0-255 數字，首段非 0，以點分隔。

bool validIPv4(const char *ip) {
    int seg[4] = {0}, idx = 0;
    char *token = strtok(strdup(ip), ".");
    while (token && idx < 4) {
        if (strlen(token) > 3) return false;
        for (char *p = token; *p; ++p) if (!isdigit(*p)) return false;
        seg[idx++] = atoi(token);
        token = strtok(NULL, ".");
    }
    return idx == 4 && seg[0] > 0 && seg[0] <= 255 &&
           seg[1] <= 255 && seg[2] <= 255 && seg[3] <= 255;
}

3. 連續字符壓縮（Run-Length Encoding）

例：aaaaeefggg → a4e2f1g3。

void rleCompress(const char *s, char *out) {
    int len = strlen(s), pos = 0;
    for (int i = 0; i < len; ) {
        int j = i + 1;
        while (j < len && s[j] == s[i]) ++j;
        pos += sprintf(out + pos, "%c%d", s[i], j - i);
        i = j;
    }
}

4. RLE 解壓還原

例：a4e2f1g3 → aaaaeefggg。

void rleDecompress(const char *s, char *out) {
    int pos = 0;
    for (int i = 0; s[i]; ) {
        char c = s[i++];
        int cnt = 0;
        while (s[i] >= '0' && s[i] <= '9') cnt = cnt * 10 + (s[i++] - '0');
        while (cnt--) out[pos++] = c;
    }
    out[pos] = '\0';
}

5. 最長連續相同字符子串查找

輸入：逗號分隔數字串 1,3,3,3,4,4,4,4,4,0...，輸出最長連續段（如 44444）。

void longestRun(const char *s, char *out) {
    int maxLen = 0, maxPos = 0, curLen = 1;
    for (int i = 2; s[i]; i += 2) {  // 跳過逗號
        if (s[i] == s[i-2]) ++curLen;
        else {
            if (curLen > maxLen) maxLen = curLen, maxPos = i - 2;
            curLen = 1;
        }
    }
    if (curLen > maxLen) maxLen = curLen, maxPos = strlen(s) - 1;
    for (int i = 0; i < maxLen; ++i) out[i] = s[maxPos];
    out[maxLen] = '\0';
}

6. 兩字串首個公共子串（長度 > 1）

void firstCommonSubstr(const char *s1, const char *s2, char *out) {
    int len1 = strlen(s1), len2 = strlen(s2), outPos = 0;
    for (int i = 0; i < len1 - 1; ++i) {
        for (int j = 0; j < len2 - 1; ++j) {
            if (s1[i] == s2[j] && s1[i+1] == s2[j+1]) {
                int k = 0;
                while (i+k < len1 && j+k < len2 && s1[i+k] == s2[j+k])
                    out[outPos++] = s1[i+k++];
                out[outPos] = '\0';
                return;
            }
        }
    }
    out[0] = '\0';
}

7. 單詞字典序排序

void sortWords(char *s) {
    char *words[100]; int n = 0;
    words[n++] = strtok(s, " ");
    while ((words[n++] = strtok(NULL, " ")));
    --n;
    for (int i = 0; i < n-1; ++i)
        for (int j = 0; j < n-1-i; ++j)
            if (strcmp(words[j], words[j+1]) > 0) {
                char *t = words[j]; words[j] = words[j+1]; words[j+1] = t;
            }
    for (int i = 0; i < n; ++i) printf("%s%c", words[i], i==n-1?'\n':' ');
}

8. 單詞計數

int countWords(const char *s) {
    int cnt = 0;
    bool inWord = false;
    for (; *s; ++s) {
        if (isspace(*s)) inWord = false;
        else if (!inWord) inWord = true, ++cnt;
    }
    return cnt;
}

9. Snake Case 與 Camel Case 雙向轉換

規則：long_and_mnemonic_identifier ↔ longAndMnemonicIdentifier，混合風格報錯。

void convertCase(char *s) {
    bool hasUnderscore = strchr(s, '_'), hasUpper = false;
    for (char *p = s; *p; ++p) if (isupper(*p)) hasUpper = true;
    if (hasUnderscore && hasUpper) { strcpy(s, "Error!"); return; }
    if (hasUnderscore) {  // snake → camel
        for (char *p = s; *p; ++p)
            if (*p == '_') { memmove(p, p+1, strlen(p)); *p = toupper(*p); }
    } else {  // camel → snake
        for (int i = strlen(s)-1; i >= 0; --i)
            if (isupper(s[i])) {
                memmove(s+i+2, s+i+1, strlen(s)-i);
                s[i] = '_'; s[i+1] = tolower(s[i+1]);
            }
    }
}

10. 字串刪除（指定位置長度）

void strDelete(char *s, int pos, int len) {
    int slen = strlen(s);
    if (pos < 0 || pos >= slen) return;
    if (pos + len > slen) len = slen - pos;
    memmove(s + pos, s + pos + len, slen - pos - len + 1);
}

11. 字串插入

void strInsert(char *dest, const char *src, int pos) {
    int dlen = strlen(dest), slen = strlen(src);
    if (pos < 0 || pos > dlen) return;
    memmove(dest + pos + slen, dest + pos, dlen - pos + 1);
    memcpy(dest + pos, src, slen);
}

12. 字串替換

void strReplace(char *dest, const char *src, int pos, int len) {
    strDelete(dest, pos, len);
    strInsert(dest, src, pos);
}

13. 字串抽取並插入

void extractAndInsert(const char *src, char *dest, int pos, int len, int insertPos) {
    char sub[100] = {0};
    strncpy(sub, src + pos, len);
    strInsert(dest, sub, insertPos);
}

14. 指標陣列字串交換

void swapPtrArray(char **arr, int n, int i, int j) {
    if (i<0||i>=n||j<0||j>=n) return;
    char *t = arr[i]; arr[i] = arr[j]; arr[j] = t;
}

15. 字串陣列查找首次出現索引

int findInArray(char **arr, int n, const char *target) {
    for (int i = 0; i < n; ++i)
        if (strcmp(arr[i], target) == 0) return i + 1;  // 1-based
    return -1;
}

16. 多字串連接（指定分隔符）

void joinStrings(char **words, int n, const char *sep, char *out) {
    out[0] = '\0';
    for (int i = 0; i < n; ++i) {
        strcat(out, words[i]);
        if (i < n-1) strcat(out, sep);
    }
}

17. 多字符分隔符分割

void splitMultiChar(const char *s, const char *sep, char **out, int *cnt) {
    *cnt = 0;
    const char *p = s;
    while (*p) {
        out[(*cnt)++] = (char*)p;
        p = strstr(p, sep);
        if (!p) break;
        *(char*)p = '\0';  // 修改原串，若需保留請先複製
        p += strlen(sep);
    }
}

18. 字母頻率統計（以 '.' 結束）

void freqStats(const char *s) {
    int cnt[26] = {0};
    for (; *s && *s != '.'; ++s)
        if (islower(*s)) ++cnt[*s - 'a'];
    for (int i = 0; i < 26; ++i)
        if (cnt[i]) printf("%c: %d\n", 'a'+i, cnt[i]);
}