数据结构基础 (Coursera)

本课程围绕着“算法+数据结构=程序”的思路，以问题求解为导向进行学习，帮助大家提高理论、抽象、设计的能力。主要包括的内容有：线性表，栈与队列，字符串，二叉树，树，图。学生将通过权衡时空和其他资源开销，利用数据结构来组织数据、设计高效的算法、完成高质量的程序以满足错综复杂的实际应用需要。

Syllabus

WEEK 1

欢迎来到数据结构基础

欢迎你学习《数据结构基础》！相信大家听说过一个著名的公式“程序 = 数据结构 + 算法”，掌握数据结构和相关算法是设计程序来解决实际问题的基础能力。如何在解决一个问题的过程中把信息抽象出来？数据管理应当以什么样的方法存储？应当使用什么算法去求解问题？所选择的算法是否高效？学习了概论内容之后，你将对数据结构和相关算法有基本的了解，掌握一些算法效率分析的基本方法。另外，本模块还补充了编程作业指南和C++面向对象知识。重点：问题求解、数据结构的基本概念（逻辑、存储、运算），抽象数据类型，算法和算法的复杂度分析。难点：问题建模，抽象数据类型的理解，算法复杂度渐进分析。PS：我们这门课程一直处在不断地建设与优化当中，吸取了很多以往课程的经典视频，所以如果你看到视频中出现了不同课程的名字，也不要惊讶哦，因为你正在集百家所长：）

WEEK 2

线性表

线性结构是最简单而应用最广泛的一种数据结构，在不同的场合会采取不同的存储结构和实现方法。本模块将介绍一种简单的线性结构——线性表，就是同类型的元素排成的一个线性序列，并且介绍了线性表的两种实现方法，即顺序表和链表。如何来实现顺序表和链表？什么时候应该用顺序表，什么时候链表更好？这一模块可以让你学会使用线性表及其相关的一些操作，解决一些简单问题，并考察分析时间空间上的效率，例如约瑟夫问题。重点：线性结构的逻辑定义，线性表的各种分类，顺序表、链表的定义和相关操作。难点：注意顺序表、链表的各种时间空间效率讨论，包括插入删除检索等在各种概率分布情况下的讨论。链表要特别注意表头结点的作用，链表指针的正确操作。PS：我们这门课程一直处在不断地建设与优化当中，吸取了很多以往课程的经典视频，所以如果你看到视频中出现了不同课程的名字，也不要惊讶哦，因为你正在集百家所长：）

WEEK 3

栈与队列

日常生活中，你会发现如果桌上有一叠盘子，大家都只会拿最上面的那一个，食堂排队的时候，你总是先找到队尾加入，而排在队首的同学打完饭之后就会离开。也就是说，有的时候你也许只需要在线性序列的一端或两端进行操作，对应的就是栈和队列这两种受限的线性表，他们是最简单的基础数据结构，应用也最广泛。

栈和队列有哪些特殊的操作？栈和队列能解决什么样的问题？学习完本章之后，你就可以用栈和队列这种数据结构，来解决与“先进先出”、“先进后出”有关的实际问题了，如宽度优先搜索、表达式求值等。 重点：栈的 LIFO 特性，深度优先搜索，理解递归中栈的作用；队列的 FIFO 特性，宽度优先搜索。 难点：机械的递归转非递归，简单理解就可以了，不需要掌握；顺序队列的实现假溢出处理。

WEEK 4

字符串

生活中不仅仅只有数值或单个字符，很多情况下，由若干个字符构成的字符串能表达更明确的信息。

在计算机中，字符串是如何存储的？有哪些相关操作？字符串常用的运算——模式匹配有哪些相关算法？你将会了解到字符串在计算机中的存储形式，常用的字符串操函数，以及模式匹配的一些高效的算法，并在实际问题中运用字符串处理技术。 重点：掌握字符串的基本概念（注意‘\0’结束符），KMP快速模式匹配。 难点：KMP快速模式匹配在一些重复子串问题中的应用。

