1图的表示
这节课学习了图这种非线性表数据结构，关于图，我们需要理解这样几个概念：无向图、有向图、带权图、定点、边、度、入度、出度。除此之外，我们还学习了图的两个主要的存储方式：邻接矩阵和邻接表。
邻接矩阵存储方法的缺点是比较浪费空间，但是优点是查询效率高，而且方便矩阵运算。邻接表存储方法中每个顶点都对应一个链表，存储与其相连接的其他顶点。尽管邻接表的存储方式比较节省存储空间，但链表不方便查找，所以查询效率没有邻接矩阵存储方式高。针对这个问题，邻接表还有改进升级版，即将链表换成更加高效的动态数据结构，比如平衡二叉查找树、跳表、散列表等。
2深度和广度优先搜索
广度优先搜索和深度优先搜索是图上的两种最常用、最基本的搜索算法，比起其他高级的搜索算法，比如A*、IDA*等，要简单粗暴，没有什么优化，所以，也被叫做暴力搜索算法。所以，这两种搜索算法仅适用于状态空间不大，也就是说图不大的搜索。
广度优先搜索，通俗的理解就是，地毯式层层推进，从起始顶点开始，依次往外遍历。广度优先搜索需要借助队列来实现，遍历得到的路径就是，起始顶点到终止顶点的最短路径。
深度优先搜索用的是回溯思想，非常适合用递归实现。换种说法，深度优先搜索是借助栈来实现的。
在执行效率方面，深度优先搜索和广度优先搜索的时间复杂度都是O(E)，空间复杂度是O(V)。
3字符串匹配基础（上）
这节课学习了两种字符串匹配算法，BF算法和RK算法。
BF算法是最简单、粗暴的字符串匹配算法，它的实现思路是，拿模式串与主串中所有子串匹配，看是否有能匹配的子串。所以，时间复杂度也比较高，是O(n*m)，n、m表示主串和模式串的长度。不过在实际的软件开发中，这种算法实现简单，对于处理小规模的字符串匹配很好用。
RK算法是借助哈希算法对BF算法进行改造，即对每个子串分别求哈希值，然后拿子串的哈希值与模式串的哈希值比较，减少了比较的时间。所以，理想情况下，RK算法的时间复杂度是O(n)，跟BF算法相比，效率提高了很多。不过这样的效率取决于哈希算法的设计方法，如果存在冲突的情况下，时间复杂度可能会退化。极端情况下，哈希算法大量冲突，时间复杂度就退化为O(n*m)。
4字符串匹配基础（中）
这节课学习了一种比较复杂的字符串匹配算法，BM算法。尽管复杂、难懂，但是匹配的效率却很高，在实际的软件开发中，特别是一些文本编辑器中，应用很多。
BM算法的核心思想是，利用模式串本身的特点，在模式串中某个字符与主串不能匹配的时候，将模式串往后多滑动几位，以此来减少不必要的字符比较，提高匹配的效率。BM算法构建的规则有两类，坏字符规则和好后缀规则。好后缀规则可以独立于坏字符规则使用，因为坏字符规则的实现比较消耗内存，为了节省内存，我们可以只用好后缀规则来实现BM算法。
5字符串匹配基础（下）
KMP算法和上一节讲的BM算法的本质非常类似，都是根据规律在遇到坏字符的时候，把模式串往后多滑动几位。
BM算法有两个规则，坏字符和好后缀。KMP算法借鉴BM算法的思想，可以总结成好前缀规则。这里面最难懂的就是next数组的计算。如果用最笨的方法来计算，确实不难，但是效率会比较低。所以我们学习了一种类似动态规划的方法，按照下标i从小到大，依次计算next[i]，并且next[i]的计算通过前面已经计算出来的next[0]，next[1]，......，next[i-1]来推导。
KMP算法的时间复杂度是O(n+m)，不过它的分析过程稍微需要一点技巧，不那么直观，我们懂了即可，无需掌握，在平常的开发中，很少会有这么难分析的代码。
