Algorithm In C 习题 第一章

1.1 Answer
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].

1. #include "stdafx.h"
   
2. #include <stdio.h>
   
3. #define N 7
   
4. int _tmain(int argc, _TCHAR* argv[])
   
5. {
   
6.    int count,j;
   
7.    int i=0,p,q,t,id[N];
   
8.    freopen("01quickfindin.txt","r",stdin);
   
9.    for (i=0; i < N; ++i)//初始化
   
10.    {
    
11.       id[i]=i;
    
12.    }
    
13.    while(scanf("%d %d",&p,&q)==2)
    
14.    {
    
15.       if(id[p]==id[q]) continue;
    
16.       count=0;
    
17.       t=id[p];
    
18.       for(i=0;i<N;++i)
    
19.       { //遍历id数组,如果某元素与左侧相同,那么向右侧靠拢
    
20.          if (id[i]==t)
    
21.          {
    
22.             count++;
    
23.             id[i]=id[q];
    
24.          }
    
25.       }
    
26.       printf("\n%d-%d\n",p,q);
    
27.       for (i=0; i < N; ++i)
    
28.       {
    
29.          printf("%d ",id[i]);
    
30.       }
    
31.    }
    
32.    return 0;
    
33. }
34. /*
35. 0 2
    1 4
    2 5
    3 6
    0 4
    6 0
    1 3
    */
    

1.5 quick union

1. //quick union
   
2. #include "stdafx.h"
   
3. #include <stdio.h>
   
4. #define N 7
   
5. int _tmain(int argc, _TCHAR* argv[])
   
6. {
   
7.    int count,j;
   
8.    int i=0,p,q,id[N],sz[N];
   
9.    freopen("02quickunionin.txt","r",stdin);
   
10.    for (i=0; i < N; ++i)//初始化
    
11.    {
    
12.       id[i]=i;
    
13.       sz[i]=1;
    
14.    }
    
15.    while(scanf("%d %d",&p,&q)==2)
    
16.    {
    
17.       if(id[p]==id[q]) continue;
    
18.       count=0;
    
19.       for(i=p; i!=id[i]; i=id[i]);//找到i的最顶端,相当于下面所有的都接过去了
    
20.       for(j=q; j!=id[j]; j=id[j]);//找到j的最顶端,接到最顶端可以减少路径的长度
    
21.       if(i==j)
    
22.          continue;
    
23.       id[i]=j;//将i接到j的下面
    
24.       printf("\n%d-%d\n",p,q);
    
25.       for (i=0; i < N; ++i)
    
26.       {
    
27.          printf("%d ",id[i]);
    
28.       }
    
29.    }
    
30.    return 0;
    
31. }
    
32. /*
    
33. 0 2
    
34. 1 4
    
35. 2 5
    
36. 3 6
    
37. 0 4
    
38. 6 0
    
39. 1 3
40. */

1.6 weight quick union

1. //加权快速合并算法
   
2. #include "stdafx.h"
   
3. #include <stdio.h>
   
4. #define N 10
   
5. int _tmain(int argc, _TCHAR* argv[])
   
6. {
   
7.    int count,j;
   
8.    int i=0,p,q,id[N],sz[N];
   
9.    freopen("03weightquickunion.txt","r",stdin);
   
10.    for (i=0; i < N; ++i)//初始化
    
11.    {
    
12.       id[i]=i;
    
13.       sz[i]=1;
    
14.    }
    
15.    while(scanf("%d %d",&p,&q)==2)
    
16.    {
    
17.       if(id[p]==id[q]) continue;
    
18.       count=0;
    
19.       for(i=p; i!=id[i]; i=id[i])//找到根节点
    
20.          ;
    
21.       for(j=q; j!=id[j]; j=id[j])//找到根节点
    
22.          ;
    
23.       if(i==j)
    
24.          continue;
    
25.       if(sz[i]<sz[j])
    
26.       {
    
27.          id[i]=j;
    
28.          sz[j]+=sz[i];//更新树的节点数
    
29.       }
    
30.       else{
    
31.          id[j]=i;
    
32.          sz[i]+=sz[j];//更新树的节点数
    
33.       }
    
34.       printf("\n%d-%d\n",p,q);
    
35.       for (i=0; i < N; ++i)
    
36.       {
    
37.          printf("%d ",id[i]);
    
38.       }
    
39.    }
    
40.    return 0;
    
41. }

1.8 带有等分路径压缩的加权快速合并算法

1. //带有等分路径压缩的加权快速合并
   
2. #include "stdafx.h"
   
3. #include <stdio.h>
   
4. #define N 10
   
5. int _tmain(int argc, _TCHAR* argv[])
   
6. {
   
7.    int count,j;
   
8.    int i=0,p,q,id[N],sz[N];
   
9.    freopen("04pathcompress_weightquickunion.txt","r",stdin);
   
10.    for (i=0; i < N; ++i)//初始化
    
11.    {
    
12.       id[i]=i;
    
13.       sz[i]=1;
    
14.    }
    
15.    while(scanf("%d %d",&p,&q)==2)
    
16.    {
    
17.       if(id[p]==id[q]) continue;
    
18.       for(i=p; i!=id[i]; i=id[i])
    
19.          id[i]=id[id[i]];
    
20.       for(j=q; j!=id[j]; j=id[j])
    
21.          id[j]=id[id[j]];
    
22.       if(i==j)
    
23.          continue;
    
24.       if(sz[i]<sz[j])
    
25.       {
    
26.          id[i]=j;
    
27.          sz[j]+=sz[i];
    
28.       }
    
29.       else{
    
30.          id[j]=i;
    
31.          sz[i]+=sz[j];
    
32.       }
    
33.       printf("\n%d-%d\n",p,q);
    
34.       for (i=0; i < N; ++i)
    
35.       {
    
36.          printf("%d ",id[i]);
    
37.       }
    
38.    }
    
39.    return 0;
    
40. }

算法导论 第二版影印版
计算机网络第四版
GCC技术参考大全
4G移动通信技术权威指南