目錄
第一章 資料結構基礎
1-1 演算法
一、演算法特性
(一)輸入(Input)
(二)輸出(Output)
(三)明確性(Definiteness)
(四)有限性(Finiteness)
(五)有效性(Effectiveness)或正確性(Correctness)
二、演算法工具
(一)工具
(二)舉例
三、其他議題
(一)演算法與程式最大的不同
(二)填魔術方陣的方法
1-2 演算法的分類
一、貪婪法(Greedy Method)
(一)定義
(二)步驟
(三)特性
(四)實例
(五)適用時機
二、各個擊破法(Divide-and-Conquer)
(一)定義
(二)演算法
(三)特性
(四)優點
(五)缺點
(六)適用時機
三、動態規劃(Dynamic Programming)
(一)定義
(二)實例
※Greedy Approach與Dynamic Programming的比較
※子問題重覆(Overlapping Subproblem)
※各個擊破法與動態規劃的比較
四、回溯法(Backtracking)
(一)定義
(二)實例
五、分支設限(Branch and Bound)
(一)定義
(二)實例
※窮舉法(exhaustive search)：暴力法
1-3 資料結構
一、定義
※各種資料結構的關係
※在設計資料結構時，常將其運算設計成函數的原因
※線性結構(linear structure)
※非線性結構(nonlinear structure)
※資料(Data)
二、常用結構
1-4 資料型態(Data Types)
一、定義
二、資料抽象性(Data Abstraction)
三、抽象資料型態(Abstract Data Type)
(一)定義
(二)優點
(三)舉例
四、抽象資料型態的表示法
(一)說明
(二)舉例
1-5 軟體開發生命週期(software development lifecycle)與結構化程式設計
※軟體開發生命週期的五大重要階段
※軟體開發生命週期的七個階段：軟體生命周期的七個階段
※結構化程式設計(Structured Programming)
※安全容錯(Fail-Safe)
1-6 迴圈的計數(Counting of Iterations)
1-7 程式效率的分析
一、程式分析方法
(一)事先預測(Priori-Estimate)
(二)事後測試(Posteriori Testing)
(三)功能
二、事先預測的困難點
(一)不同系統
(二)不同的指令集
(三)不同的語言與不同的編譯器
三、解決預測困難的方法
(一)頻率計數法(Frequency Count)
(二)漸近式表示法(Asymptotic Notations)
四、複雜度等級(Order of Complexity)
(一)定義
(二)複雜度等級(Order of Complexity)：種類
(三)常見的複雜度等級及其高低關係
(四)判斷複雜度等級高低常用的規則
(五)常用的數學公式
※指數
※比較順序
※時間複雜度比較
※asymptotic notations的運算
※證明法
五、遞迴關係式(Recurrence Relations)
(一)型一：線性齊次方程式(Linear Homogeneous Equations)
(二)型二：線性非齊次方程式(Linear Inhomogeneous Equations)
(三)型三：定義域轉換法(Domain Transform)
(四)型四：值域轉換法(Range Transform)
(五)型五：大項定理(Master Theorem)
(六)型六：遞迴樹分析(Recursion Tree Analysis)
1-8 迭代函式(Functional Iteration)：疊代函式
一、定義
二、範例
※迭代與遞迴的比較
1-9 遞迴程序(Recursive Procedure)
一、定義
二、種類
(一)直接遞迴(Direct Recursion)
(二)間接遞迴(Indirect Recursion)
(三)尾端遞迴(Tail Recursion)：屬於直接遞迴的特例
三、常見遞迴
(一)n的階乘(Factorial)
(二)S = 1+2+3+...+N
(三)陣列最大值
(四)最大公因數(Greatest Common Divisor, GCD)
(五)費氏級數(Fibonacci Numbers)
(六)組合公式(Combination)
(七)艾克曼函數(Ackermann’s Function)
(八)Tower of Hanoi：河內塔
(九)N項資料的全部排列
(十)同時找出最小與最大的資料
(十一)找尋第k小的元素
※數學歸納法(Mathematical Induction, MI)
1-10 遞迴的去除
一、尾端遞迴改寫
第二章 陣列
2-1 陣列
一、定義
二、有序串列(ordered list)
(一)定義
(二)提供的運算
(三)常見的實作法
※陣列與鏈結串列的比較
2-2 陣列空間的安排
一、一維陣列
二、二維陣列
(一)定義
(二)以列為主(row-major)
(三)以行為主(column-major)
三、多維陣列
(一)定義
(二)以列為主(row-major)
(三)以行為主(column-major)
※二維陣列與參差陣列(Ragged Array)的比較
※矩陣相乘
※使用動態規劃實作矩陣相乘
2-3 特殊矩陣(Special Matrix)
※對角線編號
一、下三角矩陣(Lower Triangular Matrix)
(一)定義
(二)列優先
(三)行優先
二、上三角矩陣(Upper Triangular Matrix)
(一)定義
(二)列優先
(三)行優先
三、對稱矩陣(symmetric matrix)
四、方陣(square matrix)
五、三對角線陣列(tridiagonal array)
(一)定義
(二)方式
六、帶狀矩陣(band matrix)
2-4 字串(String)
一、暴力法
(一)圖解
(二)程式
(三)時間複雜度
二、KMP
(一)使用Next表格實作KMP
(二)使用失敗函數實作KMP
第三章 鏈結串列(Linked Lists)
3-1 鏈結串列介紹與分類
一、表示法
(一)實作
(二)宣告
※間接定址運算 “*” 的優先等級低於子欄位運算子 “.”，故必須使用括號
二、循序串列(Sequential List)與鏈結串列(Linked List)的比較
三、單鏈串列(Single linked list)
(一)結構
(二)程式碼
四、雙向鏈結串列(Doubly Linked List)
(一)結構
(二)程式碼
五、鏈結串列的分類
(一)單鏈串列與雙鏈串列的比較
(二)循環串列與非循環串列的比較
(三)尾指標
(四)首節點
※linked list與array的比較
※動態變數(dynamic variable)
※指標不是動態配置
3-2 鏈結串列的運算
一、基本串列運算
(一)輸入n項資料，建立一個鏈結串列
(二)將新的資料y插入在x的節點之後
(三)將新的資料y插入在x的節點之前
(四)由小而大排序好的串列中插入一項資料後仍維持排序好的狀況
(五)在雙向鏈結中的某個節點p之後，插入一項新資料x
(六)鏈結串列的反轉
(七)將兩個尾指標所指的串列串接在一起
(八)釋放整個非循環串列全部的節點
(九)計算串列的長度
※鏈結串列刪除特定節點
※使用循環串列計算節點的總數
※Josephus problem
※將兩個單鏈串列x和y結合起產生一新單鏈串列z
※環狀單向鏈結串列(circular singly linked list)：環狀連結串列(Circular Linked Lists)
※環狀雙向鏈結串列(Circular doubly-linked lists)
※兩個環狀雙向鏈結串列(Circular doubly-linked lists)的連結
※以單鏈串列實作雙向鏈結串列
※以單鏈串列實作雙向循環鏈結串列
※用鏈結串列來儲存任意大小的非負整數
※單一鏈結錯誤更正
3-3 儲存體管理(Storage Pools)
一、定義
二、實作
(一)create
(二)getnode
(三)retnode
三、Storage pool與malloc的差別
※將循環串列中的所有節點全部歸還到Storage pool
3-4 鏈結串列式堆疊與佇列(Linked Stacks and Queues)
一、鏈結串列式堆疊
(一)push
(二)pop
二、鏈結串列式佇列
(一)addq
(二)delq
※使用環狀鏈結串列模擬佇列
3-5 等價關係(Equivalence Relations)
一、定義
二、特性
(一)反身性(reflexive)
(二)對稱性(symmetric)
(三)遞移性(transitive)
3-6 動態記憶體管理(Dynamic Memory Management)
一、邊界標籤(Boundary Tag)
(一)定義
(二)欄位
3-7 伙伴系統(Buddy System)
一、定義
二、空間配置
(一)若有一記憶體空間需求為 n
三、特性
(一)若有一記憶體空間需求為 n
(二)記憶體合併
(三)內部碎片
3-8 廣義串列(Generalized List)
一、定義
二、範例
3-9 多項式的表示法
一、一個陣列表示法
(一)定義
(二)Horner’s rule
二、二個陣列表示法
(一)定義
(二)time complexity
(三)多項式的加法運算
(四)多項式的乘法運算
(五)多項式的求值運算
三、鏈結串列表示法
(一)定義
(二)節點結構宣告
(三)步驟
(四)圖解
(五)多項式相加範例
3-10 稀疏矩陣(sparse matrix)
一、定義
二、Row-Column index表示法
(一)定義
(二)Row-Column index的轉置(transpose)
(三)矩陣乘法
※轉置矩陣(transpose)的實作
※快速轉置(fast transpose)的實作
※兩個稀疏矩陣相乘的實作
三、鏈結串列表示法
(一)定義
(二)環狀鏈結串列節點的結構
(三)利用環狀鏈結串列表示稀疏矩陣
第四章 堆疊與佇列(Stacks and Queues)
4-1 堆疊(Stacks)
一、定義
(一)有序串列(Ordered List)
(二)後進先出(Last In First Out, LIFO)
(三)Push、Pop及Top
二、基本的運算
(一)Push
(二)Pop
(三)TopItem
(四)IsEmpty
(五)IsFull
三、堆疊的溢位(overflow)及反向溢位(underflow)
(一)溢位(overflow)
(二)反向溢位(underflow)
四、堆疊的推入(Push)運算
(一)檢查堆疊是否已滿
(二)檢查堆疊是否未滿
五、堆疊的彈出(Pop)運算
(一)檢查堆疊是否為空
(二)檢查堆疊是否非空
六、應用
七、以陣列實作佇列
八、以鏈結串列實作堆疊
※火車車箱的排列順序
※在合理序列的任一個字首 (Proper Prefix) 中，E 的個數不可少於 X
※n個車箱堆疊排列個數 =
※n個車箱進入stack的所有排列數，則可以得到下面的遞迴關係式
※二項式定理
4-2 回溯式演算法
一、迷宮問題(Maze problem)
(一)定義
(二)演算法
※八皇后問題(Eight queens puzzle)
4-3 佇列(Queues)
一、線性佇列(Linear Queue)
(一)定義
(二)圖例
(三)基本的運算
(四)佇列的加入(Enqueue)與取出(Dequeue)
(五)實作陣列佇列
(六)實作串列佇列
(七)應用
二、單純使用線性陣列表示佇列的缺點
三、改進單純使用線性陣列表示佇列的缺點
(一)解決方法一
(二)解決方法二
四、環狀佇列(Circular Queue)
(一)定義
(二)基本的運算
(三)用陣列實作環狀佇列
(四)用鏈結串列實作環狀佇列
五、加標籤的環狀佇列(Tagged Circular Queue)
六、使用特殊註標值的環狀佇列(Circular Queue with Special Value)
七、使用長度檢查的環狀佇列
八、Deque種類
(一)Deque(Double-Ended Queue)
(二)Input-Restricted Deque(Scroll)：限入型deque
(三)Output-Restricted Deque(Shelf)：限出型deque
※將1, 2, 3, 4四個數依不同方式排列
※將1, 2, 3, 4四個數依不同方式排列
※雙向佇列(Double ended Queue, Deque)
※循環的雙向佇列(Double ended Queue, Deque)
4-4 多重堆疊與多重佇列(Multiple Stacks and Queues)
一、用一個陣列表示二個堆疊(Two Stack within an Array)
(一)相對的stacks
(二)同向的stacks
(三)相背的stacks
二、多重堆疊(Multiple stacks)
(一)說明
4-5 運算式轉換(Expression Conversion)
一、優先次序表
(一)說明
二、中序式(infix expression)轉後序式(postfix expression)
(一)演算法一：堆疊法
(二)演算法二：括號法
(三)演算法三：二元樹法
三、中序式(infix expression)轉前序式(prefix expression)
(一)演算法：堆疊法
(二)演算法二：括號法
(三)演算法三：二元樹法
四、後序式(postfix expression)轉中序式(infix expression)
(一)演算法一：括號法
(二)演算法二
五、算術運算式求值(Evaluation of Expression)
(一)後序式(postfix expression)求值計算(Evaluation of Postfix Expression)
(二)前序式(prefix expression)求值計算(Evaluation of Prefix Expression)
(三)中序式(infix expression)求值計算(Evaluation of Infix Expression)
六、後序式語法檢查(Syntax Checking of Postfix Expressions)
(一)演算法
第五章 圖形(Graph)
5-1 名詞與定義 (Tenninology and Definitions)
一、名詞
(一)簡單路徑(Simple Path)
(二)迴路(Cycle)
(三)連通頂點(Connected Vertices)
(四)連通圖形(Connected Graph)
(五)連通單元(Connected Component)
(六)強連通頂點(Strongly Connected Vertices)
(七)強連通圖形(Strongly Connected Graph)
(八)強連通單元(Strongly Connected Component)
(九)有向圖形的degree
(十)自由樹(Free Tree)
(十一)樹(Tree)
(十二)樹林(Forest)：森林
(十三)有根樹(Rooted Tree)
(十四)有序樹(Ordered Tree)
(十五)有向非循環圖形(Directed Acyclic Graph)
※簡單圖(Simple graph)
※完全圖(Complete graph)
※樹與圖最大的差異點
※漢米爾頓路徑(Hamiltonian path)：Hamiltonian Cycle
※尤拉路徑(Eulerian Path)
※尤拉鏈(Eulerian Chain)
※尤拉循環(Eulerian Cycle)：Euler Tour / Eulerian Circuit / 尤拉迴路(Euler Cycle)
※尤拉圖(Eulerian Graph)
※漢米爾頓路徑與尤拉路徑的差異
5-2 圖形表示法(Graph Represeations)
一、鄰接矩陣(Adjacency Matrix)
(一)M[i, j] = 1表示有邊；0表示無邊
(二)資料結構
(三)時間複雜度
(四)空間複雜度
※成本相鄰矩陣(cost-adjacency-matrix)
二、鄰接串列(Adjacency List)
(一)定義
(二)資料結構
(三)空間複雜度
(四)時間複雜度
(五)相鄰串列時間複雜度O(n+e)的進一分析
(六)鄰接串列的循序表示法(Sequential representation of adjacency lists)
(七)反轉鄰接串列(Inverse adjacency lists)
(八)Altemate adjacency list
(九)Orthogonallist representation
※加權圖形的相鄰串列表示法
※相鄰矩陣與相鄰串列的比較
三、鄰接多重串列(Adjacency Multilist)
(一)說明
四、Incidence martix
5-3 深度優先搜尋法(Depth-First Search, DFS)
一、定義
二、步驟
(一)說明
三、範例
四、遞迴：回溯式演算法
(一)演算法
(二)範例
五、非遞迴：用堆疊
(一)演算法
(二)範例
六、流程圖
七、時間複雜度
(一)使用 adjacency matrix
(二)使用 adjacency list
八、應用
(一)檢查迴路
(二)檢查二分圖
※使用堆疊實作DFS
5-4 廣度優先追蹤(Breadth-First Search, BFS)
一、定義
二、步驟
(一)由近而遠逐一拜訪節點
(二)伯伯兒子比叔叔兒子先(因為採用佇列)
三、範例
四、演算法
五、流程圖
六、時間複雜度
(一)使用adjacency list
(二)使用adjacency matrix
七、應用
(一)尋找圖中所有連通單元
(二)尋找連通單元中的所有節點
(三)尋找非加權圖中任兩點的最短路徑
(四)測試一圖是否為二分圖
※使用佇列實作BFS
5-5 連通單元(Connected Components)
一、關節點(articulation point)
二、二連通元件(biconnected component)：雙連通單元
三、找出連通單元的演算法
5-6 展開樹(Spanning Trees)：生成樹
一、定義
(一)說明
(二)特性
二、spanning forest邊個數
三、實作方式
(一)無向圖G
(二)DFS生成樹
(三)BFS生成樹
四、應用方面
(一)興建的道路
(二)網路線的配置
5-7 最小成本展開樹(Minimum Cost Spanning Tree)：最小成本生成樹
一、定義
(一)說明
(二)特色
(三)演算法
二、Kruskal’s algorithm
(一)演算法一
(二)演算法二：建立min-heap
(三)範例
(四)時間複雜度
三、Prim’s algorithm(greedy method)
(一)演算法
(二)範例
(三)時間複雜度
(四)Kruskal與Prim的適用性
四、Sollin’s algorithm
(一)演算法
(二)範例
5-8 雙連通單元(Biconnected Components)
一、定義
(一)關節點(Articulation Point)
(二)雙連通圖形(Biconnected graph)
(三)雙連通單元(Biconnected component)
二、雙連通單元求法
(一)做法
(二)邊的分類
(三)判斷u是否為關節點的條件
5-9 最短路徑問題(Shortest Path Problem, SPP)
一、Dijkstra’s Algorithm
(一)定義
(二)範例
(三)演算法
(四)時間複雜度
(五)限制
二、Bellman-Ford演算法
(一)定義
(二)步驟
(三)時間複雜度
三、All-Pairs Shortest Paths
(一)定義
(二)方法一
(三)方法二
(四)Floyd-Warshall：佛洛依德最短路徑演算法(Floyd’s Algorithm for Shortest Paths)
(五)範例
(六)說明
※Floyd-Warshall實作
※Dijkstra、Bellman-Ford與Floyd-Warshall的比較
5-10 遞移閉集合(Transitive Closures)
一、定義
(一)遞移閉集合(transitive closure)
(二)反身遞移閉集合(reflexive transitive closure)
二、演算法
(一)虛擬碼
(二)時間複雜度
5-11 巡迴售貨員問題(Traveling Salesperson Problem, TSP)
一、定義
二、演算法
三、範例
5-12 AOV網路與拓樸排序(AOV-Network and Topological Sort)
一、AOV網路
二、拓樸排序(Topological Sort)
(一)定義
(二)演算法
(三)時間複雜度
(四)範例
(五)應用
※拓樸排序有幾組？
5-13 AOE－網路與臨界路徑問題
一、定義
(一)說明
二、演算法
三、時間複雜度
四、關鍵活動(Critical Activity)
(一)在 critical path 上的 activity
(二)e(i) = l(i)
(三)是工程的瓶頸
※AOV Network與AOE Network的比較
第六章 樹(Trees)
6-1 基本名詞與表示法
一、定義
(一)樹(tree)
(二)樹的基本觀念
二、樹的分類
(一)有序樹
(二)無序樹
三、樹的一般表示法
(一)范氏圖
(二)廣義串列
(三)階層表示法
(四)內縮表示法
(五)鏈結串列表示法
(六)左子右弟(Left-child right-sibling)
※樹與圖的比較
6-2 二元樹(Binary Trees)
一、二元樹
(一)定義
(二)二元樹與樹的比較
(三)特點
(四)種類
※建立二元樹
二、分支度(degree)
(一)定義
(二)範例
※樹與二元樹的比較
6-3 二元樹的表示法
一、串列表示法
二、陣列表示法(隱含式陣列表示法)
三、擴充
※m-ary tree(n-ary tree, k-ary tree or k-way tree)
6-4 二元樹的追蹤(Binary Tree Traversals)
一、中序追蹤(Inorder Traversal)
※中序追蹤的分析
二、前序追蹤(Preorder Traversal)
三、後序追蹤(Postorder Traversal)
四、左前序(left preorder)
五、右前序(right preorder)
六、左後序(left postorder)
七、右後序(right postorder)
八、階層序(level order)：廣度優先追蹤(Breadth-First Search, BFS)
※使用非遞迴方式實作二元樹走訪
※時間複雜度
※給前序及中序畫出二元樹
※給中序及後序畫出二元樹
※給前序及後序畫出二元樹
※比較兩棵二元樹是否相等
※計算二元樹節點的總個數
※計算二元樹leaf nodes的個數
※實作二元樹節點個數及計算二元樹葉節點個數
※計算二元樹的高度
※實作二元樹的高度
※copy二元樹
※二元樹T的各個節點，左右交換
6-5 森林與二元樹間的轉換
一、左子右弟
(一)森林轉二元樹
※為何森林轉二元樹？
二、森林的追蹤
三、樹的追蹤
(一)前序追蹤
(二)中序追蹤
(三)後序追蹤
6-6 引線二元樹(Threaded Binary Tree)
一、定義
二、為何使用引線二元樹？
三、引線的做法
(一)說明
四、引線二元樹的結構
五、優點
(一)不需要使用堆疊或遞迴處理
(二)避免鏈結閒置浪費
(三)中序走訪時速度比較快
(四)任一節點容易找出中序後繼者與中序前行者
六、缺點
(一)在加入或刪除節點時的速度較一般的二元樹慢
(二)引線在子樹之間不能共享
七、建立後引線(Post-thread)
八、引線二元樹的中序走訪
6-7 二元搜尋樹(Binary Search Trees)
一、定義
(一)二元搜尋樹是一種二元樹，它可以為空，若不為空，則必須要滿足以下條件
二、建立二元搜尋樹
(一)建置步驟
(二)搜尋方式
三、實作
(一)插入節點
(二)搜尋節點
四、時間複雜度
(一)插入
(二)搜尋
(三)刪除
五、比較次數
六、二元搜尋樹中要刪除資料x時
(一)說明
(二)範例
(三)程式碼
七、二元搜尋樹中插入一個節點的演算法：遞迴
八、插入一個節點的演算法：非遞迴
※樹排序法(Tree sort)
※所有高度為 n 的二元搜尋樹數目
※二元搜尋樹的平均搜尋時間(平均比較次數)
6-8 算式樹(Expression Trees)
一、定義
二、算式樹與運算式之間的關係
三、中序算式樹加括號
四、算式樹的求值計算
五、中序式建立算式樹
※運算子優先順序
6-9 決策樹(Decision Trees)
6-10 堆積(Heaps)
一、堆積(Heaps)
(一)堆積(Heap)
(二)堆積樹(Heap Tree)
(三)最大堆積樹(Max Heap Tree)
(四)最小堆積樹(Min Heap Tree)
(五)最小堆積插入新節點
(六)最小堆積刪除節點
(七)堆積的建立方式
(八)用途
(九)最大堆積插入新節點
(十)刪除根節點(最大值或最小值)
(十一)建立最大堆積
※堆積樹的調整方式
二、優先權佇列
(一)定義
(二)實作方式
(三)種類
(四)缺點
※使用堆積實作優先權佇列
※使用陣列、線性串列、樹來表現優先權佇列
※雙向優先權佇列(Double-ended priority queue, DEPQ)
6-11 集合的表示法(Set Representations)
一、鏈結串列表示法
二、位元向量(bit vector)
三、互斥集合(Disjoint Sets)
(一)定義
(二)運算
※Weighting rule
※Collapsing rule
6-12 遊戲樹(Game Trees)
一、遊戲樹(Game Trees)
(一)定義
(二)應用
二、the min-max procedure
(一)定義
(二)範例
三、α-β裁剪(Alpha-Beta Pruning)：alpha-beta procedure
(一)定義
(二)符號
(三)範例一
(四)範例二
6-13 AVL-樹(AVL-trees)
一、AVL-樹(AVL-trees)
(一)定義
(二)Most Skewed AVL-tree
(三)AVL的節點數
二、AVL-樹插入新資料的方法
(一)說明
(二)調整方式
(三)範例
(四)時間複雜度
三、AVL-樹刪除資料的方法
(一)說明
(二)時間複雜度
(三)範例一
(四)範例二
四、時間複雜度
(一)搜尋/插入/刪除
(二)建立一個AVL樹
※計算一個有n個節點的AVL樹高度
※計算一個AVL樹節點個數
五、範例
※判斷一個二元搜尋樹是否為AVL樹？
6-14 斜張樹(splay tree)
一、定義
二、Splay的起始節點
(一)搜尋
(二)插入
(三)刪除
三、原則
(一)將起始節點經一連串的旋轉移到樹根
四、作用
6-15 延伸二元樹(Extend binary tree)
一、定義
二、內徑長與外徑長
(一)外徑長 (E)
(二)內徑長 (I)
(三)內徑長與外徑長的關係
(四)舉例
三、加權外徑長
6-16 m-路搜尋樹(m-way Search Tree)
一、m-路搜尋樹(m-way Search Tree)
(一)定義
(二)相關特性
(三)目的
(四)應用
6-17 B-樹(B-Trees)
一、B-樹(B-Trees)
(一)定義
(二)度數(order)
(三)B-tree 中 key value 的數目為何？
二、B-Tree的Insert動作
(一)步驟
(二)分裂(Split)處理
(三)範例一
(四)範例二
三、B-Tree的Delete動作
(一)步驟
(二)範例一：x位於葉節點
(三)範例二：x位於葉節點
(四)範例三：x位於非葉節點
※B+-樹(B+-tree)
※B+-Tree的插入動作
6-18 2-3樹
一、2-3樹(2-3 Trees)
(一)定義
(二)特性
二、B-tree T of order 3的插入：2-3樹
(一)一律加在最下層(非失敗節點)
(二)檢查是否違反B-tree規定
(三)範例
三、B-tree T of order 3的刪除：2-3樹
(一)說明
(二)範例一
(三)範例二
6-19 2-3-4樹
一、定義
二、特性
三、插入
(一)Backward
(二)Forward
四、刪除
6-20 紅黑樹(Red-Black trees)
一、紅黑樹(Red-Black trees)
(一)定義
二、節點顏色
(一)性質1
(二)性質2
(三)性質3
(四)性質4
(五)性質5
三、插入－紅色/黑色節點
(一)情形一：新節點N位於樹的根上，沒有父節點
(二)情形二：新節點的父節點P是黑色
(三)情形三：如果父節點P和叔父節點U二個都是紅色
(四)情形四：如果父節點P是紅色，叔父節點U是黑色或空值
四、範例－紅色/黑色節點
(一)建立一紅黑樹，其數字依序為1, 2, 3, 4, 5, 6, 7
(二)建立一紅黑樹，其數字依序為10, 72, 14, 68, 20, 58, 30, 50, 65, 63
五、插入－紅色/黑色指標
(一)新插入的節點與其父節點之間的指標一定是紅指標
(二)調整
(三)指向父節點和叔叔節點的兩個紅色指標
六、範例-紅色/黑色指標
七、刪除
八、2-3-4樹轉為紅黑樹
(一)說明
(二)一個 2-node 轉成一個紅黑樹的節點
(三)一個 3-node 轉成二個紅黑樹的節點
(四)一個 4-node 轉成三個紅黑樹的節點
(五)整棵樹的轉換
九、插入或刪除運算
十、Rank
6-21 最小最大堆積(Min-Max Heaps)
一、最小最大堆積(Min-Max Heaps)
(一)定義
二、加入
(一)規則
(二)範例
三、刪除
(一)規則
(二)範例
6-22 兩頭堆積(Double-ended heaps, Deaps)
一、兩頭堆積(Double-ended heaps, Deaps)
(一)定義
二、插入
(一)規則
(二)範例
三、刪除
(一)規則
(二)範例
6-23 對稱最小最大堆積(Symmetric min-max heap, SMMH)
一、對稱最小最大堆積
(一)定義
(二)特性
二、插入節點到一個SMMH
(二)時間複雜度
(三)範例一
(四)範例二
三、從SMMH中刪除節點
(一)步驟
(二)時間複雜度
(三)範例一
(四)範例二
※以SMMH建構的優先佇列與以一般的堆積建構的優先佇列功能有何不同？
※區間堆積(interval heap)
6-24 左撇子樹(Leftist Trees)
略
6-25 二項式堆積(Binomial Heaps, Binomial Queues)
一、二項式堆積(Binomial Heaps, Binomial Queues)
(一)定義
(二)特性
6-26 霍夫曼樹(Huffman Tree)
一、霍夫曼樹(Huffman Tree)
(一)定義
(二)原理
(三)特性
(四)用途
二、霍夫曼碼(Huffman codes)
(一)步驟
(二)範例
三、霍夫曼演算法
(一)演算法
(二)時間複雜度
6-27 查找樹(Tries)
一、查找樹(Tries)
(一)定義
(二)應用
(三)優點
二、用C語言來建立trie結構
三、實作
※後綴樹(Suffix tree)
第七章 排序法(Internal Sorts)
7-1 基本定義
一、內部排序(Internal sort)
二、外部排序(External sort)
三、比較排序(comparison sort)
四、分配排序(distributive sort)
7-2 插入排序法(Insertion sort)：Ranking sort
一、插入排序法虛擬碼(pseudo code)
二、範例
三、插入排序法實作
(一)實作一
(二)實作二
四、時間複雜度
(一)Insertion sort的best case：已排序好的資料(ordered data)
(二)Insertion sort的worst case：反轉資料(reversed data)
(三)比較表格
五、分析
(一)說明
六、反轉表(Invertion Table)
※二分查詢排序法
7-3 泡沫排序法(Bubble sort)
一、泡沫排序法(Bubble sort)
二、演算法
三、實作
四、時間複雜度(Time Complexity)
(一)Bubble sort的best case：已排序好的資料(ordered data)
(二)Bubble sort的worst case：反轉資料(reversed data)
(三)最佳狀況(Best Case)
(四)最壞狀況(Worst Case)
(五)平均狀況(Average Case)
五、分析
(一)說明
※兩個變數 X 與 Y 欲做內容的交換
※臭皮匠排序(Stooge sort)
7-4 選擇排序法(Selection Sort)
一、選擇排序法(Selection Sort)
二、範例
三、虛擬碼
四、實作
五、時間複雜度(Time Complexity)
(一)Selection sort的case
(二)時間複雜度
六、分析
(一)說明
7-5 謝耳排序法(Shell Sort)
一、謝耳排序法(Shell Sort)
(一)定義
二、原理
三、實作
四、分析
(一)說明
※計數排序法(count sort)
※分布式計數排序法(Distributive Counting Sort)
7-6 快速排序法(Quick sort)
一、快速排序法(Quick sort)
(一)演算法
二、舉例
(一)範例
三、實作
四、分析
(一)說明
五、範例
(一)Selection sort、Insertion sort、Bubble sort和Quick sort的比較
(二)median of tree
※排序最快可以多快？
7-7 合併排序法(Merge Sort)
一、合併排序法(Merge Sort)
(一)定義
二、實作二筆已排序資料的合併
三、實作遞迴版的合併排序
四、分析
(一)時間複雜度
(二)空間複雜度(Space Complexity)
(三)穩定排序
※穩定排序與不穩定排序
7-8 堆積排序(Heap sort)
一、堆積排序(Heap sort)
(一)定義
(二)特性
(三)最適合的資料結構
二、演算法
(一)第一階段建立堆積
(二)第二階段堆積排序
三、實作
四、分析
(一)說明
※快速排序與堆積排序的比較
7-9 基數排序法(Radix sort)
一、方法
(一)LSD(Least Significant Digit First)
(二)MSD(Most Significant Digit First)
二、實作
三、比較
※桶排序法(Bucket Sort)：bin sort
7-10 使用磁碟的外部排序(Sorting with disks)
一、K-路合併排序法
(一)定義
二、選擇樹(Selection Tree)
(一)目的
(二)優勝樹(Winner Tree)
(三)失敗樹(Loser’s Tree)
7-11 各種排序方法的比較
一、排序法分類
(一)內部排序與外部排序
(二)穩定與不穩定排序法
(三)簡單與高等排序法
二、內部排序法(internal sort)
(一)定義
(二)特性
(三)種類
三、外部排序法(External Sort)
(一)定義
(二)特性
(三)種類
四、排序法的效益評估
(一)大都脫離不了三個基本動作
(二)衡量因素
(三)各種排序法的優點與缺點
※內部排序法
※排序法的分類
※各種排序演算法的時間複雜度
※各種排序演算法的優缺點
※各種排序演算法的時間測試
第八章 資料搜尋
8-1 搜尋法
一、循序搜尋法(Sequential Search)：線性搜尋(Linear Searching)
(一)定義
(二)實作
(三)優點
(四)缺點
(五)時間複雜度
(六)特性
(七)改善方式
二、二分搜尋法(Binary Search)
(一)定義
(二)範例
(三)特性
(四)虛擬碼
(五)實作
(六)優點
(七)缺點
(八)時間複雜度
(九)適用情況
※循序搜尋法與二分搜尋法的比較
※比較二分搜尋與一般二元搜尋樹在建置與搜尋程序上作法與效能的差異
三、費氏搜尋法(Fibonacci Search)
(一)定義
(二)步驟
(三)範例
(四)實作
(五)優點
(六)分析
四、內插搜尋法(Interpolation Search)：插補搜尋法
(一)定義
(二)原理
(三)步驟
(四)範例
(五)實作
(六)時間複雜度
(七)分析
(八)Robust Interpolation Search
※循序搜尋法、二元搜尋法、內插搜尋法與費氏搜尋法的比
8-2 雜湊法(Hashing)
一、雜湊法
(一)定義
(二)功能
(三)優點
(四)缺點
(五)名詞
(六)常見的雜湊函數
(七)時間複雜度
(八)空間複雜度
(九)應用
二、滿溢處理
(一)開放定址法(Open Addressing)
(二)獨立鏈結串列(Separate Chaining)
※合併鏈結(coalesced chaining)
※查找成功及查找失敗的平均查找長度(Average Search Length, ASL)
三、討論
(一)主要群聚(Primary Clustering)
(二)Secondary Clustering(次要群聚)
(三)完美雜湊函數(Perfect Hashing)
(四)插入所需時間與失敗搜尋的探索次數相同
(五)開放定址法需要注意刪除資料後的位置調整問題
※雜湊函數設計的要點
留言列表
國考資訊處理解答 (7)
