常用算法经典程序C++

一、快速排序voidqsort(intx,inty)//待排序的数据存放在a[1]..a[n]数组中

{inth=x,r=y;

intm=a[(x+y)>>1];//取中间的那个位置的值

while(h<r){while(a[h]<m)h++;//比中间那个位置的值小，循环直到找一个比中间那个值大的

while(a[r]>m)r--;//比中间那个位置的值大，循环直到找一个比中间那个值小的

if(h<=r){inttemp=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<y)qsort(h,y);//注意此处，头指针跑到后半部分了}调用：qsort(1,n)即可实现数组a中元素有序。适用于n比较大的排序

二、冒泡排序voidpaopao(void)//待排序的数据存放在a[1]..a[n]数组中{for(inti=1;i<n;i++)

//控制循环（冒泡）的次数，n个数，需要n-1次冒泡

for(intj=1;j<=n-i;j++)//相邻的两两比较

if(a[j]<a[j+1]){inttemp=a[j];a[j]=a[j+1];a[j+1]=temp;}}或者voidpaopao(void)//待排序的数据存放在a[1]..a[n]数组中{for(inti=1;i<n;i++)

//控制循环（冒泡）的次数，n个数，需要n-1次冒泡

for(intj=n-i;j>=1;j--)//相邻的两两比较

if(a[j]<a[j+1]){inttemp=a[j];a[j]=a[j+1];a[j+1]=temp;}}

调用：paopao()，适用于n比较小的排序

三、桶排序voidbucketsort(void)//a的取值范围已知。如a<=cmax。

{memset(tong,0,sizeof(tong));//桶初始化for(inti=1;i<=n;i++)//读入n个数

{intacin>>a;tong[a]++;}//相应的桶号计数器加1

for(inti=1;i<=cmax;i++)

{if(tong[i]>0)//当桶中装的树大于0，说明i出现过tong[i]次，否则没出现过i

while(tong[i]!=0)

{tong[i]--;cout<<i<<’‘;}}}

桶排序适用于那些待排序的关键字的值在已知范围的排序。

四、合（归）并排序voidmerge(intl,intm,intr)//合并[l,m]和[m+1,r]两个已经有序的区间{intb[101];//借助一个新的数组B，使两个有序的子区间合并成一个有序的区间，b数组的大小要注意

inth,t,k;

k=0;//用于新数组B的指针

h=l;t=m+1;//让h指向第一个区间的第一个元素，t指向第二个区间的第一个元素。

while((h<=m)&&(t<=r))//在指针h和t没有到区间尾时，把两个区间的元素抄在新数组中

{k++;

//新数组指针加1

if(a[h]<a[t]){b[k]=a[h];h++;}

//抄第一个区间元素到新数组

else{b[k]=a[t];t++;}

//抄第二个区间元素到新数组

}

while(h<=m){k++;b[k]=a[h];h++;}

//如果第一个区间没有抄结束，把剩下的抄在新数组中

while(t<=r){k++;b[k]=a[t];t++;}

//如果第二个区间没有抄结束，把剩下的抄在新数组中

for(into=1;o<=k;o++)//把新数组中的元素，再抄回原来的区间，这两个连续的区间变为有序的区间。a[l+o-1]=b[o];}voidmergesort(intx,inty)//对区间[x,y]进行二路归并排序{

intmid;

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);//把已经有序的前后两段进行合并}

归并排序应用了分治思想，把一个大问题，变成两个小问题。二分是分治的思想。

五、二分查找intfind(intx,inty,intm)//在[x,y]区间查找关键字等于m的元素下标{inthead,tail,mid;

head=x;tail=y;mid=((x+y)/2);//取中间元素下标

if(a[mid]==m)returnmid;//如果中间元素值为m返回中间元素下标mid

if(head>tail)return0;//如果x>y，查找失败，返回0

if(m>a[mid])

//如果m比中间元素大，在后半区间查找，返回后半区间查找结果

returnfind(mid+1,tail);

else//如果m比中间元素小，在前半区间查找，返回后前区间查找结果

returnfind(head,mid-1);}六、高精度加法#include<iostream>#include<cstring>usingnamespacestd;intmain(){

