常用经典算法及其实现

1、常用算法经典代码（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(

2、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数组中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的

3、取值范围已知。如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数组的大小要注意 int

4、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) re

5、turn; mid=(x+y)/2;/求x,y区间，中间的那个点mid,mid把x,y区间一分为二 mergesort(x,mid);/对前一段进行二路归并 mergesort(mid+1,y);/对后一段进行二路归并 merge(x,mid,y);/把已经有序的前后两段进行合并归并排序应用了分治思想，把一个大问题，变成两个小问题。二分是分治的思想。五、二分查找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) ret

6、urn 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#includeusing namespace std;int main() string str1,str2; int a250,b250,len; /数组的大小决定了计算的高精度最大位

7、数 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;注意：两个数相加，结果的位数，应该比两个数中大的

8、那个数多一位。七、高精度减法#includeusing 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); 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(st

9、r1,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-; for(i=b0;i=1;i-) coutbi; couts2.length() return 0; /先比较长度，哪个字符串长，对应的那个数就大 if(s1.length()s2.length() return 1; for(int i=0;is

10、2i) return 0; if(s1is2i) return 1; return 0; /如果长度相同，每一位也一样，就返回0，说明相等做减法时，首先要判断两个字符串的大小，决定是否输出负号，然后就是按位减法，注意处理借位。八、高精度乘法#include#includeusing namespace std;int main() 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.len

11、gth(); 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;注意：两个数相乘，结果的位数应该是这两个数的位数和减1。优化：万进制#include#includeusing namespace std;void num1(i

12、nt 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+) /作按位乘法并处理进位，此处是万

13、进制进位 for(int j=1;j1) len-;/去掉高位的0，并输出最高位 cout=1;i-)/把剩下来的每一位还原成4位输出 if (ci1000) cout0; if (ci100) cout0; if (ci10) cout0; 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

14、+; s0=k; /存放数组的位数，就是按4位处理后的万进制数的位数。 Return;九、高精度除法（没讲）十、筛选法建立素数表void maketable(int x)/建立X以内的素数表prim，primi为0，表示i为素数，为1表示不是质数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;对于那些算法中，经常要判断素数的问题，建立一个素数表，可以达到一劳永逸的目

15、的。十一、深度优先搜索void dfs(int x) 以图的深度优先遍历为例。 coutx ; 访问x顶点 visitedx=1; 作已访问的标记 for(int k=1;k=n;k+) 对与顶点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+) if(visited

16、v=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+; /队尾指针加1qr=j; /j入队 /end-if h+; /end -while十三、二叉树的前序、中序和后序遍历void preord

17、er(int x)/二叉树的先序遍历 if(x=0) return; coutx;/先访问根 preorder(ax.ld);/再先序遍历根的左子树 preorder(ax.rd);/最后先序遍历根的右子树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

18、.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 int r=fmin(i-1); /查找次小权值的编号r ai.rchild=r; /把l作为结点i的右孩子 ar.father=i; /把r的父结点修改为i ai.da=al.da+ar.da;

19、/合并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) a

20、x.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) x=fatherx;return x;int getfather(int x)/递归求X结点的根结点的编号if(x=fatherx)

21、 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的父结点指向Px=temp; return p;int getfather(int x)/递归求X结点的根结点编号同时进行路径压缩if(x=fatherx) return x;el

22、se int temp=getfather(fatherx); fatherx=temp; return temp;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+

23、)/初始化结点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=

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

25、结点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; visk=1; /思考：如果k=X说明什么？说明后面的点，无解。 for(int j=1;j=n;j+) /用当前找的结点更新未求结点到X的最短路径 if(visj=0)&(disk

26、+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); fatherx=f; return f; void merge(int x,int y)/合并x,y结点，在此题中的x,y为两个根结点。father

27、x=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

28、算法，还要开一个二维的数组来表示图的邻接矩阵，对于10000个点的数据，显然在空间上是无法容忍的。二十一、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时获得的最大价值。显然fn