.png)
邏輯學
| 層級： | 課程資料 |
| 媒體： | 影音 講義 |
11101資料結構導論 Introduction to Data Structure
2022-11-23-2030-12-30
國立清華大學 資訊工程學系 韓永楷
關鍵字： Introduction to Data Structure Sorting Lower Bound Searching Set Data Hashing Suffix Tree and Suffix Array
「資料結構」是學習以聰明的方法去儲存資料，使得我們在有需要的時候能夠快速有效地把資料擷取....
課程說明
Course Description
「資料結構」是學習以聰明的方法去儲存資料，使得我們在有需要的時候能夠快速有效地把資料擷取。例如我們希望把學生某一科的考試成績整理，使得我們能隨時查詢任何學生的排名。為了節省查詢的時間，我們或許會把學生們的成績從高至低排好，而不會以隨意的順序排列。〈對此問題，其實還有一個更好的方法呢！〉
| Week 1 | Getting Started、Heap |
● Introduction ● Sorting 的方法 & 分析 ● Exercise - Insertion Sort ● Sorting 的分析 ● Exercise - Merge Sort ● Growth of Functions ● Exercise - Growth of Functions ● Insertion Sort 上機 ● Heap-1 ● Exercise - Heap I ● Heap-2 ● Exercise - Heap II | |
| Week 2 | Sorting Lower Bound、Basic Data Structures I (List, Queue, Stack) |
● Lower Bound on Comparison Sorts - 1 ● Exercise - Lower Bound on Comparison Sorts I ● Lower Bound on Comparison Sorts - 2 ● Exercise - Lower Bound on Comparison Sorts II ● Pointers in C ● Basic Data Structure Ⅰ - 1 ● Basic Data Structure Ⅰ - 2 ● Exercise - Basic Data Structure I ● Josephus 上機 ● Exercise - Josephus Problem ● Balanced 括號上機 ● Exercise - Balanced Parentheses ● List 上機_insert ● List 上機_delete | |
| Week 3 | Basic Data Structures II (Tree, Graph)、Graph and Tree Traversals I |
| (BFS, DFS) | |
● Tree and Graph ● Exercise - Tree ● Breadth First Search ● Exercise - Breadth First Search ● Depth First Search ● Exercise - Depth First Search ● Depth First Search 分析 | |
| Week 4 | Graph and Tree Traversals II (Tree Traversals, Expression Tree )、 |
| | Graph and Tree Traversals III (Topological Sort) |
● Tree Traversal ● Exercise - Tree Traversal ● Expression Tree & Postfix Notation of an Expression ● Infix-Postfix Coversion ● Exercise - Expression ● Topological Sort ● Topological Sort 證明 ● Exercise - Topological Sort ● Two IQ Questions ● Exercise - Josephus Problem Revisited | |
| Week 5 | Searching Set Data I (Binary Search Tree) |
● Binary Search Tree ● Binary Search Tree 實作 (Min / Max) ● Binary Search Tree 實作 (Search / Predecessor) ● Binary Search Tree 實作 (Insert / Delete) ● Binary Search Tree 實作 (Delete) - Case 1 & 2 ● Binary Search Tree 實作 (Delete) - Case 3 ● BST上機_insert ● BST上機_delete_1 ● BST上機_delete_2 ● BST上機 - 3 ● Exercise - Binary Search Tree | |
| Week 6 | Searching Set Data II (AVL Tree) |
● AVL Tree ● AVL Tree - Rotation ● AVL Tree - Insertion 的情形 ● AVL Tree - Insertion實作 Case 2.2 ● AVL Tree - Insertion 實作 Case 2.3 ● AVL Tree Insert 補充 & Delete ● Augmenting Data Structure ● Exercise - AVL Tree | |
| Week 7 | Searching Set Data III (B-Tree) |
● B-tree EM Model ● B-tree insert ● B-tree delete ● Exercise - B Tree I ● Exercise - B Tree II | |
| Week 8 | Hashing (Chaining, Open Addressing)、Suffix Tree and Suffix Array |
● Hashing ● Common Hash Function ● Exercise - Hashing ● Indexing Strings & Suffix Array ● Exercise - Suffix Array | |
指定用書
Text Book
| ♠ | Introuction to Algorithms |
| Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein | |
| ♠ | Fundamentals of Data Structures in C＋＋ |
| Ellis Horowitz, Sartaj Sahni, Dinesh Mehta |
參考書籍
References
| ♠ | Algorithms in C＋＋Robert Sedgewick |
先修課程
Advanced Placement
| ♠ | C/C＋＋ Programming |
https://ocw.nthu.edu.tw/ocw/index.php?page=course&cid=313&
https://www.youtube.com/channel/UC-iw--AhrSzrabmLL6l7Qeg