資料結構理論與實務 – 以C語言實作 Data Structures in C：Concept and Implementation

Presentation on theme: "資料結構理論與實務 – 以C語言實作 Data Structures in C：Concept and Implementation"— Presentation transcript:

1 資料結構理論與實務 – 以C語言實作 Data Structures in C：Concept and Implementation
課程名稱：資料結構 指導老師：吳弘翔

2 目錄 第1章：資料結構導論（Introduction） 第2章：陣列與結構（Arrays and Structures）
第3章：指標與字串（Pointers and Strings） 第4章：鏈結串列（Linked Lists） 第5章：堆疊（Stacks）

3 目錄 第6章：佇列（Queues） 第7章：樹與二元樹（Trees and Binary Trees） 第8章：圖形結構（Graphs）
第9章：資料排序（Sorting） 第10章：資料搜尋（Searching）

4 第1章 資料結構導論 （Introduction）
1-1 資料結構的基礎 1-2 程式設計與演算法 1-3 抽象資料型態ADT 1-4 C語言的模組化程式設計 1-5 遞迴函數 1-6 程式的分析方法

5 1-1 資料結構的基礎-說明 「資料結構」（Data Structures）是一門計算機科學的基礎學科，其目的是研究程式使用的資料在電腦記憶體的儲存方式，以便撰寫程式處理問題時，能夠使用最佳的資料結構，並且提供一種策略或方法來有效率的善用這些資料，以便達到下列目的，如下所示： 程式執行速度快。 資料佔用最少的記憶空間。 更快速的存取這些資料。

6 1-1 資料結構的基礎-圖例 上述轉換資料的方法策略就是「演算法」（Algorithms）。
演算法和資料結構的關係非常的密切，因為程式使用的演算法和資料結構都會影響程式的執行效率，換句話說，演算法加上資料結構就等於程式，如下所示： 「演算法」 + 「資料結構」 = 「程式」

7 1-2 程式設計與演算法 1-2-1 程式設計的過程 1-2-2 演算法 1-2-3 模組化 1-2-4 由上而下的設計方法

8 1-2-1 程式設計的過程-階段 程式設計是將需要解決的問題轉換成程式碼，程式碼不只能夠在電腦上正確的執行，而且可以驗證程式執行的正確性，程式設計的過程可以分成5個階段，如下所示： 需求（Requirements） 設計（Design） 分析（Analysis） 撰寫程式碼（Coding） 驗證（Verification）

9 1-2-1 程式設計的過程-需求 需求（Requirements）：程式設計的需求是在了解問題本身，以便確切獲得程式需要輸入的資料和其產生的結果，如下圖所示：

10 1-2-1 程式設計的過程-設計 設計（Design）：在了解程式設計的需求後，我們就可以開始找尋解決問題的方法和策略，簡單的說，設計階段就是找出解決問題的步驟，如下圖所示：

11 1-2-1 程式設計的過程-分析 分析（Analysis）：在解決需求時，只有一種解決方法嗎？例如：如果有100個變數，我們可以宣告100個變數來儲存資料，或是使用陣列來儲存，在分析階段是將所有可能解決問題的演算法都寫下來，然後分析比較那一種方法比較好，選擇最好的演算法來撰寫程式。

12 1-2-1 程式設計的過程-撰寫 撰寫程式碼（Coding）：現在就可以開始使用指定的程式語言來撰寫程式碼，以本書為例是使用C程式語言，在實際撰寫程式時，可能發現另一種方法比較好，因為設計歸設計，在實際撰寫程式時才能真正發現其優劣，如果這是一個良好的設計方法，就算改為其它方法也不會太困難。

13 1-2-1 程式設計的過程-驗證 驗證（Verification）：驗證是證明程式執行的結果符合需求的輸出資料，在這個階段可以再細分成三個部分： 證明：執行程式時需要證明它的執行結果是正確的，程式符合所有輸入資料的組合，程式規格也都符合演算法的需求。 測試：程式需要測試各種可能情況、條件和輸入資料，以測試程式執行無誤，如果有錯誤產生，就需要除錯來解決程式問題。 除錯：如果程式無法輸出正確的結果，除錯是在找出錯誤的地方，我們不但需要找出錯誤，還需要決定如何更正它。

14 1-2-2 演算法-定義 演算法是完成目標工作的一組指令，這組指令的步驟是有限的。除此之外，演算法還必須滿足一些條件，如下所示：
輸入(Input)：沒有或數個外界的輸入資料。 輸出(Output)：至少有一個輸出結果。 明確性(Definiteness)：每一個指令步驟都十分明確，沒有模稜兩可。 有限性(Finiteness)：這組指令一定結束。 有效性(Effectiveness)：每一個步驟都可行，可以追蹤其結果。

