计算机科学论坛--06-DS 路径压缩

新书推介：《语义网技术体系》
作者：瞿裕忠，胡伟，程龚

XML论坛

W3CHINA.ORG讨论区

计算机科学论坛

SOAChina论坛

Blog

开放翻译计划

新浪微博

首页

软件下载

资料下载

核心成员

帮助

>> 研友的交流园地，讨论关于计算机考研的方方面面。

[返回] 计算机科学论坛 → 计算机理论与工程 → 『计算机考研交流』 → 06-DS 路径压缩

◇查看新帖 ◇ 用户列表 ◇

(订阅本版)

您是本帖的第 4071 个阅读者　　

*	贴子主题： 06-DS 路径压缩	举报打印推荐 IE收藏夹
	本主题类别:

海天飞鸿

  等级：大一新生
  文章：4
  积分：74
  门派：XML.ORG.CN
  注册：2006/4/4

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	楼主

06-DS 路径压缩

哪位大哥帮忙讲解一下06-DS 路径压缩的那道题.图是怎么画出来的,没见过这种题型呀!

收藏分享
顶(0)

2006/11/15 22:58:00

Supremgoooo

  等级：大四下学期(考上研究生啦!)
  文章：201
  积分：1872
  门派：XML.ORG.CN
  注册：2006/4/9

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第2楼

这个题没什么新的，就是考察一个小算法。看懂算法就会做题。
struct Node
{
    T value;
    Node*  p;
};
Node *Find_Parent_withCompression(Node *c)
{
      Node *parent;
      if(!c->p) parent=c;
      else {
               parent=Find_Parent_withCompression(c->p); //找
               c->p=parent; //压缩
      }
      return parent;
}
意思就是说沿着c的p路径一直找下去，直到找到不能走为止。返回这个最后找到的节点，让这条路上的所有节点的p都指向这个节点。

2006/11/16 17:50:00

GoogleAdSense

  等级：大一新生
  文章：1
  积分：50
  门派：无门无派
  院校：未填写
  注册：2007-01-01

	广告

2024/5/18 6:56:49

本主题贴数2，分页： [1]

管理选项：修改tag | 锁定 | 解锁 | 提升 | 删除 | 移动 | 固顶 | 总固顶 | 奖励 | 惩罚 | 发布公告


	W 3 C h i n a ( since 2003 ) 旗下站点苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》	42.969ms