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

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