新书推介：《语义网技术体系》
作者：瞿裕忠，胡伟，程龚
   XML论坛     W3CHINA.ORG讨论区     计算机科学论坛     SOAChina论坛     Blog     开放翻译计划     新浪微博  
 
  • 首页
  • 登录
  • 注册
  • 软件下载
  • 资料下载
  • 核心成员
  • 帮助
    		•   Add to Google

    >> 研友的交流园地，讨论关于计算机考研的方方面面。
    [返回] 计算机科学论坛 → 计算机理论与工程 → 『 计算机考研交流 』 → 请教DS课本上的两个问题 ◇查看新帖 ◇ 用户列表 ◇

      发表一个新主题  发表一个新投票  回复主题  (订阅本版) 您是本帖的第 3475 个阅读者浏览上一篇主题  刷新本主题   树形显示贴子　浏览下一篇主题
     * 贴子主题： 请教DS课本上的两个问题 举报  打印  推荐  IE收藏夹 
       本主题类别:     
     蝶影 美女呀，离线，快来找我吧！狮子座1985-8-1
      
      
      威望：1
      等级：大四(总算啃完XML规范了)
      文章：183
      积分：1291
      门派：IEEE.ORG.CN
      注册：2006/5/10

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给蝶影发送一个短消息 把蝶影加入好友 查看蝶影的个人资料 搜索蝶影在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给蝶影 引用回复这个贴子 回复这个贴子 查看蝶影的博客楼主
    发贴心情 请教DS课本上的两个问题

    DS课本P286 败者树初始化代码

    1)中间有三行个代码
    //计算s=2^log(n-1)
    int i,s;
    for(s=1;2*s<=n-1;s+=s);

    应该是s=2^(logn-1)吧?s应该代表次底层的结点个数吧?(n为选手数)

    2)if(n%2)
    {//n为奇数,内部结点和外部结点比赛
    //这里用L[LowExt+1]和它的父节点比赛
    //因为此时它的父结点中存放的是其兄弟结点处的比赛胜者索引
    Play(n/2,B[(n-1)/2],LowExt+1,winner,loser);
    i=LowExt+3;
    }
    请问怎么推出内部结点是B[(n-1)/2],父结点的下标是n/2?


       收藏   分享  
    顶(0)
      




    ----------------------------------------------
    不许偷懒~!

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2007/6/10 6:37:00
     
     virlinG 帅哥哟，离线，有人找我吗？
      
      
      等级：大一(猛啃高等数学)
      文章：26
      积分：188
      门派：IEEE.ORG.CN
      注册：2007/3/27

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给virlinG发送一个短消息 把virlinG加入好友 查看virlinG的个人资料 搜索virlinG在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看virlinG的博客第2楼
    发贴心情 
    s=2^log(n-1),s代表次底层第一个内部节点的编号，可由公式for(s=1;2*s<=n-1;s+=s)推出。

      内部结点B[(n-1)/2]的父结点的下标与n/2无关，这里不是求B[(n-1)/2]的父结点的下标，B[(n-1)/2]
      中存放了子节点的比赛胜者索引（字节点是最底层），而次底层中L[LowExt+1]的兄弟节点存放了相对
      与B[(n-1)/2]的比赛败者索引，因此Play(n/2,B[(n-1)/2],LowExt+1,winner,loser)中n/2为LowExt+1
      和n-1的父节点索引，即内部节点B[(n-1)/2]。

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2007/6/10 12:50:00
     
     蝶影 美女呀，离线，快来找我吧！狮子座1985-8-1
      
      
      威望：1
      等级：大四(总算啃完XML规范了)
      文章：183
      积分：1291
      门派：IEEE.ORG.CN
      注册：2006/5/10

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给蝶影发送一个短消息 把蝶影加入好友 查看蝶影的个人资料 搜索蝶影在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给蝶影 引用回复这个贴子 回复这个贴子 查看蝶影的博客第3楼
    发贴心情 
    还有两个问题:
    1.s=2^log(n-1),这个公式的log是以2为底的吧?那s=2^log(n-1)不就等于n-1了?
    2.也就是LowExt+1和它的父节点比赛,然后败者还存回LowExt+1的父节点里?那为什么不写成(n-1)/2,还非得写成n/2...

    ----------------------------------------------
    不许偷懒~!

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2007/6/10 19:33:00
     
     virlinG 帅哥哟，离线，有人找我吗？
      
      
      等级：大一(猛啃高等数学)
      文章：26
      积分：188
      门派：IEEE.ORG.CN
      注册：2007/3/27

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给virlinG发送一个短消息 把virlinG加入好友 查看virlinG的个人资料 搜索virlinG在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看virlinG的博客第4楼
    发贴心情 
    我大概说一下，可能不太准确，一直在看离散，DS还没开始
        1. s=2^log(n-1)在这里她默认先计算log(n-1)并取下整， 可能P282讲过，在这里的注释中省略了
       2.  Play(n/2,B[(n-1)/2],LowExt+1,winner,loser)中(n-1)/2和n/2结果是相同的，但逻辑上有区别，(n-1)/2：L[LowExt+1]兄弟节点的子节点中胜者存入L[LowExt+1]兄弟节点的父节点，左路的归并其父节点自然用L[LowExt+1]兄弟节点表示：(n-1)/2
                n/2：LowExt+1和它的父节点比赛，这时逻辑上用LowExt+1来表示其父节点比较合理。     
    写成n/2也可能是和Play((offset+i)/2,i-1,i,winner,loser)保持一致性（右子节点表示父节点）。。其实没必要，结果都一样
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2007/6/10 23:31:00
     
     蝶影 美女呀，离线，快来找我吧！狮子座1985-8-1
      
      
      威望：1
      等级：大四(总算啃完XML规范了)
      文章：183
      积分：1291
      门派：IEEE.ORG.CN
      注册：2006/5/10

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给蝶影发送一个短消息 把蝶影加入好友 查看蝶影的个人资料 搜索蝶影在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给蝶影 引用回复这个贴子 回复这个贴子 查看蝶影的博客第5楼
    发贴心情 
    恩,这样说,明白很多,谢谢~

    ----------------------------------------------
    不许偷懒~!

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2007/6/11 16:29:00
     
     GoogleAdSense狮子座1985-8-1
      
      
      等级：大一新生
      文章：1
      积分：50
      门派：无门无派
      院校：未填写
      注册：2007-01-01
    给Google AdSense发送一个短消息 把Google AdSense加入好友 查看Google AdSense的个人资料 搜索Google AdSense在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给Google AdSense 访问Google AdSense的主页 引用回复这个贴子 回复这个贴子 查看Google AdSense的博客广告
    2024/6/15 21:30:18

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

    管理选项： 修改tag | 锁定 | 解锁 | 提升 | 删除 | 移动 | 固顶 | 总固顶 | 奖励 | 惩罚 | 发布公告
    W3C Contributing Supporter! W 3 C h i n a ( since 2003 ) 旗 下 站 点
    苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
    		 78.125ms