基础入门：并查集ufset类_c语言教程_c++教程_c语言培训_c++教程培训.txt

基础入门：并查集UFSet类_C语言教程_C++教程_C语言培训_C++教程培训 基础入门：并查集UFSet类_C语言教程_C++教程_C语言培训_C++教程培训

基础入门：并查集UFSet类_C语言教程_C++教程_C语言培训_C++教程培训_C/C++频道_中国IT实验室 首页 | 互联网 | IT动态 | IT培训 
| Cisco | Windows | Linux | Java | .Net | Oracle | 软件测试 | C/C++ | 嵌入式开发 | 存储世界 | 
服务器 
网络设备 | IDC | 安全 | 求职招聘 | 数字网校 | 网页设计 | 平面设计 | 技术专题 | 电子书下载 | 教学视频 | 源码下载 | 搜索 | 
博客 | 论坛   输入您的搜索字词  提交搜索表单           


            首页资讯动态C语言C++编程C∕C++开发应用VC++C++Builder专题下载博客论坛

您现在的位置： 中国IT实验室 >> C∕C＋＋频道 >> C语言 >> 基础入门 >> 正文 基础入门：并查集UFSet类 10大城市2万个热门IT职位 
注册有奖
JAVAV工程师权威认证
广州中星报MCSE送CCNA3600元 上海英孚教育急聘
系统管理员　初级程序员　软件开发工程师
数据库工程师 高级项目经理 界面设计经理 中国IT实验室收集整理 佚名 2008-12-26 保存本文 推荐给好友 收藏本页 
欢迎进入C/C++编程社区论坛，与200万技术人员互动交流 >>进入
    /* Name： 并查集UFSet类Copyright： 始发于goal00001111的专栏；允许自由转载，但必须注明作者和出处Author： 
goal00001111 Date： 23-12-08 15：21 Description： 
实现了普通的查找和合并的算法，也实现了压缩路径和按大小求并高效算法，并对两者进行了测试比较。
    
有关算法的分析讨论详见拙作《一种简单而有趣的数据结构——并查集》：http://blog.csdn.net/goal00001111/archive/2008/12/24/3595844.aspx 
       */
      #include <iostream>
      #include <time.h>
      using namespace std;
      const int MAX = 50000; //集合的最大成员数量
      class UFSet{ //并查集类
      public:
      UFSet(int s = MAX); //构造函数
      UFSet(const UFSet & obj); //拷贝构造函数
      ~UFSet() //析构函数
      {
      delete []father;
      }
      UFSet & operator = (const UFSet & obj); //赋值函数
      int FindFather(int pos); //寻找序号pos的族长大人
      bool Unite(int posI, int posJ);//将成员posI和posJ合并到同一个家族
      int FindFatherAndReducePath(int pos); //查找族长并压缩路径
      bool UnionBySize (int posI, int posJ); //按大小求并
      bool SameFamily(int posI, int posJ); //判断成员posI和posJ是否属于同一家族
      void PrintUFSet();
      private:
      int *father; //并查集成员数组，存放各元素的父亲结点
      int size; //并查集成员数量
      };
      UFSet::UFSet(int s) : size(s) //构造函数
      {
      father = new int[size + 1];
      for (int i=0; i<=size; i++) //所有的数组元素值均初始化为-1
      father[i] = -1;
      }
      UFSet::UFSet(const UFSet & obj) //拷贝构造函数
      {
      size = obj.size;
      father = new int[size + 1];
      for (int i=0; i<=size; i++)
      father[i] = obj.father[i];
      }

      UFSet & UFSet::operator = (const UFSet & obj) //赋值函数
      {
      if (this == &obj) //检查自赋值
      return *this;
      delete []father; //释放原有的内存资源
      size = obj.size; //分配新的内存资源，并复制内容
      father = new int[size + 1];
      for (int i=0; i<=size; i++)
      father[i] = obj.father[i];
      return *this; //返回本对象的引用
      }
      int UFSet::FindFather(int pos)//寻找序号pos的族长大人。若pos本身是族长，则返回自身
      {
      if (father[pos] < 0)
      return pos;
      return FindFather(father[pos]);
      }
      bool UFSet::Unite(int posI, int posJ)//将成员posI和posJ合并到同一个家族
      {
      //首先各自去寻找自己的族长
      int fI = FindFather(posI);
      int fJ = FindFather(posJ);
      if (fI == fJ) //如果是同一个族长门下，不必合并，即合并失败
      return false;
      else
      father[fJ] = fI; //否则fI当族长：谁让posI站在posJ的前面呢！
      return true;
      }
      int UFSet::FindFatherAndReducePath(int pos)//查找族长并压缩路径
      {
      if (father[pos] < 0)
      return pos;
      //若自己不是族长，则找到族长后，将所途经的结点均指向族长
      return father[pos] = FindFatherAndReducePath(father[pos]);
      }
      bool UFSet::UnionBySize(int posI, int posJ)//按大小求并
      {
      //首先各自去寻找自己的族长
      int fI = FindFatherAndReducePath(posI);
      int fJ = FindFatherAndReducePath(posJ);
      if (fI == fJ) //如果是同一个族长门下，不必合并，即合并失败
      return false;
      else if (father[fI] < father[fJ])
      {//如果族长fI的实力比fJ强，即|fI|>|fJ|，则fI当族长，并修改father[fI]和father[fJ]
      father[fI] += father[fJ];
      father[fJ] = fI;
      }
      else //否则fJ当族长
      {
      father[fJ] += father[fI];
      father[fI] = fJ;
      }
      return true;
      }
      bool UFSet::SameFamily(int posI, int posJ)//判断成员posI和posJ是否属于同一家族
      {
      return FindFatherAndReducePath(posI) == FindFatherAndReducePath(posJ);
      }
      void UFSet::PrintUFSet()//输出集合的所有元素
      {
      for (int i=0; i<=size; i++)
      cout << father[i] << ' ';
      cout << endl;
      }
      int main()
      {
      time_t startTime, endTime;
      UFSet obj;
      int p, q;
      time(&startTime);
      for (int i=0; i<MAX; i++)
      {
      p = rand() % MAX + 1;
      q = rand() % MAX + 1;
      if (p == q)
      continue;
      //cout << p << "-" << q << " ";
      // if (i % 10 == 0)
      // cout << endl;
      obj.Unite(p, q);
      }
      while (1)
      {
      p = rand() % MAX + 1;
      q = rand() % MAX + 1;
      if (p == q)
      continue;
      if (obj.SameFamily(p, q))
      cout << endl << p << "≡" << q << endl;
      else
      cout << endl << p << "!≡" << q << endl;
      break;
      }
      time(&endTime);
      cout << difftime(endTime, startTime) << endl;
      //////////////////////////////////////////////////////////////////////////
      time(&startTime);
      for (int i=0; i<MAX; i++)
      {
      p = rand() % MAX + 1;
      q = rand() % MAX + 1;
      if (p == q)
      continue;
      //cout << p << "-" << q << " ";
      // if (i % 10 == 0)
      // cout << endl;
      obj.UnionBySize(p, q);
      }
      while (1)
      {
      p = rand() % MAX + 1;
      q = rand() % MAX + 1;
      if (p == q)
      continue;
      if (obj.SameFamily(p, q))
      cout << endl << p << "≡" << q << endl;
      else
      cout << endl << p << "!≡" << q << endl;
      break;
      }
      time(&endTime);
      cout << difftime(endTime, startTime) << endl;
      system("pause");
      return 0;
      }

