計算機概論 第五章 資料結構 陳維魁/陳邦治 旗標出版社.

Presentation on theme: "計算機概論 第五章 資料結構 陳維魁/陳邦治 旗標出版社."— Presentation transcript:

1 計算機概論 第五章 資料結構 陳維魁/陳邦治 旗標出版社

2 本章重點 二大類主題 在設計程式的過程中經常被用來表示資料的基本工具例如陣列、鏈結串列、堆疊、樹狀結構及圖形等都算是資料的結構
常用的演算法 在設計程式的過程中經常被用來表示資料的基本工具例如陣列、鏈結串列、堆疊、樹狀結構及圖形等都算是資料的結構 在撰寫程式的過程中所經常使用的演算法例如搜尋法、排序法、樹及圖形的追蹤法等都是資料結構所含括的內容 資料結構、演算法及程式設計這三個主題彼此間具有密不可分的關係

3 大綱 陣列(array) 鏈結串列(linked list) 堆疊與佇列(stack and queue) 樹(tree)
搜尋作業(searching) 排序作業(sorting) 圖形(graph) 3 3

4 陣列 陣列主要是由陣列的名稱，維度(dimension)，元素型態以及陣列註標(index)組成 陣列有二項特別的限制
必須配置連續的記憶體空間給陣列元素使用 陣列中所有元素的型態必須完全相同，也就是說每個元素所佔用的記憶體空間必須是相同的

5 範例 若A是一個包含5個元素的陣列，元素的型態為整數。若整數型態資料佔用記憶體的空間為2個位元組，假設配置給陣列A的記憶體位址由100開始，利用A[1]、A[2]、A[3]、A[4]及A[5]來表示陣列的5個元素，則陣列A的所有元素之記憶體空間使用情形將如下圖所示 由上圖知A[1]、A[2]、A[3]、A[4]及A[5]佔用了連續的記憶體空間且因為元素的型態相同，因此使用的記憶體空間也相同

6 陣列儲存方法 陣列在記憶體中的儲存方式 「以列為優先」是在編排陣列中元素之順序時，由最右邊的註標值開始進位
「以列為優先」(row major ordering) 「以行為優先」(column major ordering) 「以列為優先」是在編排陣列中元素之順序時，由最右邊的註標值開始進位 「以行為優先」則是在編排陣列中元素之順序時，由最左邊的註標值開始進位 以列為優先法較符合人類的習慣，因此除了FORTRAN採用「以行為優先」外，其他的程式語言多是採用「以列為優先」

7 範例 請針對二維陣列X[1:3, 1:5]，說明「以列為優先」陣列元素在記憶體中排列的順序

8 範例 請針對二維陣列X[1:3, 1:5]，說明「以行為優先」陣列元素在記憶體中排列的順序

9 陣列求址公式 對於陣列中特定的元素若要知道儲存該元素的記憶體空間之位址，必須利用陣列求址公式來計算 陣列求址公式分為 一維陣列 二維陣列
多維陣列

10 一維陣列求址公式 陣列為X(l:u)，其中l為陣列之註標下限，u為陣列之註標上限，w為每個元素所使用的記憶體空間大小
陣列佔用記憶體空間量：(u- l+1)×w。 陣列X的位址函數L：L(X[i])=α＋w×(i-l) 其中α為陣列X在記憶體中之起始位址

11 一維陣列求址範例 假設一陣列規格如下：int X [1:100]；陣列起始為20，一個整數佔用二個記憶體空間，則X這個陣列佔用的記憶體空間的計算方法如下

12 二維陣列求址公式 陣列為X(l1:u1, l2:u2)，其中l1為陣列左方維度之註標下限，u1為陣列左方維度之註標上限，l2為陣列右方維度之註標下限，u2為陣列右方維度之註標上限 陣列元素個數：(u1- l1+1)×(u2- l2+1) 陣列佔用記憶體空間量：(u1- l1+1)×(u2- l2+1)×w 陣列X的位址函數，分為「以列為優先」及「以行為優先」二種，假設α為陣列X在記憶體中之起始位址： 「以列為優先」位址函數： Lrow (X[i,j])=α＋w×[(i-l1)×(u2- l2+1)+(j-l2)] 「以行為優先」位址函數： Lcolumn (X[i,j])=α＋w×[(j-l2)×(u1- l1+1)+(i-l1)]

13 二維陣列求址範例 假設一陣列規格如下：int X [1:100, 5:90]；陣列起始為20，一個整數佔用二個記憶體空間，則X陣列佔用的記憶體空間的計算方法如下

14 二維陣列求址範例 (cont.)

15 多維陣列求址公式

16 多維陣列求址公式 (cont.)

17 多維陣列求址範例 三維陣列A[1:4;0:5;2:6]，共有幾個元素？ 解：120 分別計算各個維度元素的個數：
「1:4」：有4個元素，「0:5」：有6個元素，「2:6」：有5個元素。 將各個維度元素的個數相乘即為所求：4×6×5＝120。 由以上說明可知，題意的三維陣列A共有120個元素

18 特殊矩陣表示法 矩陣便是二維陣列 介紹三種特殊矩陣表示法 稀疏矩陣(sparse matrix)
下三角矩陣(lower triangular matrix) 上三角矩陣(upper triangular matrix)

19 稀疏矩陣 稀疏矩陣是指矩陣中非零的元素數量很少，常用的表示法有「直接表示法」及「列-行索引表示法」(row-column indexing)二種

