只为自己学习进行一下记录
虽然之前上了一些关于数据结构、算法之类的课，但之前都没有怎么搞懂，尤其是算法里面的一些算法思想，现在看能不能补上，就是一些大佬的算法指导，刷LeetCode的一些题，回看之前的书上面的重点。
教材是清华大学出版社的数据结构(C语言版)、计算机算法分析与设计(第四版)
大 O 时间复杂度表示法( T(n) =O(f(n)) ） 实际上并不具体表示代码真正的执行时间，而是表示 代码执行时间随数据规模增长的变化趋势，所以也叫 渐进时间复杂度，简称 时间复杂度
由于 时间复杂度 描述的是算法执行时间与数据规模的 增长变化趋势，所以 常量、低阶、系数 实际上对这种增长趋势不产生决定性影响，所以在做时间复杂度分析时 忽略 这些项
例：
function cal(m, n) {
let sum_3 = 0;
let i = 1;
let j = 1;
for (; i <= m; ++i) {
j = 1;
for (; j <= n; ++j) {
sum_3 = sum_3 + i * j;
}
}
}
以上代码也是求和，两层 for 循环 ，求 sum_3 的数据规模为 m 和 n，所以时间复杂度为 O(m*n)。
时间复杂度可以分为：
一般我们最关心的还是最坏情况下的时间复杂度或平均复杂度
O(1) < O(logn) < (n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)
类比一下，空间复杂度全称就是 渐进空间复杂度（asymptotic space complexity），表示 算法的存储空间与数据规模之间的增长关系
例：
function print(n) {
const newArr = []; // 第 2 行
newArr.length = n; // 第 3 行
for (let i = 0; i <n; ++i) {
newArr[i] = i * i;
}
for (let j = n-1; j >= 0; --j) {
console.log(newArr[i])
}
}
跟时间复杂度分析一样，我们可以看到，第 2 行代码中，我们申请了一个空间存储变量 newArr ，是个空数组。第 3 行把 newArr 的长度修改为 n 的长度的数组，每项的值为 undefined ，除此之外，剩下的代码都没有占用更多的空间，所以整段代码的空间复杂度就是 O(n)。
这是一个进行字符串匹配的算法，原理是求一个字符串的某一个字符的前面的字符串最大相等的前缀和后缀
kmp算法为
int kmp(string s,string t,int pos){//s为主串，t为模式串
i = pos;
j=1;
while(i<s[0] && j<t[0]){//这两个0的位置存储的是string的长度
if(j==0 || s[i] == t[j]) {++i;++j}//j=0表示主串第i个字符和模式串第1个字符不匹配，需从第i+1个字符从新匹配
else j = next[j];
}
if(j>t[0]) return i-t[0]; // 匹配成功
else return 0;
}
求next数组的算法是仿照kmp的算法来的，i不进行后退，只有模式串滑动。因为求next也就是主串和模式串都是自己，可进行模仿kmp
void get_next(string t,int next[]){
i=1; j=0; next[1]=0;
while(i<t[0]){
if(j==0 || t[i] == t[j]){++i;++j;next[i]=j}
else j = next[j];
}
}
核心就是next[i]=j，先进行++是因为前面相等，则后面一个字符的next就是在if里相等的最后一个字符j的后面一个字符。符合前缀等于后缀的原则。
改进后的next算法
void get_nextval(string t,int nextval[]){
i=1; j=0; nextval[1]=0;
while(i<t[0]){
if(j=0 || t[i] == t[j]){
++i;j++;
if(t[i] != t[j]) nextval[i]=j;
else nextval[i] = nextval[j];
}
else j = nextval[j];
}
}
一般研究二叉树
1.第i层至多有2^(i-1)个节点
2.深度为k的二叉树至多有2^k-1个节点
3.任何一颗二叉树t，若其叶子节点数为N0，度为2的节点数为N2，则N0=N2+1
对于完全二叉树，就是对每一个节点，若有右孩子，则必有左孩子，且右分支的子孙的最大层次为l，则其左分支下的子孙的最大层次必为l或l+1.就是节点从左到右排顺序，这个顺序不能断。
4.有n个节点的完全二叉树的深度为log2 n向下取整+1
5.对任意节点i，若2i>n，则节点i无左孩子；如果有左孩子，其左孩子必是节点2i
6.若2i+1>n，则节点i无右孩子；如果有右孩子，其右孩子必是节点2i+1
7.i=1，则为根节点，若i>1，则双亲节点为i/2向下取余
二叉树可使用二叉链表进行存储，例如lchild | data | rchild。
遍历
先序，中序，后序。为根节点在查序中的位置
//先序的递归算法
Status preorderTraverse(Bitree t,Status(* visit)(TElemType e)){
status printelement(telemType e){
printf(e); //打印输出节点, 调用实例preorderTraverse(t,printelement);
return ok;
}
if(t){
if(visit(t->data))
if(preorderTraverse(t->lchild,visit))
if(preorderTraverse(t->rchild,visit)) return ok;
return error;
}else return ok;
}
//二叉树数据结构 js语法
function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
function DFStraval(node){
if(!node) return 0;
console.log(node.val);
traval(node.left);
traval(node.right);
}
function BFStraval(node){
const queue = [root];
while(queue.length){
let len = queue.length;
while(len){
let node = queue.shift();
console.log(node.val);
node.left&&queue.push(node.left);
node.right&&queue.push(node.right);
len--;
}
}
}
图的遍历
深度优先，广度优先
//深度优先遍历
Boolean visited[MAX]; //访问标志数组，初始值为false，当此节点被访问了，对应的visited[i]变为true
Status(*Visitedfunc)(int v)); //函数变量
void DFSTraverse(Graph G,Status(*visit)(int v)){
VisitedFunc = Visit;
for(v=0;v<G.vexnum;v++){visited[v] = false} //初始化
for(v=0;v<G.vexnum;v++){
if(!visited[v]) DFS(G,v); //对未访问过的节点调用DFS
}
}
DFS(Graph G,int v){
visited[v] = true; VisitFunc(v); //输出v节点
//FirstAdjVex返回v的第一个邻接节点，NextAdjVex返回v的相对于w的下一个节点，若w是v的最后一个节点，返回空
for(w=FirstAdjVex(G,v);w>0;w=NextAdjVex(G,v,w)){
if(!visted[w]) DFS(G,w); //对v的未访问过的邻接节点w递归调用DFS
}
}
最小生成树
稀疏图用Kruskal，稠密图用Prim
n个节点至少需要n-1条边连通，但边上还有权值，选择权值之和最小的n-1条边，可能不唯一
//最小生成树，普里姆算法，最小生成树不断壮大的过程，选顶点.使用邻接矩阵存储的网
//不断寻找与逐渐生成的最小生成树相连的边权最小的点加入
void MiniSpanTree_prim(MGraph G ,vertexType u){
//从第u个顶点出发构造最小生成树
//closedge记录从顶点集U到V-U的代价最小的边的辅助数组定义。就是未加入的节点和这棵生成树之间的权值
struct {
VertexType adjvex;//存储该边依附在顶点集U中的顶点
VRtype lowcost;//存储在该边上的权值
}closedge[MAX_VERTEX_NUM]
k = LocateVex(G,u); //开始的顶点的位置
for(j=0;j<G.vexnum;j++){ //辅助数组初始化,lowcost为开始节点u与其他节点之间的权值，权值可为无穷大
if(j != k) closedge[j] = {u,G.arc[k][j].adj} //{adjvex,lowcost}
}
closedge[k].lowcost = 0; //初始U={u}
for(i=1;i<G.vexnum;i++){ //选择剩下的G.vexnum-1个顶点
k=minimum(closedge)； //选择一个在closedge里边权值最小的顶点的序号，将其顶点和边加入最小生成树
printf(closedge[k].adjvex,G.vexs[k]); //输出边
closedge[k].lowcost = 0; //第K顶点并入U集
for(j=0;j<G.vexnum;j++){
//新顶点并入U后，重新选择最小边。就是更新closedge里面的lowcost的值
if(G.arcs[k][j].adj<closedge[j].lowcost)
//权值比原有的lowcost小，更新。 注意是k节点和其他节点之间的权值与之前节点的权值进行比较
closedge[j] = {G.vexs[k],G.arcs[k][j].adj};
}
}
}
另一个就是Kruskal算法，即连通分量（即不能形成环）不断合并的过程。在开始就将n个顶点加入U，选边。
每次选择边权最小的边链接两个端点是kruskal的规则，并实时判断两个点之间有没有间接联通形成环。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,tot=0,k=0;//n端点总数，m边数，tot记录最终答案，k已经连接了多少边
int fat[200];//记录集体老大。
//并查集就是一个用双亲表示法所表示的森林，我们可以利用这个结构来查找某一个顶点的双亲，进而找到根结点。这样，我们就能判断某两个顶点是否同源，在图中的表现就是加上这条边后会不会形成环。并查集以顶点为基准，有几个顶点，就有几项。
struct node
{
int from,to,dis;//结构体储存边,dis为权值
}edge[2000];
bool cmp(const node &a,const node &b)//sort排序（当然你也可以快排）
{
return a.dis<b.dis;
}
int father(int x)//找集体老大，并查集的一部分，就是寻找这个顶点的根
{
if(fat[x]!=x) //如果这不是根，就继续向上查找，直至找到根
return father(fat[x]);
else return x;
}
void unionn(int x,int y)//加入团体，并查集的一部分
{
//fat[father(x)]=father(y); //这感觉有些不能理解，甚至fat[x]=y好像也行
fat[x]=father(y); //这样也行
}
int main()
{
scanf("%d%d",&n,&m);//输入点数，边数
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&edge[i].from,&edge[i].to,&edge[i].dis);//输入边的信息
}
for(int i=1;i<=n;i++) fat[i]=i;//自己最开始就是自己的老大（初始化），自己的根就是自己
sort(edge+1,edge+1+m,cmp);//按权值排序（kruskal的体现）
for(int i=1;i<=m;i++)//从小到大遍历
{
if(k==n-1) break;//n个点需要n-1条边连接
if(father(edge[i].from)!=father(edge[i].to))//假如不在一个团体，其根不一样，就是判断形不形成环
{
unionn(edge[i].from,edge[i].to);//加入这个根的团体
printf("from=%d to=%d \n",edge[i].from,edge[i].to);//打印加入的边的路径
tot+=edge[i].dis;//记录边权
k++;//已连接边数+1
}
}
printf("%d",tot);
return 0;
}
//测试用例
//6 7
//0 2 1
//2 5 4
//5 3 2
//2 1 5
//1 4 3
//4 5 6
//0 4 3
拓扑排序
在有向图中选一个没有前驱的顶点（入度为0）输出，在图中删除该顶点和所有以它为尾的弧（也就是边）
可通过拓扑排序判断网中是否存在环，若所有的顶点都在拓扑排序序列中，则不存在环。
//拓扑排序，判断是否有环
Status topologicalSort(AlGraph G){
findinDegree(G,indegree); //对各个顶点求入度 indegree[0……vexnum-1]
InitStack(S);
for(i=0;i<G.vexnum;++i){
if(!indegree[i]) Push(S,i); `//入度为0的顶点入栈
}
count = 0; //对输出顶点计数
while(!StackEmpty(S)){
Pop(S,i);
printf(i,G.vertices[i].data); ++count; //输出i号顶点
for(p=G.vertices[i].firstarc; p;p=p->nextarc){ //判断这个输出顶点的邻接点
k = p->adjvex; //对i号顶点的每个邻接点的入度-1
if(!(--indegree[k])) Push(S,k); //若入度为0，则入栈
}
}
if(count<G.vexnum) return error; //该有向图有回路
else return Ok;
}
单源最短路径
// 单源最短路径：Dijkstra 算法
#include <iostream>
using namespace std;
int matrix[100][100]; // 邻接矩阵
bool visited[100]; // 标记数组
int dist[100]; // 源点到顶点 i 的最短距离
int path[100]; // 记录最短路的路径
int source; // 源点
int vertex_num; // 顶点数
int edge_num; // 边数
void Dijkstra(int source)
{
memset(visited, 0, sizeof(visited)); // 初始化标记数组
visited[source] = true; //开始节点被访问
for (int i = 0; i < vertex_num; i++)
{
dist[i] = matrix[source][i]; //开始节点到其他节点之间的权值
path[i] = source;
}
int min_cost; // 权值最小
int min_cost_index; // 权值最小的下标
for (int i = 1; i < vertex_num; i++) // 找到源点到另外 vertex_num-1 个点的最短路径
{
min_cost = INT_MAX; //先设为最大值
for (int j = 0; j < vertex_num; j++)
{
if (visited[j] == false && dist[j] < min_cost) // 先找到与之相连的权值最小的节点
{
min_cost = dist[j];
min_cost_index = j;
}
}
visited[min_cost_index] = true; // 该点已找到，进行标记
for (int j = 0; j < vertex_num; j++) // 更新 dist 数组
{
if (visited[j] == false && //表示这个节点还未被访问
matrix[min_cost_index][j] != INT_MAX && // 确保两点之间有边
matrix[min_cost_index][j] + min_cost < dist[j]) //**算法核心
{
dist[j] = matrix[min_cost_index][j] + min_cost;
path[j] = min_cost_index;
}
}
}
}
int main()
{
cout << "请输入图的顶点数（<100）：";
cin >> vertex_num;
cout << "请输入图的边数：";
cin >> edge_num;
for (int i = 0; i < vertex_num; i++)
for (int j = 0; j < vertex_num; j++)
matrix[i][j] = (i != j) ? INT_MAX : 0; // 初始化 matrix 数组
cout << "请输入边的信息：\n";
int u, v, w;
for (int i = 0; i < edge_num; i++)
{
cin >> u >> v >> w;
matrix[u][v] = matrix[v][u] = w;
}
cout << "请输入源点（<" << vertex_num << "）：";
cin >> source;
Dijkstra(source);
for (int i = 0; i < vertex_num; i++)
{
if (i != source)
{
cout << source << " 到 " << i << " 的最短距离是：" << dist[i] << "，路径是：" << i;
int t = path[i];
while (t != source)
{
cout << "--" << t;
t = path[t];
}
cout << "--" << source << endl;
}
}
return 0;
}
//结果
1.顺序表查找
二分法查找，low和high作为待元素的下界和上界，mid指示区间的中间位置。mid=(low+high)/2 向下取整，若mid对应的值大于被查找值key，则high = mid-1，否则low = mid+1，若相等则返回mid。当low<=high时，返回未查找到。
索引顺序表或分块查找
将表分成几个子表，对每个子表建立一个索引项，包含关键字项（子表里面最大的数）和一个指针项。
索引表暗关键字有序，则表有序或块有序
所以最后的查找是分两步进行，先确定待查记录所在的块，然后在块里面顺序查找
2.动态查找表
二叉排序树
动态树表，若左子树不空，则左子树所有节点均小于根节点的值，同理，右子树的节点均大于根节点的值。若查找不成功，就将关键字插入查找路径的访问的最后一个节点的左孩子或右孩子中。
一个无序列表就可通过构造二叉排序树成为一个有序序列。
3.哈希表
使每一个关键字和结构中一个唯一的存储位置相对应。
哈希表有些构造方法，但注意不要产生同义词，产生冲突
1.直接定址法
2.数字分析法
3.平方取中法
4.折叠法
5.随机数法
6.除留余数法 主流
H(key) = key mod p ; p<=m m为表长
核心是对p的取值
一般经验：P可选为质数或不包含小于20的质因数的合数
处理冲突的方法
1.开放定址法
Hi = (H(key) + di) mod m i = 1,2,3…,k (k<=m-1)
H(key)为hash函数，m为hash表长，di为增量序列
di有三种取法
2.再hash法
Hi = RHi (key)
当产生冲突时计算另一个hash函数地址
3.链地址法 主流
将所有关键字为同义词的记录存储在同一线性链表中，凡hash地址为i的记录都插入到线性链表中对应的头节点中，需保持同义词在同一线性链表中按关键字有序。
对hash表的查找和hash表的构造过程基本一致
给定K值，根据构造表的hash函数求得hash地址，若表中此位置没有记录，则查找不成功，否则比较关键字，若相等，则查找成功
有两个基本操作，1.比较两个关键字的大小。 2.将记录从一个位置移到另一个位置。 一般改变存储方式避免2.
1.插入排序 O(n^2)
将一个记录插入到已排好序的有序表中，从而的到一个新的、记录值+1的有序表
也有一种折半插入排序，优化了查找，结合了之前的二分法查询，进行关键字的判断，进而得到位置 仍是O(n^2)
2.希尔排序
优化了时间复杂度
先将整个待排记录序列分割成若干个子序列分别进行直接插入排序，待记录基本有序之后，再对全体记录进行一次直接插入排序
特点是：子排序的构成不是简单的“逐段分割”，而是将**相隔某个“增量”**的记录组成的一个子序列。增量最好为质数，最后一次排序必须为1，通常为5,3,1
3.快速排序
1.起泡排序 O(n^2)
若为逆序（r[1.key>r[2].key）交换两个记录的位置，然后比较第二个记录和第三个记录关键字，直至n-1和n进行比较过为止。
这算一次起泡排序，结果为最大的记录值被排到了最后一个的位置，之后进行第二次起泡排序，对前n-1个记录进行相同操作
2.快速排序
其是对起泡排序的一个改进
核心思想为通过一次排序将待排记录分割成独立的两部分，其中一部分的关键字均比另一组的关键字小，则可分别对这两部分记录继续排序，以达到整个序列的有序
首先需要选取一个枢轴，一般为第一个记录，之后将比他小的记录移到左边，大的移到右边。这样的一次操作称作一次快排
具体做法为附设两个指针low和high，初值指向low和high，还有一个枢轴记录的关键字pivotkey，之后首先从high的位置向前搜索找到第一个关键字小于pivotkey的记录并和枢轴记录交换位置，之后从low的位置向后搜索找到 一个比privotkey大的记录，并交换位置，重复这两部操作，直至low==high。可使用L[0]存储pivotkey，因为对枢轴的复制是多余的，只需要最后进行移位即可
//快速排序
int Prtition(SqList &L,int low,int high){
L.r[0] = L.r[low]; //子表的第一个记录做枢轴记录
privotkey = L.r[low].key;
while(low<high){ //从表的两端交替向中间扫描
while(low<high && L.r[high].key>=privotkey) --high;
L.r[low] = L.r[high]; //比枢轴记录小的记录移到左边
while(low<high && L.r[low].key>=privotkey) ++low;
L.r[high] = L.r[low];//比枢轴记录大的记录移到右边
}
L.r[low] = L.r[0]; //枢轴记录到位
return low;
}
4.选择排序
1.简单选择排序
通过n-i次关键字比较，选出最小的一个记录，并和第i个记录交换
2.树形选择排序
首先n个关键字进行两两比较，然后再n/2(向上取整)个较小者之间再两两比较，如此重复，直至选出最小的关键字为止
可使用有n个叶子节点的完全二叉树表示，两两比较，最后的根即是最小，之后选出次最小关键字，只需将原来的叶子节点里面的最小关键字，即上一次选出来的根的那个关键字，变为无穷大，这样就选出了次最小关键字
3.堆排序
堆排序是对树形选择排序的优化，主要是“筛选”，“建堆”
4归并排序
将两个或以上的有序表组合成一个新的有序表
递归看之前的一些就行，这里主要说分治法，各个击破，分而治之
基本思想是将一个规模为n的问题分解成k个规模较小的子问题，这些子问题相互独立，不包含公共的子问题，且与原问题相同，递归的解这些子问题（将这些子问题继续划分），然后将各个子问题的解合并得到原问题的解。常见的 k = 2
例：二分查找技术，棋盘覆盖，归并排序，快速排序等的具体实现
适用于解最优化问题，依赖于问题本身的两个核心性质：最优子结构性质和子问题重叠性质。分解的子问题往往不是互相独立的
最优子结构性质：动态规划算法的第一步首先是构造最优解的结构，当问题的最优解包含了其子问题的最优解，称为最优子结构
重叠子问题：递归运算自顶向下解此问题时，每次产生的子问题并不总是新问题，有些种子问题被计算多次，动态规划利用此性质，对每个子问题只解一次，而后将其解保存在一个表格中，当需要再次解此子问题时，只需要查看一下表格。
其每一步的选择都依赖于相关子问题的解，只有相关子问题的解出来后，才进行选择
例：矩阵连乘，最长公共子序列，最大子段和（分治与动规的区分），租用游艇问题
分治和动规都是自底向上解决问题
//租用游艇问题
int getMinRent(int n)
{
int dp[200];//令dp[i]为从出租站1到出租站n所需要的最少租金
dp[1]=0;//初始化
dp[2]=r[1][2];//初始化
for(int i=3;i<=n;i++)
{
dp[i]=r[1][i];//先初始化dp[i]为第1到i站的租金
for(int j=2;j<i;j++)
{
dp[i]=min(dp[i],dp[j]+r[j][i]);//状态转移方程
}
}
return dp[n];//返回n个
}
并不从整体最优上进行考虑，而是在局部最优进行选择，我们希望最后的结果也是整体最优的，虽然一些时候并不知道最优解，但最终结果确实最优解的很好地近似解。通常自顶向下进行求解
贪心每次仅做局部最优解，之后去解做出这个选择后产生的相应的子问题。
贪心算法基本要素：最优子结构性质，
贪心选择性质：所求问题的整体最优解可通过一系列局部最优的选择来达到。而且需要证明每一步做的贪心选择最终导致问题的整体最优解
例：活动安排问题，最优装载，多机调度问题，dijkstra最短路径算法，最小生成树算法
深度遍历解空间树，从根节点进行遍历，当发现某一节点肯定不包含问题的解，则跳过对其子树的遍历，逐层向祖先节点回溯
通常解题步骤为：首先定义问题的解空间树；确定易于搜索的解空间结构；深度优先搜索解空间，并在搜索过程中使用剪枝函数避免无效搜索
通常使用剪枝函数避免无效搜索：
1.用约束函数咋扩展节点处剪去不满足约束的子树
2.用限界函数减去得不到最优解的子树
一般可使用递归回溯，迭代回溯，子集树与排列树
子集树：从n个元素中找出满足要求的子集
排列树：确定n个元素满足某种性质的排列
左边的for循环中间，i<=n
例：0-1背包问题，旅行售货员问题 ，装载问题
广度优先+剪枝
一般来说，回溯法是求出问题的所有解；分支限界是求出一个解，或者说是在满足某一约束的最优解
在分支限界法中，活节点一旦成为扩展节点，就一次性生成所有子节点，舍弃所有不可行解或非最优解的儿子节点，其余儿子节点加入活结点表中。
从活节点表中选择下一扩展节点有几种方式
1.先入先出方式
2.优先队列式分支限界法（看哪一个节点先成为扩展节点）
例：装载问题，旅行员售货问题
总之先写到这里了，后面再改吧