数据结构

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

国立清华大学

分享

数据结构
  • 分类: 计算机
  • 平台: 中国大学MOOC
  • 语言: 中文

课程概述

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

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

授课大纲

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

声明:MOOC中国收录之课程均源自下列机构,版权均归他们所有。本站仅作报道并尊重其著作权益,感谢他们对MOOC事业做出的贡献!(排名不分先后)
  • Coursera
  • edX
  • OpenLearning
  • FutureLearn
  • iversity
  • Udacity
  • NovoEd
  • Canvas
  • Open2Study
  • Google
  • ewant
  • FUN
  • IOC-Athlete-MOOC
  • World-Science-U
  • Codecademy
  • CourseSites
  • opencourseworld
  • ShareCourse
  • gacco
  • MiriadaX
  • JANUX
  • openhpi
  • Stanford-Open-Edx
  • 网易云课堂
  • 中国大学MOOC
  • 学堂在线
  • 顶你学堂
  • 华文慕课
  • 好大学在线CnMooc

Copyright © 2008-2015 MOOC.CN 慕课改变你,你改变世界