如何求两个集合的交集？

我的labview程序中需要计算两个array中元素的交集，有现成的子程序吗？没有该如何实现？多谢！

飞雨天

所谓算法，就是把你的思想用程序表达出来，或者，算法就是思想~

比如求两个集合的交集，那么，你可以这样来做：
假设集合A，B
取集合a的第一个元素a1，在集合b里看看，有没和它（a1）相等的（这里需要假设在一个集合内部，元素互相是不同的），如果有，记录该元素，然后取集合a的第二个元素a2... ...

算法也需要讲究效率，真正的解决这个具体问题的算法，应该不是我说的这样的（因为它太低效了），不过如果就我这个方法而言，有如下的讨论：

假设集合A的元素个数是n，集合B的元素个数是m，交集元素个数是h，并且假设m<n
则最大可能比较次数为m+(m-1)+...+(m-h+1)=(2m+1-h)/2

现在以集合B的元素作为索引来到集合A中寻找匹配（A、B集合角色对调）
则最大可能比较次数为（2n+1-h）/2

明显不如第一种效率高，做个程序测试下？

                             

运行test_main.vi，可以看到，两者耗时相差之大！如果在后面板上把大数组的元素增加（就是for循环的200改为1000，比如说），那么，可以看到，其中一个，耗时几乎曾线性增加，而另外一个几乎没什么变化~~~~

当然了，真正的算法不可能像我写的这么笨的，以上的程序，只是一个简单的演示，用来说明算法效率的重要性而已~~~~

[ 本帖最后由 飞雨天 于 2007-12-26 15:01 编辑 ]

西门吹水

我做了个交集的程序，使用了两个while循环，我觉得程序还有很多不足的地方，就算法我也说不出什么来，感觉就是减少程序的计算次数就好了。原本是使用for来做，可是发现会将相同的元素都插入到交集的结果中，导致重复出现。飞雨天的程序还没拜读，我的是7.1的打不开，请飞雨天指点点。

西门吹水

程序经过一段时间修改，我师妹提出更简单的办法，先把图片截取效果如下，计算复杂度减少了

飞雨天

呵呵，我瞎写的，这里无法保存7.1的，我截图好了~~~

这个是主程序后面板：
   


这个是子程序后面板：



[ 本帖最后由 飞雨天 于 2007-12-26 17:50 编辑 ]

gzw371

帮你改了一下