WEEK 5

二叉树基础

你是不是发现，在线性表中查找一个元素每次都要遍历整个表？效率如此低下，怎么改进呢？解决方案是使用非线性的数据结构——树型结构，这一章主要介绍一种最基础而最重要的非线性结构——二叉树。

二叉树有哪些性质？如何在一棵二叉树中寻找一个特定的元素？如何来实现一棵二叉树？学习完这一模块，你会对二叉树的概念，以及一些简单的相关操作有基本的了解。 重点：二叉树、满二叉树、完全二叉树的概念和性质，二叉树的前中后序各种深度优先遍历，二叉树宽度优先遍历。 难点：栈在二叉树非递归深搜中的应用。

WEEK 6

二叉树应用

你需要在一堆数据中快速查找某一个元素？你需要经常删除数据中的最大值？你需要对一些信息进行最优编码？在学习了二叉树这种数据结构之后，我们可以对二叉树附加一些限制条件，使得二叉树满足一些特殊的性质，并方便我们进行插入、删除、修改的操作，从而可以用来解决相关的实际问题。

在这一模块中，你将学到二叉搜索树、堆与优先队列、Huffman树这三种最常用的特殊二叉树，了解他们的性质和实现方法。 重点：二叉搜索树的索引性质，在二叉搜索树中插入删除的操作，Huffman树、堆的性质和应用。 难点：在各种特殊二叉树中插入删除结点时要注意保持该数据结构的性质而且尽量保持各种操作的性能。

WEEK 7

树

生活中，树形结构是很多客观事物与关系的抽象模型，例如亲属关系可以形成一个族谱，公司的上下级关系可以形成一个人事表。不过这些树形结构中，父结点往往都不止一个子结点，说明二叉树的表达能力不足以表示这些常见的客观问题。

本章将引入树和森林的概念，介绍树的存储结构和多种表示方法。在实际应用中，你可以根据不同的情境，使用不同存储方式的树，从而解决相关的问题。 重点：树的深搜、宽搜遍历，树的左子/右兄表示，父结点表示法与并查集运算，树的顺序存储（输入/输出都要考虑）。 难点：树的各种应用基本上都基于遍历框架，需要注意左子/右兄表述方法中的对右兄弟链的访问；树的顺序存储通常也适应于二叉树的情况，可以用于完成建树的操作。

WEEK 8

图

实际生活中可以用图的形式描述的问题随处可见，例如通信网络、社交网络等。图通常用来描述一个网状关系，图的结点描述了个体的信息，结点与结点之间的边描述了个体之间的关系，边还可以有权重，描述了这种关系的强弱程度。

在这一章中，除了图的存储结构、遍历方法，你还会学到图结构的实际应用，如最短路径和最小生成树这两类最常见、最经典问题的解决方法。 重点：图的深搜、宽搜框架；图的相邻矩阵、邻接表、十字链表等存储方法。图的最短路Dijkstra算法、Floyd算法，最小生成树Prim、Kruskal算法。 难点：基于这图搜索框架的应用，例如拓扑排序；图的不同存储方式，适应范围和时空复杂度；最短路、最小生成树等综合应用。

WEEK 9

期末考试，新征程起航！

恭喜大家完成了《数据结构基础》这门课的所有教学模块，现在就让我们一鼓作气完成期末考试，给这段难忘的学习里程画上一个圆满的句号吧！期末考试的题目将帮助你全方位地回顾课程中的重难点，让你体会到我们一路学习过后的成长与进步。如果测试没有一次通过也不要紧，只要认真复习相应的教学视频，一定能找到答案，我们的自助平台课程鼓励你反复尝试直到取得满意的成绩，加油！如果你成功地通过了测试，那我们就相约在专项课程的下一门《高级数据结构与算法》中见咯！