15 1-2-2 演算法-方法 演算法只是將解決問題步驟詳細的寫出來，所以並沒有固定的方式，基本上只要能夠描述這組指令的執行過程即可，常用的方式如下所示： 一般語言文字：直接使用文字描述來說明執行的步驟。 虛擬碼（Pseudo Code）：趨近程式語言的描述方法，其每一列約可轉換成一列程式碼。 流程圖（Flow Chart）：使用結構化的圖表描述執行過程，以各種不同形狀的圖形表示不同的操作。

16 1-2-2 演算法-虛擬碼範例 從1加到10演算法的虛擬碼，如下所示： /* 計算1加到10 */ Let counter = 1
Let total = 0 while counter <= 10 total = total + counter Add 1 to counter Output the total /* 顯示結果 */

17 1-2-2 演算法-流程圖範例 從1加到10演算法的 流程圖，如右圖所示：

18 1-2-3 模組化-說明 模組化主要是針對解決問題的方法，把一件大型的工作切割成多個小工作，切割的工作屬於一種結構化分析的範疇，最常使用的是「由上而下的設計方法」，其主要是使用程序為單位來切割工作，也就是所謂的「程序式程式設計」（Procedural Design）。

19 1-2-3 模組化-意義1 筆者使用一個簡單的數學不等式來說明模組化的意義，如下所示：
C(x)：函數表示問題的複雜度。 E(x)：函數代表需要花費多少工時來解決這個問題。 上述數學函數分別表示問題的複雜度和花費時間，現在有兩個問題P1和P2等待解決，問題P1的複雜度比問題P2高，可以得到不等式，如下所示： C(P1) > C(P2) → E(P1) > E(P2) (1) 上述不等式表示問題P1的工作量比解決問題P2來的費時，因為問題P1比較複雜。

20 1-2-3 模組化-意義2 接下來，將問題P1和P2合併解決，但是必須考慮兩個問題間的關連性，如此會延伸出更多的問題。所以，可以得到不等式，如下所示： C(P1+P2) > C(P1)+C(P2) 接著從不等式(1)開始推導，可以得到不等式，如下所示： → E(P1+P2) > E(P1)+E(P2) 上述不等式的意義是將一個問題劃分成數個小問題，然後分別解決這些問題的工作量比直接解決一個大問題所需的工作量來的少，這就是模組化的目的。

21 1-2-4 由上而下的設計方法-說明 由上而下的設計方法（Top-down Design）是在面對問題時，先考慮將整個解決問題的方法分解成數個大「模組」（Modules），然後針對每一個大模組，一一分割成數個小模組，如此一直細分，最後等這些細分小問題的小模組完成後，再將它們組合起來，如此一層層的向上爬，完成整個軟體系統或應用程式的設計。 例如：玩拼圖遊戲一定會先將整個拼圖粗分為數個區域，等每一個區域都拼好後，整張拼圖也就完成

22 1-2-4 由上而下的設計方法-注意事項 獨立性：每一個分割模組間的關聯性愈少，處理起來就會愈快。所謂獨立性，是指當處理某一個子問題時，無需考慮到其它子問題。換一句話說，獨立性是要將每一個問題都定義成一件簡單且明確的問題。 結合問題：小心控制子問題間的結合方法，而且要注意結合這些子問題的邏輯順序，避免語焉不詳的結果。 子問題間的溝通：雖然獨立性可以減少各問題間的關聯性，但是並無法避免掉全部的溝通。因此各問題間如何溝通的問題（即函數的參數傳遞）也是十分重要的考量。

23 1-3 抽象資料型態ADT 1-3-1 抽象化 – 塑模 1-3-2 程序或函數抽象化 1-3-3 抽象資料型態（ADT）

24 1-3-1 抽象化 – 塑模(說明) 程式設計的目的是解決問題，也就是將現實生活中的真實問題轉換成電腦程式，讓電腦執行程式幫助我們解決問題，這個過程是找出問題的模型，稱為「塑模」（Modeling），使用抽象觀點來檢視問題，以便建立問題的模型，將問題轉換成模型的方式稱為「抽象化」（Abstraction），如下圖所示：

