| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 978 人关注过本帖
标题:完全路径压缩
只看楼主 加入收藏
zy_space
Rank: 5Rank: 5
等 级:职业侠客
帖 子:163
专家分:364
注 册:2011-11-14
结帖率:100%
收藏
已结贴  问题点数:5 回复次数:6 
完全路径压缩
书上给的例子是等分路径压缩

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]];                          //同上

要求自己领悟写出完全路径压缩,自己研究了一下写了一个:

for (i = p; i != id[i]; i = id[i]) {
   for (t = i; t != id[t]; t = id[t])
      ;
   id[i] = t;                                 //增设标记变量t,在循环开始给其赋以i的初值,通过循环使t由当前位置遍历至当前树的顶端,最后把值传递到id[i]中存储
}
for (j = q; j != id[j]; j = id[j]) {
   for (t = j; t != id[t]; t = id[t])
      ;
   id[j] = t;                                 //同上
}

不知道对不对,有劳各位大虾指点
搜索更多相关主题的帖子: 压缩 
2011-11-24 09:03
zy_space
Rank: 5Rank: 5
等 级:职业侠客
帖 子:163
专家分:364
注 册:2011-11-14
收藏
得分:0 
表情好像不太对。。。。

何必等待?梦在今朝
2011-11-24 09:04
laoyang103
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:内蒙古包头
等 级:贵宾
威 望:19
帖 子:3082
专家分:11056
注 册:2010-5-22
收藏
得分:2 
矩阵压缩存储?

                                         
===========深入<----------------->浅出============
2011-11-24 10:21
zy_space
Rank: 5Rank: 5
等 级:职业侠客
帖 子:163
专家分:364
注 册:2011-11-14
收藏
得分:0 
回复 3楼 laoyang103
呃不是,是刚开始学习算法的连通问题的改进算法

何必等待?梦在今朝
2011-11-24 10:41
id3663423
Rank: 2
来 自:浙江
等 级:论坛游民
帖 子:48
专家分:63
注 册:2009-4-15
收藏
得分:2 
没看明白

每多学一点知识,就少写一行代码.
2011-11-24 10:45
zy_space
Rank: 5Rank: 5
等 级:职业侠客
帖 子:163
专家分:364
注 册:2011-11-14
收藏
得分:0 
那我把其余不重要的代码部分补全吧==

#include<stdio.h>

#define     N   10000

int main(void)
{
   int   i, j, p, q, sz[N], id[N];

   for (i = 0; i < N; i++){
      id[i] = i;
      sz[i] = 1;
   }
   while (scanf("%d %d\n", &p, &q) == 2){
      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("%d %d\n", p, q);
   }
   return 0;
}

---------------------------------------------------------

等分路径压缩的加权快速合并算法

何必等待?梦在今朝
2011-11-24 11:37
zy_space
Rank: 5Rank: 5
等 级:职业侠客
帖 子:163
专家分:364
注 册:2011-11-14
收藏
得分:0 
求大侠指点算法分析。。。。。PS:为什么说我这是送分贴还扣我分。。。。

何必等待?梦在今朝
2011-11-24 22:46
快速回复:完全路径压缩
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.015202 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved