首页 > Erlang并发教程 > 4.5 Erlang并发编程-集合
2013
11-06

4.5 Erlang并发编程-集合

BACK TOP文章索引

  1. 集合
  2. 共0条评论

集合

程序3.2是一组简单的集合操作函数。在Erlang中表示集合的最直白的方法就是采用一个不包含重复元素的无序列表。

集合操作函数如下:

new()

返回一个空集合。

add_element(X, S)

返回将元素X并入集合S 产生的新集合。

del_element(X, S)

返回从集合S中删去元素X的新集合。

is_element(X, S)

当元素X在集合S中时返回true,否则返回false

is_empty(S)

当集合S为空集时返回true,否则返回false

union(S1, S2)

返回集合S1S2的并集,即包含了S1S2所有元素的集合。

intersection(S1, S2)

返回集合S1S2的交集,即仅包含既包含于S1又包含于S2的元素的集合。

严格地说,我们并不能说new返回了一个空集,而应该说new返回了一个空集的表示。如果我们将集合表示为列表,则以上的集合操作可以编写如下:

程序3.2

-module(sets).
-export([new/0, add_element/2, del_element/2,
         is_element/2, is_empty/1, union/2, intersection/2]).

new() -> [].

add_element(X, Set) ->
    case is_element(X, Set) of
        true -> Set;
        false -> [X|Set]
    end.

del_element(X, [X|T]) -> T;
del_element(X, [Y|T]) -> [Y|del_element(X,T)];
del_element(_, [])    -> [].

is_element(H, [H|_])   -> true;
is_element(H, [_|Set]) -> is_element(H, Set);
is_element(_, [])      -> false.

is_empty([]) -> true;
is_empty(_)  -> false.

union([H|T], Set) -> union(T, add_element(H, Set));
union([], Set)    -> Set.

intersection(S1, S2)       -> intersection(S1, S2, []).
intersection([], _, S)     -> S;
intersection([H|T], S1, S) ->
    case is_element(H,S1) of
        true -> intersection(T, S1, [H|S]);
        false -> intersection(T, S1, S)
    end.

运行程序3.2的代码:

> S1 = sets:new().
[]
> S2 = sets:add_element(a, S1).
[a]
> S3 = sets:add_element(b, S2).
[b,a]
> sets:is_element(a, S3).
true
> sets:is_element(1, S2).
false
> T1 = sets:new().
[]
> T2 = sets:add_element(a, T1).
[a]
> T3 = sets:add_element(x, T2).
[x,a]
> sets:intersection(S3, T3).
[a]
10> sets:union(S3,T3).
[b,x,a]

这个实现并不十分高效,但足够简单以保证其正确性(但愿如此)。今后还可以将之替换为一套更高效的实现。


留下一个回复

你的email不会被公开。