25 1-3-1 抽象化 – 塑模(定義屬性) 「塑模」（Modeling）的主要的目的是定義問題的二個屬性，如下所示：
資料（Data）：問題影響的資料。 操作（Operators）：問題產生的操作。 例如：學生基本資料的問題，可以抽象化成Students模型，資料部分是：學號、姓名、地址和電話號碼，操作部分有：指定和取得學生的姓名、地址和電話號碼。

26 1-3-2 程序或函數抽象化-說明 程序或函數抽象化（Porcedure Abstraction or Function Abstraction）的針對傳統由上而下的程式設計方法，將問題分割成一個個子工作，分割的程序或函數並不用考量實作的程式碼，只需定義好程序或函數使用介面的參數和傳回值，將它視為一個黑盒子，換句話說，程式可以使用任何符合介面的程序或函數來取代，稱為程序或函數抽象化。

27 1-3-2 程序或函數抽象化-範例 當定義繪出門框程序的使用介面後，如果開發出更佳的演算法，只需將程序取代成實作的新程式碼，並不用更改使用介面，就可以增加程式執行效率，如果程序擁有此特性，稱為程序抽象化。

28 1-3-3 抽象資料型態（ADT）-說明 「抽象資料型態」（Abstract Data Type）是一種自訂資料型態，包含資料和相關操作，將資料和處理資料的操作一起思考，結合在一起，操作是對外的使用介面，如下圖所示：

29 1-3-3 抽象資料型態（ADT）-範例 例如：將學生基本資料抽象化成Students抽象資料型態，內含學號id、姓名name、地址address和電話號碼phone等資料，和setStudent()指定學生資料，getName()、getAddress()和getPhone()取出學生資料等操作，如下圖所示：

30 1-3-3 抽象資料型態（ADT）-實作 以物件導向程式語言：C++或Java語言來說，Students資料型態就是Students類別，程式可以使用Students類別建立多個Students副本（Instances，副本是物件導向名詞，它就是一個物件），用來模擬真實世界的學生，例如：同班同學、高中同學和同修一門課的同學等。 雖然C語言不是物件導向程式語言，不過仍然可以使用C語言的模組化程式設計來實作抽象資料型態，其主要的問題是只能建立一個副本，並不能像物件導向程式語言的類別能夠建立多個副本。

31 1-4 C語言的模組化程式設計-說明 「模組」（Modules）是特定功能的相關資料和函數集合，程式設計者只需知道模組對外的使用介面（即各模組函數的呼叫方式），就可以使用模組提供的功能，而不用實際了解模組內部程式碼的實作和內部資料儲存使用的資料結構。

32 1-4 C語言的模組化程式設計-種類 模組化程式設計（Modular Programming）就是建立相關資料和函數集合的模組，模組主要可以分成兩個部分：介面與實作，如下所示： 模組介面（Module Interface）：模組介面是定義模組函數和使用的資料，即定義讓使用此模組的程式可以呼叫的函數和存取的變數資料，在C語言是使用標頭檔.h定義模組介面。 模組實作（Module Implementations）：模組的實作部分是模組函數和資料的實際程式碼，程式設計者需要定義哪些函數屬於公開介面，哪些只能在模組程式檔使用，C語言的程式檔案.c可以實作模組的程式碼。

33 1-4 C語言的模組化程式設計-公開與私用關鍵字
extern和static關鍵字來區分公開或內部使用的函數與變數，如下所示： 在標頭檔宣告成extern的變數和函數：這是可供其它程式使用的外部函數和變數。 在模組程式檔宣告成static的變數和函數：只能在模組程式檔中使用。

34 1-5 遞迴函數 1-5-1 遞迴的基礎 1-5-2 遞迴的階層函數

35 1-5 遞迴函數 「遞迴」（Recursive）是程式設計的一個重要觀念。「遞迴函數」（Recursive Functions）可以讓函數的程式碼變的很簡潔，但是設計這類函數需要很小心，不然很容易就掉入類似無窮迴圈的陷阱。

36 1-5-1 遞迴的基礎-說明 遞迴的觀念主要是在建立遞迴函數，其基本定義，如下所示：
一個問題的內涵是由本身所定義的話，稱之為遞迴。 遞迴函數是由上而下分析方法的一種特殊的情況，因為子問題本身和原來問題擁有相同的特性，只是範圍改變，範圍逐漸縮小到一個終止條件。

37 1-5-1 遞迴的基礎-特性 遞迴函數的特性，如下所示： 遞迴函數在每次呼叫時，都可以使問題範圍逐漸縮小。
函數需要擁有一個終止條件，以便結束遞迴函數的執行，否則遞迴函數並不會結束，而是持續的呼叫自已。

