C++常用经典算法及其实现.doc

_常用算法经典代码（C+版） 一、快速排序void qsort(int x,int y) /待排序的数据存放在a1.an数组中  int h=x,r=y;   int m=a(x+y)>>1; /取中间的那个位置的值   while(h<r)while (ah<m) h+; /比中间那个位置的值小，循环直到找一个比中间那个值大的      while (ar>m) r-; /比中间那个位置的值大，循环直到找一个比中间那个值小的      if(h<=r)int temp=ah;/如果此时h<=r，交换ah和ar         ah=ar;         ar=temp;         h+;r-; /这两句必不可少哦     if(r>x) qsort(x,r);/注意此处，尾指针跑到前半部分了     if(h<y) qsort(h,y); /注意此处，头指针跑到后半部分了调用：qsort(1,n)即可实现数组a中元素有序。适用于n比较大的排序 二、冒泡排序void paopao(void) /待排序的数据存放在a1.an数组中for(int i=1;i<n;i+)  /控制循环（冒泡）的次数，n个数，需要n-1次冒泡  for(int j=1;j<=n-i;j+) /相邻的两两比较    if(aj<aj+1) int temp=aj;aj=aj+1;aj+1=temp;或者void paopao(void) /待排序的数据存放在a1.an数组中for(int i=1;i<n;i+)  /控制循环（冒泡）的次数，n个数，需要n-1次冒泡  for(int j=n-i;j>=1;j-) /相邻的两两比较    if(aj<aj+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;i<=n;i+)/读入n个数    int acin>>a;tonga+;/相应的桶号计数器加1  for(int i=1;i<=cmax;i+)  if(tongi>0) /当桶中装的树大于0，说明i出现过tongi次，否则没出现过i     while (tongi!=0)       tongi-;cout<<i<< ; 桶排序适用于那些待排序的关键字的值在已知范围的排序。 四、合（归）并排序void merge(int l,int m,int r)/合并l,m和m+1,r两个已经有序的区间 int b101;/借助一个新的数组B，使两个有序的子区间合并成一个有序的区间，b数组的大小要注意  int h,t,k;  k=0;/用于新数组B的指针  h=l;t=m+1;/让h指向第一个区间的第一个元素，t指向第二个区间的第一个元素。  while(h<=m)&&(t<=r)/在指针h和t没有到区间尾时，把两个区间的元素抄在新数组中    k+;       /新数组指针加1     if (ah<at)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<=k;o+)/把新数组中的元素，再抄回原来的区间，这两个连续的区间变为有序的区间。al+o-1=bo;void mergesort(int x,int y)/对区间x,y进行二路归并排序  int mid;  if(x>=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返回中间元素下标mid  if(head>tail) return 0;/如果x>y，查找失败，返回0  if(m>amid)  /如果m比中间元素大，在后半区间查找，返回后半区间查找结果    return find(mid+1,tail);  else /如果m比中间元素小，在前半区间查找，返回后前区间查找结果    return find(head,mid-1);六、高精度加法#include<iostream>#include<cstring>using namespace std;int main()  string str1,str2;  int a250,b250,len;   /数组的大小决定了计算的高精度最大位数  int i;  memset(a,0,sizeof(a);  memset(b,0,sizeof(b);  cin>>str1>>str2;   /输入两个字符串  a0=str1.length();  /取得第一个字符串的长度  for(i=1;i<=a0;i+)  /把第一个字符串转换为整数，存放在数组a中    ai=str1a0-i-'0'  b0=str2.length();   /取得第二个字符串长度  for(i=1;i<=b0;i+)   /把第二个字符串中的每一位转换为整数，存放在数组B中    bi=str2b0-i-'0'  len=(a0>b0?a0:b0);   /取两个字符串最大的长度  for(i=1;i<=len;i+)   /做按位加法，同时处理进位      ai+=bi;    ai+1+=ai/10;    ai%=10;       len+;    /下面是去掉最高位的0，然后输出。  while(alen=0)&&(len>1) len-;  for(i=len;i>=1;i-)    cout<<ai;  return 0;  注意：两个数相加，结果的位数，应该比两个数中大的那个数多一位。 七、高精度减法#include<iostream>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);  cin>>str1>>str2;  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 (ai<0) ai+1-;ai+=10;          a0+;    while(aa0=0)&&(a0>1) a0-;    for(i=a0;i>=1;i-)      cout<<ai;    cout<<endl;                               else      cout<<'-'  /小于就输出负号    for(i=1;i<=b0;i+)  /做按位减，大的减小的      bi-=ai;       if (bi<0) bi+1-;bi+=10;          b0+;    while(bb0=0)&&(b0>1) b0-;    for(i=b0;i>=1;i-)      cout<<bi;    cout<<endl;            return 0; int compare(string s1,string s2)  /比较字符串（两个数）数字的大小，大于等于返回0，小于返回1。  if(s1.length()>s2.length() return 0;  /先比较长度，哪个字符串长，对应的那个数就大  if(s1.length()<s2.length() return 1;  for(int i=0;i<=s1.length();i+)  /长度相同时，就一位一位比较。      if(s1i>s2i) return 0;    if(s1i<s2i) return 1;                              return 0;   /如果长度相同，每一位也一样，就返回0，说明相等 做减法时，首先要判断两个字符串的大小，决定是否输出负号，然后就是按位减法，注意处理借位。 八、高精度乘法#include<iostream>#include<cstring>using 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);  cin>>str1>>str2;  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;j<=b0;j+)        ci+j-1+=ai*bj;    ci+j+=ci+j-1/10;    ci+j-1%=10;         len=a0+b0+1;  /去掉最高位的0，然后输出  while(clen=0)&&(len>1) len-;   /为什么此处要len>1?  for(i=len;i>=1;i-)    cout<<ci;  return 0;  注意：两个数相乘，结果的位数应该是这两个数的位数和减1。优化：万进制#include<iostream>#include<cstring>using namespace std;void num1(int s,string st1);int a2501,b2501,c5002;/此处可以进行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<=a0;i+) /作按位乘法并处理进位，此处是万进制进位      for(int j=1;j<=b0;j+)                  ci+j-1+=ai*bj;          ci+j+=ci+j-1/10000;          ci+j-1%=10000;            len=a0+b0;/a0和b0存放的是每个数按4位处理的位数    while (clen=0)&&(len>1) len-;/去掉高位的0，并输出最高位      cout<<clen;    for(int i=len-1;i>=1;i-)/把剩下来的每一位还原成4位输出              if (ci<1000) cout<<0;        if (ci<100) cout<<0;        if (ci<10) cout<<0;                cout<<ci;          cout<<endl;    return 0;void num1(int s,string st1)/此函数的作用就是把字符串st1，按4位一组存放在数组s中   int k=1,count=1;    s0=st1.length();/存放st1的长度，省去一长度变量    for(int i=s0-1;i>=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表示不是质数 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)  以图的深度优先遍历为例。           cout<<x<< ; 访问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(visitedv=0 )         /v尚未访问         int h=1,r=1;    /置空的辅助队列q         visitedv=1；/顶点v,作访问标记         cout<<v<< ; /访问顶点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作访问标记                    cout<<j<< ; 访问j                    r+; /队尾指针加1qr=j; /j入队  /end-if             h+;           /end -while十三、二叉树的前序、中序和后序遍历void preorder(int x)/二叉树的先序遍历    if(x=0) return;   cout<<x;/先访问根   preorder(ax.ld);/再先序遍历根的左子树   preorder(ax.rd);/最后先序遍历根的右子树 void inorder(int x)/二叉树的中序遍历    if(x=0) return;   preorder(ax.ld);/先中序遍历根的左子树   cout<<x;/再访问根   preorder(ax.rd);/最后中序遍历根的右子树 void reorder(int x)/二叉树的后序遍历    if(x=0) return;   preorder(ax.ld);/先后序遍历根的左子树   preorder(ax.rd);/再后序遍历根的右子树   cout<<x;/最后访问根  十四、树转换为二叉树算法 十五、二叉排序树 十六、哈夫曼树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; /合并l,j结点，生成新结点i     int fmin(int k)/在1到K中寻找最小的权值的编号                int mins=0;         for(int s=1;s<=k;s+)           if(amins.da>as.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)/输出叶子结点     cout<<ax.da<<':'<<ax.code<<endl;  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为<I,j>的权值。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.w<elistm.w) m=j;   if(m!=i) /如果最小的边不是第i条边就交换edge tmp=elisti;elisti=elistm;elistm=tmp;   for(int j=i+1;j<=n-1;j+)/更新第i+1至n-1条边的最小距离。     if(elistj.w>aelisti.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); /初始化，visi0表示源点到结点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;j<=n;j+)   /在未求出的结点中找一个源点到其距离最小的点        if(visj=0&&m>disj)m=disj;k=j;      visk=1;   /思考：如果k=X说明什么？说明后面的点，无解。      for(int j=1;j<=n;j+)   /用当前找的结点更新未求结点到X的最短路径      if(visj=0)&&(disk+gkj<disj)                    disj=disk+gkj;  /更新         prej=k;  /保存前趋结点，以便后面求路径            说明：disi表示x到i的最短距离，prei表示i结点的前趋结点。二十、Kruscal算法void qsort(int x,int y)/对边集数组进行快速排序int h=x,r=y,m=elist(h+r)>>1.w; while(h<r)  while(elisth.w<m) h+;   while(elistr.w>m) r-;   if(h<=r)    edge tmp=elisth;elisth=elistr;elistr=tmp;h+;r-;   if(x<r) qsort(x,r); if(h<y) 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;i<=t;i+)     int x1=getfather(elisti.from);/取第i条边的起点所在的树的根int x2=getfather(elisti.to);/ 取第i条边的终点所在的树的根if(x1!=x2)sum+;merge(x1,x2);ans+=elisti.w;/不在同一个集合，合并，即第i条边可以选取。if(sum>n-1)break;/已经确定了n-1条边了，最小生成树已经生成了，可以提前退出循环了   if(sum<n-1)cout<<"Impossible"<<endl; /从t条边中无法确定n-1条边，说明无法生成最小生成树   else  cout<<ans<<endl;   克鲁斯卡尔算法，只用了边集数组，没有用到图的邻接矩阵，因此当图的结点数比较多的时候，输入数据又是边的信息时，就要考虑用Kruscal算法。对于岛国问题，我们就要选择此算法，如果用Prim算法，还要开一个二维的数组来表示图的邻接矩阵，对于10000个点的数据，显然在空间上是无法容忍的。 二十一、Floyed算法void floyed(void)/ aij表示结点i到结点j的最短路径长度，初始时值为<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;j<=n;j+)      if (aij>aik+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<=v;j+)/枚举状态，当然此处也可写成:for(int j=v;j>=0;j-)   fij=fi-1j;/不选第i个物品if(fij<fi-1j-wi+ci) fij=fi-1j-wi+ci;/选第i个物品cout<<fnv<<endl;/输出结果。 优化：用一维数组实现，把第i-1阶段和第i阶段数据存在一块。for(int i=1;i<=n;i+)/枚举阶段 for(int j=v;j>=0;j-)/枚举状态，当然此处也可写成:for(int j=v;j>=0;j-)   fj=fj;/不选第i个物品，可省略此语句。     if(j>wi)&&(fj<fj-wi+ci) fj=fj-wi+ci;/选第i个物品cout<<fv<<endl;/输出结果。 对比优化前后，我们不难发现，优化后的代码实际上就是在原来基本的代码基础上，减少了阶段这一维，同时在枚举状态时，为了保证结果的正确性，枚举的顺序只能是v到0，而不能是0到v。大家细想一下为什么？就是保证在求第i阶段j状态时，fj-wi为第i-1阶段的值。 进一步优化，在上面代码中，枚举状态时，还可以写成for(int j=v;j>=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<=v;j+)/枚举状态，当然此处也可写成:for(int j=v;j>=0;j-)    fij=fi-1j;/k=0的情况作为fij的初始值，然后在k=1,2,v/wi中找最大值    for(int k=1;k<=v/wi;k+)  if(fij<fi-1j-k*wi+k*ci) fij=fi-1j-k*wi+k*ci;/选第i个物品cout<<fnv<<endl;/输出结果。 二十四、多属性背包问题 二十五、多背包问题 二十六、最长不降（上升）子序列问题    fi表示从第1个数开始，以第i个数结尾的最长递增子序列。 状态转移方程：fi=maxfj+1 （1ji-1，1in，aiaj）临界状态：f1=1; 二十七、最长公共子序列问题    fij表示第一个串前i个字符和第二个串前j个字符的最长公共子序列数。   状态转移方程：        fi-1j-1                 (若ai=bj)fij=                          maxfi-1j,fij-1+1     (若aibj)    临界状态:f0j=0，fi0=0THANKS !致力为企业和个人提供合同协议，策划案计划书，学习课件等等打造全网一站式需求欢迎您的下载，资料仅供参考-可编辑修改-