常用算法经典代码（C++版） 一、快速排序 void qsort(int x,int y) //待排序的数据存放在 a[1]..a[n]数组中 {int h=x,r=y; int m=a[(x+y)>>1]; //取中间的那个位置的值 while(hm) r--; //比中间那个位置的值大，循环直到找一个比中间那个值小的 if(h<=r) {int temp=a[h];//如果此时 h<=r，交换 a[h]和 a[r] a[h]=a[r]; a[r]=temp; h++;r--; //这两句必不可少哦 } } if(r>x) qsort(x,r);//注意此处，尾指针跑到前半部分了 if(h=1;j--) //相邻的两两比较 if(a[j]>a; tong[a]++;}//相应的桶号计数器加 1 for(int i=1;i<=cmax;i++) {if(tong[i]>0) //当桶中装的树大于 0，说明 i 出现过 tong[i]次，否则没出现过 i while (tong[i]!=0) {tong[i]--; cout<=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(a[mid]==m) return mid;//如果中间元素值为 m 返回中间元素下标 mid if(head>tail) return 0;//如果 x>y，查找失败，返回 0 if(m>a[mid]) //如果 m 比中间元素大，在后半区间查找，返回后半区间查找结果 return find(mid+1,tail); else //如果 m 比中间元素小，在前半区间查找，返回后前区间查找结果 return find(head,mid-1); } 六、高精度加法 #include #include using namespace std; int main() { string str1,str2; int a[250],b[250],len; //数组的大小决定了计算的高精度最大位数 int i; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); cin>>str1>>str2; //输入两个字符串 a[0]=str1.length(); //取得第一个字符串的长度 for(i=1;i<=a[0];i++) //把第一个字符串转换为整数，存放在数组 a 中 a[i]=str1[a[0]-i]-'0'; b[0]=str2.length(); //取得第二个字符串长度 for(i=1;i<=b[0];i++) //把第二个字符串中的每一位转换为整数，存放在数组 B 中 b[i]=str2[b[0]-i]-'0'; len=(a[0]>b[0]?a[0]:b[0]); //取两个字符串最大的长度 for(i=1;i<=len;i++) //做按位加法，同时处理进位 { a[i]+=b[i]; a[i+1]+=a[i]/10; a[i]%=10; } len++; //下面是去掉最高位的 0，然后输出。 while((a[len]==0)&&(len>1)) len--; for(i=len;i>=1;i--) cout< using namespace std; int compare(string s1,string s2); int main() { string str1,str2; int a[250],b[250],len; int i; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); cin>>str1>>str2; a[0]=str1.length(); for(i=1;i<=a[0];i++) a[i]=str1[a[0]-i]-'0'; b[0]=str2.length(); for(i=1;i<=b[0];i++) b[i]=str2[b[0]-i]-'0'; if((compare(str1,str2))==0) //大于等于，做按位减，并处理借位。 { for(i=1;i<=a[0];i++) {a[i]-=b[i]; if (a[i]<0) {a[i+1]--;a[i]+=10;} } a[0]++; while((a[a[0]]==0)&&(a[0]>1)) a[0]--; for(i=a[0];i>=1;i--) cout<1)) b[0]--; for(i=b[0];i>=1;i--) cout<s2.length()) return 0; //先比较长度，哪个字符串长，对应的那个数就大 if(s1.length()s2[i]) return 0; if(s1[i] #include using namespace std; int main() { string str1,str2; int a[250],b[250],c[500],len; //250 位以内的两个数相乘 int i,j; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); cin>>str1>>str2; a[0]=str1.length(); for(i=1;i<=a[0];i++) a[i]=str1[a[0]-i]-'0'; b[0]=str2.length(); for(i=1;i<=b[0];i++) b[i]=str2[b[0]-i]-'0'; memset(c,0,sizeof(c)); for(i=1;i<=a[0];i++) //做按位乘法同时处理进位，注意循环内语句的写法。 for(j=1;j<=b[0];j++) { c[i+j-1]+=a[i]*b[j]; c[i+j]+=c[i+j-1]/10; c[i+j-1]%=10; } len=a[0]+b[0]+1; //去掉最高位的 0，然后输出 while((c[len]==0)&&(len>1)) len--; //为什么此处要 len>1?? for(i=len;i>=1;i--) cout< #include using namespace std; void num1(int s[],string st1); int a[2501],b[2501],c[5002];//此处可以进行 2500 位万进制乘法，即 10000 位十进制乘法。 Int main() { string str1,str2; int len; cin>>str1>>str2; 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<=a[0];i++) //作按位乘法并处理进位，此处是万进制进位 for(int j=1;j<=b[0];j++) { c[i+j-1]+=a[i]*b[j]; c[i+j]+=c[i+j-1]/10000; c[i+j-1]%=10000; } len=a[0]+b[0];//a[0]和 b[0]存放的是每个数按 4 位处理的位数 while ((c[len]==0)&&(len>1)) len--;//去掉高位的 0，并输出最高位 cout<=1;i--)//把剩下来的每一位还原成 4 位输出 { if (c[i]<1000) cout<<‟0‟; if (c[i]<100) cout<<‟0‟; if (c[i]<10) cout<<‟0‟; cout<=0;i--) //从最低位开始，处理每一位 { if (count%4==0) {s[k]+=(st1[i]-„0‟)*1000; if(i!=0) k++;} if (count%4==1) s[k]=(st1[i]-„0‟); if (count%4==2) s[k]+=(st1[i]-„0‟)*10; if (count%4==3) s[k]+=(st1[i]-„0‟)*100; count++; } s[0]=k; //存放数组的位数，就是按 4 位处理后的万进制数的位数。 Return; } 九、高精度除法（没讲） 十、筛选法建立素数表 void maketable(int x)//建立 X 以内的素数表 prim，prim[i]为 0，表示 i 为素数，为 1 表示不是质数 { memset(prim,0,sizeof(prim));//初始化质数表 prim[0]=1;prim[1]=1;prim[2]=0;//用筛选法求 X 以内的质数表 for(int i=2;i<=x;i++) if (prim[i]==0) {int j=2*i; while(j<=x) {prim[j]=1;j=j+i;} } } 对于那些算法中，经常要判断素数的问题，建立一个素数表，可以达到一劳永逸的目的。 十一、深度优先搜索 void dfs(int x) \\以图的深度优先遍历为例。 { cout<a[s].da)&&(a[s].father==0)) //a[s].father=0,说明这个结点还不是别个结点 mins=s; //的孩子，不等于 0 说明这个结点已经用过。 return mins; } void inorder(int x)//递归生成哈夫曼编码 { if(a[x].father==0) {a[x].code=”“;}//根结点 if(a[a[x].father].lchild==x) a[x].code=a[a[x].father].code+'0'; if(a[a[x].father].rchild==x) a[x].code=a[a[x].father].code+'1'; if(a[x].lchild!=0) inorder(a[x].lchild);//递归生成左子树 if((a[x].lchild==0)&&(a[x].rchild==0))//输出叶子结点 cout<的权值。edge 为结构 体类型。 {for (int i=1;i<=n-1;i++)//初始化结点 1 到其它 n-1 个结点形成的边集 {elist[i].from=1; elist[i].to=i+1; elist[i].w=a[1][i+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(elist[j].wa[elist[i].to][elist[j].to]) elist[j].w=a[elist[i].to][elist[j].to];} } for(int i=1;i<=n-1;i++)//求最小生成树的值 ans=ans+elist[i].w; } 如果要求出哪些边构成最小生成树，在更新第 i+1 至 n-1 条边到已经生成的树中最小距离时(上面代 码中加粗的部分)，还要加上 elist[j].from=elist[i].to;语句，即在更新权值时，还应该更新起点。 Prime 算法适用于顶点不是太多的稠密图，如果对于顶点数较多的稀疏图，就不太适用了。 十九、Dijkstra 算法 void dijkstra(int x) //求结点 x 到各个结点的最短路径 { memset(vis,0,sizeof(vis)); //初始化，vis[i]＝0 表示源点到结点 i 未求，否则已求 vis[x]=1;pre[x]=0; //初始化源点。 for(int i=1;i<=n;i++) //对其它各点初始化。 if(i!=x) { dis[i]=g[x][i]; pre[i]=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;j<=n;j++) //在未求出的结点中找一个源点到其距离最小的点 if(vis[j]==0&&m>dis[j]) { m=dis[j]; k=j; } vis[k]=1; //思考：如果 k=X 说明什么？说明后面的点，无解。 for(int j=1;j<=n;j++) //用当前找的结点更新未求结点到 X 的最短路径 if((vis[j]==0)&&(dis[k]+g[k][j]>1].w; while(hm) r--; if(h<=r) {edge tmp=elist[h];elist[h]=elist[r];elist[r]=tmp;h++;r--;} } if(xn-1) break;//已经确定了 n-1 条边了，最小生成树已经生成了，可以提前退出循环了 } if(sum的权值。 {for(int k=1;k<=n;k++) //枚举中间加入的结点不超过 K 时 f[i][j]最短路径长度，K 相当 DP 中的阶 段 for(int i=1;i<=n;i++) //i，j 是结点 i 到结点 J，相当于 DP 中的状态 for(int j=1;j<=n;j++) if (a[i][j]>a[i][k]+a[k][j]) a[i][j]=a[i][k]+a[k][j];//这是决策，加和不加中间点，取最小的值 } 弗洛伊德算法适合于求没有负权回路的图的最短路径长度，利用 FLOYED 算法，可写出判断结点 i 和 结点 J 是否连通的算法。 二十二、01 背包问题 n 为物品的数量，w[i]表示第 i 个物品的重量，c[i]表示第 i 个物品的价值，v 为背包的最大重量。 有状态转移方程 f[i][j]=max{f[i-1][j],f[i-1][j-w[i]]+c[i]}。f[i][j]表示前 i 个物品，在背包载重为 j 时获 得的最大价值。显然 f[n][v]即为所求。边界条件为 f[0][s]=0,s=0,1,…,v。 for(int i=1;i<=n;i++)//枚举阶段 for(int j=0;j<=v;j++)//枚举状态，当然此处也可写成:for(int j=v;j>=0;j--) { f[i][j]=f[i-1][j];//不选第 i 个物品 if(f[i][j]=0;j--)//枚举状态，当然此处也可写成:for(int j=v;j>=0;j--) { f[j]=f[j];//不选第 i 个物品，可省略此语句。 if((j>w[i])&&(f[j]=w[i];j--)，此时下面的判断条件 j>=w[i]就可以省略了。 二十三、完全背包问题 和 01 背包问题不同的是，完全背包，对于任何一个物品 i，只要背包重量允许，可以多次选取，也就 是在决策上，可以选 0 个，1 个，2 个，…，v/w[i]个。 状态转移方程 f[i][j]=max{f[i-1][j],f[i-1][j-w[i]]+c[i]，f[i-1][j-2*w[i]]+2*c[i]，…，f[i-1][j- k*w[i]]+k*c[i]}。k=0，1，2，…，v/w[i]。f[i][j]表示前 i 个物品，在背包载重为 j 时获得的最大价值。 显然 f[n][v]即为所求。边界条件为 f[0][s]=0,s=0,1,…,v。 for(int i=1;i<=n;i++)//枚举阶段 for(int j=0;j<=v;j++)//枚举状态，当然此处也可写成:for(int j=v;j>=0;j--) {f[i][j]=f[i-1][j];//k=0 的情况作为 f[i][j]的初始值，然后在 k=1,2,…,v/w[i]中找最大值 for(int k=1;k<=v/w[i];k++) if(f[i][j]