stringstr1,str2;

inta[250],b[250],len;

//数组的大小决定了计算的高精度最大位数

inti;

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<<a[i];

return0;

}

注意：两个数相加，结果的位数，应该比两个数中大的那个数多一位。

七、高精度减法#include<iostream>usingnamespacestd;intcompare(strings1,strings2);intmain(){

stringstr1,str2;

inta[250],b[250],len;

inti;

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<<a[i];

cout<<endl;

}

else

{

cout<<'-';

//小于就输出负号

for(i=1;i<=b[0];i++)

//做按位减，大的减小的

{b[i]-=a[i];

if(b[i]<0){b[i+1]--;b[i]+=10;}

}

b[0]++;

while((b[b[0]]==0)&&(b[0]>1))b[0]--;

for(i=b[0];i>=1;i--)

cout<<b[i];

cout<<endl;

}

return0;

}intcompare(strings1,strings2)

//比较字符串（两个数）数字的大小，大于等于返回0，小于返回1。{

if(s1.length()>s2.length())return0;

//先比较长度，哪个字符串长，对应的那个数就大

if(s1.length()<s2.length())return1;

for(inti=0;i<=s1.length();i++)

//长度相同时，就一位一位比较。

{

if(s1[i]>s2[i])return0;

if(s1[i]<s2[i])return1;

}

return0;

//如果长度相同，每一位也一样，就返回0，说明相等}

做减法时，首先要判断两个字符串的大小，决定是否输出负号，然后就是按位减法，注意处理借位。

八、高精度乘法#include<iostream>#include<cstring>usingnamespacestd;intmain(){

stringstr1,str2;

inta[250],b[250],c[500],len;

//250位以内的两个数相乘

inti,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<<c[i];

return0;

}

注意：两个数相乘，结果的位数应该是这两个数的位数和减1。优化：万进制#include<iostream>#include<cstring>usingnamespacestd;voidnum1(ints[],stringst1);inta[2501],b[2501],c[5002];//此处可以进行2500位万进制乘法，即10000位十进制乘法。Intmain(){

stringstr1,str2;

intlen;

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(inti=1;i<=a[0];i++)//作按位乘法并处理进位，此处是万进制进位

for(intj=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<<c[len];

for(inti=len-1;i>=1;i--)//把剩下来的每一位还原成4位输出

{

if(c[i]<1000)cout<<’0’;

if(c[i]<100)cout<<’0’;

if(c[i]<10)cout<<’0’;

cout<<c[i];

}

cout<<endl;

return0;}voidnum1(ints[],stringst1)//此函数的作用就是把字符串st1，按4位一组存放在数组s中{

intk=1,count=1;

s[0]=st1.length();//存放st1的长度，省去一长度变量

for(inti=s[0]-1;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;}

九、高精度除法（没讲）

十、筛选法建立素数表voidmaketable(intx)//建立X以内的素数表prim，prim[i]为0，表示i为素数，为1表示不是质数{

memset(prim,0,sizeof(prim));//初始化质数表

prim[0]=1;prim[1]=1;prim[2]=0;//用筛选法求X以内的质数表

for(inti=2;i<=x;i++)

if(prim[i]==0)

{intj=2*i;

while(j<=x)

{prim[j]=1;j=j+i;}}}

对于那些算法中，经常要判断素数的问题，建立一个素数表，可以达到一劳永逸的目的。

十一、深度优先搜索voiddfs(intx)

\\以图的深度优先遍历为例。

{

cout<<x<<‘‘;\\访问x顶点

visited[x]=1;\\作已访问的标记

for(intk=1;k<=n;k++)\\对与顶点x相邻而又没访问过的结点k进行深度优先搜索。

if((a[x][k]==1)&&(visited[k]==0))

dfs(k);

}十二、广度优先搜索void

bfs(void)//按广度优先非递归遍历图G，n个顶点，编号为1..n。注：图不一定是连通的{//使用辅助队列Q和访问标记数组visited。

for(v=1;v<=n;v++)

visited[v]=0；//标记数组初始化

