资源描述
常用算法经典代码( 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 数组中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+;/ 相应的桶号计数器加1for(int i=1;i0) / 当桶中装的树大于0，说明i 出现过 tongi 次，否则没出现过iwhile (tongi!=0)tongi-;couti ;桶排序适用于那些待排序的关键字的值在已知范围的排序。四、合(归)并排序void merge(int l,int m,int r)/合并l,m和m+1,r两个已经有序的区间b 数组的 int b101;/ 借助一个新的数组B， 使两个有序的子区间合并成一个有序的区间，大小要注意int h,t,k;k=0;/ 用于新数组 B 的指针h=l;t=m+1;/ 让 h 指向第一个区间的第一个元素， t 指向第二个区间的第一个元素。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(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);/ 把已经有序的前后两段进行合并归并排序应用了分治思想，把一个大问题，变成两个小问题。二分是分治的思想。五、二分查找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 返回中间元素下标midif(headtail) return 0;/ 如果 xy ，查找失败，返回 0if(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;/ 数组的大小决定了计算的高精度最大位数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;注意：两个数相加，结果的位数，应该比两个数中大的那个数多一位。七、高精度减法#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(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;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;is2i) 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.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;1。注意：两个数相乘，结果的位数应该是这两个数的位数和减 优化：万进制#include#includeusing 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 位输出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-if (count%4=2) sk+=(st1i-if (count%4=3) sk+=(st1i-count+;s0=k; / 存放数组的位数，就是按Return;0);4 位处理后的万进制数的位数。)*10;)*100;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; 对于那些算法中，经常要判断素数的问题，建立一个素数表，可以达到一劳永逸的目的。十一、深度优先搜索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+)if(visitedv=0 ) /v 尚未访问int h=1,r=1;/ 置空的辅助队列 qvisitedv=1 ; /顶点v,作访问标记coutv 访问顶点; /vqr=v ；/v 入队列while(h=r) / 当队列非空时循环int tmp=qh; / 队头元素出队，并赋值给tmpfor(int j=1;j=n;j+)if(visitedj=0)&(atmpj=1)/j 为 tmp 的尚未访问的邻接顶点visitedj=1; 对 j 作访问标记coutj 访问 ; jr+; / 队尾指针加1qr=j; /j 入队 /end-ifh+;/end -while十三、 二叉树的前序、中序和后序遍历void preorder(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.rd);/ 再后序遍历根的右子树coutx;/ 最后访问根十四、树转换为二叉树算法十五、二叉排序树十六、哈夫曼树void haff(void) / 构建哈夫曼树for(int i=n+1;i=2*n-1;i+) / 依次生成 n-1 个结点int l=fmin(i-1); / 查找权值最小的结点的编号lai.lchild=l; / 把 l 作为结点 i 的左孩子int r=fmin(i-1); / 查找次小权值的编号 rai.rchild=r; / 把 l 作为结点 i 的右孩子ar.father=i; / 把 r 的父结点修改为 iai.da=al.da+ar.da; / 合并 l,j 结点，生成新结点 iint 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)if(aax.father.rchild=x)根结点 ”“;/ax.code=aax.father.code+0;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)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 的父结点指向 Px=temp;return p;int getfather(int x)/ 递归求 X 结点的根结点编号同时进行路径压缩if(x=fatherx) return x;else 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+)/ 初始化结点 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+)/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;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);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 条边，说明无法生成最小生成树elsecoutansendl;克鲁斯卡尔算法，只用了边集数组，没有用到图的邻接矩阵，因此当图的结点数比较多的时候，输入数据又是边的信息时，就要考虑用 Kruscal 算法。对于岛国问题，我们就要选择此算法，如果用 Prim 算法，还要开一个二维的数组来表示图的邻接矩阵，对于 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时获得的最大价值。显然fnv即为所求。边界条件为f0s=0,s=0,1,vfor(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-)fj=fj;/ 不选第 i 个物品，可省略此语句。if(jwi)&(fjfj-wi+ci) fj=fj-wi+ci;/ 选第 i 个物品coutfv=wi 就可以省略了。for(int j=v;j=wi;j-)，此时下面二十三、完全背包问题和 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,vfor(int i=1;i=n;i+)/ 枚举阶段for(int j=0;j=0;j-)fij=fi-1j；/k=0的情况作为fij的初始值，然后在k=1,2,，v/wi中找最大值选第 i 个物品for(int k=1;k=v/wi;k+)if(fijfi-1j-k*wi+k*ci) fij=fi-1j-k*wi+k*ci;/coutfnvaj临界状态： f1=1;二十七、最长公共子序列问题fij 表示第一个串前i 个字符和第二个串前j 个字符的最长公共子序列数。状态转移方程：fi-1j-1(若 ai=bj)fij=maxfi-1j,fij-1+1(若 ai w bj)临界状态 :f0j=0， fi0=0
展开阅读全文