算法大全(数据结构)(C版本).doc

《算法大全(数据结构)(C版本).doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、算法大全（C，C++）一、数论算法1．求两数的最大公约数intgcd(inta,intb){intr;while(b!=0){r=a%b;a=b;b=r;}returna;}2．求两数的最小公倍数intlcm(inta,b);{returna*b/gcd(a,b);}3．素数的求法A.小范围内判断一个数是否为质数：boolprime(intn){inti;for(i=2;i

2、lp[50001];memset(p,true,sizeof(p));p[1]=false;for(i=2;i<50001;i++){if(p[i]){for(j=i*2;j<50001;j+=i){p[j]=false;}}}二、图论算法1．最小生成树A.Prim算法：/*邻接矩阵cost[maxN][maxN]*/#definemaxLongInt#definemaxN10000intcost[maxN][maxN];//cost[i][i]=0;inttot;intlowcost[maxN],//点i到MST的当前最小距离，lowcost[i]==0表示/

3、/点i已经加入MSTclosest[maxN];//点j到MST距离最小的边的另一个顶点prim(intv0,intn){inti,j,k,min;tot=0;for(i=0;i

4、点k加入生成树//{生成树中增加一条新的边k到closest[k]}//{修正各点的lowcost和closest值}for(j=0;j

5、v2为//边i所连接的两个顶点的序号，e[i].len为第I条边的长度intv1;intv2;intlen;}e[maxn*maxn/2];structvsets//森林集合{intv[maxn];//集合中的顶点intnum;//集合中树的个数}vset[maxn];intn;intfind(intv)//返回点v属于哪个森林集合{inti,j;for(i=0;i

6、能生成返回true{inti,j,tot;//tot表示MST中所有边长度的总和intp,q;for(i=0;i0){if(q>=n*(n-1)/2)//n为顶点的数量，n*(n-1)/2为边的总数-》如果遍历所有边也无returnfalse;//法筛选出n-1条边，则不能生成最小生成树，返回false;i=find(e[q].v1);//返回点v1属于哪个

7、森林集合j=find(e[q].v2);if(i!=j){tot+=e[q].len;for(intk=0;k

8、{intbest,bes