文档编制序号：[KK8UY-LL9IO69-TTO6M3-MTOL89-FTT688]C常用算法及其实现常用算法经典代码（C++版）一、快速排序voidqsort(intx,inty)//待排序的数据存放在a[1]..a[n]数组中{inth=x,r=y;intm=a[(x+y)>>1];//取中间的那个位置的值while(h
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=1;j--)//相邻的两两比较if(a[j]>a;tong[a]++;}//相应的桶号计数器加1for(inti=1;i<=cmax;i++){if(tong[i]>0)//当桶中装的树大于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);//把已经有序的前后两段进行合并}归并排序应用了分治思想，把一个大问题，变成两个小问题。二分是分治的思想。五、二分查找intfind(intx,inty,intm)//在[x,y]区间查找关键字等于m的元素下标{inthead,tail,mid;head=x;tail=y;mid=((x+y)/2);//取中间元素下标if(a[mid]==m)returnmid;//如果中间元素值为m返回中间元素下标midif(head>tail)return0;//如果x>y，查找失败，返回0if(m>a[mid])//如果m比中间元素大，在后半区间查找，返回后半区间查找结果returnfind(mid+1,tail);else//如果m比中间元素小，在前半区间查找，返回后前区间查找结果returnfind(head,mid-1);}六、高精度加法#include#includeusingnamespacestd;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<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<1))b[0]--;for(i=b[0];i>=1;i--)cout<s2.length())return0;//先比较长度，哪个字符串长，对应的那个数就大if(s1.length()s2[i])return0;if(s1[i]#includeusingnamespacestd;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>1for(i=len;i>=1;i--)cout<#includeusingnamespacestd;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<=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;}九、高精度除法（没讲）十、筛选法建立素数
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
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<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<的权值。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].wa[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个结点的最短距离{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]>1].w;while(hm)r--;if(h<=r){edgetmp=elist[h];elist[h]=elist[r];elist[r]=tmp;h++;r--;}}if(xn-1)break;//已经确定了n-1条边了，最小生成树已经生成了，可以提前退出循环了}if(sum的权值。{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]=0;j--)//枚举状态，当然此处也可写成:for(intj=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(inti=1;i<=n;i++)//枚举阶段for(intj=0;j<=v;j++)//枚举状态，当然此处也可写成:for(intj=v;j>=0;j--){f[i][j]=f[i-1][j];//k=0的情况作为f[i][j]的初始值，然后在k=1,2,…,v/w[i]中找最大值for(intk=1;k<=v/w[i];k++)if(f[i][j]
本文档为【C常用算法及其实现】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483