0 2
1 4
2 5
3 6
0 4
6 0
1.4 quick find
quick find的思想是:对每一对数p, q,用一个临时变量 t 记住左边的数 p, 然后遍历整个 id 数组
如果该元素 id[i] 与 t 相等那么 标记id[i] = id[q].
- #include "stdafx.h"
- #include <stdio.h>
- #define N 7
- int _tmain(int argc, _TCHAR* argv[])
- {
- int count,j;
- int i=0,p,q,t,id[N];
- freopen("01quickfindin.txt","r",stdin);
- for (i=0; i < N; ++i)//初始化
- {
- id[i]=i;
- }
- while(scanf("%d %d",&p,&q)==2)
- {
- if(id[p]==id[q]) continue;
- count=0;
- t=id[p];
- for(i=0;i<N;++i)
- { //遍历id数组,如果某元素与左侧相同,那么向右侧靠拢
- if (id[i]==t)
- {
- count++;
- id[i]=id[q];
- }
- }
- printf("\n%d-%d\n",p,q);
- for (i=0; i < N; ++i)
- {
- printf("%d ",id[i]);
- }
- }
- return 0;
- }
- /*
- 0 2
1 4
2 5
3 6
0 4
6 0
1 3
*/
1.5 quick union
- //quick union
- #include "stdafx.h"
- #include <stdio.h>
- #define N 7
- int _tmain(int argc, _TCHAR* argv[])
- {
- int count,j;
- int i=0,p,q,id[N],sz[N];
- freopen("02quickunionin.txt","r",stdin);
- for (i=0; i < N; ++i)//初始化
- {
- id[i]=i;
- sz[i]=1;
- }
- while(scanf("%d %d",&p,&q)==2)
- {
- if(id[p]==id[q]) continue;
- count=0;
- for(i=p; i!=id[i]; i=id[i]);//找到i的最顶端,相当于下面所有的都接过去了
- for(j=q; j!=id[j]; j=id[j]);//找到j的最顶端,接到最顶端可以减少路径的长度
- if(i==j)
- continue;
- id[i]=j;//将i接到j的下面
- printf("\n%d-%d\n",p,q);
- for (i=0; i < N; ++i)
- {
- printf("%d ",id[i]);
- }
- }
- return 0;
- }
- /*
- 0 2
- 1 4
- 2 5
- 3 6
- 0 4
- 6 0
- 1 3
- */
1.6 weight quick union
- //加权快速合并算法
- #include "stdafx.h"
- #include <stdio.h>
- #define N 10
- int _tmain(int argc, _TCHAR* argv[])
- {
- int count,j;
- int i=0,p,q,id[N],sz[N];
- freopen("03weightquickunion.txt","r",stdin);
- for (i=0; i < N; ++i)//初始化
- {
- id[i]=i;
- sz[i]=1;
- }
- while(scanf("%d %d",&p,&q)==2)
- {
- if(id[p]==id[q]) continue;
- count=0;
- for(i=p; i!=id[i]; i=id[i])//找到根节点
- ;
- for(j=q; j!=id[j]; j=id[j])//找到根节点
- ;
- if(i==j)
- continue;
- if(sz[i]<sz[j])
- {
- id[i]=j;
- sz[j]+=sz[i];//更新树的节点数
- }
- else{
- id[j]=i;
- sz[i]+=sz[j];//更新树的节点数
- }
- printf("\n%d-%d\n",p,q);
- for (i=0; i < N; ++i)
- {
- printf("%d ",id[i]);
- }
- }
- return 0;
- }
1.8 带有等分路径压缩的加权快速合并算法
- //带有等分路径压缩的加权快速合并
- #include "stdafx.h"
- #include <stdio.h>
- #define N 10
- int _tmain(int argc, _TCHAR* argv[])
- {
- int count,j;
- int i=0,p,q,id[N],sz[N];
- freopen("04pathcompress_weightquickunion.txt","r",stdin);
- for (i=0; i < N; ++i)//初始化
- {
- id[i]=i;
- sz[i]=1;
- }
- while(scanf("%d %d",&p,&q)==2)
- {
- if(id[p]==id[q]) continue;
- for(i=p; i!=id[i]; i=id[i])
- id[i]=id[id[i]];
- for(j=q; j!=id[j]; j=id[j])
- id[j]=id[id[j]];
- if(i==j)
- continue;
- if(sz[i]<sz[j])
- {
- id[i]=j;
- sz[j]+=sz[i];
- }
- else{
- id[j]=i;
- sz[i]+=sz[j];
- }
- printf("\n%d-%d\n",p,q);
- for (i=0; i < N; ++i)
- {
- printf("%d ",id[i]);
- }
- }
- return 0;
- }
算法导论 第二版影印版
计算机网络第四版
GCC技术参考大全
4G移动通信技术权威指南