第11章 資料結構 – 使用C語言的模組 11-1 資料結構的基礎 11-2 C語言的模組化程式設計 11-3 基本鏈結串列

Presentation on theme: "第11章 資料結構 – 使用C語言的模組 11-1 資料結構的基礎 11-2 C語言的模組化程式設計 11-3 基本鏈結串列"— Presentation transcript:

1 第11章 資料結構 – 使用C語言的模組 11-1 資料結構的基礎 11-2 C語言的模組化程式設計 11-3 基本鏈結串列
11-4 堆疊與佇列 11-5 二元樹 11-6 資料排序 11-7 資料搜尋

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

3 11-1 資料結構的基礎-策略或方法 策略或方法是指如何選擇最恰當的資料結構，並 且將這些資料轉換成有用的資訊，如下：
轉換資料的方法就是演算法（Algorithms）。演 算法和資料結構的關係非常的密切，因為演算法 加上資料結構就等於程式。

4 11-2 C語言的模組化程式設計 11-2-1 C語言的模組化程式設計 11-2-2 新增Dev-C++的專案
專案管理的基本操作

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

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

7 11-2-1 C語言的模組化程式設計-extern和static關鍵字

8 11-2-1 C語言的模組化程式設計-Ch11-2.h 01: /* 程式範例: Ch11-2.h */
02: #define MAXCMP 1 03: #define MINCMP 0 04: /* 外部變數宣告 */ 05: extern int var1; 06: extern int var2; 07: /* 顯示整數變數的比較結果 */ 08: extern void cmpresult(int);

9 11-2-1 C語言的模組化程式設計-Ch11-2.c 01: /* 程式範例: Ch11-2.c */
02: #include <stdio.h> 03: #include "Ch11-2.h" 04: /* 函數原型宣告 */ 05: static void maxvalue(void); 06: static void minvalue(void); 07: int var1, var2; 08: static int result; 09: /* 最大值 */ 10: static void maxvalue() { } 17: /* 最小值 */ 18: static void minvalue() { } 25: /* 顯示整數變數的比較結果 */ 26: void cmpresult(int type) { }

10 新增Dev-C++的專案-說明 Dev-C++的「專案」（Projects）是用來幫助程式設計者開發和維護C/C++應用程式，通常是使用在多個程式檔案的大型應用程式，專案包含應用程式檔案和相關檔案清單，程式檔案所在路徑和相關編譯設定等資訊，例如：C語言的模組是由.h標頭檔和.c的程式檔案組成，如此即可使用專案來管理模組所需的檔案。

11 新增Dev-C++的專案-建立 請啟動Dev-C++，執行「檔案」→「開新檔案」→「專案」指令，可以看到「建立新專案」對話方塊。

12 專案管理的基本操作 Dev-C++的專案管理不只能夠新增存在的C程式檔案，還可以在專案的檔案清單新增、刪除程式檔案或重新命名檔案。 開啟Dev-C++專案 新增檔案 重新命名 移除檔案

13 11-3 基本鏈結串列-說明 「鏈結串列」（Linked Lists）是一種動 態資料結構，如同火車掛車廂一般，將每 一個車廂的節點連結起來，如下圖所示：

14 11-3 基本鏈結串列-snode結構 C語言串列節點snode結構的宣告，如下所示：
struct snode { int data; struct snode *next; }; typedef struct snode node; 在鏈結串列模組一共使用兩個指標first和last分別指向串列的第一個和最後一個節點，如下： static node *first = NULL; static node *last = NULL;

15 11-3 基本鏈結串列-插入節點 在串列插入新節點，因為節點位置的不同，可以分為三種情況，如下所示：
將節點插入串列第一個節點之前：只要將新節點的指標指向串列的第一個節點，指向新節點的指標就成為串列的first指標。 將節點插入串列最後一個節點的後面：將串列最後一個節點的指標指向新節點，然後將新節點的指標指向null，last指標指向新節點。 將節點插在串列的中間：如果節點是插在p和q節點指標之間，p是指向q的前一個節點，只需將p指標指向新節點，然後將新節點指標指向q，即可插入節點。

16 11-3 基本鏈結串列-插入中間節點圖例

