算法导论中的不相交集合的链表实现

不相交集合上的操作 算法导论中有提到不相交集合的两个重要操作,即找出给定的元素所属的集合和合并两个集合。我们首先要清楚,什么是不相交集合?顾名思义,就是集合上,没有相交的元素,交叉集为空集。这个时候,每个集合需要一个代表来识别,代表即集合中的某个成员,集合中的每个成员的代表都是相同的。然后判断某两个成员是否在同一个集合中,只需要判断代表是否相等就可以了。 ...

经典的单链表逆转

单链表的逆转,有递归与非递归两种实现方式。 非递归的实现中,主要就是不断的移动新链表头,然后让新链表头的next指向上一个新链表头。 递归中,我们控制新的链表头的不断变化,然后让旧链表头的next一直指向下一个新链表的头部。 完整代码如下: ...

排序算法系列 - 合并排序

    合并排序是使用分治模式的一个实现实例。分治模式在每一层递归上都有三个步骤:  分解(Divide) : 将原问题分解成一系列子问题 解决(Conquer) : 递归地解决各子问题。若子问题足够小,则可以结束递归动作 ...