线性结构
线性结构¶
考点一 线性表的基本操作¶
对于链表这类题目，通过画图可以不费脑子准确的解出。同时牢记：插入删除找前驱。
- 有些题目选项本身来说是没有问题的，但是为了代码的健壮性，我们要选择最对的，如：
B选项画图得出是完全正确的，但是没有考虑到当前链表里只有一个头节点和首元结点（！！！第一个真正拥有有效数据的结点！！！），当删除首元节点后，尾指针需要指向头结点。因此这类题目一定不能着急定结论，看到了if首先要想到健壮性。
408中链表的第一个元素常常指的是首元结点。
考点二 栈和队列的基本操作¶
此类考题画图模拟通常来说就可以解决
- 对于这类没有给出出入栈顺序的题目，由于abc顺序是一定的，因此，只需要让e插空即可。
- 对于此类求出对序列的题，由于出队只能在一边，并且元素是如对后再进行出队操作的，所以可以确定下来元素在队列中的状态，检查是否能通过入队操作放成这种状态即可。
考点三 卡特兰数¶
对于第二条，先序序列其实就是入栈序列，中序序列就是出栈序列，先 + 中确定一个唯一的二叉树。
如果将本题改为 先序序列有四个不同元素时的不同二叉树形的个数是？ 答案依旧是14，这是因为无论这几个值怎么取，二叉树形一共就这么几个，只是里面填的数据不一样。当然，如果问的不是二叉树形而是二叉数，那就是A44乘上每一种排序的卡特兰数。
有坑，实际是ps的位置已经确定，所以不确定的只有前面三个不同的o，带入n = 3即可。
考点四 假溢出和循环队列¶
下图为第一种设置方式，rear先放数再移动
下图为第二种设置方式，rear先移动后放数，并且rear初始默认放在数组最后一个地方
不难发现，无论是那种方式，队空队满是无法区分的，因此引入了：（方案1最常用）
此时队空条件为：rear -> next == front；队满条件为：rear -> next -> next = front(初始需要申请两个结点)
对于上述公式，可以根据下标做差 + 1得出。我个人的理解是让rear往右跑Max保证能大于front然后做差一减就可以了，当然别忘了取模。
此时，队空条件为：rear == front；队满条件为：rear -> next = front。（上图还未满）
考点五 栈的应用¶
考点六 队列的应用¶
考点七 特殊矩阵¶
本题在一轮时卡住了我，BOK的思路为：把这个二维数组放到一维数组里，与前面的方法统一，算出A[][]前有多少个元素，再加上二维数组起始地址就是最终答案。
考点八 KMP中的next数组和nextval数组¶
如何计算ne?可以数最长前后缀长度，但是长度一长可能容易出错。如果现在在算ne[i]，若模式串（字串）为s，s[i - 1] == s[ne[i - 1]]，那ne[i] = ne[i - 1] + 1;否则就不断回退，直到成功或失败。注意，成功时ne[i] = 跳到这个成功字符的ne + 1。失败指的是回退到下标为0时发现ne == -1了，意味着失败，也就意味着最长公共前后缀长度为0。