for(v=1;v<=n;v++)

if(visited[v]==0){

//v尚未访问

inth=1,r=1;

//置空的辅助队列q

visited[v]=1；//顶点v,作访问标记

cout<<v<<‘‘;//访问顶点v

q[r]=v；

//v入队列

while(h<=r)//当队列非空时循环

{

inttmp=q[h];

//队头元素出队，并赋值给tmp

for(intj=1;j<=n;j++)

if((visited[j]==0)&&(a[tmp][j]==1)){//j为tmp的尚未访问的邻接顶点

visited[j]=1;

对j作访问标记

cout<<j<<‘‘;访问j

r++;//队尾指针加1q[r]=j;//j入队}

//end-if

h++;

}//end-while}十三、二叉树的前序、中序和后序遍历voidpreorder(intx)//二叉树的先序遍历

{

if(x==0)return;

cout<<x;//先访问根

preorder(a[x].ld);//再先序遍历根的左子树

preorder(a[x].rd);//最后先序遍历根的右子树}

voidinorder(intx)//二叉树的中序遍历

{

if(x==0)return;

preorder(a[x].ld);//先中序遍历根的左子树

cout<<x;//再访问根

preorder(a[x].rd);//最后中序遍历根的右子树}

voidreorder(intx)//二叉树的后序遍历

{

if(x==0)return;

preorder(a[x].ld);//先后序遍历根的左子树

preorder(a[x].rd);//再后序遍历根的右子树

cout<<x;//最后访问根}

十四、树转换为二叉树算法

十五、二叉排序树

十六、哈夫曼树voidhaff(void)//构建哈夫曼树{

for(inti=n+1;i<=2*n-1;i++)//依次生成n-1个结点

{intl=fmin(i-1);//查找权值最小的结点的编号l

a[i].lchild=l;//把l作为结点i的左孩子

a[l].father=i;//把l的父结点修改为i

intr=fmin(i-1);//查找次小权值的编号r

a[i].rchild=r;//把l作为结点i的右孩子

a[r].father=i;//把r的父结点修改为i

a[i].da=a[l].da+a[r].da;//合并l,j结点，生成新结点i

}}intfmin(intk)//在1到K中寻找最小的权值的编号

{

intmins=0;

for(ints=1;s<=k;s++)

if((a[mins].da>a[s].da)&&(a[s].father==0))//a[s].father=0,说明这个结点还不是别个结点mins=s;

//的孩子，不等于0说明这个结点已经用过。

returnmins;

}voidinorder(intx)//递归生成哈夫曼编码{

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<<a[x].da<<':'<<a[x].code<<endl;

if(a[x].rchild!=0)inorder(a[x].rchild);//递归生成右子树}十七、并查集intgetfather(intx)//非递归求X结点的根结点的编号{while(x!=father[x])

x=father[x];

returnx;}

intgetfather(intx)//递归求X结点的根结点的编号{if(x==father[x])returnx;

elsereturngetfather(father[x]);

}

intgetfather(intx)//非递归求X结点的根结点编号同时进行路径压缩{intp=x;while(p!=father[p])//循环结束后，P即为根结点

p=father[p];

while(x!=father[x])//从X结点沿X的父结点进行路径压缩

{inttemp=father[x];//暂存X没有修改前的父结点father[x]=p;//把X的父结点指向Px=temp;

}

returnp;}

intgetfather(intx)//递归求X结点的根结点编号同时进行路径压缩{if(x==father[x])returnx;

else{

inttemp=getfather(father[x]);

father[x]=temp;

returntemp;}}

voidmerge(intx,inty)//合并x,y两个结点

