演算法 陣列 鏈結串列 堆疊與佇列 樹狀結構 搜尋 第15章 資料結構理論與實務 演算法 陣列 鏈結串列 堆疊與佇列 樹狀結構 搜尋

前言 資料結構 分析或探討計算機中資料的各種特性和衍生的儲存結構 各種數量化描述的相關演算法(Algorithm) 藉以提升中大型軟體系統的執行績效 討論如何將資料儲存在電腦的運用方式 例如陣列、鏈結串列、樹狀結構、堆疊、佇列 最佳化程式設計的方法論 討論到儲存的資料 考慮到彼此之間的關係與運算

演算法 演算法(Algorithm) 在任何一種使用電腦解決問題的過程中 通常的情況就是要先 進行問題的描述 系統的規劃安排 透過某種能與電腦溝通的介面來讓電腦執行 對任何一種電腦的應用系統而言 有效率的規劃問題流程 扮演著電腦系統績效成敗的關鍵角色

資料與資訊 資料(Data)與資訊(Information)的定義 「資料」(Data)的定義形容 例如 一種沒有評估價值的基本項目或原素(Atom) 包括文字、數字、圖等 例如 報紙上的文字 學校的成績單 郵寄信件地址等 都是一種資料

資料與資訊 資訊(Information) 「資訊革命」 將資料經過適當的整理或分析之後 得到具備某種有特別意義的文字、數字或符號 資訊的處理和電腦的應用是息息相關 如何掌握資訊、利用資訊 個人或事業體發展成功的重要原因

演算法的定義(1) 演算法定義 任何演算法，必須滿足以下5種原則 一種「計算方法或法則」 解決某一個工作或問題 所需要的一些有限個數的指令或步驟 任何演算法，必須滿足以下5種原則 有限性(Finiteness) 在有限的步驟內解決問題，而且不可造成無窮迴路 演算法和程序(procedure)是有所區別 因為程式不一定要滿足有限性的要求 如作業系統或機器上的運作程式

演算法的定義(2) 任何演算法，必須滿足以下5種原則（續） 有效性(Effectiveness) 每個步驟或運算若交給人們用筆或紙計算 在有限時間內達成同樣效果 明確性(Definiteness) 每一個步驟或指令必須要敘述的十分清楚 不可以模糊不清 輸入資料(Input) 演算法的輸入資料 可有可無，零或一個以上都可以 輸出資料(Output) 演算法的結果 一定要有一或一個以上的輸出資料

演算法的定義(3) 演算法 在演算法中 演算法和「程序」(Procedure)是不同 表達問題的觀念流程 以適當的資料結構來描述問題中抽象或具體的事物 還得定義資料結構本身有哪些操作 演算法和「程序」(Procedure)是不同 程序不要求必須具有限性 可以容許無窮迴路（無限性）

演算法的工具(1) 能夠清楚、明白、符合演算法的五項基本原則 表達演算法的工具 一般文字 虛擬語言(Pseudo-language) 表格或圖形、流程圖 任何一種程式語言 流程圖 圖形演算法

演算法的工具(2) 流程圖(Flow Diagram) 最為通用的表示法 繪製者應先安排好 版面的位置分配 程式流程圖符號

演算法績效評估(1) 程式或演算法的效能分析 「時間複雜度」(Time Complexity) 著重在以執行時間為主 例如在程式設計中 決定程式區段的「步驟計數」的精確次數 絕對是一件困難的工作 「時間複雜度」(Time Complexity) 一種「概量」精神做為衡量準則 「漸近式表示法」(Asymptotic Notation)的應用

演算法績效評估(2) Big-Oh ( 唸成“big-o”) 分析演算法在所有可能的輸入組合下 最多所需要的時間 例如定義一個T(n) 在一個完全理想狀態的計算機中， 程式執行所花費的時間 一個程式的執行時間並不完全和輸入量有關 演算法的好壞也有影響 當作輸入量n的一種函數

演算法績效評估(3) 若某演算法的執行時間T(n)的時間複雜度是O(f(n)) 也就是T(n) ＝O(f(n)) 意謂存在兩個常數c與n0 若n≧n0，則T(n)≦cf(n) 例如執行時間T(n)＝2n3＋3n2＋n＋7 它的時間複雜度： 首先必須找出c和n0 可得當n0 ＝0，c＝6時 2n3＋3n2 ＋n≦6n3 所以時間複雜度為O(n3)

