[資料結構] 使用 C 語言:如何練習

PUBLISHED ON FEB 21, 2019 — DATA STRUCTURES
Facebook Twitter LinkedIn LINE Skype EverNote GMail Yahoo Email

    雖然資料結構是抽象的概念,但我們仍需某種程式語言來實作電腦程式。在本文中,我們以 C 語言為準,說明練習資料結構的方法。

    撰寫虛擬碼

    練習資料結構 (或演算法) 時一定要練習寫虛擬碼 (pseudocode),不僅是為了練習邏輯思考,有些考試也不考實作,反而考虛擬碼。但是,虛擬碼是文字敘述,無法用編譯器或直譯器檢查我們的想法是否正確;此外,C 編譯器的錯誤訊息有時候幫助不太,像是陣列或指標存取錯誤就噴 segmentation fault,一開始也不知道怎麼除錯。所謂的萬事起頭難大概就是這樣子。

    如果真的有困難,建議用 Python 先做一次,再重新用 C 或 C++ 做一次。Python 號稱 executable pseudocode 就是因為語法上夠簡明,也不用處理指標、記憶體等細部問題,對於初學者來說是較簡單的選擇 (這裡有相關說明)。由於大專院校很少接受 Python 的實作,本系列文章仍然會用 C 實作。要注意不能直接用 Python 程式碼取代虛擬碼,等熟悉資料結構 (和演算法) 後還是要重新練習寫虛擬碼。有關更多虛擬碼的說明可看這裡

    開發平台

    如果要上機考,最好平常就用和上機考一樣的平台來練習,藉此熟悉該平台;要不然就用優先使用自己熟悉的平台。只是要注意 Visual C++ 對於 C 標準的支援相對落後,僅支援到一部分的 C99 特性,如果學校只用到 ANSI C 就無妨,但若要以 C99 以後的版本為主,建議換編譯器;如果要在 Windows 平台上練習可考慮用 Code::Block 加上 MinGW (GCC 移植品) 來練習。這裡這裡有相關的說明。

    筆者本身主要用 GNU/Linux 來練習,除了個人習慣外,可以用 Valgrind 來檢查記憶體也是一個原因。如果各位讀者想用 GNU/Linux 來練習但又覺得 GNU/Linux 較難上手,可以用 Cloud 9 或其他類似的雲端 IDE 來練習,省去建置系統的心力。

    專案架構

    練習資料結構的專案架構很簡單,通常僅需三個檔案:

    • 標頭檔 (header):該資料結構的公開介面
    • 核心程式碼:實際的內部實作
    • 測試程式碼:用來測試我們的實作是否正碓

    以佇列 (queue) 為例,可對應到以下三個檔案:

    • queue.h
    • queue.c
    • main.c

    由於 C 語言不限制檔案的名稱,這些名稱僅供參考。

    檔案較少時,採扁平式專案架構即可;如果檔案較多,則會採巢狀架構,通常是把原始碼放 *src*,標頭檔放 *include*;不論是扁平架構或巢狀架構,都需要撰寫相對應的 Makefile 或 CMake 設定檔。如果覺得 Make 這類編譯自動化 (build automation) 工具比較難,初期可先用 IDE 內建的專案管理工具來管理程式碼。

    筆者寫了一個小工具,可用來自動產生以 GNU Make 為基礎的 C (或 C++) 應用程式或函式庫專案。這個小工具的好處是省下一開始建置專案的時間,而且 GNU Make 不會綁定特定 IDE,算是跨平台的專案管理程式。

    編譯自動化

    一開始比較不熟悉時可能要反覆編譯和執行程式,每次都重新打編譯程式碼的指令比較麻煩,建議用流程自動化軟體來協助我們簡化工作。一般來說,IDE 會協助我們編譯程式,對於初心者來說是比較簡單的選擇。但工作流程有分支時,用 IDE 設定反而比較不靈活;有時要帶入命令列參數時,使用終端機反而比較簡單。make(1) 雖然是一個很老的工具,但仍然相當可靠,讀者也可以自行選用其他同質的工具。

    make(1) 預設的設定檔是 *Makefile*,其「虛擬碼」如下:

    task: dependency
    	command
    

    例如,以下的例子:

    compile:
    	gcc -Wall -g -o file file.c
    

    在終端上輪入 make compile 即可執行 compile 任務的指令。

    我們想要編譯完後自動執行:

    run: compile
    	./file
    
    compile:
    	gcc -Wall -g -o file file.c
    

    在這個例子中,我們輸入 make run 指令,run 任務會相依到 compile 任務,所以就會先編譯程式後再執行。

    不過,在這個例子中,我們只要輸入 make 指令,make 程式會自動找 run 任務,而 run 任務又相依於 compile 任務,這個指令就會依序執行。這是因為未指定目標時,make 會自動使用第一個目標。

    當然,我們可以用 make(1) 的語法進一步整理 Makefile 設定檔。我們這裡展示一個簡單的例子:

    CC=gcc
    MEM_CHECK=valgrind
    RM=rm
    RMFLAG=-rf
    TARGET=test_deque
    
    all: run
    
    check: compile
    	$(MEM_CHECK) ./$(TARGET)
    	echo $$?
    
    run: compile
    	./$(TARGET)
    	echo $$?
    
    compile:
    	$(CC) -Wall -g -o $(TARGET) test_deque.c deque.c
    
    clean:
    	$(RM) $(RMFLAG) $(TARGET)
    

    在這個例子中,我們輸入 make 會執行測試程式,make check 會進行記憶體檢查,make clean 會刪掉執行檔。說實在的,make(1) 的語法不太好學,但只是要寫簡單的小程式用的 Makefile 倒也不會花太多時間。筆者在這裡撰寫一份 GNU Make 相關的入門教學,有需要的讀者可自行參考。

    檢查記憶體洩露

    練習資料結構時最好檢查一下記憶體是否正確釋放,即使程式正確運行,不代表就沒有記憶體洩漏,僅憑人工檢查程式碼不易看出是否有記憶體洩漏。Valgrind 是 GNU/Linux 上相當知名的記憶體檢查軟體,但 Valgrind 新版已經不支援 Mac 了,如果在 Mac 上練習時,可用 clang 的 AddressSanitizer 來代替。使用方法如下:

    $ clang -O1 -g -fsanitize=address -fno-omit-frame-pointer -o file file.c
    $ ASAN_OPTIONS=detect_leaks=1 ./file

    註:目前 AddressSanitizer 僅支援 OS X 10.7 - 10.11。

    更多說明,請看這裡

    如果使用 Windows 系統的讀者,可參考 Dr. Memory 或其他同質軟體。

    你或許對以下產品有興趣:
    © 2014-2019. Michael Chen
    All code in the website is licensed under Apache 2.0 unless otherwise mentioned.