首页 > 其他 > 详细

第一章连通性问题-----algorithm in C 读书笔记

时间：2017-01-25 01:02:08      阅读：259      评论：0      收藏：0      [点我收藏+]

首先不得不吐槽一下翻译的质量，霍红卫。。。。你给我站出来，不打死你，只想问你一下，你当年四级过了吗？

  1. 问题描述  
  2.    输入两个整数，代表两个节点，如果这两个整数没有建立连接（这包括直接连接和通过其他节点连接），那么我们就建立这两个节点之间的连接，否则，继续输入下一个节点  
 

四个逐步改进的算法如下：

  1. //算法一  
  2. #include <stdio.h>  
  3.   
  4. #define N 10  
  5.   
  6. int main(void)  
  7. {  
  8.     int id[N];  
  9.     int t,i,p,q;  
  10.   
  11.     //一定要初始化啊  
  12.     for(i=0;i<N;i++)  
  13.     {  
  14.         id[i] = i;  
  15.     }  
  16.   
  17.     while( scanf("%d%d",&p,&q)==2 )  
  18.     {  
  19.         if( id[p]==id[q] )  
  20.             continue;  
  21.         t = id[p];  
  22.         for(i=0;i<N;i++)  
  23.         {  
  24.             if( id[i]==t )  
  25.             {  
  26.                 id[i] = id[q];  
  27.             }  
  28.         }  
  29.   
  30.         for(i=0;i<N;i++)  
  31.         {  
  32.             printf("%d\t",id[i]);  
  33.         }  
  34.         printf("\n");  
  35.     }  
  36.   
  37.     return 0;  
  38. }  

 

     这四个算法所使用的数据结构都是数组，算法一是把连接（包括直接连接和间接连接）在一起的整数所对应的数组元素都赋值为相同的值。

 

 
  1. //算法二  
  2. #include <stdio.h>  
  3.   
  4. #define N 10  
  5.   
  6. int main(void)  
  7. {  
  8.     int id[N];  
  9.     int i,j,p,q;  
  10.   
  11.     for(i=0;i<N;i++)  
  12.     {  
  13.         id[i] = i;  
  14.     }  
  15.   
  16.     while( scanf("%d%d",&p,&q)==2 )  
  17.     {  
  18.         //必须使用下面两次循环，否则当心陷入死循环  
  19.         for(i=p;id[i]!=i;i=id[i]);  
  20.         for(j=q;id[j]!=j;j=id[j]);  
  21.   
  22.         if( i==j )  
  23.             continue;  
  24.         id[i] = j;  
  25.   
  26.         for(i=0;i<N;i++)  
  27.         {  
  28.             printf("%d\t",id[i]);  
  29.         }  
  30.         printf("\n");  
  31.     }  
  32.   
  33.     return 0;  
  34. }  

 

     算法二采用的数据结构仍然是数组，但是逻辑上确实树的结构。我们首先根据输入的两个整数，分别找到其所在的树的根节点，然后检测两个节点所在的树的根节点是否相同，如果相同，就说明是同一棵树，否则就把这两个根节点连接起来。

 

  1. //算法三  
  2. #include <stdio.h>  
  3.   
  4. #define N 10  
  5.   
  6. int main(void)  
  7. {  
  8.     int id[N],sz[N];  
  9.     int p,q,i,j;  
  10.   
  11.     for(i=0;i<N;i++)  
  12.     {  
  13.         id[i] = i;  
  14.         sz[i] = 1;  
  15.     }     
  16.   
  17.     while( scanf("%d%d",&p,&q)==2 )  
  18.     {  
  19.         for(i=p;id[i]!=i;i=id[i]);  
  20.         for(j=q;id[j]!=j;j=id[j]);  
  21.         if( sz[i]<sz[j] )  
  22.         {  
  23.             id[i] = j;  
  24.             sz[j] += sz[i];  
  25.         }  
  26.         else  
  27.         {  
  28.             id[j] = i;  
  29.             sz[i] += sz[j];  
  30.         }  
  31.           
  32.         printf("i=%d\nj=%d\n",i,j);  
  33.   
  34.         for(i=0;i<N;i++)  
  35.         {  
  36.             printf("%d\t",sz[i]);  
  37.         }  
  38.         printf("\n");  
  39.           
  40.         for(i=0;i<N;i++)  
  41.         {  
  42.             printf("%d\t",id[i]);  
  43.         }  
  44.         printf("\n");  
  45.     }  
  46.   
  47.     return 0;  
  48. }     

 

     算法三是在算法二的基础之上改进而来的，但是它添加了一个数据结构，记录以每个节点为根的树中的元素的个数。通过这个数据结构，每次都把小树连接到大树上，防止树的深度过深。

 

  1. //算法四  
  2. #include <stdio.h>  
  3.   
  4. #define N 10  
  5.   
  6. int main(void)  
  7. {  
  8.     int id[N];  
  9.     int sz[N];  
  10.     int p,q,i,j;  
  11.   
  12.     //初始化  
  13.     for(i=0;i<N;i++)  
  14.     {  
  15.         id[i] = i;  
  16.         sz[i] = 1;  
  17.     }  
  18.   
  19.     while( scanf("%d%d",&p,&q)==2 )  
  20.     {  
  21.         for(i=p;id[i]!=i;i=id[i])  
  22.         {  
  23.             id[i] = id[id[i]];  
  24.         }  
  25.         for(j=q;id[j]!=j;j=id[j])  
  26.         {  
  27.             id[j] = id[id[j]];  
  28.         }  
  29.   
  30.         if( sz[i]<sz[j] )  
  31.         {  
  32.             id[i] = j;  
  33.             sz[j] += sz[i];  
  34.         }   
  35.         else  
  36.         {  
  37.             id[j] = i;  
  38.             sz[i] += sz[j];  
  39.         }  
  40.   
  41.         printf("i=%d\nj=%d\n",i,j);  
  42.   
  43.         for(i=0;i<N;i++)  
  44.         {  
  45.             printf("%d\t",sz[i]);  
  46.         }  
  47.         printf("\n");  
  48.   
  49.         for(i=0;i<N;i++)  
  50.         {  
  51.             printf("%d\t",id[i]);  
  52.         }  
  53.         printf("\n");  
  54.     }  
  55.   
  56.     return 0;  
  57. }  


     算法四就是在算法三的基础之上又做了进一步的改进，将树的深度进一步的缩小。

 

    

第一章连通性问题-----algorithm in C 读书笔记

原文：http://www.cnblogs.com/guohaoyu110/p/6347866.html
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！