演算法績效評估(4) 時間複雜度 事實上只是表示實際次數的一個量度層級 不是真實的執行次數

SPARKS語言(1) SPARKS 語言 SPARKS 語法及規則 指令介紹(Assignment Statement) 屬於一種「虛擬語言」 提供程式語言外較不嚴謹、且淺顯易懂的表示法 避免以某種程式語言實作時 在型態和定義上所要花費的功夫 SPARKS 語法及規則 演算法的名稱及相關傳遞的參數 指令與流程 相關註解 指令介紹(Assignment Statement) 變數←表示式或數值

SPARKS語言(2) 運算子(Operators) 布林運算子(Boolean Operator) true、false 邏輯運算子(Logical Operator) and、or、not 關係運算子(Relational Operator) ≥、>、=、≠、<、≤ 數學運算子(Arithmetic Operator) 如+、-、**、*、/、%（mod 符號）

SPARKS語言(3) while 和repeat 指令 迴圈 loop 指令與for 指令

SPARKS語言(4) if 指令與case 指令

SPARKS語言(5) 離開指令(Exit Statement) 範例 Exit 跳出迴圈 Return 返回呼叫程式或傳回值 描述串列反轉的演算法

SPARKS語言(6) 範例

SPARKS語言(7) 範例

演算法的應用(1) 演算法的應用 排序(Sorting) 排序的演算法 涵蓋在許多程式設計領域 例如常用的排序、搜尋的技巧與原理 將一群資料按照某一個特定規則重新排列 使其具有遞增或遞減的次序關係 排序的演算法 氣泡排序法 選擇排序法

演算法的應用(2) 氣泡排序法 又稱為交換排序法 由觀察水中氣泡變化構思而成 逐次比較2個相鄰的記錄 若大小順序有誤，則立即對調 掃描一遍後一定有一個記錄被置於正確位置 彷彿氣泡逐漸由水底逐漸冒升到水面上一樣

演算法的應用(3) 氣泡排序法（續） 五筆資料26、5、37、1、61用氣泡法表示步驟及演算法

演算法的應用(4) 氣泡排序法（續） n個元素的氣泡排序法必須執行n-1次掃瞄 以上例而言，共經過4次掃瞄 第一次掃瞄需要作4次的比較 第二次掃瞄需要作3次的比較 第三次掃瞄需要作2次的比較 第四次掃瞄需要作1次比較 其總比較次數為4+3+2+1=10(次) 主要在避免重覆比較已完成排序的資料

演算法的應用(5) 快速排序法 假設有n筆R1、R2、R3…Rn記錄 其鍵值為k1、k2、k3…kn ①先假設K的值為第一個鍵值 ②由左向右找出鍵值Ki，使得Ki>K ③由右向左找出鍵值Kj使得Kj <K ④如果i<j，那麼Ki與Kj互換，並回到步驟② ⑤若i≧j則將K與Kj交換 並以j為基準點分割成左右部份 然後再針對左右兩邊進行步驟①至⑤ 直到左半邊鍵值=右半邊鍵值為止

演算法的應用(6) 快速排序法 以快速排序法將資料排序過程 利用以上過程， 將左半部與右半部分別排序，形成遞迴 排序過程

陣列 陣列(Array) 陣列元素 陣列的資料型態 其結構就是一排緊密相鄰的可數記憶體 提供一個能夠直接存取單一資料內容的計算方法 索引 表示該陣列元素是在記憶體空間的第幾個位置 陣列名稱 表示一塊位置緊密相鄰的記憶體空間起始位址 陣列的資料型態 指陣列中所有元素的資料型態 陣列的使用 一維陣列、二維陣列與多維陣列 基本的運作原理都相同

一維陣列(1) 假設A是一維陣列(One-dimension Array)名稱 例如在C/C++中 含有n個元素 即A是n個連續記憶體的集合 (各個元素為A[0],A[1]…A[n-1]) 每個元素的內容為a0,a1…an-1 例如在C/C++中 宣告一個整數的一維陣列score

一維陣列(2) 表示宣告一個一維整數陣列 請注意！ 名稱是score 陣列中可以放入6個整數元素設定值 陣列元素是score[0]、score[1]、score[2]、…score[5] 請注意！ C/C++陣列的第一個元素索引值為0 而不是1 依序排列下去

