课程概况
“数据结构”是学习以聪明的方法去储存数据，使得我们在有需要的时候能够快速有效地把数据撷取。例如我们希望把学生某一科的考试成绩整理，使得我们能随时查询任何学生的排名。为了节省查询的时间，我们或许会把学生们的成绩从高至低排好，而不会以随意的顺序排列。（对此问题，其实还有一个更好的方法呢！）在此课程，我们将针对各种基本的数据结构，进行理论探讨及分析，并辅以适量的程序训练，加强学生对数据结构实际应用的掌握。
本课程由台湾新竹清华大学提供，因课程视频由主讲教师录制并上传，凡课程视频中“国立清华大学”均指“台湾新竹清华大学”。
课程大纲
Week 0 Overview 课程介绍
Week 1 Getting Started; Heap
Sorting的方法&分析
Sorting的分析
Growth of Function
Insertion Sort上机
Exercises
Heap-1
Heap-2
Exercises
Week 2 Sorting Lower Bound
Lower Bound on Comparison Sorts- 1
Lower Bound on Comparison Sorts- 2
Exercises
Basic Data Structures I (List, Queue, Stack)
Pointers in C
Basic Data StructureⅠ- 1
Basic Data StructureⅠ- 2
Josephus上机
Balanced括号上机
List上机_insert
List上机_delete
Exercises
Week 3 Basic Data Structures II (Tree, Graph)
Tree and Graph
Exercises
Graph and Tree Traversals I (BFS, DFS)
Breadth First Search
Depth First Search
Depth First Search分析
Exercises
Week 4 Graph and Tree Traversals II (Tree Traversals, Expression Tree )
Tree Traversal
Expreesion Tree&Postfix Notation of an Expression
Infix-Postfix Coversion
Exercises
Graph and Tree Traversals III (Topological Sort)
Topological Sort
Topological 证明
Two IQ questions
Exercises
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
Exercises
Week 6 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
Exercises
Week 7 Searching Set Data III (B-Tree)
B-tree EM Model
B-tree insert
B-tree delete
Exercises
Week 8 Hashing (Chaining, Open Addressing)
Hashing
Common Hash Function
Exercises
Suffix Tree and Suffix Array
Indexing Strings& Suffix Array
Exercises
预备知识
C/C＋＋ Programming
证书或学分
修习完毕课程内容并完成所有课程要求，可获得「修课证明」。
参考资料
指定用書
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