38 1-5-2 遞迴的階層函數-公式 遞迴函數最常見的應用是數學的階層函數n!，如下所示：

39 1-5-2 遞迴的階層函數-範例 例如：計算4!的值，從上述定義n>0，使用n!定義的第2條計算階層函數4!的值，如下所示：
4!=4*3*2*1=24 4!=4*(4-1)!=4*3! 3! = 3*(3-1)! = 3*2! 2! = 2*(2-1)! = 2*1! 1! = 1*(1-1)! = 1*0! = 1*1 = 1 在知道1!的值後，就可以計算出2!~4!的值，如下所示： 2! = 2*(2-1)! = 2*1! = 2 3! = 3(3-1)! = 3*2! = 3*2 = 6 4! = 4*(4-1)! = 4*3! = 24

40 1-6 程式的分析方法 1-6-1 頻率計數的基礎 1-6-2 頻率計數的計算 1-6-3 遞迴函數的頻率計數 1-6-4 Big Oh函數

41 1-6 程式的分析方法 一個好程式需要滿足一些條件，如下所示： 正確的執行結果：程式滿足分析的輸入和輸出結果。
可維護性高：程式不只需要正確，而且是可讀、容易修改和擴充，這屬於程式設計方法和風格的問題，例如：使用模組化來設計程式和加上完整程式註解的說明。 執行效率高：執行效率是指程式執行花費的時間和所需的記憶體空間，一般來說，這兩項在大多數情況是矛盾的，因為使用較大的記憶體空間，通常可以換取程式執行效率的改進，反之亦然，至於如何找到其間的平衡點，就需視解決的問題而定。

42 1-6-1 頻率計數的基礎-說明 程式執行效率就是在計算程式執行的時間，例如：在程式中有一列程式碼，如下所示：
a = a + 1; 上述程式碼將變數a的值加1。如果使用for迴圈執行此程式碼n次，如下所示： for ( i = 0; i < n ; i++ ) a = a + 1; 上述程式碼執行的全部時間是n*t，t為單獨執行a = a + 1程式碼所需的時間。

43 1-6-1 頻率計數的基礎-標準 如何決定時間t，其評量的標準如下所示： 執行程式碼使用的電腦種類：桌上型電腦、工作站或大型電腦。
CPU使用的機器語言指令集是哪一種？某些CPU的機器語言指令包含乘法和除法指令，有些沒有，有些是以硬體實作，有些是軟體加持。 CPU執行機器語言指令所需的時間，即CPU的執行速度，每秒可以執行的指令數不同，執行所需的時間當然不同。 使用的編譯程式，一個好的編譯程式可以將指令轉譯成為單一機器語言指令，相對於將它轉譯成數個機器語言指令的編譯程式，其執行時間的差異就十分明顯。

44 1-6-1 頻率計數的基礎-頻率計數 執行單位時間t的差異可能十分大，所以我們並不會直接計算程式的執行時間，取而代之是計算程式每一列程式碼的執行頻率，也就是「頻率計數」（Frequency Count），以程式執行的次數代替每一列程式碼實際執行的時間。 頻率計數（Frequency Count）是以原始程式碼的每一列可執行指令作為一個執行單位，計算出程式中每一列程式碼的執行次數，這個次數就是頻率計數。

45 1-6-2 頻率計數的計算-函數 05: void fibonacci(int n) { 06: int fn; /* F(n)變數 */
09: int i; 10: if ( n <= 1 ) /* 項數是否小於1 */ 11: printf("[%d]\n",n); /* 顯示費氏數列 */ 12: else { 13: fn2 = 0; /* 設定 F(n-2) */ 14: fn1 = 1; /* 設定 F(n-1) */ 15: printf("[0][1]"); /* 顯示前二項 */ 16: for ( i = 2; i <= n; i++ ) {/* 顯示數列的迴圈 */ 17: fn = fn2 + fn1; /* 計算各一般項 */ 18: printf("[%d]",fn); /* 顯示數列 */ 19: fn2 = fn1; /* 重設 F(n-2) */ 20: fn1 = fn; /* 重設 F(n-1) */ 21: } 22: printf("\n"); 23: } 24: }

46 1-6-2 頻率計數的計算-計數 函數fibonacci()可執行程式碼的頻率計數，如下表所示：

