一、绪论
1.1 数据结构的基本概念
逻辑结构：线性、非线性（树、图、网、集合）
非线性数据结构：其逻辑特征是一个结点元素可能有多个直接前驱和多个直接后继
存储密度
“单链表的存储密度小于1。原因：“存储密度=单链表数据项所占空间/结点所占空间”，而“ 结点所占空间＝数据项所占空间＋存放后继结点地址的链域”；所以，存储密度小于1。”
1.2算法和算法评价
算法五大特征：
输入、输出、有穷性、确定性和可行性
二、线性表
2.1 定义
广义表对应树
Q:假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树的长度、深度为？
A: 3，2。
2.2 线性表的顺序表示
2.3 线性表的链式表示
三、栈和队列
3.1 栈
3.2 队列
数组Q[0…n]用来表示一个循环队列，f为当前队头元素的前一位置，r为队尾元素的位置，假定队列中元素的个数总小于n，计算：
注意：区别表达式——
队空、队满、队中元素数量
牺牲一个单元时：
队空：Q.f=Q.r
队满：(Q.r+1)%n=Q.f
队列中元素个数:(n+Q.r-Q.f)% n
波兰式（前缀）
是在通常的表达式中，二元运算符总是置于与之相关的两个运算对象之前，所以，这种表示法也称为前缀表达式。
栈和队列都是线性表？·
他们是受限线性表。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列，分一般线性表和受限线性表。
3.3 栈和队列的应用
括号匹配
表达式求值P92
在运算符优先原则下，画出运算符栈和操作数栈的变化过程：
检测到括号，则可以弹出。。。
递归
层次遍历
计算机系统
3.4 特殊矩阵的压缩存储
四、串
4.1 串的定义和实现
Q：两个字符串相等的充要条件？
A：长度相等；对应位置字符相同。
4.2 串的模式匹配
Next数组：
| 序号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 模式串M | a | b | a | b | a | a | a | b | a |
| Next[j] | 0 | 1 | 1 | 1 | 2 | 3 | 4 | 2 | 3 |
| Nextval[j] | 0 | 1 | 0 | 1 | 0 | 4 | 2 | 1 | 0 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
M同，nextval=next指向的nv;
M不同，nextval=自己的next
数组下标，不说就是0，0起，说了一般是1，1起
五、树与二叉树
5.1 树的基本概念
5.2 二叉树的概念
Q：二叉树是不是树的特殊形式?
不是!虽然二叉树也属于一种树结构,但它 是另外单独定义的一种树,并非一般树的特例。
它的子树有顺序规定,分为左子树和右子树。不能随意颠倒。
二叉树公式合集：
n个结点：n-1个非空指针域（n1+2n2）
n0=n2+1
H=[down log2n]+1 = [up log2(n+1)]
叶子数n0 = [up n/2] = [奇数 (n+1)/2] = [偶数 n/2]
双亲序号= [down i/2]
孩子序号= [left 2i] = [right 2i+1]
完全二叉树_编号最小的叶子结点 = [n=奇数 n2+1] = [n=偶数 n2+2]
5.3 二叉树的遍历与线索二叉树
二叉链表的空指针：左前驱，右后继
5.4 树、森林
树的存储结构
树有0（空树）或1个根节点：
定义：树是N个结点的有限集合，N=0时为空树，任意非空树应满足：
1.仅有一个根结点
2.当N>1时，其余结点又分为互不相交的有限集合，为根结点子树
树、森林、二叉树的转换
树转 二叉树：左孩子右兄弟：形态唯一
二叉树转 森林：右孩子变兄弟，右孩子的右孩子也变兄弟
树和森林的遍历
普通树：某个节点可能有多个孩子，没有中根遍历
森林：由多棵树组成，逻辑上没有后序遍历
5.5 树与二叉树的应用
二叉排序树
平衡二叉树
目的：避免树增高过快
平衡因子：h左-h右
LL（右单旋转）
RR（左单旋转）
这里的LL、RR指的是初始状态而不是操作动作，因为动作和状态是反着来的
LR、RL旋转则不会引起歧义
5.5.3 哈夫曼树和哈夫曼编码
- 哈夫曼树：n1=0
WPL最小的二叉树
WPL=(W1L1+W2L2+W3L3+...+WnLn)
n = 2n0-1个结点（n0为叶子数）
H_max = n2+1 = n0
H_min = [up log2(n+1)]
- 哈夫曼编码
末端矩形内容：字符+出现次数
只有度为0、1的结点！（若有000，必有001）
六、图
6.1图的基本概念
关节点
如果一个连通的无向图中的任一顶点被删除后，剩下的图仍然连通，那么这样的无向连通图就称作是双连通的(biconnected)。(上图的无向图是双连通的)
如果一个图不是双连通的，也就是说存在一些顶点，将其删除后图将不在连通，我们把那些顶点称为割点或者关节点(articulation point)。
6.2图的存储与基本操作
存储结构：
邻接矩阵法O(n^2)
邻接表法O(n+e)
6.3图的遍历
6.3.1 BFS
6.3.2 DFS
Q：深度优先生成树怎么画？
A：可以有多个儿子，不一定是二叉树，所以随意画就行；
注意，连通图才有生成树，非连通图产生生成森林。
6.3.4 图的遍历与图的连通性
无向图的最小生成树：包含所有V，不成环，保持有连通最少的边
无向图的连通分量：极大连通子图，一定成环
无向图：度=边的2倍
无向连通图至少有n个结点
无向非连通图至少有n+1个结点
有向连通图至少有n个结点
有向非连通图至少有n+1个结点
6.4图的应用
任何一个无向连通图的最小生成树为什么有一棵或多棵呢？
一棵：只有两个结点
多棵：保持连通即可
6.4.1 最小生成树：
6.4.1.1 Prim普里姆算法（稠密）：不断加顶点、边
O(V^2)
边数较多可以用普里姆算法，因为它是每次加一个顶点，对边数多的适用。
6.4.1.2 Kruskal克鲁斯卡尔算法（稀疏）：不断连边
O(ElogE)
边数较少可以用Kruskal克鲁斯卡尔算法，因为克鲁斯卡尔算法算法每次查找最短的边。
6.4.2 最短路径
6.4.2.1 Dijkstra（单源最短路径）
每一轮新加入一个顶点到集合S中，之后该顶点的行标记打钩，即不更新。
6.4.2.2 Floyd（每对顶点的最短路径）
逐步尝试在原路径加入顶点k作为中间顶点，若新路径短于原路径，则代替之。
6.4.4 拓扑排序
6.4.5 关键活动
AOE网
有向边代表活动
七、查找
7.1查找
静态查找
动态查找：二叉排序树
动态查找的过程中对表的操作会多两个动作：如果某特定的关键字在表中不存在，则按照一定的规则将其插入表中；如果已经存在，则可以对其执行删除操作。动态查找的过程虽然只是多了“插入”和“删除”的操作。
7.2 顺序查找与折半查找
链表是不知道地址的，不能随机访问数据，所以用二分查找是不合适的。
总的查找次数是n/2+n/4+n/8+n/16 +........≈ n
在脑海中想象一下最大值的二分查找，每个数其实都查找了一遍。
另外，这里说的比较次数，如果查找次数不算是比较次数的话，那比较次数应该是你说的log2n.
7.3 B树和B+树
判定树：
查找成功ASL
查找失败ASL
7.4 散列表
散列表的基本概念
建立关键字和地址的直接映射关系
散列函数的构造方法
散列表处理冲突的方法：
开放定址：
H_i = ( H(key) + d_i ) % m
线性探测法：d_i为常数
H(key)=key%P，P一般取质数
平方探测法（二次探测法，平方再散列）：di=1^2,-1^2,2^2,-2^2......
再散列法（双散列法）：Hi=(H(key) + i*Hash_2(key) ) % m，用第二个散列函数计算关键字地址的增量，每一次增加1也可以，叫做线性探测再散列
伪随机序列法：d_i为随机数序列
拉链法
八、排序
8.1 排序的基本概念
基本有序：
Q:在第i 趟直接插入排序中,要进行 i-1 次关键字的比较吗?
8.2 插入排序
直接插入排序：
折半插入排序
希尔排序
8.3 交换排序
冒泡排序：
没有发生交换，提前结束，不会做多余运算
希尔排序
8.4 选择排序
简单选择排序
堆排序
8.5 归并排序和基数排序
8.6 各种内部排序的应用和比较
8.7 外部排序
九、数组和广义表
数组：没说开头序号，开头序号就是0,0
广义表：
GetTail取最后一个元素，尾巴多(一个)括号；
GetHead 取第一个元素
