资源描述
常用算法经典代码（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 页
展开阅读全文