第一章
数据类型
大端：高位在低地址（形容的是单个数据内部的构造形式）
OOP->AOP：object oriented program；封装、继承多态
Java
第二章
空间复杂度
组件：指令空间、数据空间、环境栈空间（保存恢复执行部分完成的函数所需的信息）
部分：定长+变量
S(n)=0：空间复杂度为常数级（S：space）
n以byte为单位（8bit）
时间复杂度
模糊的、取平均情况
插入i++，对程序主要步骤进行计数，以估计时间复杂度
大O表示法：相同数量级
O(1)：常数级
Omega Ω表示法：表示下界
Theta θ表示法：不能向大了写，也不能向小了写
递归
迭代
第三章
线性表
数组实现：查找、删除、插入复杂度O(n)
单链表实现：查找O(n)、删除、插入O(1)
单链循环表
front为队头指针，rear为队尾指针，m为队列最大容量
- 入队：rear = (rear + 1) % m
- 出队：front = (front + 1) % m
- 队空：front = rear
- 队满：front = (rear + 1) % m
- 当前队列中的元素数目： n = (rear - front + m) % m
静态链表
由数组实现的单链表，每个单元含有element和next两个元素栈
FIFO表；单链表（从栈顶指向栈底）；数组实现（栈底为0，一个int类型指向栈顶）中缀表达式转后缀表达式
操作：
1、遇操作数直接输出
2、遇符号、左括号压栈
3、遇右括号出栈，直到遇左括号（不打印括号）
4、遇结尾’#’全部出栈队列
一边进，一边出
数组实现：视为一个圈；两个指针
当队列队尾指针到数组尾部时，调整到数组头部
- back = (back + 1) % theArray.length
算法：寻找路径
搜索过程：从起点开始，循环：相邻位置标i，进栈，i++，直到终点被标记；
路径构造：保存终点，循环：出栈距离为n-1的点，查找与终点相邻点，加入队列，n—，直到起点出栈；
单调栈
种类：
- 单调递增栈：数据出栈的序列为单调递增序列
- 单调递减栈：数据出栈的序列为单调递减序列
入栈实现（单调递增栈）：
- 如果入栈元素大于栈顶元素，则直接入栈
如果入栈元素小于栈顶元素，则需要出栈知道大于栈顶元素，然后依次按照顺序入栈。
第四章：树（4、树）
第五章
散列表：Address = hash(key)
常用的哈希函数:奇偶校验法散列函数应用
散列函数
取余法：H(Key) = Key%M
平方取中法：H(Key) = Key^2的中间部分，其长度取决于表的大小
乘法杂凑函数：H(Key = [M((θKey)%1)]；%1是留下小数部分
字符串-1：把字符串的ASCLL值或者Unicode值相加
字符串-2：添加一个常数形成多项式，H(Key)=x_0+kx_1+k^2x_2……；再对表长求余解决散列表冲突
线性探测：若冲突则线性顺序（向后）查找
二次探测法：非线性，按照1、4、9顺序增加
双散列哈希：设置两种哈希算法，再第一种位置被占用的时候，放在第二种；再冲突则进行相应探测=》表项数>表70%时，再散列，将数据重新存入两边容量的哈希表中。
分离链法：近似于邻接表的实现；该哈希值对应空间存放一个指向单链表的表头的指针第六章
优先级队列
实现：无序线性表
物理实现：堆（大、小根堆）
插入：放在末端，上滤；O(log{2}n)
删除：与最末端交换，下滤；O(log{2}n)
初始化：从最后一个节点的父结点[currentSize/2]开始，对所有的非叶节点进行下滤操作（类似下滤）；O(n)
1、i为当前节点；c=2i；y为i节点大小（大根堆）
进入循环{
2、判断c和c+1的大小；若c+1大；则c++（使c中存子节点较大者）
3、判断c和y大小；y大：跳出循环；c大：交换[c/2]和c；
3.1、此时c中保存的是y；c*2；再进行步骤2；
}对应关系
节点i：父节点[i/2]；子节点（2i）、（2i+1）;从1开始计数
堆排序
初始化O(n)
逐个删除O(log{2}n)
复杂度：O(nlog{2}n)第七章
并查集
实现：数组；存储值为0时，表示根节点
物理实现：森林
合并：根节点指向另一并查集
查找：递归（从下向上）性能提升
1、
合并：结点数少的树挂到结点多的树下面=>减少高度
实现：根节点储存值变为负数，用负数记录树高
2、
在查找途中将所遇节点归到根节点上（压缩路径）
实现：递归public int find(int x) {if( s[x] < 0 )return x;elsereturn s[x] = find(s[x]);}第八章
顶点度数：有向图：TD(v) = ID(v)+OD(v)
性质：度数和为边条数的两倍
路径：没有环
极大连通子图：结点个数最多的连通的子图
强连通：有来回图的实现
1、邻接矩阵（无向图是对称的）
2、邻接表（逆邻接表）（数组+单链表）多重邻接表
在邻接表中，每条边含有两个端点，故在邻接表中需要2n个节点来储存
每个边结构代表一条边：
边结构
{
vertex1：
vertex2：
path1：
path2：
}
通过path1形成一条vertex1相同的单链表，含有vertex1元素的数组空间指向该单链表表头；
path2同上；
对于有向图，vertex1元素对于的空间含有两个指针，分别指向其出边和入边的单链表的表头；在边结构中，vertex1为起始点，vertex2为终点遍历
最小生成树
kruskal
1、所有边权重排序
2、选取最小代价边加入，且不构成回路，直到有n-1条边
复杂度分析：建立e条边的最小堆
- 检测邻接矩阵O(n2)
- 每插入一条边，执行一次 fiterup() 算法：log2e 所以，总的建堆时间为O(elog2e)
构造最小生成树时
使用两个数组Lowcost[ ]、nearvex[ ]
- Lowcost[]:存放生成树顶点集合内顶点到生成树外各顶点的边上的当前最小权值
- nearvex[]:记录生成树顶点集合外各顶点，距离集合内那个顶点最近。
注意：加入新的点后，在更新Lowcost[]时需在nearvex更新该最小值的对应边
最短路径
Dijkstra(固定点到其余点最短距离，非负)
- 起点V0，首先直接连接，不管是否直接连接。
- 循环（直到所有点的最短路径都已确定）{
- 将最短路径加入结果
- 借道上一最短路径，计算到其余点距离，若小于目前值，则替换；
- }
贝尔曼——福特改进算法 (固定点到其余点的最短距离，权重可为负，无负回路)
与Dijkstra的区别：第k步要计算第k-1步的最短距离到其余所有点的距离（以确认的最小值仍需判断），然后取最小值，形成第k步的距离集。
第k步只受第k-1步影响
复杂度：O(n^3)
floyed算法（任意点到任意点的最短距离，权重大于0）
从所有点中选取一个中介点（n个）
遍历所有两点，判断经由该中介点是否让距离变短：是：修正该两点距离（n^2次）
复杂度：O(n^3)
活动网络
AOV
用顶点表示活动，用弧表示活动间的优先关系的有向图称为AOV网（无环）
AOV的拓扑排序
- 从图中选择一个入度为0的结点输出之。(如果一个图中，同时存在多个入度为0的结点，则随便输出任意一个结点)
- 从图中删掉此结点及其所有的出边。
- 反复执行以上步骤
- 直到所有结点都输出了，则算法结束
- 如果图中还有结点，但入度不为0，则说明有环路
实现：（栈或队列都可以）
- 具体实现算法：AOV网用邻接表来实现数组count存放各顶点的入度
- 并且为了避免每次从头到尾查找入度为0的顶点，建立入度为0的顶点栈，栈顶指针为top，初始化时为-1.
- 出栈后；若有新的点度变为0，则入栈；（循环直到栈为空）
复杂度：
- 算法分析：n个顶点，e条边
建立链式栈O(n)，每个结点输出一次，每条边被检查一次O(n＋e)，所以为:O(n＋n＋e)
AOE网络(无环有向图，有起点和终点)
用边表示活动的网络(AOE网络, Activity On Edge Network)又称为事件顶点网络
- 顶点：
- 表示事件(event) 事件——状态。表示它的入边代表的活动已完成，它的出边 代表的活动可以开始，如下图v0表示整个工程开始，v4表示a4，a5活动已完成a7，a8活动可开始。
有向边：
对于事件:
- Ve[i]－表示事件Vi的可能最早发生时间:定义为从源点V0->Vi的最长路径长度, 如Ve[4]=7天
- Vl[i]－表示事件Vi的允许的最晚发生时间:是在保证汇点 Vn-1 在Ve[n-1]时刻(18)完成的前提下，事件Vi允许发生的最晚时间＝ Ve[n-1]－ Vi->Vn－1的最长路径长度。是从最后汇点时间长度-两者之间最长路径
- 对于活动:
- e[k]－表示活动ak=
- l[k]－表示活动ak=
- l[k]-e[k]－表示活动ak的最早可能开始时间和最迟允许开始时间的时间余量。也称为松弛时间。 (slack time)
- l[k]==e[k]－表示活动ak是没有时间余量的关键活动
算法实现
1、拓扑排序（AOV）
2、计算事件最早时间Ve[i]，Ve[i]=max{Ve[j]+dur(< Vj,Vi >)}，沿着拓扑排序，从1到n-1，迭代遍历所有点（事件）（遍历当前节点之后的节点（事件））
3、计算事件最晚时间VI[i]，Vl[i]=min{Vl[j]-dur (
4、计算边（活动）最早开始时间，e[k]=Ve[i]，k =
5、计算边（活动）最晚开始时间，I[k]=VI[j]-dur
6、如果e[k]=I[k]，表示活动k是没有时间余量的关键活动第九章
插入排序
稳定的
复杂度：O(n^2)折半插入排序
改进了查找的复杂度：O(n^2)->O(nlogn)
插入复杂度仍为：O(n^2)希尔排序
实现：
1、取增量（gap），按增量分组（i，i+gap，i+2gap，……），数据组内排序（插入排序）
2、组合并
3、减半gap
4、循环步骤1、2、3，直到gap=1
复杂度：O(n^1.3)
不稳定冒泡排序
实现：
比较相邻元素，遍历n次
稳定的快速排序
实现：
大递归（left，right）
1、取基准值e（最左端）；如果left和right的差值小于等于1，则return
2、从右端（j）开始，循环{
比较D[j]和e大小
大：j—；
小：D[i]=D[j]；break
等：break
}
3、左端（i）开始移动，循环{
比较D[i]和e大小
小：i++
大：D[j]=D[i]；break
等：break
}
4、1，2，3递归（left，i-1）（i+1，right）
复杂度：O(nlogn)最大可到O(n^2)
基准值选取：随机；三数中值分割法（对三数排序，取中间）选择排序
直接选择排序
实现：
首先在n个记录中选出关键码最小(最大)的 记录，然后与第一个记录(最后第n个记录)交换位置，再在其余的n-1个记录中选关键码 最小(最大)的记录，然后与第二个记录(第n-1个记录)交换位置，直至选择了n－1个记录
复杂度：O(n^2)锦标赛排序
实现：
1、两两比较，大者上位
略堆排序
略秩排序
实现：
遍历，两两比较，败者排名加一
- e[k]－表示活动ak=
若有收获，就点个赞吧
0 人点赞
