计算机科学论坛--请教一个ds问题和一个os问题

贴子主题：请教一个ds问题和一个os问题

本主题类别:

DS那道:
先讲一下单独使用重量权衡合并规则进行归并:
算法:对于(i,j),先使用Find函数(非路径压缩)找到i和j的根结点(注意,是根结点,不是父结点),然后再根据规则,这里是将结点值较大的根结点作为结点值较小的根结点的子结点，进行处理
再看具体的步骤：
X：Y1，Y2。。。X代表根结点，Y1，Y2是子结点
（0，2）：0的根结点是0，2的根结点是2，0<2，所以将0设置为2的父结点，此时0：2
（1，2）：2的根结点是0，1的根结点是1，0小于1，所以将1的父结点设置成0，此时是0：2，1
（3，4）：3小于4，所以将3设置成4的父结点，3：4
（3，1）：3的根结点是3，1的根结点是0，所以就将0设置成3的根结点，此时是0：2，1，（3：4）
（3，5）：3的根结点是0，5的根结点是5，所以将5的根结点设置成0，此时是0：2，1，（3：4），5
（9，11）：9的根结点是9，11的根结点是11，9小于11，有9：11
（12，14）：同（9，11），有12：14
（3，9）：3的根结点是0，9的根结点是9，0小于9，所以将9的父结点设置成0，有0：2，1，（3：4），5，（9：11）
（4，14）：4的根结点是0，14的根结点是12，所以将12的父结点设置成0，有0：2，1，（3：4），5，（9：11），（12：14）
（6，7）：同（9，11），有6：7
（8，10）：同（9，11），有8：10
（8，7）：8的根结点是8，7的根结点是6，所以有6：7，（8：10）
（7，0）：7的根结点是0，有0：2，1，（3：4），5，（9：11），（12：14），（6：7，（8：10））
（10，15）：10的根结点是0，所以有0：2，1，（3：4），5，（9：11），（12：14），（6：7，（8：10）），15
（10，13）：同（10，15），此时有0：2，1，（3：4），5，（9：11），（12：14），（6：7，（8：10）），15，13
这样就出了第一个图
我得上自习了，带路径压缩的那个的细节没时间讲了（或者晚上），课本算法5.9上面是关于这个算法的说明，仔细理解一下，然后你就按上面那样一个一个地拿来看，把算法走一次，就明白了~


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