開放原始碼技術文件網 如何練習資料結構

最後修改日期為 FEB 21, 2019

前言

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

撰寫虛擬碼 (Pseudocode)

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

虛擬碼可以用文字敘述撰寫,也可以用半程式語言的方式撰寫。使用半程式語言的方式會比較簡單,因為可以和自己的實作對照,大概就可以知道虛擬碼正確與否。

要注意不能直接用程式碼取代虛擬碼,因為這樣會暴露受測者無法使用抽象思維寫資料結構。最好在考試前先練習幾次用虛擬碼寫程式,才不會在考試時臨時想不出來怎麼寫。筆者寫了篇有關練習虛擬碼的文章,有需要的讀者可以參考。

如果真的有困難,建議用 Python 先做一次,再重新用 C 或 C++ 做一次。Python 號稱 executable pseudocode 就是因為語法上夠簡明,也不用處理指標、記憶體等細部問題,對於初學者來說是較簡單的選擇 (這裡有相關說明)。

由於大專院校很少接受 Python 的實作,本系列文章仍然會用 C 實作。要注意不能直接用 Python 程式碼取代虛擬碼,等熟悉資料結構 (和演算法) 後還是要重新練習寫虛擬碼。

練習平台

如果要上機考,最好平常就用和上機考一樣的平台來練習,藉此熟悉該平台;要不然就用優先使用自己熟悉的平台。

雖然 Visual Studio 是大家常用的工具,但 Visual C++ 對於 C 標準的支援相對落後,僅支援到一部分的 C99 特性,目前仍不支援 C11。此外,Visual C++ 無法指定 C 標準,對於學習 C 標準來說,Visual C++ 不是良好的工具。如果學校不嚴格規定 C 標準,仍然可用 Visual C++ 來練習。

但若要使用 C99 或 C11 等現代 C 語言的特性,建議換編譯器 (參考C 標準的文章)。如果要在 Windows 平台上練習可考慮用 Code::Block 加上 MinGW (GCC 移植品) 來練習。筆者撰寫了有關 Windows 上的 IDE在 Windows 上建置 C 開發環境的文章。

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

C 專案架構

C 語言本身沒有專案的概念,我們需要用第三方軟體來管理 C 專案。可用 IDE 內建的專案管理程式來管理 C 專案,或是用 CMake、Make 等跨平台工具來管理。

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

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

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

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

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

檔案較少時,採扁平式專案架構即可;如果檔案較多,則會採巢狀架構,通常是把原始碼放 src ,標頭檔放 include 。不論是扁平架構或巢狀架構,都需要撰寫相對應的 Make 或 CMake 設定檔。

如果覺得 Make 這類編譯自動化 (build automation) 工具比較難,初期可先用 IDE 內建的專案管理工具來管理程式碼。

筆者寫了一個可立即使用的 C 函式庫樣板專案。透過這個樣板專案,可以省下一開始建置專案的時間,而且 GNU Make 不會綁定特定 IDE,算是跨平台的專案管理程式。

使用 GNU Make 或 CMake 的話,可以搭配 KDevelop 使用,因為 KDevelop 可以直接吃以 CMake 或 Make 組態的專案。

以 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 Yahoo
追蹤本站
Facebook Facebook Twitter