数据结构

随堂模式

  • 什么是随堂模式?

    随堂模式课程一般为每学期一轮次,课程每周更新,作业、考试有截止时间,由课程提供方老师、助教指导,课程完结,成绩由老师确认后,统一发放证书。

  • 什么是自主模式?

    自主模式课程常年开放加入,课件全部开放,作业、考试无截止时间,有学堂在线招募选拔的助教指导,考核通过即可自动获得证书。

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

课程描述

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

什么是认证证书?
免费学习
认证学习
名师签名
实名认证
权威性
纸质证书
付费购买
免费赠送

课程简介

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

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
Sandbox (non-scoring, just for practice)
HW1
HW2
HW3
HW4
HW5
HW6
HW7
HW8

授课教师

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

    学经历: *台湾清华大学资讯工程系副教授(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