常用算法经典代码(c++版).doc

常用算法经典代码（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(hx) qsort(x,r);//注意此处，尾指针跑到前半部分了if(h=1;j--) //相邻的两两比较if(a[j]>a;tong[a]++;}//相应的桶号计数器加 1for(int i=1;i0) //当桶中装的树大于 0，说明 i 出现过 tong[i]次，否则没出现过 iwhile (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 返回中间元素下标 midif(head>tail) return 0;//如果 x>y，查找失败，返回 0if(m>a[mid]) //如果 m 比中间元素大，在后半区间查找，返回后半区间查找结果return find(mid+1,tail);else //如果 m 比中间元素小，在前半区间查找，返回后前区间查找结果return find(head,mid-1);}六、高精度加法#include#includeusing 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;ib[0]?a[0]:b[0]); //取两个字符串最大的长度for(i=1;i1)) len--;for(i=len;i>=1;i--)coutusing 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;i1)) a[0]--;for(i=a[0];i>=1;i--)cout1)) b[0]--;for(i=b[0];i>=1;i--)couts2.length()) return 0; //先比较长度，哪个字符串长，对应的那个数就大if(s1.length()s2[i]) return 0;if(s1[i]#includeusing 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;i1)) len--; //为什么此处要 len>1??for(i=len;i>=1;i--)cout#includeusing 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;i1)) len--;//去掉高位的 0，并输出最高位cout=1;i--)//把剩下来的每一位还原成 4 位输出{if (c[i]=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;ia[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;ia[elist[i].to][elist[j].to]) elist[j].w=a[elist[i].to][elist[j].to];}} for(int i=1;idis[j]){m=dis[j];k=j;}vis[k]=1; //思考：如果 k=X 说明什么？说明后面的点，无解for(int j=1;j>1].w;while(hm) r--;if(hn-1)break;//已经确定了 n-1 条边了，最小生成树已经生成了，可以提前退出循环了}if(sum的权值{for(int k=1;ka[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,…,vfor(int i=1;i=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])//选第 i 个物品}cout=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,…,vfor(int i=1;i=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]