algorithm in c 习题 第一章-凯发app官方网站

凯发app官方网站-凯发k8官网下载客户端中心 | | 凯发app官方网站-凯发k8官网下载客户端中心

熟睡的企鹅

凯发app官方网站首页　| 　　| 　

zhln

  • 博客访问： 1540405
  • 博文数量： 327
  • 博客积分： 10000
  • 博客等级： 上将
  • 技术积分： 3556
  • 用 户 组： 普通用户
  • 注册时间： 2005-04-05 21:28
个人简介

东黑布衣，流浪幽燕。 真诚善良，值得信赖。

文章分类

（327）

  • （42）
  • （13）
  • （30）
  • （16）
  • （14）
  • （17）
  • （4）
  • （34）
  • （36）
  • （9）
  • （24）
  • （2）
  • （3）
  • （7）
  • （1）
  • （3）
  • （2）
  • （0）
  • （7）
  • （39）
  • （6）
  • （1）
  • （11）
  • （6）
我的朋友
推荐博文
相关博文
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
algorithm in c 习题 第一章

分类： bsd

2017-06-09 11:26:09

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移动通信技术权威指南

阅读(1757) | 评论(0) | 转发(0) |
0

上一篇：

下一篇：

给主人留下些什么吧！~~
| | | | |

凯发app官方网站 copyright 2001-2010 chinaunix.net all rights reserved 北京皓辰网域网络信息技术有限公司. 凯发k8官网下载客户端中心的版权所有

感谢所有关心和支持过chinaunix的朋友们
")); function link(t){ var href= $(t).attr('href'); href ="?url=" encodeuricomponent(location.href); $(t).attr('href',href); //setcookie("returnouturl", location.href, 60, "/"); }
网站地图