数据结构

来自于: 台湾清华大学 | 分类: 计算机(243)

课程描述

“数据结构”是学习以聪明的方法去储存数据,使得我们在有需要的时候能够快速有效地把数据撷取。例如我们希望把学生某一科的考试成绩整理,使得我们能随时查询任何学生的排名。为了节省查询的时间,我们或许会把学生们的成绩从高至低排好,而不会以随意的顺序排列。(对此问题,其实还有一个更好的方法呢!)在此课程,我们将针对各种基本的数据结构,进行理论探讨及分析,并辅以适量的程序训练,加强学生对数据结构实际应用的掌握。

课程简介

本课程目标是帮助学生学得下列观念和能力:

1. 各种基本数据结构的认识。2. 透过实作数据结构让同学对所学有更深刻的了解,并加强同学写程式的训练。3. 用数据结构配合基本的演算法来解决问题。4. 本课程将透过OJ (Online Judge) 程式判读功能进行测验。


授课大纲 Syllabus

Week 0        Overview
Week 1        Getting Started
                        Heap
Week 2        Sorting Lower Bound
                        Basic Data Structures I (List, Queue, Stack) 
Week 3        Basic Data Structures II (Tree, Graph)
                        Graph and Tree Traversals I (BFS, DFS)
Week 4        Graph and Tree Traversals II (Tree Traversals, Expression Tree )
                        Graph and Tree Traversals III (Topological Sort)
Week 5        Searching Set Data I (Binary Search Tree)
Week 6        Searching Set Data II (AVL Tree)
Week 7        Searching Set Data III (B-Tree)
Week 8        Hashing (Chaining, Open Addressing)
                        Suffix Tree and Suffix Array

 


课程章节

01 Getting Started
Sorting的方法&分析
Sorting的分析
Growth of Function
Insertion Sort上機
exercise
02 Heap
Heap-1
Heap-2
exercise
03 Sorting Lower Bound
Lower Bound on Comparison Sorts- 1
Lower Bound on Comparison Sorts- 2
exercise
04 Basic Data Structures I (List, Queue, Stack)
Pointers in C
Basic Data StructureⅠ- 1
Basic Data StructureⅠ- 2
Josephus上機
Balanced括號上機
List上機_insert
List上機_delete
05 Basic Data Structures II (Tree, Graph)
Tree and Graph
exercise
06 Graph and Tree Traversals I (BFS, DFS)
Breadth First Search
Depth First Search
Depth First Search分析
07 Graph and Tree Traversals II (Tree Traversals, Expression Tree)
Tree Traversal
Expreesion Tree&Postfix Notation of an Expression
Infix-Postfix Coversion
exercise
08 Graph and Tree Traversals III (Topological Sort)
Topological Sort
Topological 證明
Two IQ questions
exercise
09 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
10 Searching Set Data II (AVL Tree)
AVL Tree
AVL Tree- Rotation
AVL Tree- Insertion的情形
AVL Tree- Insertion實作Case2.2
AVL Tree- Insertion實作Case2.3
AVL Tree Insert 補充& Delete
Augmenting Data Structure
exercise
11 Searching Set Data III (B-Tree)
B-tree EM Model
B-tree insert
B-tree delete
exercise
12 Hashing (Chaining, Open Addressing)
Hashing
Common Hash Function
13 Suffix Tree and Suffix Array
Indexing Strings& Suffix Array
Homework
HW1
HW2
HW3
HW4
HW5
HW6
HW7
HW8
Exam
Exam1
Exam2
Exam3

授课教师

  • 韩永楷台湾新竹清华大学 资讯工程学系 副教授

    学经历: *台湾清华大学资讯工程系副教授(2011.8 至今) *台湾清华大学资讯工程系助理教授(2006.8–2011.7) *美国普渡大学计算机科学系客座教授(2004–2006) *香港大学计算机科学系博士(2000–2005) 研究专长: *字串比对、资料压缩、组合最优化 荣誉奖项: *2008年度台湾清华大学校杰出教学奖 *电资学院杰出教学奖 *电资院新进人员研究奖

精华笔记

精华笔记正在评选中,去看看全部笔记

常见问题

指定用書

1.Introuction to Algorithms Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein 2.Fundamentals of Data Structures in C++ Ellis Horowitz, Sartaj Sahni, Dinesh Mehta

參考資料

Algorithms in C++; Robert Sedgewick