C++常用经典算法及其实现

1、常用算法经典代码(C+版)、快速排序voidqsort(intx,inty)/待排序的数据存放在 a1.an数组中inth=x,r=y;intm=a(x+y)1;/取中间的那个位置的值while(hr)while(ahm)r-;/比中间那个位置的值大，循环直到找一个比中间那个值小的if(h=r)inttemp=ah;/如果此时 hx)qsort(x,r);/注意此处，尾指针跑到前半部分了if(hy)qsort(h,y);/注意此处，头指针跑到后半部分了调用：qsort(1,n)即可实现数组 a 中元素有序。适用于 n 比较大的排序二、冒泡排序voidpaopao(void)/待排序的数据存放在

2、 a1.an数组中for(inti=1;in;i+)/控制循环(冒泡)的次数，n 个数，需要 n-1 次冒泡for(intj=1;j=n-i;j+)/相邻的两两比较if(aj=1;j-)/相邻的两两比较if(ajaj+1)inttemp=aj;aj=aj+1;aj+1=temp;调用：paopao()，适用于 n 比较小的排序三、桶排序voidbucketsort(void)/a 的取值范围已知。如 a=cmax。memset(tong,0,sizeof(tong);/桶初始化for(inti=1;ia;tonga+;/相应的桶号计数器加 1for(inti=1;i0)/当桶中装的树大于 0，

3、说明 i 出现过 tongi次，否则没出现过 iwhile(tongi!=0)tongi-;couti?,;桶排序适用于那些待排序的关键字的值在已知范围的排序。四、合(归)并排序voidmerge(intl,intm,intr)/合并l,m和m+1,r两个已经有序的区间intb101;/借助一个新的数组 B，使两个有序的子区间合并成一个有序的区间，大小要注意inth,t,k;for(inti=1;in;i+)/控制循环（冒泡）的次数，n 个数，需要 n-1 次冒泡b 数组的k=0;/用于新数组 B 的指针h=l;t=m+1;/让 h 指向第一个区间的第一个元素，t 指向第二个区间的第一个元素。

4、while(h=m)&(t=r)/在指针 h 和 t 没有到区间尾时，把两个区间的元素抄在新数组中k+;/新数组指针加 1if(ahat)bk=ah;h+;/抄第一个区间元素到新数组 elsebk=at;t+;/抄第二个区间元素到新数组while(h=m)k+;bk=ah;h+;/如果第一个区间没有抄结束，把剩下的抄在新数组中while(t=r)k+;bk=at;t+;/如果第二个区间没有抄结束，把剩下的抄在新数组中for(into=1;o=y)return;mid=(x+y)/2;/求x,y区间，中间的那个点 mid,mid 把 x,y 区间一分为二 mergesort(x,mid)

5、;/对前一段进行二路归并mergesort(mid+1,y);/对后一段进行二路归并 merge(x,mid,y);/把已经有序的前后两段进行合并归并排序应用了分治思想，把一个大问题，变成两个小问题。二分是分治的思想。五、二分查找intfind(intx,inty,intm)/在x,y区间查找关键字等于 m 的元素下标inthead,tail,mid;head=x;tail=y;mid=(x+y)/2);/取中间元素下标 if(amid=m)returnmid;/如果中间元素值为 m 返回中间元素下标 midif(headtail)return0;/如果 xy，查找失败，返回 0if(mami

6、d)/如果 m 比中间元素大，在后半区间查找，返回后半区间查找结果 returnfind(mid+1,tail);else/如果 m 比中间元素小，在前半区间查找，返回后前区间查找结果returnfind(head,mid-1);六、高精度加法#include#includeusingnamespacestd;intmain()stringstr1,str2;inta250,b250,len;/数组的大小决定了计算的高精度最大位数inti;memset(a,0,sizeof(a);memset(b,0,sizeof(b);cinstr1str2;/输入两个字符串a0=str1.length()

7、;/取得第一个字符串的长度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;return0;注意：两个数相加，结果的位数，应该比两个数中大的那个数多一位。七、高精度减法#includeusingnamespacestd;intcompare(strings1,strings2);intmain()stringstr1,str2;inta250,

8、b250,len;inti;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;if(compare(str1,str2)=0)/大于等于，做按位减，并处理借位。for(i=1;i=a0;i+)ai-=bi;if(ai1)a0-;for(i=a0;i=1;i-)coutai;coutendl;elsecout-;/小于就输出负号for(i=1;i=b0;

9、i+)/做按位减，大的减小的bi-=ai;if(bi1)b0-;for(i=b0;i=1;i-)coutbi;couts2.length()return0;/先比较长度，哪个字符串长，对应的那个数就大if(s1.length()s2.length()return1;for(inti=0;is2i)return0;if(s1is2i)return1;return0;/如果长度相同，每一位也一样，就返回 0，说明相等做减法时，首先要判断两个字符串的大小，决定是否输出负号，然后就是按位减法，注意处理借位。八、高精度乘法#include#includeusingnamespacestd;intmain

10、()stringstr1,str2;inta250,b250,c500,len;/250 位以内的两个数相乘inti,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?f

11、or(i=len;i=1;i-)coutci;return0;注意：两个数相乘，结果的位数应该是这两个数的位数和减 1。优化：万进制#include#includeusingnamespacestd;voidnum1(ints,stringst1);inta2501,b2501,c5002;/此处可以进行 2500 位万进制乘法，即 10000 位十进制乘法。Intmain()stringstr1,str2;intlen;cinstr1str2;memset(a,0,sizeof(a);memset(b,0,sizeof(b);memset(c,0,sizeof(c);num1(a,str1)

12、;/把 str1 从最低位开始，每 4 位存放在数组 a 中num1(b,str2);/把 str2 从最低位开始，每 4 位存放在数组 b 中for(inti=1;i=a0;i+)/作按位乘法并处理进位，此处是万进制进位for(intj=1;j1)len-;/去掉高位的 0，并输出最高位cout=1;i-)/把剩下来的每一位还原成 4 位输出if(ci1000)cout?0?;if(ci100)cout?0?;if(ci10)cout?0?;coutci;cout=0;i-)/从最低位开始，处理每一位if(count%4=0)sk+=(st1i-if(count%4=1)sk=(st1i-i

13、f(count%4=2)sk+=(st1i-if(count%4=3)sk+=(st1i-count+;s0=k;/存放数组的位数，就是按Return;九、高精度除法(没讲)十、筛选法建立素数表voidmaketable(intx)/建立 X 以内的素数表 prim，primi为 0，表示 i 为素数，为 1 表示不是质数memset(prim,0,sizeof(prim);/初始化质数表prim0=1;prim1=1;prim2=0;/用筛选法求 X 以内的质数表for(inti=2;i=x;i+)if(primi=0),0?)*1000;if(i!=0)k+;,0?);,0?)*10;,0

14、?)*100;4 位处理后的万进制数的位数。intj=2*i;while(j=x)primj=1;j=j+i;对于那些算法中，经常要判断素数的问题，建立一个素数表，可以达到一劳永逸的目的。十一、深度优先搜索voiddfs(intx)以图的深度优先遍历为例。coutx,;访问 x 顶点作已访问的标记对与顶点 x 相邻而又没访问过的结点 k 进行深度优先搜索。if(axk=1)&(visitedk=0)dfs(k);十二、广度优先搜索voidbfs(void)/按广度优先非递归遍历图 G，n 个顶点，编号为 1.n。注：图不一定是连通的/使用辅助队列 Q 和访问标记数组 visited。f

15、or(v=1;v=n;v+)visitedv=0；/标记数组初始化for(v=1;v=n;v+)if(visitedv=0)/v 尚未访问inth=1,r=1;/置空的辅助队列 qvisitedv=1；/顶点 v,作访问标记coutv,;/访问顶点 vqr=v；/v 入队列while(h=r)/当队列非空时循环inttmp=qh;/队头元素出队，并赋值给for(intj=1;j=n;j+)if(visitedj=0)&(atmpj=1)/j 为 tmp 的尚未访问的邻接顶点visitedj=1;对 j 作访问标记 coutj,;访问 jr+;/队尾指针加 1qr=j;/j 入队/end

16、-ifh+;/end-while十三、二叉树的前序、中序和后序遍历voidpreorder(intx)/二叉树的先序遍历if(x=0)return;coutx;/先访问根preorder(ax.ld);/再先序遍历根的左子树preorder(ax.rd);/最后先序遍历根的右子树tmpvoidinorder(intx)/二叉树的中序遍历if(x=0)return;preorder(ax.ld);/先中序遍历根的左子树coutx;/再访问根preorder(ax.rd);/最后中序遍历根的右子树voidreorder(intx)/二叉树的后序遍历if(x=0)return;preorder(ax

17、.ld);/先后序遍历根的左子树 preorder(ax.rd);/再后序遍历根的右子树 coutx;/最后访问根十四、树转换为二叉树算法十五、二叉排序树十六、哈夫曼树voidhaff(void)/构建哈夫曼树for(inti=n+1;i=2*n-1;i+)/依次生成 n-1 个结点intl=fmin(i-1);/查找权值最小的结点的编号 laichild=l;/把 I 作为结点 i 的左孩子al.father=i;/把 l 的父结点修改为 iintr=fmin(i-1);/查找次小权值的编号 rai.rchild=r;/把 l 作为结点 i 的右孩子ar.father=i;/把 r 的父结点

18、修改为 iai.da=al.da+ar.da;/合并 l,j 结点，生成新结点 iintfmin(intk)/在 1 到 K 中寻找最小的权值的编号intmins=0;for(ints=1;sas.da)&(as.father=0)/as.father=0,别个结点mins=s;/的孩子，不等于 0 说明这个结点已经用过。returnmins;voidinorder(intx)/递归生成哈夫曼编码说明这个结点还不是if(ax.father=0)ax.code=if(aax.father.lchild=x)if(aax.father.rchild=x)根结点”“;/ax.code=aax

19、.father.code+0;ax.code=aax.father.code+1x=fatherx;returnx;intgetfather(intx)/递归求 X 结点的根结点的编号if(x=fatherx)returnx;elsereturngetfather(fatherx);intgetfather(intx)/非递归求 X 结点的根结点编号同时进行路径压缩intp=x;while(p!=fatherp)/循环结束后，P 即为根结点p=fatherp;while(x!=fatherx)/从 X 结点沿 X 的父结点进行路径压缩inttemp=fatherx;/暂存 X 没有修改前的父结

20、点fatherx=p;/把 X 的父结点指向 Px=temp;returnp;intgetfather(intx)/递归求 X 结点的根结点编号同时进行路径压缩if(x=fatherx)returnx;elseif(ax.lchild!=0)inorder(ax.lchild);/递归生成左子树if(ax.lchild=0)&(ax.rchild=0)/输出叶子结点coutax.da:ax.codeendl;if(ax.rchild!=0)inorder(ax.rchild);/递归生成右子树十七、并查集intgetfather(intx)/非递归求 X 结点的根结点的编号while(

21、x!=fatherx)inttemp=getfather(fatherx);fatherx=temp;returntemp;voidmerge(intx,inty)/合并 x,y 两个结点intx1,x2;x1=getfather(x);/取得 X 的父结点x2=getfather(y);/取得 Y 的父结点if(x1!=x2)fatherx1=x2;/两个父结点不同的话就合并，注意：合并的是 X，Y 两个结点的根。十八、Prime 算法voidprime(void)/prim为结构体类型。算法求最小生成树，elisti是边集数组，aij为l,j的权值。edgefor(inti=1;i=n-1

22、;i+)/elisti.from=1;elisti.to=i+1;elisti.w=a1i+1;初始化结点 1 到其它 n-1 个结点形成的边集for(inti=1;i=n-1;i+)/依次确定 n-1 条边intm=i;for(intj=i+1;j=n-1;j+)/确定第 i 条边时，依次在 i+1 至 n-1 条边中找最小的那条边if(elistj.welistm.w)m=j;if(m!=i)/如果最小的边不是第 i 条边就交换edgetmp=elisti;elisti=elistm;elistm=tmp;for(intj=i+1;jaelisti.toelistj.to)elistj.w

23、=aelisti.toelistj.to;for(inti=1;i=n-1;i+)/求最小生成树的值ans=ans+elisti.w;如果要求出哪些边构成最小生成树，在更新第 i+1 至 n-1 条边到已经生成的树中最小距离时(上面代码中加粗的部分)，还要加上 elistj.from=elisti.to;语句，即在更新权值时，还应该更新起点。Prime 算法适用于顶点不是太多的稠密图，如果对于顶点数较多的稀疏图，就不太适用了。十九、Dijkstra 算法voiddijkstra(intx)/求结点 x 到各个结点的最短路径memset(vis,0,sizeof(vis);II 初始化，visi

24、=0 表示源点到结点 i 未求，否则已求 visx=1;prex=0;/初始化源点。for(inti=1;i=n;i+)II 对其它各点初始化。if(i!=x)disi=gxi;prei=x;for(inti=1;i=n-1;i+)II 对于 n 个结点的图，要求 x 到其它 n-1 个结点的最短距离intm=big;II 虚拟一个最大的数 big=99999999;intk=x;for(intj=1;jdisj)m=disj;k=j;visk=1;/思考：如果 k=X 说明什么？说明后面的点，无解。for(intj=1;j=n;j+)/用当前找的结点更新未求结点到 X 的最短路径if(vis

25、j=0)&(disk+gkj1.w;while(hr)while(elisth.wm)r-;if(h=r)edgetmp=elisth;elisth=elistr;elistr=tmp;h+;r-;if(xr)qsort(x,r);if(hy)qsort(h,y);intgetfather(intx)/找根结点，并压缩路径，此处用递归实现的。if(x=fatherx)returnx;elseintf=getfather(fatherx);fatherx=f;returnf;voidmerge(intx,inty)/合并 x,y 结点，在此题中的 x,y 为两个根结点。fatherx=y

26、;voidkruscal(void)intsum=0,ans=0;qsort(1,t);/对 t 条边按权值大小按从小到大的次序进行快速排序for(inti=1;in-1)break;/已经确定了 n-1 条边了，最小生成树已经生成了，可以提前退出循环了if(sumn-1)coutImpossibleendl;/从 t 条边中无法确定 n-1 条边，说明无法生成最小生成树elsecoutansendl;克鲁斯卡尔算法，只用了边集数组，没有用到图的邻接矩阵，因此当图的结点数比较多的时候，输入数据又是边的信息时，就要考虑用 Kruscal 算法。对于岛国问题，我们就要选择此算法，如果用 Prim

27、算法，还要开一个二维的数组来表示图的邻接矩阵，对于 10000 个点的数据，显然在空间上是无法容忍的。二十一、Floyed 算法voidfloyed(void)/aij表示结点 i 到结点 j 的最短路径长度，初始时值为的权值。for(intk=1;k=n;k+)/枚举中间加入的结点不超过 K 时 fij最短路径长度，K 相当 DP 中的阶段for(inti=1;i=n;i+)i，j 是结点 i 到结点 J，相当于 DP 中的状态for(intj=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,vfor(inti=1;i=n