引线二元树的节点结构课件.ppt

1、1本章重點本章重點l二大類主題表示資料的基本工具常用的演算法l在設計程式的過程中經常被用來表示資料的基本工具例如陣列、鏈結串列、堆疊、樹狀結構及圖形等都算是資料的結構l在撰寫程式的過程中所經常使用的演算法例如搜尋法、排序法、樹及圖形的追蹤法等都是資料結構所含括的內容l資料結構、演算法及程式設計這三個主題彼此間具有密不可分的關係 2大綱l陣列(array)l鏈結串列(linked list)l堆疊與佇列(stack and queue)l樹(tree)l搜尋作業(searching)l排序作業(sorting)l圖形(graph)2 23陣列陣列 l陣列主要是由陣列的名稱，維度(dimensio

2、n)，元素型態以及陣列註標(index)組成l陣列有二項特別的限制必須配置連續的記憶體空間給陣列元素使用陣列中所有元素的型態必須完全相同，也就是說每個元素所佔用的記憶體空間必須是相同的 4範例 l若A是一個包含5個元素的陣列，元素的型態為整數。若整數型態資料佔用記憶體的空間為2個位元組，假設配置給陣列A的記憶體位址由100開始，利用A1、A2、A3、A4及A5來表示陣列的5個元素，則陣列A的所有元素之記憶體空間使用情形將如下圖所示 由上圖知A1、A2、A3、A4及A5佔用了連續的記憶體空間且因為元素的型態相同，因此使用的記憶體空間也相同 5陣列儲存方法陣列儲存方法 l陣列在記憶體中的儲存方式以

3、列為優先(row major ordering)以行為優先(column major ordering)l以列為優先是在編排陣列中元素之順序時，由最右邊的註標值開始進位l以行為優先則是在編排陣列中元素之順序時，由最左邊的註標值開始進位l以列為優先法較符合人類的習慣，因此除了FORTRAN採用以行為優先外，其他的程式語言多是採用以列為優先 6範例範例 l請針對二維陣列X1:3,1:5，說明以列為優先陣列元素在記憶體中排列的順序 7範例範例l請針對二維陣列X1:3,1:5，說明以行為優先陣列元素在記憶體中排列的順序8陣列求址公式陣列求址公式 l對於陣列中特定的元素若要知道儲存該元素的記憶體空間之位

4、址，必須利用陣列求址公式來計算l陣列求址公式分為一維陣列二維陣列多維陣列 9一維陣列求址公式一維陣列求址公式l陣列為X(l:u)，其中l為陣列之註標下限，u為陣列之註標上限，w為每個元素所使用的記憶體空間大小 l陣列元素個數：(u-l+1)。l陣列佔用記憶體空間量：(u-l+1)w。l陣列X的位址函數L：L(Xi)=w(i-l)其中為陣列X在記憶體中之起始位址 10一維陣列求址範例 l假設一陣列規格如下：int X 1:100；陣列起始為20，一個整數佔用二個記憶體空間，則X這個陣列佔用的記憶體空間的計算方法如下 11二維陣列求址公式二維陣列求址公式l陣列為X(l1:u1,l2:u2)，其中l

5、1為陣列左方維度之註標下限，u1為陣列左方維度之註標上限，l2為陣列右方維度之註標下限，u2為陣列右方維度之註標上限l陣列元素個數：(u1-l1+1)(u2-l2+1)l陣列佔用記憶體空間量：(u1-l1+1)(u2-l2+1)wl陣列X的位址函數，分為以列為優先及以行為優先二種，假設為陣列X在記憶體中之起始位址：以列為優先位址函數：lLrow(Xi,j)=w(i-l1)(u2-l2+1)+(j-l2)以行為優先位址函數：lLcolumn(Xi,j)=w(j-l2)(u1-l1+1)+(i-l1)12二維陣列求址範例l假設一陣列規格如下：int X 1:100,5:90；陣列起始為20，一個整

