2022年完整word版,C++常用经典算法及其实现要点 .pdf

常用算法经典代码（C+ 版）一、快速排序void qsort(int x,int y) /待排序的数据存放在a1.an数组中int h=x,r=y; int m=a(x+y)1; /取中间的那个位置的值while(hr) while (ahm) r-; /比中间那个位置的值大，循环直到找一个比中间那个值小的if(h=r) int temp=ah;/如果此时hx) qsort(x,r);/注意此处，尾指针跑到前半部分了 if(hy) qsort(h,y); /注意此处，头指针跑到后半部分了 调用： qsort(1,n)即可实现数组a 中元素有序。适用于n 比较大的排序二、冒泡排序void paopao(void) /待排序的数据存放在a1.an数组中for(int i=1;in;i+) / 控制循环（冒泡）的次数，n 个数，需要n-1 次冒泡for(int j=1;j=n-i;j+) /相邻的两两比较if(ajaj+1) int temp=aj;aj=aj+1;aj+1=temp; 或者void paopao(void) /待排序的数据存放在a1.an数组中精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 22 页for(int i=1;i=1;j-) /相邻的两两比较if(ajaj+1) int temp=aj;aj=aj+1;aj+1=temp; 调用： paopao()，适用于n 比较小的排序三、桶排序void bucketsort(void)/a的取值范围已知。如a=cmax 。 memset(tong,0,sizeof(tong);/桶初始化for(int i=1;ia; tonga+;/相应的桶号计数器加1 for(int i=1;i0) /当桶中装的树大于0，说明 i 出现过 tongi 次，否则没出现过i while (tongi!=0) tongi-; couti ; 桶排序适用于那些待排序的关键字的值在已知范围的排序。四、合（归）并排序void merge(int l,int m,int r)/合并 l,m 和m+1,r两个已经有序的区间 int b101;/借助一个新的数组B，使两个有序的子区间合并成一个有序的区间，b 数组的大小要注意精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 22 页int h,t,k; k=0;/用于新数组B 的指针h=l;t=m+1;/让 h 指向第一个区间的第一个元素，t 指向第二个区间的第一个元素。while(h=m)&(t=r)/在指针 h 和 t 没有到区间尾时，把两个区间的元素抄在新数组中k+; / 新数组指针加1 if (ahat)bk=ah;h+; / 抄第一个区间元素到新数组elsebk=at;t+; / 抄第二个区间元素到新数组 while(h=m)k+;bk=ah;h+; / 如果第一个区间没有抄结束，把剩下的抄在新数组中while(t=r)k+;bk=at;t+; / 如果第二个区间没有抄结束，把剩下的抄在新数组中for(int o=1;o=y) return; mid=(x+y)/2;/求x,y 区间，中间的那个点mid,mid把 x,y 区间一分为二mergesort(x,mid);/对前一段进行二路归并mergesort(mid+1,y);/对后一段进行二路归并merge(x,mid,y);/把已经有序的前后两段进行合并 归并排序应用了分治思想，把一个大问题，变成两个小问题。二分是分治的思想。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 22 页五、二分查找int find(int x,int y,int m) /在x,y 区间查找关键字等于m 的元素下标 int head,tail,mid; head=x;tail=y;mid=(x+y)/2);/取中间元素下标if(amid=m) return mid;/如果中间元素值为m 返回中间元素下标mid if(headtail) return 0;/如果 xy ，查找失败，返回0 if(mamid) / 如果 m 比中间元素大，在后半区间查找，返回后半区间查找结果return find(mid+1,tail); else / 如果 m 比中间元素小，在前半区间查找，返回后前区间查找结果return find(head,mid-1); 六、高精度加法#include #include using namespace std; int main() string str1,str2; int a250,b250,len; / 数组的大小决定了计算的高精度最大位数int i; memset(a,0,sizeof(a); memset(b,0,sizeof(b); cinstr1str2; / 输入两个字符串a0=str1.length(); / 取得第一个字符串的长度for(i=1;i=a0;i+) / 把第一个字符串转换为整数，存放在数组a 中ai=str1a0-i-0; b0=str2.length(); / 取得第二个字符串长度for(i=1;ib0?a0:b0); / 取两个字符串最大的长度for(i=1;i1) len-; for(i=len;i=1;i-) coutai; return 0; 注意：两个数相加，结果的位数，应该比两个数中大的那个数多一位。七、高精度减法#include using namespace std; int compare(string s1,string s2); int main() string str1,str2; int a250,b250,len; int i; memset(a,0,sizeof(a); memset(b,0,sizeof(b); 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 22 页cinstr1str2; a0=str1.length(); for(i=1;i=a0;i+) ai=str1a0-i-0; b0=str2.length(); for(i=1;i=b0;i+) bi=str2b0-i-0; if(compare(str1,str2)=0) / 大于等于，做按位减，并处理借位。 for(i=1;i=a0;i+) ai-=bi; if (ai1) a0-; for(i=a0;i=1;i-) coutai; coutendl; else cout-; / 小于就输出负号for(i=1;i=b0;i+) / 做按位减，大的减小的bi-=ai; if (bi1) b0-; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 22 页for(i=b0;i=1;i-) coutbi; couts2.length() return 0; / 先比较长度，哪个字符串长，对应的那个数就大if(s1.length()s2.length() return 1; for(int i=0;is2i) return 0; if(s1is2i) return 1; return 0; / 如果长度相同，每一位也一样，就返回0，说明相等 做减法时，首先要判断两个字符串的大小，决定是否输出负号，然后就是按位减法，注意处理借位。八、高精度乘法#include #include using namespace std; int main() 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 22 页 string str1,str2; int a250,b250,c500,len; /250位以内的两个数相乘int i,j; memset(a,0,sizeof(a); memset(b,0,sizeof(b); cinstr1str2; a0=str1.length(); for(i=1;i=a0;i+) ai=str1a0-i-0; b0=str2.length(); for(i=1;i=b0;i+) bi=str2b0-i-0; memset(c,0,sizeof(c); for(i=1;i=a0;i+) / 做按位乘法同时处理进位，注意循环内语句的写法。for(j=1;j1) len-; / 为什么此处要len1? for(i=len;i=1;i-) coutci; return 0; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 22 页注意：两个数相乘，结果的位数应该是这两个数的位数和减1。优化：万进制#include #include using namespace std; void num1(int s,string st1); int a2501,b2501,c5002;/此处可以进行2500 位万进制乘法， 即 10000 位十进制乘法。Int main() string str1,str2; int len; cinstr1str2; memset(a,0,sizeof(a); memset(b,0,sizeof(b); memset(c,0,sizeof(c); num1(a,str1); /把 str1 从最低位开始，每4 位存放在数组a 中num1(b,str2); /把 str2 从最低位开始，每4 位存放在数组b 中for(int i=1;i=a0;i+) /作按位乘法并处理进位，此处是万进制进位for(int j=1;j1) len-;/去掉高位的0，并输出最高位 cout=1;i-)/把剩下来的每一位还原成4 位输出精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 22 页 if (ci1000) cout 0;if (ci100) cout 0;if (ci10) cout 0;coutci; cout=0;i-) /从最低位开始，处理每一位 if (count%4=0) sk+=(st1i- 0 )*1000; if(i!=0) k+;if (count%4=1) sk=(st1i- 0 );if (count%4=2) sk+=(st1i- 0 )*10;if (count%4=3) sk+=(st1i- 0 )*100;count+; s0=k; /存放数组的位数，就是按4 位处理后的万进制数的位数。Return; 九、高精度除法（没讲）十、筛选法建立素数表void maketable(int x)/建立 X 以内的素数表prim ，primi 为 0，表示 i 为素数，为1 表示不是质数精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 22 页 memset(prim,0,sizeof(prim);/初始化质数表 prim0=1;prim1=1;prim2=0;/用筛选法求X 以内的质数表 for(int i=2;i=x;i+) if (primi=0) int j=2*i; while(j=x) primj=1;j=j+i; 对于那些算法中，经常要判断素数的问题，建立一个素数表，可以达到一劳永逸的目的。十一、深度优先搜索void dfs(int x) 以图的深度优先遍历为例。 coutx ; 访问 x 顶点作已访问的标记对与顶点x 相邻而又没访问过的结点k 进行深度优先搜索。if(axk=1)&(visitedk=0) dfs(k); 十二、广度优先搜索void bfs(void) /按广度优先非递归遍历图G，n 个顶点，编号为1.n 。注：图不一定是连通的/ 使用辅助队列Q 和访问标记数组visited 。for(v=1;v=n;v+) visitedv=0；/ 标记数组初始化for(v=1; v=n; v+) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 22 页if(visitedv=0 ) /v 尚未访问int h=1,r=1; / 置空的辅助队列q visitedv=1；/ 顶点 v,作访问标记coutv ; /访问顶点v qr=v ；/v 入队列while(h=r) /当队列非空时循环 int tmp=qh; / 队头元素出队，并赋值给tmp for(int j=1;j=n;j+) if(visitedj=0)&(atmpj=1) /j为 tmp 的尚未访问的邻接顶点 visitedj=1; 对 j 作访问标记coutj ; 访问 j r+; /队尾指针加1 qr=j; /j入队 /end-if h+; /end -while 十三、 二叉树的前序、中序和后序遍历void preorder(int x)/二叉树的先序遍历 if(x=0) return; coutx;/先访问根preorder(ax.ld);/再先序遍历根的左子树preorder(ax.rd);/最后先序遍历根的右子树 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 22 页void inorder(int x)/二叉树的中序遍历 if(x=0) return; preorder(ax.ld);/先中序遍历根的左子树coutx;/再访问根preorder(ax.rd);/最后中序遍历根的右子树 void reorder(int x)/二叉树的后序遍历 if(x=0) return; preorder(ax.ld);/先后序遍历根的左子树preorder(ax.rd);/再后序遍历根的右子树coutx;/最后访问根 十四、树转换为二叉树算法十五、二叉排序树十六、哈夫曼树void haff(void) /构建哈夫曼树 for(int i=n+1;i=2*n-1;i+) /依次生成 n-1 个结点int l=fmin(i-1); /查找权值最小的结点的编号l ai.lchild=l; /把 l 作为结点i 的左孩子al.father=i; /把 l 的父结点修改为i 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 22 页int r=fmin(i-1); /查找次小权值的编号r ai.rchild=r; /把 l 作为结点i 的右孩子ar.father=i; /把 r 的父结点修改为i ai.da=al.da+ar.da; /合并 l,j 结点，生成新结点i int fmin(int k)/在 1 到 K 中寻找最小的权值的编号 int mins=0; for(int s=1;sas.da)&(as.father=0) /as.father=0,说明这个结点还不是别个结点mins=s; / 的孩子，不等于0 说明这个结点已经用过。return mins; void inorder(int x)/递归生成哈夫曼编码 if(ax.father=0) ax.code=”“ ;/根结点if(aax.father.lchild=x) ax.code=aax.father.code+0; if(aax.father.rchild=x) ax.code=aax.father.code+1; if(ax.lchild!=0) inorder(ax.lchild);/递归生成左子树if(ax.lchild=0)&(ax.rchild=0)/输出叶子结点coutax.da:ax.codeendl; if(ax.rchild!=0) inorder(ax.rchild);/递归生成右子树 十七、并查集int getfather(int x)/非递归求 X 结点的根结点的编号while(x!=fatherx) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 22 页x=fatherx; return x; int getfather(int x)/递归求 X 结点的根结点的编号if(x=fatherx) return x; else return getfather(fatherx); int getfather(int x)/非递归求 X 结点的根结点编号同时进行路径压缩int p=x; while(p!=fatherp)/循环结束后，P即为根结点p=fatherp; while(x!=fatherx)/从 X 结点沿 X 的父结点进行路径压缩int temp=fatherx;/暂存 X没有修改前的父结点fatherx=p;/把 X 的父结点指向P x=temp; return p; int getfather(int x)/递归求 X 结点的根结点编号同时进行路径压缩if(x=fatherx) return x; else int temp=getfather(fatherx); fatherx=temp; return temp; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页，共 22 页 void merge(int x,int y)/合并 x,y 两个结点 int x1,x2; x1=getfather(x);/取得 X 的父结点x2=getfather(y);/取得 Y 的父结点if(x1!=x2) fatherx1=x2; /两个父结点不同的话就合并，注意：合并的是X，Y 两个结点的根。 十八、 Prime算法void prime(void) /prim算法求最小生成树，elisti 是边集数组， aij 为 的权值。 edge为结构体类型。for (int i=1;i=n-1;i+)/初始化结点1 到其它 n-1 个结点形成的边集elisti.from=1; elisti.to=i+1; elisti.w=a1i+1; for (int i=1;i=n-1;i+)/依次确定n-1 条边int m=i; for(int j=i+1;j=n-1;j+)/确定第 i 条边时，依次在i+1 至 n-1 条边中找最小的那条边if(elistj.welistm.w) m=j; if(m!=i) /如果最小的边不是第i 条边就交换edge tmp=elisti;elisti=elistm;elistm=tmp; for(int j=i+1;jaelisti.toelistj.to) elistj.w=aelisti.toelistj.to; for(int i=1;i=n-1;i+)/求最小生成树的值精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 16 页，共 22 页ans=ans+elisti.w; 如果要求出哪些边构成最小生成树，在更新第i+1至 n-1 条边到已经生成的树中最小距离时( 上面代码中加粗的部分)，还要加上elistj.from=elisti.to;语句，即在更新权值时，还应该更新起点。Prime算法适用于顶点不是太多的稠密图，如果对于顶点数较多的稀疏图，就不太适用了。十九、 Dijkstra算法void dijkstra(int x) / 求结点 x 到各个结点的最短路径 memset(vis,0,sizeof(vis); /初始化， visi 0 表示源点到结点i 未求，否则已求visx=1;prex=0; /初始化源点。for(int i=1;i=n;i+) / 对其它各点初始化。if(i!=x) disi=gxi; prei=x; for(int i=1;i=n-1;i+) / 对于 n 个结点的图，要求x 到其它 n-1 个结点的最短距离 int m=big; /虚拟一个最大的数big=99999999; int k=x; for(int j=1;jdisj) m=disj; k=j; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 17 页，共 22 页 visk=1; / 思考：如果k=X 说明什么？说明后面的点，无解。 for(int j=1;j=n;j+) / 用当前找的结点更新未求结点到X 的最短路径 if(visj=0)&(disk+gkj1.w; while(hr) while(elisth.wm) r-; if(h=r) edge tmp=elisth;elisth=elistr;elistr=tmp;h+;r-; if(xr) qsort(x,r); if(hy) qsort(h,y); int getfather(int x)/找根结点，并压缩路径，此处用递归实现的。if(x=fatherx) return x; else int f=getfather(fatherx); 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 18 页，共 22 页fatherx=f; return f; void merge(int x,int y)/合并 x,y 结点，在此题中的x,y 为两个根结点。fatherx=y; void kruscal(void) int sum=0,ans=0; qsort(1,t);/对 t 条边按权值大小按从小到大的次序进行快速排序for(int i=1;in-1) break;/ 已经确定了n-1条边了，最小生成树已经生成了，可以提前退出循环了 if(sumn-1) coutImpossibleendl; /从 t 条边中无法确定n-1条边，说明无法生成最小生成树else coutansendl; 克鲁斯卡尔算法，只用了边集数组，没有用到图的邻接矩阵，因此当图的结点数比较多的时候，输入数据又是边的信息时，就要考虑用Kruscal算法。对于岛国问题，我们就要选择此算法，如果用Prim算法，还要开一个二维的数组来表示图的邻接矩阵，对于10000个点的数据，显然在空间上是无法容忍的。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 19 页，共 22 页二十一、 Floyed算法void floyed(void)/ aij表示结点i 到结点 j 的最短路径长度，初始时值为的权值。for(int k=1;k=n;k+) /枚举中间加入的结点不超过K 时 fij最短路径长度，K 相当DP 中的阶段 for(int i=1;i=n;i+) /i，j 是结点 i 到结点 J，相当于DP 中的状态for(int j=1;jaik+akj) aij=aik+akj;/这是决策，加和不加中间点，取最小的值 弗洛伊德算法适合于求没有负权回路的图的最短路径长度，利用FLOYED 算法，可写出判断结点 i 和结点 J 是否连通的算法。二十二、 01 背包问题n 为物品的数量，wi 表示第 i 个物品的重量，ci 表示第 i 个物品的价值，v 为背包的最大重量。有状态转移方程fij=maxfi-1j,fi-1j-wi+ci。fij表示前 i 个物品，在背包载重为 j 时获得的最大价值。显然fnv即为所求。边界条件为f0s=0,s=0,1,v 。for(int i=1;i=n;i+)/枚举阶段 for(int j=0;j=0;j-) fij=fi-1j;/不选第 i 个物品if(fijfi-1j-wi+ci) fij=fi-1j-wi+ci;/选第 i 个物品 coutfnvendl;/输出结果。优化：用一维数组实现，把第i-1 阶段和第i 阶段数据存在一块。for(int i=1;i=0;j-)/枚举状态，当然此处也可写成:for(int j=v;j=0;j-)精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 20 页，共 22 页 fj=fj;/不选第 i 个物品，可省略此语句。if(jwi)&(fjfj-wi+ci) fj=fj-wi+ci;/ 选第 i 个物品 coutfv=wi;j-)，此时下面的判断条件j=wi就可以省略了。二十三、完全背包问题和 01 背包问题不同的是，完全背包，对于任何一个物品i，只要背包重量允许，可以多次选取，也就是在决策上，可以选0 个， 1 个， 2 个， ，v/wi 个。状态转移方程fij=maxfi-1j,fi-1j-wi+ci， fi-1j-2*wi+2*ci，fi-1j-k*wi+k*ci。k=0 ，1，2，v/wi 。fij表示前 i 个物品，在背包载重为j时获得的最大价值。显然fnv即为所求。边界条件为f0s=0,s=0,1,v 。for(int i=1;i=n;i+)/枚举阶段 for(int j=0;j=0;j-)fij=fi-1j;/k=0的情况作为fij的初始值， 然后在 k=1,2, ,v/wi中找最大值for(int k=1;k=v/wi;k+) if(fijfi-1j-k*wi+k*ci) fij=fi-1j-k*wi+k*ci;/选第 i 个物品 coutfnvendl;/输出结果。二十四、多属性背包问题精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 21 页，共 22 页二十五、多背包问题二十六、最长不降（上升）子序列问题 fi 表示从第1 个数开始，以第i 个数结尾的最长递增子序列。状态转移方程：fi=maxfj+1 （1j i-1，1i n，ai aj ）临界状态： f1=1; 二十七、最长公共子序列问题fij 表示第一个串前i 个字符和第二个串前j 个字符的最长公共子序列数。状态转移方程：fi-1j-1 (若 ai=bj) fij= maxfi-1j,fij-1+1 ( 若 ai bj)临界状态 :f0j=0，fi0=0 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 22 页，共 22 页