第三章数据结构
线性结构
1、链表和线性表的优缺点对比。
2、链表的插删。
3、栈的进出顺序,后缀表达式的栈计算。
4、循环队列的空和满 判。
![]*(./note/test/three/queue.png)
5、串,kmp算法(求next数组)。
![]*(./note/test/three/kmp.png) 找k的技巧是找到左右对称的分界点,左边的串长度+1作为next数组的值,如无则为1
6、数组与矩阵的下标计算。可以通过特殊值代入法进行计算。稀疏矩阵存储;十字链表和三元组
![]*(./note/test/three/matx.png)
![]*(./note/test/three/tmatx.png)
7、广义表。左括号的个数就是广义表的重数。除了第一元素外,其他元素都是一个表。
树与图
1、![]*(./note/test/three/tree.png)
2、满二叉树:都具有左右孩子。完全二叉树:在满二叉树的情况下,缺少顺序末尾的结点。
二叉树第i层最多个
3、线索二叉树
![]*(./note/test/three/tree1.png)
4、最优二叉树(哈夫曼树)
![]*(./note/test/three/tree2.png)
哈夫曼树构建。左小右大。哈夫曼编码是左边为0,右边为1。
![]*(./note/test/three/hafu.png)
2、图使用邻接矩阵和邻接表存储。深度和广度遍历,使用邻接矩阵的辅助度为O(n^2) 邻接表是O(n+e)。
3、最小生成树。普利姆算法 (O(n^2))适合稠密图(边多的)和 克鲁斯卡尔算法 (O(elog2e)) 适合稀疏图(边少的)
4、拓扑排序:选择入度为0的任意一节点,删除其相关的边(弧)形成新图,重复上述直至仅剩一个结点。
5、AOE网。关键路径:最长的路径。
6、最短路径。迪杰斯特拉(贪心)和佛洛依德(动态规划)
查找和排序
1、顺序查找。
2、折半查找。有序的。(O(log2n))
3、分块查找。需要分块,建立索引表(存放开始下标,和局部最大值),块内部无需有序。效率在1,2之间
4、哈希。主要是记得解决冲突的方式。注意平均查找长度的计算。
1、插入排序
2、希尔排序,不稳定
3、冒泡排序
4、快速排序。O(nlog2n)(分治)
5、简单选择排序。不稳定
6、堆排序。O(nlog2n) O(n)
7、归并排序(分治)O(nlog2n) O(n)
8、基数排序 稳定的
![]*(./note/test/three/sort.png)