6、數佔用二個記憶體空間，則X陣列佔用的記憶體空間的計算方法如下 13二維陣列求址範例(cont.)14多維陣列求址公式多維陣列求址公式15多維陣列求址公式多維陣列求址公式(cont.)16多維陣列求址範例l三維陣列A1:4;0:5;2:6，共有幾個元素？l解：120 分別計算各個維度元素的個數：1:4：有4個元素，0:5：有6個元素，2:6：有5個元素。將各個維度元素的個數相乘即為所求：465120。由以上說明可知，題意的三維陣列A共有120個元素 17特殊矩陣表示法特殊矩陣表示法 l矩陣便是二維陣列l介紹三種特殊矩陣表示法稀疏矩陣(sparse matrix)下三角矩陣(lower trian

7、gular matrix)上三角矩陣(upper triangular matrix)18稀疏矩陣稀疏矩陣 l稀疏矩陣是指矩陣中非零的元素數量很少，常用的表示法有直接表示法及列-行索引表示法(row-column indexing)二種 19稀疏矩陣稀疏矩陣-直接表示法直接表示法直接利用二維陣列A來表示稀疏矩陣。因稀疏矩陣共有25個元素，A便需宣告為有25個元素的二維陣列，一個陣列元素存在一個矩陣元素，對應關係如下頁 20稀疏矩陣稀疏矩陣-直接表示法直接表示法(cont.)21稀疏矩陣稀疏矩陣-列列-行索引表示法行索引表示法 lint AS 3;S:總非零項個數A 0 0:總列數A 0 1:總

