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

【分享本文】
Facebook Twitter LinkedIn LINE Skype EverNote GMail Yahoo Email

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

    撰寫虛擬碼 (Pseudocode)

    練習資料結構 (或演算法) 時一定要練習寫虛擬碼 (pseudocode),除了練習邏輯思考外,有些考試不考實作,反而考虛擬碼。但是,虛擬碼是文字敘述,沒有嚴謹的語法規範 (specification),無法用編譯器或直譯器檢查我們的想法是否正確,要怎麼知道自己的虛擬碼是正確的呢?

    虛擬碼可以用文字敘述撰寫,也可以用半程式語言的方式撰寫。使用半程式語言的方式會比較簡單,因為可以和自己的實作對照,大概就可以知道虛擬碼正確與否。要注意不能直接用程式碼取代虛擬碼,因為這樣暴露受測者無法使用抽象思維寫資料結構。筆者寫了篇有關練習虛擬碼的文章,有需要的讀者可以參考。

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

    練習平台

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

    筆者本身主要用 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,算是跨平台的專案管理程式。使用 GNU Make 或 CMake 的話,可以搭配 KDevelop 使用,因為 KDevelop 可以直接吃這些設定檔。

    編譯自動化,以 GNU Make 為例

    一開始比較不熟悉時可能要反覆編譯和執行程式,每次都重新打編譯程式碼的指令比較麻煩,建議用流程自動化軟體來協助我們簡化工作。一般來說,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。

    更多說明,請看這裡。目前在 Mac 上建議用 Clang 的 scan-build 對程式碼進行靜態程式碼檢查。

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

    【分享本文】
    Facebook Twitter LinkedIn LINE Skype EverNote GMail Yahoo Email
    【追蹤新文章】
    Facebook Twitter Plurk
    標籤: DATA STRUCTURES