Bin's blog

1.并查集 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include <iostream>using namespace std;const int N=1e3+10;int Father[N];void Make_Set(int x){ Father[x]=0;}int Find(int x){ if(Father[x]<=0) return x; Father[x]=Find(Father[x]); return Father[x];}void Union(int x,int y){ int fx=Find(x),fy=Find(y); if(fx==fy) return; if(Father[x]<Father[y]) Father[fy]=fx; else{ Fat ...

1.寻找父节点 12345678910111213141516171819202122232425262728293031323334353637383940414243#include <iostream>using namespace std;struct TreeNode{ int val; TreeNode* left, * right;};TreeNode* CreateTree(){ int k; cin >> k; if (k == 0) return NULL; TreeNode* root = new TreeNode; root->val = k; root->left = CreateTree(); root->right = CreateTree(); return root;}TreeNode* fa(TreeNode* root,int k){ if (root == NULL) return NULL; if (root->val == k) return N ...

1.KMP 12345678910111213141516171819202122232425262728293031323334353637383940#include <iostream>#include <string>using namespace std;const int N=1e5+10;void buildnext(string p,int next[]){ int m=p.size(); int k=next[0]=-1; for(int j=0;j+1<m;j++) { while(k!=-1&&p[k]!=p[j]) k=next[k]; next[j+1]=++k; }}int KMP(string s,string p){ int n=s.size(),m=p.size(); int next[N]; buildnext(p,next); int i=0,j=0; ...

1.单链表基本操作 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182#include <iostream>using namespace std;const int N = 1e5 + 10;struct node{ int val; node* next;};bool insert(node* dummyhead,int k, int d){ if (k < 0) return false; node* p = dummyhead; for (int i = 0; i < k; i++) { p = p->next; if (p == NULL) return false; } node* tmp = new node; tmp->v ...

堆排序动机直接选择排序低效原因：每次找最大元素需花费O(n)时间，涉及大量重复比较能否借助树形结构，减少元素的重复比较次数 锦标赛排序利用胜者树保存了前面比较的结果，下一次选取最大元素时直接利用前面比较的结果，从而大幅减少关键词比较次数 堆的概念及基本操作最大堆（大根堆）：一颗完全二叉树，其中任意结点的关键词大于等于它的两个孩子的关键词最小堆（小根堆）：一颗完全二叉树，其中任意结点的关键词小于等于它的两个孩子的关键词 回顾:完全二叉树的顺序存储故顺序存储 堆的两个基本操作上浮操作当大根堆的元素值R[i]变大时，该结点可能会上浮 12345678void ShiftUp(int R[],int n,int i){ while(i>1 && R[i]>R[n/2]) { swap(R[i],R[i/2]); i/=2; }} 下沉操作12345678910111213141516当大根堆的元素值R[i]变小时，该结点可能会下沉```cvoid ShiftDowb(int R[] ...

平方阶排序算法基本概念度量指标 时间复杂度 空间复杂度 排序算法的稳定性：Ri和Rj关键词相同，排序前顺序与排序后一致则稳定，否则不稳定 分类从存储设备角度 内排序：排序过程中所有数据元素都在内存中 外排序：当待排序元素所占空间大到内存放不下时，排序必须借助外存完成 对关键词的操作 基于关键词比较的排序 分布排序：基于元素的分布规律 按时间复杂度： 平方阶算法：算法简单，平均时间复杂度O(n^2) 线性对数阶算法：相对复杂，平均时间复杂度O(nlogn) 线性算法：不依赖关键词排序，需要已知元素的分布规律 直接插入排序把第i个元素插入到前n-1个元素中 12345678910111213void InsertionSort(int R[],int n){ for(int i=2;i<=n;i++) { int k=R[i],j=i-1; while(j>=1 && R[j]>k)//左移，找第一个小于k的数 { R[j+1]=R[j] ...

最小支撑树及图应用最小支撑树的概念最小支撑树：包含图G的全部顶点，且包含使子图连通所需的最少的边（n-1）性质：最小跨边一定在某颗最小生成树里 Prim算法准备工作Lowcost[v]：顶点v到集合S的最小跨边的权值，初始时Lowcost[u]=0,Lowcost[i]=∞pre[v]：顶点v到集合S的最小跨边在集合S中的端点，初值-1S[v]：顶点v是否在集合S中，初值0时间复杂度O（n^2） 12345678910111213141516171819202122232425262728293031323334353637383940int FindMin(int S[],int Lowcost[],int n){ int v=-1,min=INF; for(int i=1;i<=n;i++) { if(S[i]==0&&Lowcost[i]<min) { min=Lowcost[i]; v=i;
...

图的最短路径无权图最短路径 BFS无权图的单源最短路径问题准备工作dist[]：从源点到顶点i的最短距离，即Di，初值∞pre[]：从源点到顶点i的最短路径中顶点i的前驱顶点，初值-1∞的表示：INT_MAX / 0x3f3f3f3fconst int INF=ox3f3f3f3f; 基于BFS的无权图最短路径算法时间复杂度O(n+e) 1234567891011121314151617181920212223242526const int INF=ox3f3f3f3f;void BFS(Vertex Head[],int n,int u,int dist[],int pre[]){ Queue Q; for(int i=1;i<=n;i++)//初始化数组 { pre[i]=-1; dist[i]=INF; } dist[u]=0;//源点u入队 Q.enqueue(u); while(!Q.empty()) { int v=Q. ...

拓扑排序和关键路径拓扑排序一个任务通常可以被分解成若干个子任务，某些情况下，子任务要求有序 基本概念AOV网 在有向图中，顶点表示活动，有向边表示活动间的先后关系，称这样的有向图为AOV网 在AOV网中，如果活动Vi必须在活动Vj之前进行，则存在有向边Vi->Vj AOV网中不能出现有向回路，即有向环，否则意味着某项活动以自己为先决条件 拓扑序列：把AOV网中的所有顶点排成一个线性序列，在拓扑序列中，先进性的任务一定在后进行的任务前面，按照拓扑序列完成各子任务，就可以顺利完成整个任务拓扑排序：构造AOV网的拓扑序列的过程 拓扑排序算法的基本步骤 从图中选择一个入度为0的顶点并输出 从图中删除该顶点及该顶点引出的所有边 执行①②，直至所有顶点已输出，或图中剩余顶点入度均不为0（说明存在环）对于任何无环的AOV网，其顶点均可排成拓扑序列，其拓扑序列未必唯一 拓扑排序的实现准备工作（假定AOV网以邻接表的形式存储） 数组InDegree[]:InDegree[i]作为顶点i的入度 建立一个栈存放入度为0的顶点，每当一个顶点呃入度为0，就将其压栈，每次找入度为0的顶点时，就弹栈 ...