主题:初学者求一算法,望高手帮忙~!
shanshangnu35
[专家分:0] 发布于 2006-10-15 19:02:00
算法求A,B两个单链表表示的集合的交集,并集,差集
回复列表 (共2个回复)
沙发
realcrane [专家分:190] 发布于 2006-10-16 17:44:00
没什么好办法,只能遍历比较了。如果可能的话,先排序,这样会简单一些。
板凳
liyu355 [专家分:980] 发布于 2006-10-16 18:05:00
虽然没什么好的算法
但是遍历倒也没有必要
简单的举个例子:
比如要求两个单链表的交集,那么可以这样啊,第一个单链表排序,从小排到大。
而第二个单链表恩,既可以排序,也可以用为二叉排序树的形式。
如果第二个为单链表,那么可以将他也按从小到大排列,在找交集的时候,那么从第一个开始找,如果找到某一个数比第一个单链表的数要大了,那么很显然,该数的交集就不存在了,如此循环。
如果第二单链表如果是作为排序树存在的话,那么就更简单了,直接查找撒。如此也要快很多,不过排序树是比较难实现的,而且更加重要的是,他的增加和删除非常的麻烦。所以,具体的算法的实现,视具体的环境和要求而定了
我来回复