C 語言程式設計教學:字串 (String)

PUBLISHED ON JUL 24, 2018 — PROGRAMMING
FacebookTwitter LinkedIn LINE Skype EverNote GMail Yahoo Email

    學完陣列和指標後,就可以學 C 字串了。在 C 語言中,並沒有獨立的字串型別,而 C 字串是以 char 為元素的陣列,所以要有先前的預備知識才容易學習 C 字串。

    C 語言的字串方案

    在 C 語言中,常見的字串方案有以下三種:

    • 字元陣列 (character array)
    • 寬字元陣列 (wide character array):使用 wchar.h 函式庫
    • UTF8:透過第三方函式庫來操作,如 glib 或 ICU4C 等

    在這三者之中,前兩者是等寬字元的方案,UTF8 則採不等寬字元編碼。原本的字元陣列僅能處理英文文字,寛字元陣列和 UTF8 則是為了處理多國語文文字而産生的方案。

    例如,在支援 Unicode 的終端機環境,可以透過 wchar 印出中文字串:

    #include <locale.h>
    #include <wchar.h>
    
    int main()
    {
        // Trick to print multibyte strings.
        setlocale(LC_CTYPE, "");
    
        wchar_t *s = L"你好,世界";
        printf("%ls\n", s);
    
        return 0;
    }
    

    註:筆者在 Mac 上測試此程式,可成功印出中文字串。

    由於本文的目的是了解字串的基本操作,我們仍然是以原先的字元陣列為準。

    C 字串微觀

    我們由 "Hello World" 字串來看 C 字串的組成:

    C 語言字串示意圖

    由上圖可知,C 字串除了依序儲存每個字元外,在尾端還會額外加上一個 '\0' 字元,代表字串結束。由於 C 字串需要尾端的 '\0' 字元來判斷字串結束,我們在處理字串時,別忘了在字串尾端加上該字元。

    接下來,我們會介紹數個字串操作的情境。由於 C 標準函式庫已經有 string.h 函式庫,在採作字串時應優先使用該函式庫,而非重造輪子;本文展示的程式僅供參考。

    計算字串長度

    計算字串長度時,不包含尾端的結束字尾,所以 "happy" 的字串長度為 5。可參考以下的範例程式碼:

    #include <assert.h>
    #include <stddef.h>
    #include <string.h>
    
    int main(void)
    {
        char s[] = "Hello";
        
        size_t sz = 0;
        
        for (size_t i = 0; s[i]; i++) {
            sz++;
        }
        
        assert(sz == strlen(s));
        
        return 0;
    }
    

    字串複製

    一般使用 strcpy 函式的範例,都是預先從 stack memory 配置某個長度的字元陣列;本例略加修改,先動態計算來源字串的長度,再由 heap memory 動態配置一塊新的字元陣列,將原本的字元逐一複製到目標字串即完成。參考以下程式碼:

    #include <assert.h>
    #include <stddef.h>
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    int main(void)
    {
        char s[] = "Hello World";
        
        size_t sz_s = strlen(s);
        size_t sz = sz_s + 1;  // Add tailing zero.
        
        char *out = malloc(sz * sizeof(char));
    
        for (size_t i = 0; i < sz_s; i++) {
            out[i] = s[i];
        }
        
        out[sz-1] = '\0';
        
        assert(strcmp(out, "Hello World") == 0);
        
        free(out);
        
        return 0;
    }
    

    在本例中,由於 out 是由 heap 配置記憶體,使用完要記得手動釋放。

    字串相接

    原本的 strcat 函式需預先估計目標字串的長度,筆者略為修改,採用動態計算字串長度後生成所需長度的字元陣列,最後將原本的字串逐一複製過去。範例程式碼如下:

    #include <assert.h>
    #include <stddef.h>
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    int main(void) {
        char s_a[] = "Hello ";
        char s_b[] = "World";
        
        size_t sz_a = strlen(s_a);
        size_t sz_b = strlen(s_b);
        size_t sz = sz_a + sz_b + 1;  // Include tailing zero.
        
        char *out = malloc(sz * sizeof(char));
    
        for (size_t i = 0; i < sz_a; i++) {
            out[i] = s_a[i];
        }
        
        for (size_t i = 0; i < sz_b; i++) {
            out[i+sz_a] = s_b[i];
        }
        
        out[sz-1] = '\0';  // Add tailing zero.
        
        assert(strcmp(out, "Hello World") == 0);
        
        free(out);
        
        return 0;
    }
    

    在本例中,由於 out 是由 heap 配置記憶體,使用完要記得手動釋放。

    檢查字串相等

    檢查字串相等的流程很簡單:

    • 檢查兩字串是否等長
    • 逐一掃描兩字串的元素,確認每個元素是否相等

    可參考以下範例程式碼:

    #include <assert.h>
    #include <stdbool.h>
    #include <stddef.h>
    #include <string.h>
    
    int main(void)
    {
        char s_a[] = "happy";
        char s_b[] = "hurry";
        
        bool is_equal = true;
        
        size_t sz_a = strlen(s_a);
        size_t sz_b = strlen(s_b);
        
        if (sz_a != sz_b) {
            is_equal = false;
            goto END;
        }
        
        for (size_t i = 0; i < sz_a; i++) {
            if (s_a[i] != s_b[i]) {
                is_equal = false;
                goto END;
            }
        }
        
    END:
        assert(is_equal == false);
    
        return 0;
    }
    

    尋找子字串

    尋找子字串的示意圖如下:

    在 C 字串中找尋子字串

    本例的想法相當簡單,我們逐一走訪原字串,在每個位置檢查是否符合子字串。

    將以上想法寫成虛擬碼如下:

    s is the original string.
    ss is the substring.
    
    is_found <- false
    
    for (i from 0 to Len(s) - 1) do
        if i + Len(ss) >= Len(s) then
            break
        end if
        
        flag <- true
        for (j from 0 to Len(ss) - 1) do
            if s[i+j] != s[j] then
                flag <- false
                break
            end if
        end for
        
        if flag == true then
            is_found <- true
            break
        end if
    end for
    
    check whether is_found is true or not
    

    最後展示 C 語言的實作:

    #include <assert.h>
    #include <stdbool.h>
    #include <stddef.h>
    #include <string.h>
    
    int main(void)
    {
        // Original string.
        char s[] = "The quick brown fox jumps over the lazy dog";
        // Substring.
        char ss[] = "lazy";
        
        bool is_found = false;
    
        size_t sz_s = strlen(s);
        size_t sz_ss = strlen(ss);
        
        bool temp;
        for (size_t i = 0; i < sz_s; i++) {
            if (i + sz_ss >= sz_s) {
                break;
            }
            
            temp = true;
            for (size_t j = 0; j < sz_ss; j++) {
                if (s[i+j] != ss[j]) {
                    temp = false;
                    break;
                }
            }
            
            if (temp) {
                is_found = true;
                break;
            }
        }
    
        assert(is_found);
    
        return 0;
    }