【责编:ben】


相关文章 动态内存管理是C++重要的特性
基础入门：const修饰常量
编写最有代表意义的qt程序
C编写Windows服务程序详细介绍
编写一个桌面闹钟源程序
用C语言实现按钮新技术
C++中堆和栈的基础学习
基础入门：C++中const的使用方法
C++函数模板基础学习
宏定义中的do...while(0)的使用
编辑推荐 · [ASP．NET].NET程序员新方向 Ruby核心语法入门
· [ASP．NET]基于ASP.NET MVC框架开发Web论坛应用程序
· [ASP．NET]利用UrlRewrite，asp.net动态生成htm页面
· [．NET Framework]DotNet for Symbian平台
· [ASP．NET]WCF 关于自定义MessageHeader支持
· [ASP．NET]如何定制页面提示信息（tooltips）
· [ASP．NET]对IOC和DI的理解
· [ASP．NET]主动编程与被动编程！
· [ASP．NET]发布一个锁定行列的一种方法
· [ASP．NET]使用配置文件构建和使用WCF服务
相关产品和培训 文章评论 　友情推荐链接·华硕网络交换机
·金浪网络交换机
·联想交换机报价
·联想交换机价格
·lenovo交换机
·IDC资讯大全
·机房品质万里行
·IDC托管必备知识
·网站推广优化
·全国IDC报价
　认证培训 · Linux进入紧缺人才培训体系
· 深圳CIW470培训＋考试3000元
· No.1高薪热门职业【网络系统集成】
· 全能网管思科微软黄金组合
· “紧缺人才培养计划”上海地区启动
· [上海]交大慧谷CCNP培训特价3990元
　专题推荐 
　·Oracle数据库11g 面向DBA和开发人员的重要新特性…
　·桌面应用软件编程 J2SE技术详解…
　·我“炫”我精彩-------WPF开发教程
　·Oracle数据库备份与恢复之六大总结
　·JAVA的应用编程接口——JAVA API详解…
　·Linux Shell学习技术专题[上]…
　·WEB开发——ASP.NET和PHP、JSP究竟学哪个
　·五步带你入门ＸＭＬ
　·关于Java框架技术专题
　·XML全攻略技术专题
　今日更新 · 基础入门：并查集UFSet类
· C++数值类型转换方法 心得…
· 自己的不定参数函数的实现方法
· C++图象的渐显/渐隐 实现方法…
· 间接修改指针的地址技巧
· 批量html转text的实现方法
· VC++5.0定制窗口的方法
· C++编程时避免产生临时(隐式)对象
· 编程技巧：删除指定进程代码
· 不使用中间变量快速插入字符串
　社区讨论 　博客论点 　频道精选 · 新版CCNA考试大纲 07年8月1日生效
· 新手学习宝典：Linux常用命令全集
· 知已知彼，深入了解系统安全知识
· 从入门到精通 java初学者实践系列教程
· 共同学习——Oracle入门基础专题
· ADO.net与PowerBuilder的综合比较
· 评论：中国互联网“钱”途何在？
· 中科院：龙芯要成"中国奔腾" 能卖1亿颗
　C/C++频道相关导航 C语言： 
基础入门 | 编程技巧 | 实例编程
C++编程： 
基础入门 | 实例编程 |编程技巧
C++开发应用： 
多媒体开发 | 游戏开发 | 数据库开发 | 网络通信 
组件编程 | 系统应用 | 界面开发
资讯动态:
VC++:
C++Builder:
27