1、Course 0課程介紹Introduction,2, Outline,了解本課程授課重點、目標及課程設計了解本課程評分標準課前重點資料結構 v.s. 演算法資料結構概念基礎複習, 教材,Text Book蔡宗翰, 演算法: 使用C+ 虛擬碼, 碁峰圖書, 2004.講義下載處: http:/www.csie.ntu.edu.tw/d92005Reference BookR. E. Neapolitan and K. Naimipour, Foundations of Algorithms: Using C+ Pseudocode, 3/e, Jones, 2004. (Textbook原文本
2、) 李家同教授, Computational Biology, 全文電子書第二章. 洪逸, 洪捷, 演算法-名校攻略密笈, 鼎茂圖書. 洪逸, 資料結構(含精選試題), 鼎茂圖書.,4, 課程重點,前置觀念演算法：效率，分析與量級 (Algorithms: Efficiency, Analysis, and Order)遞迴 (Recursion)排序 (Sort) 搜尋 (Search)解題策略Divide-and-Conquer (切割與征服) Dynamic Programming (動態規劃) The Greedy Approach (貪婪法則) Backtracking (回溯) B
3、ranch-and-Bound (分枝與限制) NP問題 An Introduction to the Theory of NP,5, 評分標準,期中考：35% 期末考：35%平時考：20%平時成績：10%加分程式題：10%20%,6, 資料結構 v.s. 演算法,資料結構 Array Linked List Stack Queue Tree Graph,演算法 Divide-and-Conquer Dynamic Programming The Greedy Approach Backtracking Branch-and-Bound,複雜度分析搜尋 (Search)排序 (Sort)高等樹
4、 (Advanced Tree),ADT,Theory of NP:P ProblemNP ProblemNP Complete ProblemNP Hard Problem,基礎,高階,7,資料結構概念基礎複習,8,Def: 為表示有序的線性串列之一種方式其佔用連續性的記憶體空間各元素型態皆需相同 (一致)支援Sequential及Random Access插入、刪除元素較為麻煩需挪移其它元素不易動態增刪空間大小, Array,9,Array種類,一維陣列二維陣列三維陣列N維陣列,10, Linked List,Def: 由一組節點 (Node)所組成的有序串列，各Node除了Data欄之外
5、，另外有 1 個Link欄 (或稱 Pointer)，用以指向其它Node之位址。有一個指標變數 (Pointer variable) 用來指出鏈結串列中的第一個節點之所在。指標變數的名字可用來做為其所指向之鏈結串列的名字。,11,Linked list的特質:各Node不一定要佔用連續的Memory空間各Node之型態 (Data Type) 不一定要相同僅支援Sequential AccessInsert/Delete Node 容易,12,Linked List 種類,13, Stack,Def: 具有LIFO (last in-first out)或FILO (first in-las
6、t out) 性質的有序串列。插入元素的動作稱為Push, 刪除元素的動作稱為Pop.Push/Pop的動作皆發生在同一端，此端稱為Top.,14, Queue (佇列),Def: 具有FIFO (first in-first out) 性質的有序串列。其插入元素的動作稱為發生在Rear (尾)端, 刪除元素的動作發生在Front (前)端.,15,Def: Tree是由1個以上的Nodes所組成的有限集合，滿足:至少有一個Node，稱為Root其餘的Nodes分成T1, T2, , Tn個互斥集合，稱為Subtree, Tree,16, Binary Tree (二元樹),Def: Bina
7、ry Tree為具有 0 個nodes所構成的有限集合。Binary Tree可以為空的樹。若不為空的樹，則具有Root及左, 右子樹，且左, 右子樹亦是Binary Tree。,17,二元樹之三個基本定理,定理一: 二元樹中，第i個level的node個數最多有 2i-1 個。定理二: 高 (深) 度為k的二元樹，其node個數最多有 2k-1 個。定理三: 非空二元樹若leaf個數為 n0 個，degree為2的node個數為n2個，則 n0 = n2+1。,18,二元樹的種類,Skewed Binary TreeFull Binary TreeComplete Binary Tree,1
8、9,Skewed Binary Tree,Def: 可分為Left-Skewed Binary Tree: 每個non-leaf node皆只有左子集Right-Skewed Binary Tree: 每個non-leaf node皆只有右子集,20,Full Binary Tree,Def: 具有最多Node個數的二元樹稱之即: 高度為d，其node個數必為2d-1具有n個nodes的Full B.T. ，其高度必為: 課本將之命名為: complete binary tree (7.6.1節),21,Complete Binary Tree,Def: 若二元樹高度為d，node個數為n，則
9、2d-1-1 n 2d-1n個node之編號與高度d的full binary tree之前的n個node編號一一對應，不能跳號。課本將之命名為: essentially complete binary tree (7.6.1節),22,Def: A Graph is a collection of nodes, called vertices, and a collection of line segments, called edges, that connecting pairs of vertices.In other words, a graph consists of two set
10、sa set of vertices a set of lines., Graph,23,Graph may be either directed or undirected:Directed graph (或稱 Digraph)Each line has a direction to its successor.G = (V, E), 其中V為頂點集合，E為邊集合。 。Undirected graphEach line has no direction.G = (V, E), 其中V為頂點集合，E為邊集合。 = 。,24, Data Type and Abstract Data Type,D
11、ata TypeDef: A data type consists of two partsa set of data the operations that can be performed on the data.For example:IntegerData: -, , -2, -1, 0, 1, , (沒有小數的數值集合)Operations: +, -, , , %, , , =, !=, +, -, Floating pointData: -, , -1.9, , 0.0, , Operations: +, -, , , %, , , =, !=, CharacterData: A, B, , a, b, Operations: , ,25,ADT (Abstract Data Type; 抽象資料型態)Def: ADT是一種Data Type，且要滿足： “資料的規格與操作的規格” 獨立於 “資料的實際表示方式與操作的實際製作方式.”,User Request,Spec. of Data Objects,Spec. of Operations,Designer,Representation ofDataEx: a. b. c. ,Implementation ofOperationsEx: 1. 2. 3. ,Hidden (隱藏),