二維陣列(1) 可視為一維陣列的延伸 在C/C++中 須將二維轉換為一維陣列 例如 一個含有m*n個元素的二維陣列A 宣告一個整數的二維陣列 宣告方式

二維陣列(2) 以arr[3][5]說明 在存取二維陣列中的資料時 arr為一個3列5行的二維陣列 可以視為3*5的矩陣 使用的索引值仍然是由0開始計算 以矩陣圖形說明每個元素的索引值與儲存關係

二維陣列(3) 範例

多維陣列(1) 多維陣列表示法 將arr[2][3][4]三維陣列 視為一維陣列的延伸 例如在C/C++中 宣告一個單精度浮點數的三維陣列 想像成空間上的立方體圖形

多維陣列(1) 範例

鏈結串列 鏈結串列(Linked List) 鏈結串列 一種動態的資料結構 由許多資料連接組合而成的集合體 所有節點串成一列 有多少資料用多少記憶體空間 有新資料加入就向系統要一塊記憶體空間 資料刪除後就把空間還給系統

單向鏈結串列(1) 單向鏈結串列 「串列指標首」 「串列指標尾」 串列中的每一個節點 均不需儲存於連續的記憶體位置 而且是一個指向節點的指標 至少要有兩個或以上的欄位 分別存放資料及鏈結欄位 「串列指標首」 在「單向鏈結串列」中第一個節點 「串列指標尾」 指向最後一個節點的鏈結欄位 設為Null 不指向任何地方

單向鏈結串列(2) 例如 串列A={a，b，c，d，x} 其單向串列資料結構

環狀串列 環狀串列的特點 環狀串列 在串列的任何一個節點 都可以達到此串列內的各節點 做為記憶體工作區與輸出入緩衝區的處理及應用 如果我們將串列的最後一個節點的指標 指向串列結構開始的第一個節點 可以從串列中任一節點來追蹤所有串列的其他節點 無所謂哪一個節點是首節點 建立的過程與單向鏈結串列相似 不同是必須要將最後一個節點指向第一個節點

雙向鏈結串列 雙向鏈結串列資料結構的定義指標 每個節點具有三個欄位 中間為資料欄位 RLINK指向下一個節點 LLINK指向上一個節點 通常加上一個串列首 此串列不存任何資料 其左邊鏈結欄指向串列最後一個節點 而右邊鏈結指向第一個節點 假設ptr為一指向此串列上任一節點的指標

堆疊與佇列 堆疊(Stack)與佇列(Queue) 堆疊 佇列 相當典型的抽象資料型態 後進先出(Last In, Frist Out)的觀念 如自助餐中餐盤由桌面往上一個一個疊放 取用時由最上面先拿 佇列 先進先出(First In, First Out)的觀念 像排隊買火車票時 先到有先買票的權利

堆疊簡介(1) 堆疊的定義 堆疊是一種具有後進先出(LIFO)特性的資料型態 所有的加入與刪除動作，皆在頂端完成 計算機領域中，堆疊的應用

遞迴(1) 遞迴(Recursion) 函數(或稱副程式) 遞迴(Recursion)的定義 程式設計上是好用而且特殊的演算法 屬於一種堆疊的應用 函數(或稱副程式) 不只是能夠被其它函數呼叫(或引用)的程式單元 還提供了自身引用的功能 遞迴(Recursion)的定義 假如一個函數或副程式，是由自身所定義或呼叫的 至少要定義2種條件 包括一個可以反覆執行或呼叫的過程 與一個跳出執行過程的出口

遞迴(2) 遞迴因為呼叫對象的不同，可以區分 直接遞迴(Direct Recursion) 指遞迴函式中，允許直接呼叫該函式本身 間接遞迴(Indirect Recursion) 指遞迴函式中，如果呼叫其他遞迴函式 再從其他遞迴函式呼叫回原來的遞迴函式

遞迴(3) 例如階乘函數 任何問題想以遞迴式來表示 典型遞迴式的範例 3階乘等於3×2×1=6 0階乘則定義為1 以符號“！”來代表階乘 如4階乘，為4! 任何問題想以遞迴式來表示 需要符合兩個條件 一個反覆的過程 一個跳出執行的缺口 秉持這兩個原則，n!可以寫成

遞迴(4) C的演算法程式碼

佇列(Queue) (1) 堆疊一樣都是有序串列的抽象資料型態 不過佇列具備的特性 先進先出(FIFO：FIRST IN，FIRST OUT) 所有的刪除或加入動作 必須在兩端進行

