子,此时取出队列的第一个元素(即先前保存的x),将其Ⅲink指向y即可 6.课后练习和实习 将书本上的理论知识与最前沿的技术知识融为一体,设计验证型、探索型、应用型的 实习题和上机题,帮助同学更好的理解书本上的基本原理,锻炼学生的思维能力、实践能力。 树这一章可以安排7-9道书面作业,1-2道综合上机实习题。安排一次习题讲评 例如:实现并查集方面的考察。 使用重量权衡合并规则与路径压缩,对下列从0到15之间的数的等价对进行归并,并 给出所得树的父指针表示法的数组表示。在初始情况下,集合中的每个元素分别在独立的等 价类中。当两棵树规模同样大时,使结点值较大的根结点作为值较小的根结点的子结点。 (0,2)(1,2)(3,4)(3,1)(3,5)(9,11)(12,14)(3,9) 4,14)(6,7)(8,10)(8,7)(7,0)(10,15)(10,13) 7.教学案例 划分等价类需要对集合进行三种操作 (1)构造只含有一个元素的集合 (2)判定某个元素所在的子集,目的是为了确定两个元素是否在同一个集合之中。即搜 索包含该元素的等价类,对于同一个集合中的元素返回相同的结果,否则返回不同的结果; (3)归并两个不相交的集合为一个集合 用父指针表示的树形结构实现的并査集可以很容易地解决等价类问题。约定森林F T,T2,…,T}表示集合S,森林中的每一棵树T表示集合S的一个子集,树中的结点表 示集合S中的一个元素。树中的每一个非根结点都指向其父结点,用根结点作为集合的标 识符。 (a) 集合的表示方法4 子，此时取出队列的第一个元素(即先前保存的 x)，将其 llink 指向 y 即可。 6．课后练习和实习 将书本上的理论知识与最前沿的技术知识融为一体，设计验证型、探索型、应用型的 实习题和上机题，帮助同学更好的理解书本上的基本原理，锻炼学生的思维能力、实践能力。 树这一章可以安排 7-9 道书面作业，1-2 道综合上机实习题。安排一次习题讲评。 例如：实现并查集方面的考察。 使用重量权衡合并规则与路径压缩，对下列从 0 到 15 之间的数的等价对进行归并，并 给出所得树的父指针表示法的数组表示。在初始情况下，集合中的每个元素分别在独立的等 价类中。当两棵树规模同样大时，使结点值较大的根结点作为值较小的根结点的子结点。 (0，2) (1，2) (3，4) (3，1) (3，5) (9，11) (12，14) (3，9) (4，14) (6，7) (8，10) (8，7) (7，0) (10，15) (10，13) 7．教学案例 划分等价类需要对集合进行三种操作： (1) 构造只含有一个元素的集合； (2) 判定某个元素所在的子集，目的是为了确定两个元素是否在同一个集合之中。即搜 索包含该元素的等价类，对于同一个集合中的元素返回相同的结果，否则返回不同的结果； (3) 归并两个不相交的集合为一个集合。 用父指针表示的树形结构实现的并查集可以很容易地解决等价类问题。约定森林 F = {T1，T2，„，Tr}表示集合 S，森林中的每一棵树 Ti表示集合 S 的一个子集，树中的结点表 示集合 S 中的一个元素。树中的每一个非根结点都指向其父结点，用根结点作为集合的标 识符。 1 3 5 7 2 4 6 2 1 4 6 3 5 7 (a) (b) (c) S1 S2 S3 8 8 集合的表示方法