|
以文本方式查看主题 - 中文XML论坛 - 专业的XML技术讨论区 (http://bbs.xml.org.cn/index.asp) -- 『 计算机考研交流 』 (http://bbs.xml.org.cn/list.asp?boardid=67) ---- 关于课本堆代码的一个问题 (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=54873) |
|
-- 作者：shun -- 发布时间：11/4/2007 9:16:00 PM -- 关于课本堆代码的一个问题 remove函数(121页) //删除给定下标的元素 remove(int pos, T& mode) { if((pos<0)||(pos>=currentsize)) return false; T temp = heapArray[pos]; heapArray[pos] = heapArray[--currentsize]; SiftUp(pos); SiftDown(pos); node = temp; return true; } 问：在最小堆中，这段函数中的SiftUp(pos)是不是没起到作用呀？？ |
|
-- 作者：lionx -- 发布时间：11/4/2007 9:47:00 PM -- 不是。其实这里的siftup和siftdown只有一个起到作用。但不知道是哪个，所以都用。如果堆的内容是1,100,80,150,300,210,85(按照完全二叉树的结构)，那么删除150的时候，85替换150的位置，故需要siftup |
|
-- 作者：shun -- 发布时间：11/5/2007 8:48:00 AM -- o这样，thank u |
|
-- 作者：hanshumin -- 发布时间：11/11/2007 11:03:00 PM -- 我感觉应该分类讨论一下。因为待删除的结点要与最后一个结点交换。当交换后，待删除的结点所在的位置的值是最后一个结点值的大小，此时它有可能比先前删除的结点小，大或者相等。如果相等，就不用作什么工作，如果小的话，只需要SIFT UP（），如果大的话，只需要SIFT DOWN（）.大家认为呢？ |
|
-- 作者：buddha -- 发布时间：11/13/2007 12:39:00 PM -- 没有必要吧,要讨论反而增加判断时所需要的开销.并没有对算法在时间上起到化简. 再者,其实在这里.siftup和siftdown执行其一且只能执行其一,所以说,程序本身就能起到判断的作用了。我们又何必要再去画蛇添足呢... |
|
-- 作者：fgffggfg -- 发布时间：11/13/2007 2:55:00 PM -- 欲知详情如何，请看授课录象呵呵~ |
|
-- 作者：lionx -- 发布时间：11/14/2007 11:27:00 AM -- 可能是出于低藕合的考虑吧…… |
|
-- 作者：buddha -- 发布时间：11/14/2007 12:39:00 PM -- 呵呵，看来是想错了。 加判断后会有一种情况不执行.引入了多余的操作的同时也能减少一些操作. mzhang的授课录象上的话好象是,可以加上判断条件,这样可以提高程序的可读性.. |
|
W 3 C h i n a ( since 2003 ) 旗 下 站 点 苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》 |
62.500ms |