47 1-6-2 頻率計數的計算-說明 函數fibonacci()的頻率計數計算需要考慮兩種情況，如下所示：
n > 1：在執行函數第10列的if判斷後，頻率計數是1，然後執行第13~15列後的頻率計數是4，接著執行第16~21列的for迴圈，第16列執行n次（因為for迴圈一共執行n-1次，再加上最後一次比較跳出for迴圈），第17~20列執行4*(n-1) = 4n-4次，最後第22列可以計算出頻率計數是5n+1。 函數fibonacci()總共的頻率計數是2 + 5n + 1 = 5n+3。

48 1-6-3 遞迴函數的頻率計數-函數 05: long factorial(int n) {
06: if ( n == 1 ) /* 終止條件 */ 07: return 1; 08: else 09: return n * factorial(n-1); 10: }

49 1-6-3 遞迴函數的頻率計數-計數 頻率計數的計算，如下所示：
第6列：函數本身呼叫遞迴函數共n-1次，所以執行n-1次的比較，再加上主程式呼叫遞迴函數時的第1次比較，一共執行n-1+1次，所以頻率計數是n。 第7列：函數只有在最後一次遞迴呼叫才執行，所以頻率計數是1。 第9列：函數本身遞迴呼叫共n-1次，所以頻率計數是n-1。 遞迴函數factorial()總共的頻率計數是n n - 1 = 2n。

50 1-6-4 Big Oh函數-說明 在分析程式執行效率時考量的是頻率計數的級數，函數O()是用來表示參數頻率計數的級數，唸成Big Oh。
程式範例Ch1-6-2.c的O()函數，如下所示： n=0或1：2 O(1) n>1：5n+1 O(n) 上述頻率計數5n+1是O(n)，係數5和4並用不考慮，O(n)表示程式執行的頻率計數和n成正比，稱為是程式或演算法的「時間複雜度」（Time Complexity）。

51 1-6-4 Big Oh函數-O(1) O(1)：單行程式碼
a = a + 1; 上述程式碼a = a + 1是一列單行程式碼，沒有不包含在任何迴圈中，頻率計數是1所以是O(1)。

52 1-6-4 Big Oh函數-O(n) O(n)：線性迴圈
a = 0; for ( i = 0; i < n; i++ ) a=a+1; 上述程式碼執行n次的a = a + 1，其頻率計數是n+1，包含最後1次的比較，不計常數所以是O(n)。

53 1-6-4 Big Oh函數-O(Log n) O(Log n)：非線性迴圈 或
a = 0; for ( i = n; i > 0; i = i / 2 ) a=a+1; 或 for ( i = 0; i < n; i = i * 2 ) 上述兩個迴圈的增量是除以2或乘以2，以除來說，如果n = 16，迴圈依序為8、4、2、1，其執行次數是對數Log n，其頻率計數是Log n+1，包含最後1次的比較，不計常數所以是O(Log n)。

54 1-6-4 Big Oh函數-O(nLog n) O(n Log n)：巢狀迴圈擁有內層非線性迴圈
a = 0; for ( i = 0; i < n; i++ ) for ( j = n; j > 0; j = j / 2 ) a=a+1; 上述巢狀迴圈的外層是線性迴圈的O(n)，內層是非線性迴圈的O(Log n)，所以是： O(n) * O(Log n) = O(n Log n)

55 1-6-4 Big Oh函數-O(n2) O(n2)：巢狀迴圈 上述巢狀迴圈的外層是線性迴圈的O(n)，內層線性迴圈的O(n)，所以是：
a = 0; for ( i = 0; i < n; i++ ) for ( j = 0; j < n; j++ ) a=a+1; 上述巢狀迴圈的外層是線性迴圈的O(n)，內層線性迴圈的O(n)，所以是： O(n) * O(n) = O(n2)

56 1-6-5 Big Oh函數的等級-等級 程式執行效率的時間複雜度可以使用O(1)、O(Log n)、O(n)、O(n Log n)、O(n2)、O(n3)和O(2n)函數表示，如下表所示：

57 1-6-5 Big Oh函數的等級-成長曲線圖

58 1-6-5 Big Oh函數的等級-比較 如果一個問題有兩種不同的方法來解決，第一種方法的頻率計數是5n，第二種方法的頻率計數是n2/2，我們可以計算出頻率計數與n值的關係，如下表所示：

59 1-6-5 Big Oh函數的等級-說明 當n < 10時，第二種方法比第一種有效率，如果n > 10時，第一種方法反而比較有效率，函數O()分別為O(n)和O(n2)。 換句話說，當n足夠大時，頻率計數的常數就可以忽略不計，只需比較其級數，所以O(n)執行效率比O(n2)好。如果n很小時，常數就需要加以考量，如此才能真正比較出程式執行效率的優劣。