17 11-3 基本鏈結串列-刪除節點 在鏈結串列刪除節點，依照節點的位置分為三種情況，如下所示：
刪除串列的第一個節點：只需將串列指標first指向下一個節點。 刪除串列內的最後一個節點：只要將指向最後一個節點的指標指向null，last指標指向前一個節點，此時需要使用走訪方式找到last的前一個節點指標。 刪除串列的中間節點：只要將本來指向刪除節點的指標，改為指向刪除節點的下一個節點，就可以刪除中間節點。

18 11-3 基本鏈結串列-刪除中間節點圖例

19 11-3 基本鏈結串列-節點走訪 「走訪」（Traverses）的目的是為了存取節點資料，因為在串列取得第n個節點的資料，需要走訪到第n-1個節點後，才能知道第n個節點在那裡。在C程式是使用while迴圈走訪整個串列，如下所示： node *current = first; while ( current != NULL ) { if ( data == current->data ) isFound = TRUE; current = current->next; }

20 11-4 堆疊與佇列 堆疊 佇列

21 堆疊-說明 「堆疊」（Stacks）屬於一種抽象資料結構， 也就是說，它可以使用多種方式設計這種資料 結構，例如：陣列或串列，如下圖所示：

22 11-4-1 堆疊-特性 堆疊資料結構擁有兩種特性，如下所示： 只允許從堆疊的頂端存取資料。
資料存取的順序是後出先進（Last Out, First In），也就是後存入堆疊的資料，反而先行取出。

23 堆疊-函數 堆疊的節點結構是直接使用上一節的串列，筆者 使用list.c和list.h模組擴充建立stack.h和 stack.c模組，新增堆疊的3種操作函數，如下表 所示：

24 佇列-說明 「佇列」（Queues）是一種和堆疊十分相似的資料結構，其主要的用途是作為資料存取的緩衝區，如下圖所示：

25 11-4-2 佇列-特性 佇列資料結構擁有兩種特性，如下所示： 從佇列的一端存入資料，從另一端讀取資料。
資料存取的順序是先進先出（First In, First Out），也就是先存入佇列的資料，先行取出。

26 佇列-函數 如同堆疊資料結構，直接使用list.h和list.c的串列模組建立佇列的queue.h和queue.c模組，新增佇列的3種操作函數，如下表所示：

27 11-5 二元樹-樹狀結構 樹狀結構是模仿真實樹木的架構，只是將 它倒立顯示，樹根稱為「根節點」 （Root），在根節點下如同樹的樹枝一般， 可以擁有0到n個「子節點」（Children）。

28 11-5 二元樹-定義 「二元樹」（Binary Tree）屬於樹狀結構的一種特例，樹的「節點」（Nodes）最多只能擁有2個子節點，其基本定義如下所示： 二元樹的節點個數是有限，而且可以沒有節點。 二元樹的每一個節點下可以分為兩個子樹稱為「左子樹」（Left Subtree）和「右子樹」（Right Subtree）。

29 11-5 二元樹-圖例 一棵二元樹的範例，如下圖所示：

30 11-5 二元樹- tnode節點結構 tnode節點結構的宣告，如下所示： 在二元樹模組擁有指標變數root指向二元樹的根節點，如下所示：
struct tnode { int data; struct tnode *left; /* 參考左子樹 */ struct tnode *right; /* 參考右子樹 */ }; typedef struct tnode treeNode; 在二元樹模組擁有指標變數root指向二元樹的根節點，如下所示： static treeNode *root = NULL;

31 11-5 二元樹-插入節點 insertTree()函數是在二元樹插入節點，使用的方法是建立一棵「二元搜尋樹」（Binary Search Trees），其特性如下： 二元樹的每一個節點值都不同，整棵樹中的每一個節點都擁有不同的值。 每一個節點的資料大於左子節點（如果有的話）的資料，但是小於右子節點（如果有的話）的資料。 左、右兩棵子樹也是一棵二元搜尋樹。

32 11-5 二元樹-走訪 二元樹的走訪可以顯示所有節點資料，屬於一種遞迴走訪，因為遞迴函數中遞迴呼叫的排列順序不同，可以分為三種走訪方式，如下所示： 中序走訪方式（Inorder Traversal）。 前序走訪方式（Preorder Traversal）。 後序走訪方式（Postorder Traversal）。