8、行數A 0 2:非零項總個數l第i個非零項相關資料如下(由左而右，由上而下)：A i 0:所在列數A i 1:所在行數A i 2:值 22下三角矩陣下三角矩陣 l下三角矩陣是指矩陣內對角線以上(不含對角線)所有元素之值皆為0，如右圖 l以列為主序(即依照第一列，第二列，第n列之順序)，將下三角矩陣依序儲存則，aij元素代表第i列第j行的元素，相當於下三角矩陣中第1+2+(i-1)+j=個元素 l以行為主序(即依照第一行，第二行，第n行之順序)把下三角矩陣則aij元素代表第i列第j行的元素，相當於下三角矩陣中第n+(n-1)+(n-(j-2)+(i-j)+1=個元素 23上三角矩陣上三角矩陣 l

9、上三角矩陣是指矩陣內對角線以下(不含對角線)所有元素之值皆為0，如右圖所示 l以列為主序，將上三角矩陣依序儲存則，aij元素代表第i列第j行的元素，相當於上三角矩陣中第 個元素l以行為主序把上三角矩陣則aij元素代表第i列第j行的元素，相當於上三角矩陣中第1+2+(j-1)+i=個元素 24鏈結串列鏈結串列 l鏈結串列(linked list)是寫作程式時，常用的一種資料結構。在鏈結串列中是利用指標來表示元素之下一個元素的位址。常用的格式如下 l上圖中資料欄位用來存放資料內容，若資料項目有多個則可以有多個資料欄位，而鏈結欄位則是用來存放下一筆資料的位址 25鏈結串列實例鏈結串列實例l最後一筆資

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

11、間，難度較低 27鏈結串列與陣列的比較鏈結串列與陣列的比較 28堆疊堆疊 l堆疊(stack)是指一有序串列(ordered list)l僅能由一端做加入(add)與刪除(deletion)的動作l此端稱作開口端(或頂端)，而另一端則稱為封閉端(或底端)，l堆疊先進後出(First In Last Out-FILO)後進先出(Last In First Out-LIFO)29堆疊的操作堆疊的操作 l堆疊有下列五項主要操作create(新建一個堆疊)push(加入一新資料項進入堆疊)pop(由堆疊中刪除一個資料項)top(讀取出堆疊中最頂端的資料項，但堆疊內容未被破壞)isempty(檢查是否為

12、空堆疊)30堆疊的操作堆疊的操作 create,建立一個新的堆疊建立一個新的堆疊 31堆疊的操作堆疊的操作 push,加入一新資料項進入堆疊加入一新資料項進入堆疊 32堆疊的操作堆疊的操作 pop,從堆疊中取出一個元素從堆疊中取出一個元素 33堆疊的操作堆疊的操作 top,從堆疊中讀取最靠近開口從堆疊中讀取最靠近開口端元素之值，但不破壞堆疊之結構端元素之值，但不破壞堆疊之結構 34堆疊的操作堆疊的操作 isempty,檢驗堆疊是否為空堆疊檢驗堆疊是否為空堆疊 35範例範例 l若有一堆疊，其內的資料為ABCDEF，其中堆疊頂端的資料是F。假設push(X)代表將資料X壓入堆疊中，而pop代表從堆

13、疊頂端取出資料，試問當堆疊的操作順序是push(X)，pop，pop，push(X)，pop，pop，push(X)，push(X)，pop，pop時，完成此序列操作後，堆疊頂端的資料應為何？lANS:D 36運算式的轉換運算式的轉換 l運算式是用來表達計算過程的表示法例如a+b便是對運算元(operand)a與b執行加法運算子(operator)之計算l運算式常見的表示法有中置式(infix)、前置式(prefix)及後置式(postfix)三種 l人類習慣採用中置式來表示運算式l計算機的運算則是採用前置式或後置式較為方便l程式設計師利用中置式來表達計算過程，但這些以中置式寫成的敘述，在計算

14、機處理前會先被轉換成前置式或後置式 37中置式中置式 l將運算子擺放在對應運算元的中間 ；如：xy。38前置式前置式(prefix)l將運算子擺放在對應運算元的前面，又稱polish notation ；如：xy 39後置式後置式(postfix)l將運算子擺放在對應運算元的後面，又稱reverse polish notation ；如：xy 40中置式轉換為前置式中置式轉換為前置式 l將運算式中的運算子以左小括號(及右小括號)分隔開來，分隔之方式是對每一個運算子加入一組相對應的(，)且分隔時需考慮運算子運算的優先順序l依照運算子的優先順序對(，)加入編號l將運算子取代相對應的(，並去除剩餘的

15、所有)41中置式轉為後置式中置式轉為後置式 l將運算式中的運算子以左小括號(及右小括號)分隔開來，分隔之方式是對每一個運算子加入一組相對應的(，)且分隔時需考慮運算子運算的優先順序l依照運算子的優先順序對(，)加入編號l將運算子取代相對應的)，並去除剩餘的所有(42範例範例 l若有一中置式為A+B-C*D/E請將其轉換為對應的前置式及後置式 43範例範例 l請利用堆疊對以下前置式作求值動作：-+A B/*C D E l利用堆疊對前置置式作求值動作時，必須由右至由右至左來處理左來處理，遇到運算元時將運算元push到堆疊中，遇到運算子時由堆疊中pop出二個運算元執行該運算子之運算後，再將結果pus

16、h回堆疊中 44範例範例 l請利用堆疊對以下後置式作求值動作：AB+CD*E/-l利用堆疊對前置置式作求值動作時，必須由左至右來處理由左至右來處理，遇到運算元時將運算元push到堆疊中，遇到運算子時由堆疊中pop出二個運算元執行該運算子之運算後，再將結果push回堆疊中 45範例 l考慮下面這一個遞迴公式，其中n是正整數f(n)=f(n-1)n，f(1)=1請問f(100)是什麼？l解：100!本題為求階層值的重要範例，建議由最小的輸入值1開始往目標值100的方向來處理，處理步驟如右 46佇列佇列 l佇列(queue)是一個有序串列，元素的加入與刪除是在不同端進行，所以佇列有先進先出(FIFO

17、)的特性，元素的刪除由前端(front)進行，而元素的插入則由後端(rear)進行 47範例範例 l若有一佇列，初始時為空佇列。假設Add(X)代表將資料X加入佇列後端，而Delete代表從佇列前端取出資料，試問當佇列的操作順序是Add(A)，Add(B)，Delete，Add(C)，Add(D)，Delete，Add(E)，Add(F)，Delete時，完成此序列操作後，佇列內的資料應為何？l解：C48佇列的操作佇列的操作 l佇列有下列五項主要操作，分別是：create(新建一個佇列)add(加入一新資料項進入佇列)delete(由佇列中刪除一個資料項)front(讀取出佇列中最頂端的資料項

18、，但佇列內容未被破壞)isempty(檢查是否為空佇列)49佇列的操作佇列的操作 create,新建一個佇列新建一個佇列50佇列的操作佇列的操作l上圖中的佇列有9個元素，編號由412，因此front指標會指向佇列第3個元素處，而rear指標則會指向佇列最後一個元素處(即第12個元素)51佇列的操作佇列的操作-add,加入一新資料項加入一新資料項52佇列的操作佇列的操作-delete,刪除一個資料項刪除一個資料項53佇列的操作佇列的操作-front,讀取出佇列中最頂端讀取出佇列中最頂端的資料項，但佇列內容未被破壞的資料項，但佇列內容未被破壞54佇列的操作佇列的操作-isempty,檢查是否為空佇

19、列檢查是否為空佇列55佇列結構在電腦上的應用佇列結構在電腦上的應用 l佇列結構在電腦上的應用有作業系統的工作排程(job scheduling)，如印表機之列表工作、輸入出之緩衝區及圖形之寬度優先追蹤(Breadth-First-Search)等應用 56樹樹 l樹(tree)是由一個或多個節點(node)構成l其中一個節點稱為樹根(root)l若移去樹根節點，剩下的節點可分為n個互斥集合，n 0，每個集合也是一棵樹，稱為樹根節點的子樹(sub-tree)57樹的特性樹的特性l三項必要特性必須是連通圖(connected graph)不允許迴路(cycle)樹中節點數目必須恰比邊的數目多1(假

20、設樹中有x個節點，y個邊，則x=y+1)58相關名詞相關名詞59相關名詞相關名詞(cont.)60樹的表示法樹的表示法 l常見的樹的表示法有鏈結串列表示法串列表示法范氏圖表示法 61樹的表示法樹的表示法-鏈結串列表示法鏈結串列表示法62樹的表示法樹的表示法-鏈結串列表示法鏈結串列表示法(cont.)上圖中nil代表該欄位並未指到一存放有資料的節點，也就是空的欄位。上圖共有14個節點，鏈結欄位共有144=56個，其中只有13個鏈結欄位指到一個真正節點之位置，相當於只有13/56比例的鏈結欄位是存放有意義的資訊，其他鏈結欄位的空間因為存放了nil，相當於是一種空間的浪費 63樹的表示法樹的表示法-

21、串列表示法串列表示法l串列表示法主要的作法是利用小括號來表示樹串列表示法主要的作法是利用小括號來表示樹狀結構中上、下階層的關係狀結構中上、下階層的關係 64樹的表示法樹的表示法-范氏圖表示法范氏圖表示法 l范氏圖法類似數學之集合表示法，樹狀結構中的所有節點都會利用一個圓形來代表。樹狀結構中的子節點的圓形必須在父節點圓形的內部 65二元樹二元樹 l在樹狀結構中如果每個節點的分支度皆小於或等於2，則此類的樹狀結構可被稱為二元樹(binary tree)l二元樹的定義可為空集合有限節點的集合由一個樹根以及左右兩個子樹所構成的左右兩個子樹必須是二元樹 66二元樹與樹的差別二元樹與樹的差別 l樹不得為空

22、集合，因此二元樹不一定是樹l二元樹節點的數目大於或等於0個，而樹節點的數目則是大於或等於1個l二元樹有左、右子樹之分，樹則無l樹無子節點個數之限制而二元樹則限制任一節點之子節點個數最多為二個67二元樹的定理二元樹的定理 68實例實例 69特殊二元樹特殊二元樹 70特殊二元樹特殊二元樹71二元樹表示法二元樹表示法 l二元樹表示法陣列表示法鏈結串列表示法 72二元樹表示法二元樹表示法-陣列表示法陣列表示法(1/3)l將二元樹依完滿二元樹的節點編號後，以一維陣列來儲存此二元樹l儲存方式為以二元樹節點的編號做為陣列的註標值，將節點依編號儲存在陣列中73二元樹表示法二元樹表示法-陣列表示法陣列表示法(2

23、/3)l由上圖中知節點的編號最大值為15，因此需要一個具有15個元素的一維陣列來儲存l節點編號值有1、2、3、5、6、7、12及15共有8個l陣列中僅註標值為1、2、3、5、6、7、12及15的8個項目中會存放二元樹節點之資料，其他項目則是未存放任何資訊 74二元樹表示法二元樹表示法-陣列表示法陣列表示法(3/3)l陣列表示法最大的缺點是可能會使得空間利用率不佳。若二元樹為n層右歪斜樹 則空間利用率為n/(2n-1)l 如二元樹為七層右歪斜樹，由於一層只有一個節點，因此七層右歪斜樹共有7個節點，編號分別是1、3、7、15、31、63及127，所以需要一個具有127個元素的一維陣列來儲存具有7個

24、節點的七層右歪斜樹，只有7/127的空間被使用，其他的空間並未被使用 75二元樹表示法二元樹表示法-鏈結串列表示法鏈結串列表示法 l二元樹若以鏈結串列表示法表示其節點結構如右 l其中data代表資料欄位，L-link代表左子樹鏈結欄位，而R-link則是代表右子樹鏈結欄位 76二元樹表示法二元樹表示法-鏈結串列表示法鏈結串列表示法(cont.)77二元樹追蹤 l二元樹追蹤之目的是要依照某種規定的順序來處理二元樹中的所有節點l依照處理順序的不同，二元樹追蹤法可分為前序追蹤法中序追蹤法後序追蹤法 78前序追蹤法前序追蹤法(preorder traverse)l先追蹤樹根，再追蹤左子樹，最後再追蹤右

25、子樹 79中序追蹤法中序追蹤法(inorder traverse)l先追蹤左子樹，再追蹤樹根，最後再追蹤右子樹 80後序追蹤法後序追蹤法(post-order traverse)l先追蹤左子樹，再追蹤右子樹，最後再追蹤樹根 81範例範例 l請就右方的二元樹T作前、中、後序追蹤l解：前序追蹤之結果為：ABDCEGFH 中序追蹤之結果為：BDAGECFH 後序追蹤之結果為：DBGEHFCA 82範例範例l若一二元樹是以一維陣列來儲存，資料依序儲存，內容分別為：1,2,3,4,5,6,7。請對該二元樹作前、中、後序追蹤並寫出結果 l解：前序追蹤：1245367中序追蹤：4251637後序追蹤：452

26、6731 83範例範例l某二元樹的前序追蹤為ABDCEGFH，而中序追蹤為BDAGECFH，試繪出此二元樹 l解：二元樹的前序追蹤結果的第一個符號必定是樹根 l結論：已知前序表示式結論：已知前序表示式與中序表示式，可唯一與中序表示式，可唯一決定出一棵二元樹決定出一棵二元樹 84範例範例l某二元樹的後序追蹤為DBGEHFCA，而中序追蹤為BDAGECFH，試繪出此二元樹 l解：二元樹的後序追蹤結果的最後一個符號必定是樹根 l結論：已知後序表示式與中序表示式，可唯一決定出一棵二元樹 85範例範例l某二元樹的前序追蹤為ABC，而後序追蹤為CBA，試繪出此二元樹 l已知前序表示式與後序表示式，對應的二

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

28、，適當地加上左右小括號，並依運算順序加上編號(1)(2)(3)88二元樹排序法 l二元樹除了可以用來作為撰寫程式時的資料結構外，也可使用二元樹來執行排序作業l可執行排序作業的二元樹稱為二元搜尋樹(binary search tree)89二元搜尋樹的建立方式 l將欲排序的資料依序輸入，第一個輸入的資料做為二元樹的樹根l第二個到最後一個輸入的資料皆會由樹根值開始做比較動作，可能情形有二種若小於或等於樹根值則輸入資料將往左子樹方向移動，若無左子樹則輸入資料將成為左子樹的樹根節點，否則將繼續與左子樹之樹根值比較大小，移動方向同第一次與二元樹的樹根節點值比較時處理方式相同若大於樹根值則輸入資料將往右子

29、樹方向移動，若無右子樹則輸入資料將成為右子樹的樹根節點，否則將繼續與右子樹之樹根值比較大小，移動方向同第一次與二元樹的樹根節點值比較時處理方式相同l依此法反覆處理，直到所有輸入資料處理完畢為止l依照上述方式建立的二元樹稱為二元搜尋樹，利用中序追蹤法追蹤二元搜尋樹，輸出的結果即為由小到大之排序結果 90範例l若輸入資料依序為：5，3，7，6，4，8，2，9，1。請建立相對應的二元搜尋樹 若對此二元搜尋樹執行中序追蹤法得到的結果值為1、2、3、4、5、6、7、8、9恰為由小到大之排序結果 91二元樹計數問題二元樹計數問題 l二元樹計數問題是指當給定二元樹之節點數後，決定二元樹種類個數之問題92二元

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

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

32、對應的L-link或R-link欄位原本內容為nil，此時的L-link或R-link欄位便被稱為引線(thread)，且L-link欄位將指向該節點之中序追蹤結果的前繼節點的位置，而R-link欄位將指向該節點之中序追蹤結果的後繼節點的位置l若使用引線二元樹用途則不需使用堆疊就可作中序追蹤 97引線二元樹的表示法引線二元樹的表示法 l若引線二元樹為空集合則表示法如右圖 l若二元樹非空集合則將右圖中的L-tag欄位設為1，L-link欄位則指向二元樹的樹根節點 98引線二元樹範例引線二元樹範例(1/3)l請將下列的二元樹轉換成相對應的引線二元樹 二元樹的鏈結串列表示法二元樹的鏈結串列表示法 9

33、9引線二元樹範例引線二元樹範例(2/3)100引線二元樹範例引線二元樹範例(3/3)101搜尋搜尋 l搜尋(searching)是指根據某個鍵值在表格或檔案中找出相對應的資料l依照資料存放位置的不同將搜尋分為二大類：內部搜尋(internal searching)：可將表格或檔案直接放置在主記憶體中外部搜尋(external searching)：無法將表格或檔案直接放置在主記憶體中102常見的搜尋法常見的搜尋法l循序搜尋法(sequential search)l二元搜尋法(binary search)l雜湊搜尋法(hashing search)103循序搜尋法循序搜尋法 l循序搜尋法適用於小

34、型檔案且不需要事先排序好資料l由檔案的第一筆(也可是最後一筆)記錄開始搜尋的動作，依照順序一一的比對鍵值直到找到相同的鍵值為止或找完整個檔案未發現符合者為止l優點作法簡單易懂且資料不需事先排序l缺點當檔案較大時，處理效率不佳 104循序搜尋演算法循序搜尋演算法l/*欲搜尋的檔案名稱F。*/l/*檔案中記錄的個數n。*/l/*存放資料鍵值的一維陣列X，元素個數有n個。*/l/*目前搜尋動作處理的記錄編號i。*/l/*欲搜尋的鍵值key。*/l/*result=true：找到欲搜尋的鍵值。*/l/*result=false：未找到欲搜尋的鍵值。*/假設檔案中的資料筆數有n筆，則利用循序搜尋法最少比

35、較次數為1次，最多比較次數為n次，平均比較次數為n/2次 105範例 l假設有一批資料存放在檔案中如以下的順序：5,10,15,20,25,30,35,40,45,50,55,60,65,70 若以循序搜尋法尋找35，請問必須比對幾次資料才找到35l解：7次資料比對動作 依5,10,15,20,25,30,35的順序作資料比對動作，在第7次比對時找到資料35 106二元搜尋法二元搜尋法 l二元搜尋法要求必須先將檔案中的資料事先排序好l由檔案的中間開始做搜尋的動作，每次可除去一半的資料 107二元搜尋演算法二元搜尋演算法 l1.搜尋區間設定為所有資料。l2.取出搜尋區間中間位置的資料Dm，假設其

36、鍵值為keyml3.將欲搜尋的鍵值keyGOAL與檔案的中間鍵值 keym 比較(1)如果keyGOAL keym則Dm即為所要找的資料(2)如果keyGOAL keym則搜尋區間設定為原搜尋區間的後半部l重複步驟2和步驟3直到找到資料或搜尋區間的大小變為0（表示該資料不存在）為止。108二元搜尋法程式段二元搜尋法程式段 l/*欲搜尋的檔案名稱F。*/l/*檔案中記錄的個數n。*/l/*欲搜尋的鍵值keyGOAL。*/l/*result=true：找到欲搜尋的鍵值。*/l/*result=false：未找到欲搜尋的鍵值。*/109範例範例 l假設有一批資料存放在檔案中如以下的順序：1,5,10

37、,11,14,22,23,35,48,51,56,63,65,72,77 試以二元搜尋法尋找56。請列出尋找的順序。假設題意中的15筆資料存放於陣列X中，儲存方式如下110111112範例範例 l若檔案中的資料筆數有n筆，請問二元搜尋法的平均時間複雜度(time complexity)為何？空間複雜度(space complexity)為何？l解：(1)時間複雜度:O(log n)(2)空間複雜度:O(1)113雜湊搜尋法雜湊搜尋法 l雜湊搜尋法是利用資料的鍵值透過雜湊函數(hashing function)的轉換成為資料在儲存體中存放的位址。雜湊搜尋法所建立的資料儲存在儲存體中並無一定的順序

38、，主要特點為搜尋速度極快但理想的雜湊函數不易設計l雜湊搜尋法的作法(1)將資料區切割成以bucket為單位。(2)一個bucket中可包含有數個slot，每個slot中存放一筆記錄(3)每筆記錄皆具有一個鍵值，可利用數學函式對該鍵值進行計算以取得其存放在儲存裝置中的位址(bucket address)114雜湊函數範例雜湊函數範例 l假設s為檔案存放在儲存裝置起始位址，檔案佔用的儲存區空間為n，則雜湊函數f定義如下f(x)=s+(x mod n)l若s=1000,n=7時，記錄鍵值x與對應的儲存區空間位址如右表 若要搜尋鍵值為8的記錄時，此時必須執行以下敘述：f(8)=1000+(8 mod

39、7)1001由於結果值為1001，因此到位址1001處便可找到鍵值為8的記錄 115碰撞現象(collision)l上表中當x=1及x=8時，對應的儲存區空間位址皆為1001，代表鍵值為1及8的二筆不同記錄必須存放在相同的記憶體空間，這個現象被稱為鍵值為1及8的二筆不同記錄發生了碰撞現象。即 if x1x2 then f(x1)=f(x2)(碰撞)l碰撞現象會影響記錄在儲存區空間的存放位置，因此在設計雜湊函數時應該儘量避免發生碰撞的可能性 116排序排序 l排序(sorting)是指將一群資料根據資料中某個鍵值(key)，將資料重新安排順序(由大到小或由小到大加以排列)l排序法一般分為內部排序

40、(internal sort)與外部排序(external sort)二種外部排序：又稱檔案排序(sorting of file)，將欲執行排序的資料一部份存放在主記憶體中，一部份則存放在輔助記憶體中。此種排序法必須同時利用主記憶體及輔助記憶體才能完成工作內部排序：又稱為陣列排序(sorting of array)，將欲執行排序的資料置於全部主記憶體中進行排序 117常用的內部排序法常用的內部排序法 l常用的內部排序法插入排序法(insertion sort)、選擇排序法(selection sort)、泡沫排序法(bubble sort)、快速排序法(quick sort)、合併排序法(me

41、rge sort)、堆積排序法(heap sort)l以下將介紹常用的內部排序法，所有的演算法均基於以下的假設目標：完成將n個元素由小到大之排序作業X:代表欲排序的所有記錄之集合，X含有n 個待排序的記錄分別是X1、X2、及Xn，而其鍵值則分別是X1、X2、及Xn 118插入排序法插入排序法 l加一個虛擬記錄(dummy record)於所有資料的前端，而此虛擬記錄的值為必須小於欲排序資料中的最小值。l由左往右掃描，一次處理一個新的值，將此新值插入左邊已排序好的資料中之適當位置 119插入排序插入排序演算法演算法 120插入排序法實例插入排序法實例l(1)先加入虛擬記錄：，5，6，7，8，6*

42、，4，9，1，3，2l(2)由左往右掃描，一次處理一個新的值，將此新值插入左邊已排序好的資料中之適當位置。在插入排序法中每次處理一個新的值的動作稱為一個pass121插入排序插入排序法實例法實例l(3)各階段完成之工作如下所示：122穩定排序法/不穩定排序法l若一檔案中含有二個或二個以上相同的鍵值，則這些相同的鍵值經由排序動作處理後若仍維持原來的順序則可稱此排序法為穩定排序法，否則即為不穩定排序法123時間複雜度l最差時間複雜度是指演算法執行時所需要的最多執行步驟數l平均時間複雜度則是指所有可能狀況下的平均執行步驟數124插入排序法結論l插入排序法為穩定排序法l平均時間複雜度為O(n2)及最差

43、時間複雜度為O(n2)，而空間複雜度則為 O(1)l時間複雜度分析：若使用插入排序法排序n筆資料，執行第一次處理時，必須做一次比較動作，執行第二次處理時，必須做二次比較動作，依此類推，執行第n次處理時，必須做n次比較動作，所以總比較次數為(1+2+n)。由以上分析知插入排序法之平均時間複雜度及最差時間複雜度均為O(n2)125選擇排序法 l選擇排序法的作法相當直覺而且簡單，但是由於效率並不十分理想，所以當要處理的資料筆數較多時，不建議採用選擇排序法 l選擇排序法作法1.由左往右掃描2.每掃描一次就找出欲排序資料中具最小值的資料，並與此資料列中最左邊的元素對調重覆步驟1和2共n次，直到所有資料皆

44、處理完畢為止 126選擇排序演算法 127選擇排序法實例l請以選擇排序法來排序下列資料：5，6，7，8，6*，4，9，1，3，2（以“*”來區分相同鍵值）l 128129選擇排序法結論l選擇排序法處理的檔案中若含有二個或二個以上相同的鍵值(如本題中的6及6*)，由於這些相同的鍵值經由排序動作處理後可能會改變原來的順序，因此選擇排序法為不穩定排序法l平均時間複雜度為O(n2)及最差時間複雜度為O(n2)，而空間複雜度則為 O(1)若使用選擇排序法排序n筆資料，執行第一次處理(pass)時，必須做(n-1)次比較動作，執行第二次處理時，必須做(n-2)次比較動作，依此類推，執行第(n-1)次處理時

45、，必須做1次比較動作，所以總比較次數為(n-1)+(n-2)+1由以上分析知選擇排序法之平均時間複雜度及最差時間複雜度均為O(n2)130氣泡排序法氣泡排序法 l氣泡排序法的特色是每執行完一個階段的處理，便會將待排序資料中的最大項資料推到待排序資料的最右方，就像是氣泡由水底浮到水面的過程一樣 l氣泡排序法作法1.由左往右掃描。2.將欲排序的資料作兩兩相鄰的比較動作，較小的元素在左，較大的元素在右，當掃瞄完一次欲排序的資料後將至少有一個資料已在正確的位置3.重覆步驟1和2共 n-1次；或重覆步驟1和2直到資料無互換動作為止 131氣泡排序演算法氣泡排序演算法 132氣泡排序法實例l請以氣泡排序法

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

47、-2)+1。由以上分析知氣泡排序法之平均時間複雜度及最差時間複雜度均為O(n2)140快速排序法 l快速排序法是一種具有最佳平均時間複雜度的排序法，因此被廣泛使用l快速排序法又稱為partition exchange sort l快速排序法作法1.先將欲排序資料中之第一筆資料的值做為定界比較標準(Pivot)2.每處理完一次處理後，所有比定界比較標準小的元素皆會被搬移到定界比較標準的左邊，所有比定界比較標準大的元素皆會被搬移到定界比較標準的右邊3.在定界比較標準左邊的元素與在定界比較標準右邊的元素分別再重複執行步驟1步驟3，直到全部資料排序好為止 141快速排序演算法 l/*swap(A,B)

48、的作用為交換A與B的值*/l/*變數k 被設為定界比較標準*/l/*由左向右找到第一個Xi k，由右向左找到第一個Xj k*/l/*若ij則交換Xi與Xj的位置，否則將Xlow與Xj的位置交換*/142快速排序法實例l請以快速排序法來排序下列資料：5，6，7，8，6*，4，9，1，3，2（以*來區分相同鍵值）143144145快速排序法結論l快速排序法處理的檔案中若含有二個或二個以上相同的鍵值(如本題中的6及6*，由於這些相同的鍵值經由排序動作處理後可能會改變原來的順序，因此快速排序法為穩定排序法l平均時間複雜度為O(nlog n)及最差時間複雜度為O(n2)l快速排序法為Divide and

49、 conquer演算法的一種 146快速排序法時間複雜度分析 147(二路二路)合併排序法合併排序法 l二路合併排序法可為內部或外部排序法。二路合併排序法通常簡稱為合併排序法。作法如下1.將資料中相鄰的兩個資料為一組互相排列合併。2.每相鄰的兩組資料互相排列合併成較大的資料組。3.重覆1.和2.步驟直到所有的資料排列合併成一資料組為止 148合併排序法的處理原則合併排序法的處理原則l若合併排序法中每次合併的資料組數目不限定為2，若每次合併的資料組數目為3則為三路合併排序，若每次合併的資料組數目為4則為四路合併排序l若每次合併的資料組數目為n則為n路合併排序 149合併排序法範例 l請以合併排序

50、法來排序下列資料：5，6，7，8，6*，4，9，1，3，2（以*來區分相同鍵值）150合併排序法結論時間複雜度分析：若使用合併排序法排序n筆資料，約需log2n次處理，而每次處理所須的處理時間為O(n)，因此共需O(n log n)的時間。所以合併排序法的平均時間複雜度與最差時間複雜度皆為O(n log n)151堆積排序法 l堆積排序法採用完整二元樹的架構來表示資料，常被用來找出資料中的最大或最小值l堆積排序法作法如下：1.將所有欲做排序的資料建立成一完整二元樹。2.將此完整二元樹轉換成堆積樹(heap tree)。堆積樹必須是完整二元樹且每個節點的值均大於或等於子節點的值，因此，堆積樹中樹