台湾新竹“清华大学”

数据结构

图片
课程概述

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


本课程由台湾新竹清华大学提供,因课程视频由主讲教师录制并上传,凡课程视频中“国立清华大学”均指“台湾新竹清华大学”。


证书要求

修习完毕课程内容并完成所有课程要求,可获得「修课证明」。

预备知识

C/C++ Programming

授课大纲

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


参考资料

指定用書

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