佇列(Queue) (2) 佇列 也同樣可以使用陣列或串列來建立一個佇列 不過堆疊只需一個top 指標指向堆疊頂 佇列則必須使用兩個指標 front指向前端 rear指向尾端

佇列(Queue) (3) 佇列在電腦領域的應用

佇列(Queue) (4) 練習題

環狀佇列(1) 以一種Q(0:n-1)的一維陣列 指標front 指標rear 在製造環形佇列的環形運動 同時Q(0)為Q(n-1)的下一個元素 指標front 永遠以逆時鐘方向指向佇列中第一個元素的前一個位置 指標rear 指向佇列目前的最後位置 當front=(rear+1)%MAX_SIZE，佇列是滿的 當front=rear時，佇列是空的 在製造環形佇列的環形運動 使用「模數(mod)」來達成 運算關係

環狀佇列(2) 把佇列看成環狀結構 不過front和rear的初始值設定為0或-1 Front永遠以逆時鐘方向 指著佇列中第一個元素的前一個位置 Rear 指向佇列目前的最後位置

環狀佇列(3) 環狀佇列變動的圖例說明 比原先的佇列有更好的管理 避免空間無謂的浪費

優先佇列(1) 優先佇列的特色 其中的元素並不以優先順序進出 以每個元素的優先權進出 例如大型電腦的處理作業程序中 對排隊中的工作程序作優先等級的分類 優先等級越高的工作程序 可以搶在等級較低的程序前得到服務 對於其他等級相同的工作 則仍然依照佇列先進先出的原則處理 每一個佇列中的元素 都賦予一個代表優先權的數字 最大的數字就有最高優先權

優先佇列(2) 利用陣列來製作優先佇列的缺點 佇列具有先進先出的特性 經常需要移動大量資料 無法預知需保留多少尾部(Rear)空間給插入的工作使用 以陣列結構實作的優先佇列 佇列具有先進先出的特性 電腦作業系統用來安排電腦執行工作(Job)的優先順序 尤其是多人使用之多工(Multitask)電腦 必須安排每一位使用者都有相等的電腦使用權

樹狀結構 樹狀結構 相當重要的非線性資料結構 樹狀結構的應用 人類社會的族譜或是機關組織 計算機上的MS-DOS、UNIX 作業系統和檔案系統 資料庫的管理系統 設計的原理更是利用樹狀階層的概念

樹(tree) (1) 樹(tree)是另外一種典型的資料結構 描述有分支的結構 樹中的元素以節點(node)來表示 每個節點可代表一些資料和指標組合而成的記錄 節點之間可用樹枝相連 代表支幹(branch)的延伸 具備特點 「樹根」(Root) 特殊的節點 其餘節點分為n≧0個互斥的集合 T1,T2,T3…Tn 每一個子集合本身 是一種樹狀結構及此根節點的子樹

樹(tree) (2) 合法的樹 基本上就是符合樹是 由一個或一個以上的節點所組成 節點間可以互相連結 不能形成無出口的迴圈 例如合法的樹 節點A 為樹根

樹(tree) (3) 與樹相關的基本名詞 分支度(Degree) 每個節點所有的子樹個數 例如像節點Ｂ的分支度為2 D的分支度為3，F、K、I、J等為0 樹的分支度(Degree of a Tree) 樹中所有節點的最大分支度 如圖中節點中最大分支度為3 樹的分支度也為3 樹葉或稱終端節點(Terminal Nodes) 分支度為零的節點 如圖中的K、L、F、G、M、I、J

樹(tree) (4) 非終端節點(Nonterminal Nodes) 樹葉以外的節點 如A、B、C、D、E、H 子點(Children) 某節點所有子樹的樹根 例如：A的子點為B、C、D B的子點為Ｅ、F。 父點(Parent) 若X節點為Y節點的子點 則Y節點為X節點的父點 例如：B的父點為A，G的父點為C

樹(tree) (5) 兄弟(Siblings) 同一個父點的所有子點互稱兄弟 例如：B、C、D為兄弟，H、I、J也為兄弟 階度(Level) 令樹根的階度為1 若某節點的階度為L 則其子點的階度為L+1 例如：Ｋ位於階度4，E、F、G、H、I、J位於階度3 高度(Height) 樹的最大階度 例如：此圖的樹高度為4