20 稀疏矩陣--直接表示法 直接利用二維陣列A來表示稀疏矩陣。因稀疏矩陣共有25個元素， A便需宣告為有25個元素的二維陣列，一個陣列元素存在一個矩陣元素，對應關係如下頁

21 稀疏矩陣--直接表示法 (cont.)

22 稀疏矩陣--列-行索引表示法 int A[S] [3]; 第i個非零項相關資料如下(由左而右，由上而下)： S : 總非零項個數
A [i] [0] : 所在列數 A [i] [1] : 所在行數 A [i] [2] : 值

23 下三角矩陣 「下三角矩陣」是指矩陣內對角線以上(不含對角線)所有元素之值皆為0，如右圖
以列為主序(即依照第一列，第二列，…，第n列之順序)，將「下三角矩陣」依序儲存則，aij元素代表第i列第j行的元素，相當於「下三角矩陣」中第[1+2+…+(i-1)]+j = 個元素 以行為主序(即依照第一行，第二行，…，第n行之順序)把「下三角矩陣」則aij元素代表第i列第j行的元素，相當於「下三角矩陣」中第[n+(n-1)+…+(n-(j-2)]+(i-j)+1 = 個元素

24 上三角矩陣 「上三角矩陣」是指矩陣內對角線以下(不含對角線)所有元素之值皆為0，如右圖所示
以列為主序，將「上三角矩陣」依序儲存則，aij元素代表第i列第j行的元素，相當於「上三角矩陣」中第 個元素 以行為主序把「上三角矩陣」則aij元素代表第i列第j行的元素，相當於「上三角矩陣」中第[1+2+…+(j-1)]+i = 個元素

25 鏈結串列 鏈結串列(linked list)是寫作程式時，常用的一種資料結構。在鏈結串列中是利用指標來表示元素之下一個元素的位址。常用的格式如下 上圖中「資料欄位」用來存放資料內容，若資料項目有多個則可以有多個「資料欄位」，而「鏈結欄位」則是用來存放下一筆資料的位址

26 鏈結串列實例 最後一筆資料的「鏈結欄位」內容為「nil」代表該筆資料的後方已無資料

27 使用鏈結串列資料結構的理由 理由 說明 記憶體空間的管理較有彈性
因為陣列元素存放在記憶體中，需佔用連續的記憶體空間，而鏈結串列的元素不需佔用連續的記憶體位置來存放，只需透過指標值即可得下一個元素的位置，因此鏈結串列對於記憶體空間的管理比較有彈性 資料的插入或刪除較容易 若要對陣列中的元素執行插入(insert)或刪除(delete)的動作，由於可能會牽涉大量資料的搬移，所以需要耗費較多的時間，難度較高；若是對鏈結串列中的元素執行插入或刪除的動作，由於不會涉及資料搬移的動作，只需變動指標的指向即可，所以比較節省時間，難度較低

28 鏈結串列與陣列的比較

29 堆疊 堆疊(stack)是指一有序串列(ordered list) 僅能由一端做加入(add)與刪除(deletion)的動作
此端稱作開口端(或頂端)，而另一端則稱為封閉端(或底端)， 堆疊 先進後出(First In Last Out--FILO) 後進先出(Last In First Out--LIFO)

30 堆疊的操作 堆疊有下列五項主要操作 create (新建一個堆疊) push (加入一新資料項進入堆疊) pop (由堆疊中刪除一個資料項)
top (讀取出堆疊中最頂端的資料項，但堆疊內容未被破壞) isempty (檢查是否為空堆疊)

31 堆疊的操作 – create, 建立一個新的堆疊

32 堆疊的操作 – push, 加入一新資料項進入堆疊

33 堆疊的操作 – pop, 從堆疊中取出一個元素

34 堆疊的操作 – top,從堆疊中讀取最靠近開口端元素之值，但不破壞堆疊之結構

35 堆疊的操作 – isempty,檢驗堆疊是否為空堆疊

36 範例 若有一堆疊，其內的資料為ABCDEF，其中堆疊頂端的資料是F。假設push(X)代表將資料X壓入堆疊中，而pop代表從堆疊頂端取出資料，試問當堆疊的操作順序是push(X)，pop，pop，push(X)，pop，pop，push(X)，push(X)，pop，pop時，完成此序列操作後，堆疊頂端的資料應為何？ ANS: D

37 運算式的轉換 運算式是用來表達計算過程的表示法
例如「a+b」便是對運算元(operand) a與b執行加法運算子(operator)之計算 運算式常見的表示法有中置式(infix)、前置式(prefix)及後置式(postfix)三種 人類習慣採用中置式來表示運算式 計算機的運算則是採用前置式或後置式較為方便 程式設計師利用中置式來表達計算過程，但這些以中置式寫成的敘述，在計算機處理前會先被轉換成前置式或後置式

38 中置式 將運算子擺放在對應運算元的中間 <運算元> <運算子> <運算元>；如：x＋y。

39 前置式(prefix) 將運算子擺放在對應運算元的前面，又稱polish notation
<運算子> <運算元> <運算元>；如：＋xy

40 後置式(postfix) 將運算子擺放在對應運算元的後面，又稱reverse polish notation
<運算元> <運算元> <運算子>；如：xy＋

41 中置式轉換為前置式 將運算式中的運算子以左小括號「(」及右小括號「)」分隔開來，分隔之方式是對每一個運算子加入一組相對應的「(」，「)」且分隔時需考慮運算子運算的優先順序 依照運算子的優先順序對「(」，「)」加入編號 將運算子取代相對應的「(」，並去除剩餘的所有「)」

42 中置式轉為後置式 將運算式中的運算子以左小括號「(」及右小括號「)」分隔開來，分隔之方式是對每一個運算子加入一組相對應的「(」，「)」且分隔時需考慮運算子運算的優先順序 依照運算子的優先順序對「(」，「)」加入編號 將運算子取代相對應的「)」，並去除剩餘的所有「(」

43 範例 若有一中置式為A+B-C*D/E請將其轉換為對應的前置式及後置式

44 範例 請利用堆疊對以下前置式作求值動作： - + A B / * C D E
利用堆疊對「前置式」作求值動作時，必須由右至左來處理，遇到運算元時將運算元push到堆疊中，遇到運算子時由堆疊中pop出二個運算元執行該運算子之運算後，再將結果push回堆疊中

45 範例 請利用堆疊對以下後置式作求值動作： AB+CD*E/-
利用堆疊對「前置式」作求值動作時，必須由左至右來處理，遇到運算元時將運算元push到堆疊中，遇到運算子時由堆疊中pop出二個運算元執行該運算子之運算後，再將結果push回堆疊中

46 範例 考慮下面這一個遞迴公式，其中n是正整數f(n)=f(n-1)×n，f(1)=1請問f(100)是什麼？ 解：100!
本題為求階層值的重要範例，建議由最小的輸入值1開始往目標值100的方向來處理，處理步驟如右

47 佇列 佇列(queue)是一個有序串列，元素的加入與刪除是在不同端進行，所以佇列有先進先出(FIFO)的特性，元素的刪除由前端(front)進行，而元素的插入則由後端(rear)進行

48 範例 若有一佇列，初始時為空佇列。假設Add(X)代表將資料X加入佇列後端，而Delete代表從佇列前端取出資料，試問當佇列的操作順序是Add(A)，Add(B)，Delete，Add (C)，Add (D)，Delete，Add (E)，Add (F)，Delete時，完成此序列操作後，佇列內的資料應為何？ 解：C

49 佇列的操作 佇列有下列五項主要操作，分別是： create (新建一個佇列) add (加入一新資料項進入佇列)
delete (由佇列中刪除一個資料項) front (讀取出佇列中最頂端的資料項，但佇列內容未被破壞) isempty (檢查是否為空佇列)

50 佇列的操作– create, 新建一個佇列

51 佇列的操作 上圖中的佇列有9個元素，編號由4~12，，因此front指標會指向佇列第3個元素處，而rear指標則會指向佇列最後一個元素處(即第12個元素)

52 佇列的操作--add , 加入一新資料項

53 佇列的操作-- delete , 刪除一個資料項

54 佇列的操作-- front , 讀取出佇列中最頂端的資料項，但佇列內容未被破壞

55 佇列的操作-- isempty, 檢查是否為空佇列

56 佇列結構在電腦上的應用 佇列結構在電腦上的應用有作業系統的工作排程(job scheduling)，如印表機之列表工作、輸入出之緩衝區及圖形之寬度優先追蹤(Breadth-First-Search)等應用

57 樹 樹(tree)是由一個或多個節點(node)構成 其中一個節點稱為樹根(root)
若移去樹根節點，剩下的節點可分為n個互斥集合，n  0，每個集合也是一棵樹，稱為樹根節點的子樹(sub-tree)

58 樹的特性 三項必要特性 必須是連通圖(connected graph) 不允許迴路(cycle)
樹中節點數目必須恰比邊的數目多1(假設樹中有x個節點，y個邊，則x = y+1)

59 相關名詞

60 相關名詞(cont.)

61 樹的表示法 常見的樹的表示法有 鏈結串列表示法 串列表示法 范氏圖表示法

62 樹的表示法-- 鏈結串列表示法

63 樹的表示法-- 鏈結串列表示法(cont.)
→ 上圖中「nil」代表該欄位並未指到一存放有資料的節點，也就是「空的」欄位。上圖共有14個節點，鏈結欄位共有14×4=56個，其中只有13個鏈結欄位指到一個真正節點之位置，相當於只有13/56比例的鏈結欄位是存放有意義的資訊，其他鏈結欄位的空間因為存放了「nil」，相當於是一種空間的浪費

64 樹的表示法--串列表示法 串列表示法主要的作法是利用小括號來表示樹狀結構中上、下階層的關係 →

65 樹的表示法--范氏圖表示法 范氏圖法類似數學之集合表示法，樹狀結構中的所有節點都會利用一個圓形來代表。樹狀結構中的子節點的圓形必須在父節點圓形的內部 →

66 二元樹 在樹狀結構中如果每個節點的分支度皆小於或等於2，則此類的樹狀結構可被稱為二元樹(binary tree) 二元樹的定義 可為空集合
有限節點的集合 由一個樹根以及左右兩個子樹所構成的 左右兩個子樹必須是二元樹

67 二元樹與樹的差別 樹不得為空集合，因此「二元樹」不一定是「樹」 二元樹節點的數目大於或等於0個，而樹節點的數目則是大於或等於1個
二元樹有左、右子樹之分，樹則無 樹無子節點個數之限制而二元樹則限制任一節點之子節點個數最多為二個

68 二元樹的定理

69 實例

70 特殊二元樹

71 特殊二元樹

72 二元樹表示法 二元樹表示法 陣列表示法 鏈結串列表示法

73 二元樹表示法 --陣列表示法 (1/3) 將二元樹依完滿二元樹的節點編號後，以一維陣列來儲存此二元樹
儲存方式為以二元樹節點的編號做為陣列的註標值，將節點依編號儲存在陣列中

74 二元樹表示法 --陣列表示法 (2/3) → 由上圖中知節點的編號最大值為15，因此需要一個具有15個元素的一維陣列來儲存
節點編號值有1、2、3、5、6、7、12及15共有8個 陣列中僅註標值為1、2、3、5、6、7、12及15的8個項目中會存放二元樹節點之資料，其他項目則是未存放任何資訊 →

75 二元樹表示法 --陣列表示法 (3/3) 陣列表示法最大的缺點是可能會使得空間利用率不佳。若二元樹為n層右歪斜樹 則空間利用率為n/(2n-1) 如二元樹為七層右歪斜樹，由於一層只有一個節點，因此七層右歪斜樹共有7個節點，編號分別是1、3、7、15、31、63及127，所以需要一個具有127個元素的一維陣列來儲存具有7個節點的七層右歪斜樹，只有7/127的空間被使用，其他的空間並未被使用

76 二元樹表示法--鏈結串列表示法 二元樹若以鏈結串列表示法表示其節點結構如右
其中「data」代表資料欄位，「L-link」代表左子樹鏈結欄位，而「R-link」則是代表右子樹鏈結欄位

77 二元樹表示法--鏈結串列表示法 (cont.)
→

78 二元樹追蹤 二元樹追蹤之目的是要依照某種規定的順序來處理二元樹中的所有節點 依照處理順序的不同，二元樹追蹤法可分為 前序追蹤法 中序追蹤法
後序追蹤法

79 前序追蹤法(preorder traverse)
先追蹤樹根，再追蹤左子樹，最後再追蹤右子樹

80 中序追蹤法(inorder traverse)
先追蹤左子樹，再追蹤樹根，最後再追蹤右子樹

81 後序追蹤法(post-order traverse)
先追蹤左子樹，再追蹤右子樹，最後再追蹤樹根

82 範例 請就右方的二元樹T作前、中、後序追蹤 解： 前序追蹤之結果為：ABDCEGFH 中序追蹤之結果為：BDAGECFH
後序追蹤之結果為：DBGEHFCA

83 範例 若一二元樹是以一維陣列來儲存，資料依序儲存，內容分別為：1,2,3,4,5,6,7。請對該二元樹作前、中、後序追蹤並寫出結果 解：
前序追蹤： 中序追蹤： 後序追蹤：

84 範例 某二元樹的前序追蹤為ABDCEGFH，而中序追蹤為BDAGECFH ，試繪出此二元樹 解：
二元樹的前序追蹤結果的第一個符號必定是樹根 結論：已知前序表示式與中序表示式，可唯一決定出一棵二元樹

85 範例 某二元樹的後序追蹤為DBGEHFCA，而中序追蹤為BDAGECFH ，試繪出此二元樹 解：
二元樹的後序追蹤結果的最後一個符號必定是樹根 結論：已知後序表示式與中序表示式，可唯一決定出一棵二元樹

86 範例 某二元樹的前序追蹤為ABC，而後序追蹤為CBA，試繪出此二元樹 已知前序表示式與後序表示式，對應的二元樹不一定唯一

87 運算式的二元樹表示法 將運算式轉換成相對應的二元樹表示法的主要目的是對此二元樹執行前、中後序追蹤時可得到相對應的前置式、中置式或後置式表示法。轉換法介紹如下： 將運算式依運算子的運算優先順序，適當地加上左右小括號，並依運算順序加上編號 將每一組左右小括號內的運算子及運算元依以下原則處理 運算子做為樹根，左運算元做為左子樹及右運算元做為右子樹 若運算子為單一運算子(unary operator)則該運算子所代表之節點，可只有一子節點

88 範例 請將下列式子轉換成二元樹表示法：(a+b)*c-(d+e)/f 解：
首先，將運算式依運算子的運算優先順序，適當地加上左右小括號，並依運算順序加上編號 (2) (3) (1)

89 二元樹排序法 二元樹除了可以用來作為撰寫程式時的資料結構外，也可使用二元樹來執行排序作業
可執行排序作業的二元樹稱為二元搜尋樹(binary search tree)

90 二元搜尋樹的建立方式 將欲排序的資料依序輸入，第一個輸入的資料做為二元樹的樹根
第二個到最後一個輸入的資料皆會由樹根值開始做比較動作，可能情形有二種 若小於或等於樹根值則輸入資料將往左子樹方向移動，若無左子樹則輸入資料將成為左子樹的樹根節點，否則將繼續與左子樹之樹根值比較大小，移動方向同第一次與二元樹的樹根節點值比較時處理方式相同 若大於樹根值則輸入資料將往右子樹方向移動，若無右子樹則輸入資料將成為右子樹的樹根節點，否則將繼續與右子樹之樹根值比較大小，移動方向同第一次與二元樹的樹根節點值比較時處理方式相同 依此法反覆處理，直到所有輸入資料處理完畢為止 依照上述方式建立的二元樹稱為二元搜尋樹，利用中序追蹤法追蹤二元搜尋樹，輸出的結果即為由小到大之排序結果

91 範例 若輸入資料依序為：5，3，7，6，4，8，2，9，1。請建立相對應的二元搜尋樹
若對此二元搜尋樹執行中序追蹤法得到的結果值為1、2、3、4、5、6、7、8、9恰為由小到大之排序結果

92 二元樹計數問題 「二元樹計數」問題是指當給定二元樹之節點數後，決定二元樹種類個數之問題

93 二元樹計數問題(cont.)

94 樹的二元樹表示法 若有一個節點總數為n的K元樹(K-ary tree)，若每個節點均有K個鏈結欄位，則共有n ×(K-1)＋1個鏈結欄位會指向nil。由於二元樹比一般樹較節省儲存空間(因為可減少nil鏈結欄位之個數)，而且二元樹的追蹤法比較容易處理，所以在實際應用上，一般樹都會轉成二元樹來處理 樹轉成二元樹的作法稱為leftmost-child-next-right-sibling 將各節點的兄弟節點相連。 就某一節點而言，僅保留其與最左的子節點之鏈結欄，其餘子節點的鏈結欄全數刪除 順時針旋轉45度

95 範例 將下列的樹轉換成相對應的二元樹

96 引線二元樹 引線二元樹觀念的提出主要是為了解決大部份的二元樹鏈結欄位會指向「nil」的問題。二元樹的鏈結欄位大約有一半的比例指向「nil」(若二元樹有n個節點，則共有2×n個鏈結欄位，其中有(n-1) 個鏈結欄位會指向子節點之位址，因此將有(n+1) 個鏈結欄位所儲存的內容是「nil」)，「nil」只是代表「沒有子節點」，並非有意義的資訊，若能妥善加以利用，將鏈結欄指向特定節點，便可讓原本未存放有意義資訊的節點的內容，變為可被利用的資訊

97 引線二元樹的節點結構 其中L-tag與R-tag為boolean值，當其值為1時代表對應的L-link或R-link欄位指向子節點；當其值為0時則代表對應的L-link或R-link欄位原本內容為「nil」，此時的L-link或R-link欄位便被稱為引線(thread)，且L-link欄位將指向該節點之中序追蹤結果的前繼節點的位置，而R-link欄位將指向該節點之中序追蹤結果的後繼節點的位置 若使用引線二元樹用途則不需使用堆疊就可作中序追蹤

98 引線二元樹的表示法 若引線二元樹為空集合則表示法如右圖
若二元樹非空集合則將右圖中的「L-tag」欄位設為1，「L-link」欄位則指向二元樹的樹根節點

99 引線二元樹範例 (1/3) 請將下列的二元樹轉換成相對應的引線二元樹 二元樹的鏈結串列表示法

100 引線二元樹範例(2/3)

101 引線二元樹範例(3/3)

102 搜尋 搜尋(searching)是指根據某個鍵值在表格或檔案中找出相對應的資料 依照資料存放位置的不同將搜尋分為二大類：
內部搜尋(internal searching)：可將表格或檔案直接放置在主記憶體中 外部搜尋(external searching)：無法將表格或檔案直接放置在主記憶體中

103 常見的搜尋法 循序搜尋法(sequential search) 二元搜尋法(binary search)
雜湊搜尋法(hashing search)

104 循序搜尋法 循序搜尋法適用於小型檔案且不需要事先排序好資料
由檔案的第一筆(也可是最後一筆)記錄開始搜尋的動作，依照順序一一的比對鍵值直到找到相同的鍵值為止或找完整個檔案未發現符合者為止 優點 作法簡單易懂且資料不需事先排序 缺點 當檔案較大時，處理效率不佳

105 循序搜尋演算法 /* 欲搜尋的檔案名稱F。*/ /* 檔案中記錄的個數n。*/ /* 存放資料鍵值的一維陣列X，元素個數有n個。*/
/* 目前搜尋動作處理的記錄編號i。*/ /* 欲搜尋的鍵值key。*/ /* result=true：找到欲搜尋的鍵值。*/ /* result=false：未找到欲搜尋的鍵值。*/ 假設檔案中的資料筆數有n筆，則利用循序搜尋法最少比較次數為1次，最多比較次數為n次，平均比較次數為n/2次

106 範例 假設有一批資料存放在檔案中如以下的順序：
5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70 若以循序搜尋法尋找「35」，請問必須比對幾次資料才找到「35」 解：7次資料比對動作 依5, 10, 15, 20, 25, 30, 35的順序作資料比對動作，在第7次比對時找到資料35

107 二元搜尋法 二元搜尋法要求必須先將檔案中的資料事先排序好 由檔案的中間開始做搜尋的動作，每次可除去一半的資料

108 二元搜尋演算法 1.搜尋區間設定為所有資料。 2.取出搜尋區間中間位置的資料Dm，假設其鍵值為keym
3.將欲搜尋的鍵值keyGOAL與檔案的中間鍵值 keym 比較 (1)如果keyGOAL＝ keym則Dm即為所要找的資料 (2)如果keyGOAL < keym則搜尋區間設定為原搜尋區間的前半部 (3)如果keyGOAL > keym則搜尋區間設定為原搜尋區間的後半部 重複步驟2和步驟3直到找到資料或搜尋區間的大小變為0（表示該資料不存在）為止。

109 二元搜尋法程式段 /* 欲搜尋的檔案名稱F。*/ /* 檔案中記錄的個數n。*/ /* 欲搜尋的鍵值keyGOAL。*/
/* result=true：找到欲搜尋的鍵值。*/ /* result=false：未找到欲搜尋的鍵值。*/

110 範例 假設有一批資料存放在檔案中如以下的順序：
1, 5, 10, 11, 14, 22, 23, 35, 48, 51, 56, 63, 65, 72, 77 試以二元搜尋法尋找「56」。請列出尋找的順序。 假設題意中的15筆資料存放於陣列X中，儲存方式如下

111

112

113 範例 若檔案中的資料筆數有n筆，請問二元搜尋法的平均時間複雜度(time complexity)為何？空間複雜度(space complexity)為何？ 解： (1)時間複雜度: O(log n) (2)空間複雜度: O(1)

114 雜湊搜尋法 雜湊搜尋法是利用資料的鍵值透過雜湊函數(hashing function)的轉換成為資料在儲存體中存放的位址。雜湊搜尋法所建立的資料儲存在儲存體中並無一定的順序，主要特點為搜尋速度極快但理想的雜湊函數不易設計 雜湊搜尋法的作法 (1)將資料區切割成以bucket為單位。 (2)一個bucket中可包含有數個slot，每個slot中存放一筆記錄 (3)每筆記錄皆具有一個鍵值，可利用數學函式對該鍵值進行計算以取得其存放在儲存裝置中的位址(bucket address)

115 雜湊函數範例 假設s為檔案存放在儲存裝置起始位址，檔案佔用的儲存區空間為n，則雜湊函數f定義如下 f(x)=s+(x mod n)
若s=1000, n=7時，記錄鍵值x與對應的儲存區空間位址如右表 若要搜尋鍵值為8的記錄時，此時必須執行以下敘述： f(8)=1000+(8 mod 7)＝1001 由於結果值為1001，因此到位址1001處便可找到鍵值為8的記錄

116 碰撞現象(collision) 上表中當x=1及x=8時，對應的儲存區空間位址皆為1001，代表鍵值為1及8的二筆不同記錄必須存放在相同的記憶體空間，這個現象被稱為鍵值為1及8的二筆不同記錄發生了碰撞現象。即 if x1x2 then f(x1)=f(x2) ( 碰撞 ) 碰撞現象會影響記錄在儲存區空間的存放位置，因此在設計雜湊函數時應該儘量避免發生碰撞的可能性

117 排序 排序(sorting)是指將一群資料根據資料中某個鍵值(key)，將資料重新安排順序(由大到小或由小到大加以排列)
排序法一般分為內部排序(internal sort)與外部排序(external sort)二種 外部排序：又稱檔案排序(sorting of file)，將欲執行排序的資料一部份存放在主記憶體中，一部份則存放在輔助記憶體中。此種排序法必須同時利用主記憶體及輔助記憶體才能完成工作 內部排序：又稱為陣列排序(sorting of array)，將欲執行排序的資料置於全部主記憶體中進行排序

118 常用的內部排序法 常用的內部排序法 以下將介紹常用的內部排序法，所有的演算法均基於以下的假設
「插入排序法」(insertion sort)、「選擇排序法」(selection sort)、「泡沫排序法」(bubble sort)、「快速排序法」(quick sort)、「合併排序法」(merge sort)、「堆積排序法」(heap sort) 以下將介紹常用的內部排序法，所有的演算法均基於以下的假設 目標：完成將n個元素由小到大之排序作業 X : 代表欲排序的所有記錄之集合，X含有n 個待排序的記錄分別是X1、X2、…及Xn，而其鍵值則分別是X[1]、X[2]、…及X[n]

119 插入排序法 加一個虛擬記錄(dummy record)於所有資料的前端，而此虛擬記錄的值為必須小於欲排序資料中的最小值。
由左往右掃描，一次處理一個新的值，將此新值插入左邊已排序好的資料中之適當位置

120 插入排序演算法

121 插入排序法實例 (1)先加入虛擬記錄： －∞，5，6，7，8，6*，4，9，1，3，2
(2)由左往右掃描，一次處理一個新的值，將此新值插入左邊已排序好的資料中之適當位置。在插入排序法中每次處理一個新的值的動作稱為一個pass

122 插入排序法實例 (3)各階段完成之工作如下所示：

123 穩定排序法/不穩定排序法 若一檔案中含有二個或二個以上相同的鍵值，則這些相同的鍵值經由排序動作處理後若仍維持原來的順序則可稱此排序法為穩定排序法，否則即為不穩定排序法

124 時間複雜度 最差時間複雜度是指演算法執行時所需要的最多執行步驟數 平均時間複雜度則是指所有可能狀況下的平均執行步驟數

125 插入排序法結論 插入排序法為穩定排序法 平均時間複雜度為O(n2)及最差時間複雜度為O(n2)，而空間複雜度則為 O(1) 時間複雜度分析：
若使用插入排序法排序n筆資料，執行第一次處理時，必須做一次比較動作，執行第二次處理時，必須做二次比較動作，依此類推，執行第n次處理時，必須做n次比較動作，所以總比較次數為(1+2+…+n)。由以上分析知插入排序法之平均時間複雜度及最差時間複雜度均為O(n2)

126 選擇排序法 選擇排序法的作法相當直覺而且簡單，但是由於效率並不十分理想，所以當要處理的資料筆數較多時，不建議採用選擇排序法 選擇排序法作法
1.由左往右掃描 2.每掃描一次就找出欲排序資料中具最小值的資料，並與此資料列中最左邊的元素對調 重覆步驟1和2共n次，直到所有資料皆處理完畢為止

127 選擇排序演算法

128 選擇排序法實例 請以選擇排序法來排序下列資料： 5，6，7，8，6*，4，9，1，3，2（以“*”來區分相同鍵值）

129

130 選擇排序法結論 選擇排序法處理的檔案中若含有二個或二個以上相同的鍵值(如本題中的6及6*)，由於這些相同的鍵值經由排序動作處理後可能會改變原來的順序，因此選擇排序法為不穩定排序法 平均時間複雜度為O(n2)及最差時間複雜度為O(n2)，而空間複雜度則為 O(1) 若使用選擇排序法排序n筆資料，執行第一次處理(pass)時，必須做(n-1)次比較動作，執行第二次處理時，必須做(n-2)次比較動作，依此類推，執行第(n-1)次處理時，必須做1次比較動作，所以總比較次數為(n-1)+(n-2)+…+1 由以上分析知選擇排序法之平均時間複雜度及最差時間複雜度均為O(n2)

131 氣泡排序法 氣泡排序法的特色是每執行完一個階段的處理，便會將待排序資料中的最大項資料「推」到待排序資料的最右方，就像是氣泡由水底浮到水面的過程一樣 氣泡排序法作法 1.由左往右掃描。 2.將欲排序的資料作兩兩相鄰的比較動作，較小的元素在左，較大的元素在右，當掃瞄完一次欲排序的資料後將至少有一個資料已在正確的位置 3.重覆步驟1和2共 n-1次；或重覆步驟1和2直到資料無互換動作為止

132 氣泡排序演算法

133 氣泡排序法實例 請以氣泡排序法來排序下列資料： 5，6，7，8，6*，4，9，1，3，2（以"*"來區分相同鍵值）

134

135

136

137

138

139

140 氣泡排序法結論 氣泡排序法處理的檔案中若含有二個或二個以上相同的鍵值(如本題中的6及6*)，由於這些相同的鍵值經由排序動作處理後不會改變原來的順序，因此氣泡排序法為穩定排序法 平均時間複雜度為O(n2)及最差時間複雜度為O(n2)，而空間複雜度則為 O(1) 若使用氣泡排序法排序n筆資料，執行第一次處理(pass)時，必須做(n-1)次比較動作，執行第二次處理時，必須做(n-2)次比較動作，依此類推，執行第(n-1)次處理時，必須做1次比較動作，所以總比較次數為(n-1)+(n-2)+…+1。由以上分析知氣泡排序法之平均時間複雜度及最差時間複雜度均為O(n2)

141 快速排序法 快速排序法是一種具有最佳平均時間複雜度的排序法，因此被廣泛使用 快速排序法又稱為partition exchange sort
快速排序法作法 1.先將欲排序資料中之第一筆資料的值做為定界比較標準(Pivot) 2.每處理完一次處理後，所有比定界比較標準小的元素皆會被搬移到定界比較標準的左邊，所有比定界比較標準大的元素皆會被搬移到定界比較標準的右邊 3.在定界比較標準左邊的元素與在定界比較標準右邊的元素分別再重複執行步驟1~步驟3，直到全部資料排序好為止

142 快速排序演算法 /* swap(A, B)的作用為交換A與B的值*/ /*變數k 被設為定界比較標準*/
/*由左向右找到第一個X[i]  k，由右向左找到第一個X[j]  k*/ /*若i<j則交換X[i]與X[j]的位置，否則將X[low]與X[j]的位置交換*/

143 快速排序法實例 請以快速排序法來排序下列資料： 5，6，7，8，6*，4，9，1，3，2（以"*"來區分相同鍵值）

144

145

146 快速排序法結論 快速排序法處理的檔案中若含有二個或二個以上相同的鍵值(如本題中的6及6*，由於這些相同的鍵值經由排序動作處理後可能會改變原來的順序，因此快速排序法為穩定排序法 平均時間複雜度為O(n×log n)及最差時間複雜度為O(n2) 快速排序法為「Divide and conquer」演算法的一種

147 快速排序法時間複雜度分析

148 (二路)合併排序法 二路合併排序法可為內部或外部排序法。二路合併排序法通常簡稱為合併排序法。作法如下
1.將資料中相鄰的兩個資料為一組互相排列合併。 2.每相鄰的兩組資料互相排列合併成較大的資料組。 3.重覆1.和2.步驟直到所有的資料排列合併成一資料組為止

149 合併排序法的處理原則 若合併排序法中每次合併的資料組數目不限定為2，若每次合併的資料組數目為3則為三路合併排序，若每次合併的資料組數目為4則為四路合併排序 若每次合併的資料組數目為n則為n路合併排序

150 合併排序法範例 請以合併排序法來排序下列資料： 5，6，7，8，6*，4，9，1，3，2（以"*"來區分相同鍵值）

151 合併排序法結論 時間複雜度分析： 若使用合併排序法排序n筆資料，約需log2n次處理，而每次處理所須的處理時間為O(n)，因此共需O(n log n)的時間。所以合併排序法的平均時間複雜度與最差時間複雜度皆為O(n log n)

152 堆積排序法 堆積排序法採用完整二元樹的架構來表示資料，常被用來找出資料中的最大或最小值 堆積排序法作法如下：
1.將所有欲做排序的資料建立成一完整二元樹。 2.將此完整二元樹轉換成堆積樹(heap tree)。堆積樹必須是完整二元樹且每個節點的值均大於或等於子節點的值，因此，堆積樹中樹根的值是所有節點中最大的。 3.將樹根與堆積樹中最後一個元素對調。將原樹根的值去除後將變更後所得的新二元樹再調整成滿足堆積樹的特性，重覆此步驟直到剩下一個節點時為止。(註：每次移去的值加入一個堆疊中) 重覆步驟2及3，直到堆積樹是空集合時為止。 4.輸出堆疊的值即可得一由小到大的排序結果

153 堆積排序演算法

154 堆積排序法實例 請以堆積排序法來排序下列資料： 5，6，7，8，4，9，1，3，2 1.建立成一完整二元樹 2.將此完整二元樹轉換成堆積樹

155 3.輸出9至stack, 將編號最大的節點調整為新樹根

156 5.輸出7至stack, 將編號最大的節點調整為新樹根

157 7.輸出5至stack, 將編號最大的節點調整為新樹根

158 9.輸出3至stack, 將編號最大的節點調整為新樹根
1, 2, 3, 4, 5, 6, 7, 8, 9

159 堆積排序法結論 堆積排序法為不穩定排序法 平均時間複雜度為O(n log n)及最差時間複雜度為O(n log n)
若使用堆積排序法排序n筆資料，共需n次處理(pass)，而每次處理所須的處理時間約為log2n，因此共需O(n log n)的時間。所以堆積排序法的平均時間複雜度與最差時間複雜度皆為O(n log n)

160 各種排序法的比較

161 圖形 圖形(graph)是由「端點」 (vertex)及「端點對所構成的邊」(edge)二個非空集合所構成，一般利用以下的符號來代表對應之元件： V代表端點 E代表邊 G(V,E) 代表圖形 圖形中端點集合表示為V(G)，邊集合表示為E(G)

162 無向圖與有向圖 圖形依邊的型態可分成下列兩類
無向圖(Undirected Graph)：E中的邊無方向性，(x, y) = (y, x)，其中x及y為端點 有向圖(Directed Graph; Digraph)：E中的邊有方向性，<x, y>  <y, x>，其中x及y為端點。在<x, y>中，x是head，y是tail

163 無向圖範例 V(G) = {1, 2, 3, 4, 5}。 E(G) = {(1, 2), (1, 4), (2, 3), (2, 4), (3, 4), (3, 5), (4, 5) }

164 有向圖範例 V(G) = {1, 2, 3, 4, 5}。 E(G) = {<1, 2>, <1, 4>, <2, 3>, <2, 4>, <3, 4>, <4, 5>, <5, 3> }

165 無向圖重要名詞 (1/10) 子圖(subgraph) V(G') V(G) 且 E(G') E(G)
若G'為G的子圖，若且唯若(if and only if)： V(G') V(G) 且 E(G') E(G) 上圖中G1、G2及G3均為G的子圖

166 無向圖重要名詞 (2/10) 相鄰(adjacent) 連接(incident)
圖形中一邊的二端點稱為相鄰。若邊(x, y)是E(G)中的一邊，則端點x與y是相鄰的 連接(incident) 若邊(x, y)是E(G)中的一邊，則邊(x, y)連接端點x與端點y

167 無向圖重要名詞 (3/10) 路徑(path) 在圖形中，路徑是指一組由一連串端點所形成的連續序列 1，2，4，5，3便是一組路徑

168 無向圖重要名詞 (4/10) 路徑長度(path length) 簡單路徑(simple path) 相連(connected)
路徑中包含的邊總數 上圖1，2，4，5，3路徑長度為4 簡單路徑(simple path) 除起點和終點外，其餘節點均不可重覆的路徑 相連(connected) 兩個端點為相連，若且唯若，在這對端點間存在一條路徑

169 無向圖重要名詞 (5/10) 相連圖(connected graph)
若一個圖形相連圖，若且唯若，圖形中之任二端點均有路徑相連。如二元樹(binary tree) 相連圖 非相連圖

170 無向圖重要名詞 (6/10) 完全圖(complete graph)
一個具n個端點的無向圖中任何二端點間均恰有一邊直接相連，則恰具有 個邊。完全圖圖必定是連通圖

171 無向圖重要名詞 (7/10) 多重圖(multi-graph) 簡單圖(simple graph)
圖形中若有兩個端點間的邊數大於或等於2，則此圖形即為多重圖 簡單圖(simple graph) 圖形中，任二端點間最大的邊數為1

172 無向圖重要名詞 (8/10) 分支度(degree) 一端點的分支度是指與該端點相鄰(adjacent)的端點個數

173 無向圖重要名詞 (9/10) 尤拉路徑(Eulerian path)
在一無向圖中，若存在一條路徑可由起點出發，恰經過所有邊一次，最後到達終點(終點與起點不同)，則可稱此路徑為尤拉路徑。尤拉路徑的充分必要條件為除了二個端點的分支度為奇數外，其餘必需均為偶數。尤拉路徑又稱為尤拉鏈結(Eulerian chain)

174 無向圖重要名詞 (10/10) 尤拉循環(Eulerian cycle)
在一無向圖中，若存在一條路徑可由起點出發，恰經過所有邊一次，最後再回到起點(終點與起點相同)，則可稱此路徑為尤拉循環。尤拉循環的充分必要條件所有端點的分支度均為偶數

175 尤拉循環(Eulerian cycle)

176 有向圖重要名詞 (1/3) 完全圖(complete graph) 路徑(path) 相鄰(adjacent)
一個具n個端點的有向圖中任何二端點間均恰有一邊直接相連，則恰具有n(n-1)個邊 路徑(path) 在有向圖形中，路徑是指一組由一連串端點所形成的連續序列，連接端點的邊皆為有向邊 相鄰(adjacent) 端點x adjacent to 端點y，端點y adjacent from 端點x

177 有向圖重要名詞(2/3) 連接(incident) 強連結(strongly connected) 邊E連接端點x 與端點y
在一個有向圖中，任何兩個端點x和y間存在一條路徑從x到y，且存在另一條路徑從y到x

178 有向圖重要名詞 (3/3) 入分支度(in degree) 端點被指向的邊數 出分支度(out degree) 由端點發出的邊數

179 圖形追蹤 圖形追蹤的功能是走訪圖形中每個頂點恰好一次 圖形追蹤法可分為 深度優先搜尋(Depth First Search--DFS)
廣度優先搜尋(Breadth First Search--BFS)

180 深度優先搜尋

181 廣度優先搜尋