《数据结构与算法》
重学数据结构与算法
第二章、线性结构
线性结构有两种表示形式。1、线性表：顺序表示（数组）；2、链表：链接表示（单向链表、单向循环链表、双向链表、双向循环链表，注意头节点的设置，以及其与首节点的区别）
第三章、栈与队列
栈：基于数组实现、基于链表实现；共享栈（同一栈空间存储多个栈信息，两个栈相向设置）
队列：基于数组实现（循环队列）、基于链表实现
优先队列：每个节点存在一个优先级，每次出队列的节点都是优先级最高的节点。这种思想在操作系统的进程管理中使用。a、基于数组实现（插入操作直接为插入到尾节点O(1)，删除操作得遍历整个队列，查找优先级最高的节点进行删除O(n)。删除一个节点后，为了减少移动多个节点带来的时间消耗，直接将尾节点放置删除节点的位置即可）；b、基于链表实现（按照优先级从高到低进行排序，优先级最高的为首节点。每次出队为首节点，插入节点需要从头开始遍历，直到优先级小于当前节点则插入到这个节点之前）；c、还有基于有序表或最小化堆来实现。
栈和队列的应用：1、括号匹配检查；2、中缀式与后缀式（后缀式也称为逆波兰式），后缀式没有括号，在计算机中更容易实现，但是我们输入的还是中缀式，所以我们得考虑$如何将中缀式转换为后缀式$，并且这个转换过程不能过于复杂，不然这样操作就没有意义；3、简单计算器的实现：在弄懂了2的实现方法之后，设计一个简单的计算器就比较容易了；4、Josephus问题：N个人坐成一圈传递东西，每传递M次，则该人离开，直到最后留下一个人则该人获胜。（可以使用循环链表加以模拟，但是也可以使用单链表来完成这个任务，注意单链表是有头节点来指向首节点，每当遇到next为nullptr时，则将当前节点转换为head-node，然后删除首节点）
第四章、串
串的存储也可以从两种方法来考虑：1、顺序方式，2、链式方式；由于常常操作的对象是连续的字符子序，所以多数情况下，串的存储采用顺序存储方式最为方便。
串的基本操作：串的长度、串相等、赋值操作、定位操作、求子串操作、插入操作、删除操作等。C++中已经已经提供了string.h串库，其中比较常用的有strcmp、strcpy、memcpy等，同时也提供了标准string类。
重点需要了解是字符串的模式匹配，即查找子串在主串中第一次出现的位置。主要有两种方法：1、BF（Brute-Force）算法，即保留求解方法，时间复杂度为O(m*n)；2、KMP（Knuth-Morris-Pratt）算法，时间复杂度可为O(m+n)。
重点讲解KMP算法的思想：
由于BF方法存在一个明显的缺陷，当每次匹配不成功时，主串中的下标就要回退到本次模式匹配开始字符的下一个字符位置。KMP算法就是让子串在不匹配的情况下无需回到顺序递增的下一位，从而减少不必要的匹配。核心实现思想就是最长前缀串。
在KMP算法中，主串指针i不会减小（即不回溯），是一个很大的优点，尤其是在硬盘中寻找模式的时候。使用BF算法进行模式匹配时，一旦匹配失败需要进行回溯，但是如果是主串在外存中，很可能之前的信息已经被覆盖，需要重新读取；而KMP算法只会移动模式串的指针j到其前一位并与主串当前失配点进行匹配，如果相同则将模式串当前的指针移动到最前面的前缀串位置，然后进行继续i++,j++匹配。这个操作就需要一个前提：计算出模式串中每个节点的最长前缀串最初的位置。
代码实现：