樹(tree) (5) 樹林 是由n個互斥樹所組合成 移去樹根即為樹林 例如此圖中移去節點A 祖先(Ancestor) 則為包含三棵樹 即樹根為B、C、D的樹林 祖先(Ancestor) 指從樹根到該節點路徑上所有包含的節點 例如：K的祖先為A、B、E節點 Ｈ的祖先為A、D節點 子孫(Descendant) 為該節點的子樹中所包含任一節點 例如：節點B的子孫為E、F、K、L

樹(tree) (6) 範例

二元樹 (1) 二元樹 又稱為Kunth樹，或有序樹(Order Tree) 由節點所組成的有限集合 這個集合若不是空集合 左子樹(Left Subtree)和右子樹(Right Subtree)所組成 left及right代表指向左邊子樹和右邊子樹的指標 data這個欄位乃是存放該節點(Node)的基本資料 此節點所存放的資料型態宣告為整數

二元樹 (2) 針對樹與二元樹之間的比較作分析 從樹的觀點來看 (a)與(b)是相同的 不需要比較子樹的順序 從二元樹的角度來看

二元樹 (3) 範例

特殊二元樹簡介(1) 歪斜樹(Skewed Binary Tree) 一個二元樹的所有節點都沒有 左子樹(Left Child)或者都沒有右子樹(Right Child)時 左歪斜二元樹(Left-skewed Binary Tree) 右歪斜二元樹(Right-skewed Binary Tree)

特殊二元樹簡介(2) 完滿二元樹(Full Binary Tree) 有一階度為k 的二元樹 若正好有2k-1 個節點樹時 則稱為「完滿二元樹」（Fully Binary Tree of k） k ≥ 0   深度為4 ，共有24-1個節點

特殊二元樹簡介(3) 完整二元樹(Complete Binary Tree) 一個二元樹的深度為k 其所含節點數少於2k-1個 但是節點編號順序和完滿二元樹一樣 如(a)：

特殊二元樹簡介(4) 嚴格二元樹(Strictly Binary Tree) 二元樹中的每一個非終端節點均有非空的左右子樹 如

二元樹的儲存結構(1) 陣列表示法 建立二元樹必須遵守規則 小於父節點的值放在左子節點 大於父節點的值放在右子節點 確保 左子樹的值一定完全小於樹根 右子樹的值一定大於樹根 例如：

二元樹的儲存結構(2) 陣列表示法（續） 其循序的一維陣列表示法為 以陣列表示法來儲存二元樹 如果此二元樹愈接近完滿二元樹 愈節省空間 如果是歪斜樹(Skewed Binary Tree) 最浪費空間 在對樹中的中間節點做插入與刪除時 可能要大量移動來反應節點的變動

二元樹的儲存結構(3) 串列表示法 利用指標及鏈結串列來儲存二元樹 每個節點的結構：

二元樹的儲存結構(4) 使用鏈結串列來表示二元樹的好處 對於節點的增加與刪除相當容易 缺點 很難找到父節點 除非在每一節點多增加一個父欄位。 以上述宣告而言 此節點所存放的資料型態為整數 如果使用C語言的結構指令 可寫成如下的宣告

引線二元樹(1) 相對於樹而言，一個二元樹的儲存方式 如何將二元樹轉變為引線二元樹呢？步驟如下： 可將LINK 欄的浪費從2/3 降為1/2 依然浪費了2n-(n-1)=n+1 個欄位 若將這些浪費的欄位充分利用 使其指到其他節點，這些鏈結指標便稱為引線 如何將二元樹轉變為引線二元樹呢？步驟如下：

引線二元樹(2) 為了分辨左右子樹欄位是引線或正常的鏈結指標 引線二元樹的節點資料結構如下 節點的C語言宣告方式如下： 我們必須再加上兩個欄位LBIT 與RBIT 來加以區別 引線二元樹的節點資料結構如下 節點的C語言宣告方式如下：

引線二元樹(3) 實作如何將下列二元樹轉換為引線二元樹

引線二元樹(4) 以下是完整的引線二元樹示意圖

二元搜尋樹的應用(1) 二分樹 二元搜尋樹T 是一棵二元樹 如果一個二元樹符合每一個節點的資料 大於左子節點且小於右子節點 二分樹方便用來排序及搜尋 二元排序樹 二元搜尋樹 上述兩者是一體兩面，沒有分別 二元搜尋樹T 是一棵二元樹 可能是空集合 或者一個節點包含一個識別字(Identifier) 滿足以下條件：