{intx1,x2;

x1=getfather(x);//取得X的父结点

x2=getfather(y);//取得Y的父结点

if(x1!=x2)father[x1]=x2;//两个父结点不同的话就合并，注意：合并的是X，Y两个结点的根。}

十八、Prime算法voidprime(void)//prim算法求最小生成树，elist[i]是边集数组，a[i][j]为<I,j>的权值。edge为结构体类型。{for(inti=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(inti=1;i<=n-1;i++)//依次确定n-1条边

{intm=i;

for(intj=i+1;j<=n-1;j++)//确定第i条边时，依次在i+1至n-1条边中找最小的那条边

if(elist[j].w<elist[m].w)m=j;

if(m!=i)//如果最小的边不是第i条边就交换{edgetmp=elist[i];elist[i]=elist[m];elist[m]=tmp;}

for(intj=i+1;j<=n-1;j++)//更新第i+1至n-1条边的最小距离。

{if(elist[j].w>a[elist[i].to][elist[j].to])elist[j].w=a[elist[i].to][elist[j].to];}}

for(inti=1;i<=n-1;i++)//求最小生成树的值ans=ans+elist[i].w;}

如果要求出哪些边构成最小生成树，在更新第i+1至n-1条边到已经生成的树中最小距离时(上面代码中加粗的部分)，还要加上elist[j].from=elist[i].to;语句，即在更新权值时，还应该更新起点。Prime算法适用于顶点不是太多的稠密图，如果对于顶点数较多的稀疏图，就不太适用了。

十九、Dijkstra算法voiddijkstra(intx)

//求结点x到各个结点的最短路径{memset(vis,0,sizeof(vis));//初始化，vis[i]＝0表示源点到结点i未求，否则已求vis[x]=1;pre[x]=0;//初始化源点。for(inti=1;i<=n;i++)

//对其它各点初始化。

if(i!=x){dis[i]=g[x][i];pre[i]=x;}for(inti=1;i<=n-1;i++)

//对于n个结点的图，要求x到其它n-1个结点的最短距离

{intm=big;//虚拟一个最大的数big=99999999;intk=x;

for(intj=1;j<=n;j++)

//在未求出的结点中找一个源点到其距离最小的点

if(vis[j]==0&&m>dis[j]){m=dis[j];k=j;}

vis[k]=1;

//思考：如果k=X说明什么？说明后面的点，无解。

for(intj=1;j<=n;j++)

//用当前找的结点更新未求结点到X的最短路径

if((vis[j]==0)&&(dis[k]+g[k][j]<dis[j]))

{

dis[j]=dis[k]+g[k][j];

//更新

pre[j]=k;

//保存前趋结点，以便后面求路径

}

}}说明：dis[i]表示x到i的最短距离，pre[i]表示i结点的前趋结点。二十、Kruscal算法voidqsort(intx,inty)//对边集数组进行快速排序{inth=x,r=y,m=elist[(h+r)>>1].w;

while(h<r)

{while(elist[h].w<m)h++;

while(elist[r].w>m)r--;

if(h<=r)

{edgetmp=elist[h];elist[h]=elist[r];elist[r]=tmp;h++;r--;}

}

if(x<r)qsort(x,r);

if(h<y)qsort(h,y);}

intgetfather(intx)//找根结点，并压缩路径，此处用递归实现的。{if(x==father[x])returnx;

else{

intf=getfather(father[x]);

father[x]=f;

returnf;

}}

voidmerge(intx,inty)//合并x,y结点，在此题中的x,y为两个根结点。{father[x]=y;}

voidkruscal(void){intsum=0,ans=0;qsort(1,t);//对t条边按权值大小按从小到大的次序进行快速排序

for(inti=1;i<=t;i++)

{intx1=getfather(elist[i].from);//取第i条边的起点所在的树的根intx2=getfather(elist[i].to);//取第i条边的终点所在的树的根if(x1!=x2){sum++;merge(x1,x2);ans+=elist[i].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算法voidfloyed(void)//a[i][j]表示结点i到结点j的最短路径长度，初始时值为<I,J>的权值。{for(intk=1;k<=n;k++)//枚举中间加入的结点不超过K时f[i][j]最短路径长度，K相当DP中的阶段

for(inti=1;i<=n;i++)//i，j是结点i到结点J，相当于DP中的状态for(intj=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(inti=1;i<=n;i++)//枚举阶段

for(intj=0;j<=v;j++)//枚举状态，当然此处也可写成:for(intj=v;j>=0;j--)

{f[i][j]=f[i-1][j];//不选第i个物品if(f[i][j]<f[i-1][