文章目录

基本概念线性结构树图排序散列查找KMP

基本概念

知识点总结 抽象数据类型（Abstract Data Type）： 数据类型：数据对象集+数据集合相关联的操作集 抽象：描述数据类型的方法不依赖于具体实现（与存放数据的机器无关、与数据存储的物理结构无关、与算法和编程语言无关） 算法 空间复杂度S(n)——占用存储单元的长度 时间复杂度T(n)——耗费时间的长度 复杂度的渐进表示法

T(n) = O(f(n))——存在常数C >0, n0>0，使得当 n>=n0时有T(n) <=C·f(n) T(n) = Ω(g(n))——存在常数C >0, n0>0，使得当 n>=n0时有T(n) >=C·g(n) T(n) = Θ(h(n))——表示同时有T(n) = O(h(n))和 T(n) = Ω(h(n))

复杂度分析技巧

1.若两段算法分别有复杂度T1(n) = O(f1(n))和T2(n) = O(f2(n))，则

T1(n) + T2(n) = max( O(f1(n)), O(f2(n)) )  T1(n)*T2(n) = O( f1(n)*f2(n) ) 

2.若T(n)是关于n的k阶多项式，那么T(n)=Θ(n^k) 

3.一个for循环的时间复杂度等于循环次数乘以循环体代码的复杂度 

4.if-else结构的复杂度取决于if的条件判断复杂度和两个分枝部分的复杂度，总体复杂度取三者中最大

编程习题 题目关键点最大子列和时间复杂度分析方法、分而治之、在线处理Maximum Subsequence Sum最大子列和的修改二分查找注意端点值的确定 思考题理论练习题

线性结构

线性表的基本操作（创建、查找、插入、删除）堆栈队列 题目关键点 一元多项式的乘法与加法运算 链表基本操作Reversing Linked List 抽象链表、单向链表的反向操作Pop Sequence栈的结构特点、栈的基本操作集

树

树的定义及表示二叉树及其存储结构二叉树的遍历及应用二叉搜索树（BST）平衡二叉树（AVL）哈夫曼树堆集合及运算 题目关键点树的同构建树操作（数组存储）、输入处理List Leaves数组存储二叉树、二叉树的层序遍历Tree Traversals Again三种遍历（先、中、后）的关系是否是同一棵二叉搜索树二叉搜索树的动态建立（插入操作）Root of AVL TreeLL、RR、LR、RL旋转与二叉树Insert操作的结合Complete Binary Search Tree完全二叉树+二叉搜索树堆中的路径堆的基本操作File Transfer集合的并查集

图

排序

散列查找

KMP