二元搜尋樹的應用(2) 二元樹搜尋的C 演算法

最佳化二元搜尋樹(1) 最佳化二元搜尋樹 最小搜尋成本 在所有可能的二元搜尋樹中 有最小搜尋成本的二元樹 從延伸二元樹(Extension Binary Tree)

最佳化二元搜尋樹 以下例來比較(a)、(b)二圖的平均搜尋次數 說明它們的延伸二元樹 輕易看出(a)與(b)兩者的搜尋次數不同 在最壞情況下

最佳化二元搜尋樹(3) 在(a)中，平均比較次數為 對(b)而言，平均比較次數為 對(a)與(b) 而言， (b)的搜尋次數還是比較好

最佳化二元搜尋樹(4) 討論(a) 圖延伸二元樹的繪製方法

最佳化二元搜尋樹(5) 討論(b)圖延伸二元樹的繪製方法

最佳化二元搜尋樹(6) 在有加權(Weight)的考慮狀況下 以上(a)、(b)二圖為例 如果每個外部節點有加權值（例如搜尋機率等） 外徑長必須考慮相關加權值 或稱為「加權外徑長」 以下將討論(a)、(b)的加權外徑長：

霍夫曼樹(1) 霍夫曼樹 對一含權值的串列，該如何求其最佳化二元樹： 計算加權值，求取正確的加權外徑長 如有n個權值(q1,q2⋯⋯qn)且構成一個n個節點的二元樹 每個節點外部節點權值為qi 加權徑長度最小的就稱為 「最佳化二元樹」 或「霍夫曼樹」(Huffman Tree) 對一含權值的串列，該如何求其最佳化二元樹：

霍夫曼樹(2)

霍夫曼樹(3) 由這種方法所形成的樹就稱為「最佳化二元樹」 且最小加權外徑長是

霍夫曼樹的應用(1) 資料處理的重要領域 霍夫曼樹可用來進行資料壓縮的演算法 資料的儲存和傳輸 和資料量的大小息息相關 以達成壓縮資料的目的 編碼 解碼 演算法相當簡單 大約可得到50 筆左右資料壓縮率的效果 例如 程式設計時，對於if⋯⋯else 的次數控制

霍夫曼樹的應用(2) 計算學生成績的程式 按成績的高低分為五級 用if 指令寫成下頁型式： 學生在5 個等級中的分佈是不均勻的，分佈機率如下

霍夫曼樹的應用(3) 現在學生10000 人，試分析上面的if 指令 用以上的if 指令畫出的二元樹，如下圖(a) 在執行次數上有何差距？ 用以上的if 指令畫出的二元樹，如下圖(a) 加權外徑長 =>0.05*1+0.15*2+0.4*3+0.3*4+0.1*4=3.15 10000*3.15=31500（次）

霍夫曼樹的應用(4) 如果把五種等級分佈的機率看成加權值 0.05、0.15、0.40、0.30、0.10 步驟如下

霍夫曼樹的應用(5) 得到圖(b)後 再把2 次比較簡化成一次比較的圖(c) (a)，©相差31500-22000=9500（次）

霍夫曼樹的應用(6) 如果加上內節點也加權的話 必須綜合考慮，且規則如下 假設內節點的辨識字為a1、a2⋯⋯an a1<a2<⋯⋯an，其中ai 被搜尋的機率是pi 則任何二元搜尋樹的成功搜尋總成本是 外節點可視為失敗節點 因為不成功的搜尋（即找不到）也是會被執行 令E0、E1⋯⋯En 表示n+1 個不同失敗節點的辨識字 E0 包含所有ai<X<ai+1，被搜尋的機率為qi 則二元搜尋總成本是 其中減１的原因是因為只要找到其上一層 可以判斷出是落於哪一個失敗節點內

霍夫曼樹的應用(7)

堆積樹(1) 可應用於排序法的樹狀結構 最大堆積樹 是一個「完整二元樹」 每個節點的值都大於或等於子節點的值 樹根的值是堆積樹中所有頂點最大 最小堆積樹 每一個節點的值都小於或等於其子節點的值 樹根的值是堆積樹中所有頂點最小