33 11-5 二元樹-中序走訪 中序走訪的inOrder()函數顯示整棵二元樹的節點資料，如下所示：
static void inOrder(treeNode *node) { if ( node != NULL ) { inOrder(node->left); printf("[%d]", node->data); inOrder(node->right); }

34 11-6 資料排序 排序的基礎 泡沫排序法 快速排序法

35 11-6-1 排序的基礎 排序的工作是將一些資料依照特定的原則排列成遞增或遞減的順序。例如：整數陣列data的內容，如下所示：
data[0]=89 date[1]=34 date[2]=78 date[3]=45 陣列data以整數大小將陣列元素依遞增的順序排序，排序的結果如下所示： data[0]=34 date[1]=45 date[2]=78 date[3]=89 陣列data已經排序，其大小順序如下所示： data[0] < data[1] < data[2] < data[3]

36 泡沫排序法-說明 「泡沫排序法」（Bubble Sort）使用交換方式進行排序，將較小的元素逐漸搬移到陣列的開始，較大的元素慢慢的浮往陣列的最後，如同水缸中的泡沫，慢慢往上浮，故稱為泡沫排序法。

37 11-6-2 泡沫排序法-排序過程 使用陣列來說明排序過程，首先使用交換方法找尋數值陣列中的最大值，原來的陣列內容，如下所示：
data[0]=89 date[1]=34 date[2]=78 date[3]=45 陣列在第二層迴圈依序比較陣列索引0和1的元素，索引1和2，索引2和3，如果各組的第1個元素比較大，就交換陣列元素，如下所示： data[0]=89 > date[1]=34 => data[0]=34 date[1]=89 交換 data[1]=89 > date[2]=78 => data[1]=78 date[2]=89 交換 data[2]=89 > date[3]=45 => data[2]=45 date[3]=89 交換

38 快速排序法-說明 在目前多種的排序方式中，C.A.Hoare發明的「快速排序法」（Quick Sort）是公認最佳的排序方法，快速排序法是使用分割資料方式來增進排序效率，如下圖所示：

39 11-6-3 快速排序法-步驟 Step 1：選擇一個陣列元素為分割的標準元素，本節的程式範例是選擇第一個陣列元素35。

40 11-7 資料搜尋 搜尋的基礎 線性搜尋法 二元搜尋法

41 11-7-1 搜尋的基礎 搜尋是在資料中找出是否存在與特定值相同的資料，搜尋的值稱為「鍵值」（Key），如果資料存在，就進行後續的資料處理。
搜尋方法依照搜尋的資料分為兩種，如下所示： 沒有排序的資料：針對沒有排序的資料執行搜尋，需要從資料的第1個元素開始比較，從頭到尾以確認資料是否存在。 已經排序的資料：搜尋就不需要從頭開始一個個的比較。例如：在電話簿找電話，相信沒有人是從電話簿的第一頁開始找，而是直接從姓名出現的頁數開始找，這是因為電話簿已經依照姓名排序好了。

42 線性搜尋法 「線性搜尋法」（Sequential Search）是從陣列的第1個元素開始走訪整個陣列，然後一個一個比較是否擁有搜尋值，因為需要走訪整個陣列，陣列資料是否排序就無所謂。 int sequential(int *data, int count, int target) { int i; /* 搜尋迴圈 */ for ( i = 0; i < count; i++ ) if ( data[i] == target ) return i; return -1; }

43 11-7-3 二元搜尋法-說明 「二元搜尋法」（Binary Search）也是一種分割資料的搜尋方法，搜尋的資料需要是已經排好序的資料。
二元搜尋法先檢查排序資料的中間元素，如果與鍵值相等就是找到，如果小於鍵值，表示資料是在前半段，否則在後半段。然後繼續分割半段資料重覆上述操作，直到找到或已經沒有資料可以分割為止。

44 二元搜尋法-三種情況 例如：陣列data的上下範圍分別是low和high，中間元素是(low + high)/2。在執行二元搜尋時可以分成三種情況，如下所示： 搜尋鍵值小於陣列的中間元素：鍵值在資料陣列的前半部。 搜尋鍵值大於陣列的中間元素：鍵值在資料陣列的後半部。 搜尋鍵值等於陣列的中間元素：找到搜尋的鍵值。

45 11-7-3 二元搜尋法-函數 int binary(int *data, int low, int high, int target) {
int middle; if (low > high) { return -1; } else { /* 取得中間索引 */ middle = (low + high) / 2; if ( target == data[middle] ) /* 找到 */ return middle; /* 傳回索引值 */ else if ( target < data[middle] )/* 前半部分 */ return binary(data,low,middle-1,target); else // 後半部分 return binary(data,middle+1,high,target); }