堆積樹(2) 將二元樹轉換成堆積樹 把二元樹轉換成堆積樹的方法 假設我們現在有10 筆資料： 26、5、77、1、61、11、59、15、48、19 如果用陣列儲存 A[1]=26、A[2]=5、A[3]=77⋯⋯ A[10]=19 以二元樹表示，可以得到圖 把二元樹轉換成堆積樹的方法 由上往下(Top-down)法 由下往上(Down-top)法

堆積樹(3) 由上往下(Top-down)法 從陣列A[2] 開始調整（且A[1] 為樹根） 以A[2] 為子節點與父節點比較 如果子節點較大則互換 A(2)=5<A(1)=26(不必互換)，且A(3)=77>A(1)=26=>互換 A[4]=1<A[2]=5(不必互換)，且A(5)=61>A(2)=5(互換)， 再與A(1)=77>A(2)=61 (不必互換) A(6)=11<A(3)=26(不必互換)，A(3)=26<A(7)=59(互換)

堆積樹(4) 又A(8)=15>A(4)=1(互換)，A(9)=48>A(4)=15(互換)

堆積樹(5) 由下往上(Down-top)法 有兩點堆積樹的特性 從A(10) 開始，A(10)<A(5)=>（不必互換） 但A(5)>A(2)，又A(10) 也大於A(2) 又A(4)<A(2)，但A(3)>A(1)，且A(7)>A(1) 有兩點堆積樹的特性

搜尋 (1) 搜尋(Search) 搜尋分為 從資料檔案中找出滿足某些條件的記錄之動作 用以搜尋的條件稱為「鍵值」(Key Value) 內部搜尋 資料量較小的檔案可一次全部載入記憶體以進行搜尋 外部搜尋 資料龐大的檔案便無法全部容納於記憶體中 這種檔案通常均先加以組織化，再存於磁碟中 搜尋時也必須循著檔案的組織性來達成

搜尋 (2) 搜尋的技巧 搜尋常見的方法 靜態搜尋 搜尋過程中，搜尋的表格或檔案的內容不會受到更動 例如符號表的搜尋就是一種靜態搜尋。 動態搜尋 搜尋的表格或檔案的內容可能會更動 例如在樹狀結構中所談的B-tree搜尋 屬於一種動態搜尋的技巧 搜尋常見的方法 循序法 二元搜尋法 插補插入法 雜湊法

循序搜尋法 又稱為「線性搜尋」(Linear Search) 找尋的過程從檔案第一筆開始，依序比較每個鍵值 有可能在第1 筆就找到 在這種情形下僅需一次的比較動作 如果資料在第2 筆、第3 筆……第n 筆 需要的比較次數分別為2、3、4……n 次的比較動作 在平均狀況下 循序搜尋法搜尋一筆資料需要(n+1)/2 的比較次數

二元搜尋法(1) 二元搜尋法(Binary Search) 搜尋一個已排序好的檔案 由中間開始搜尋 若所得的檔案鍵值是遞增 則依照與中間的鍵值Km的比較結果可得

二元搜尋法(2) 二元搜尋法的特性 二元搜尋法 以資料量逐步減半的方式來進行搜尋 每進行一次比較動作 下一次搜尋範圍可縮減為前一次搜尋範圍的一半

插補搜尋法(1) 屬於一種漸近搜尋法 例如查字典中「apple」 其公式為 通常先翻到“ a ”部字頭 再逐步往前或往後找 特別是在均勻分佈 且n值愈大時 插補搜尋法甚至比二元法更好 其公式為  

插補搜尋法(2) 其中有幾點要注意的事項：

雜湊搜尋法(1) 雜湊法(Hasing Search) 重要的是 或稱「赫序法」或「散置法」 透過一個數學函數來計算(或轉換)一個雜湊表中 鍵值所對應的位址 可以直接且快速地找到鍵值所存放的地址 毋需透過循序搜尋的尋找方式 是一種由鍵值至位址之關係轉換 重要的是 任何人透過雜湊搜尋的檔案 不需經過事先的排序

雜湊搜尋法(2) 例如符號表 符號表依照特性 雜湊表(Hash Table) 在電腦上的應用領域很廣泛，包含 組譯程式(Assembler)、編譯程式(Compiler)、 資料庫使用的資料字典 利用提供的名稱來找到對應的屬性 符號表依照特性 靜態表(Static Table) 動態表(Dynamic Table) 雜湊表(Hash Table) 屬於靜態表格中的一種 將相關的資料和鍵值儲存在一個固定大小的表格中