Erlang数据结构

• Stack
• Queue
• Table
• Trees
• Graph
• Union/Find

Stack

基于单个List的实现

% stack
-module(stack).
-export([emptyStack/0, stackEmpty/1, push/2, pop/1, top/1]).


% 生成空栈
emptyStack() -> [].

% 判断是否为空
stackEmpty([]) -> true;
stackEmpty(_) -> false.

%
push(X, XS) -> [X|XS]. 

%
pop([]) -> error("pop from am empty stack");
pop(_|XS) -> XS.

%
top([]) -> error("top from an empty stack");
top([X|_]) -> X.

queue

用单个List实现

-module(queue).
-export([emptyQueue/0, queueEmpty/1, enqueue/2, dequeue/1, front/1, showQ/1]).

emptyQueue() -> [].

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

enqueue(X, Q) -> Q ++ [X].

dequeue([_|XS]) -> XS;
dequeue([]) -> error("dequeue : empty queue").

front([X|_]) -> X;
front([]) -> error("front: empty queue").

用一对List实现（或者说用列表的元组）

showQ({F, R}) -> F++lists:reverse(R).

queueEmpty({[], []}) -> true;
queueEmpty(_) -> false.

emptyQueue() -> {[], []}.

enqueue(X, {[], []}) -> {[X], []};
enqueue(Y, {XS, YS}) -> {XS, [Y|YS]}.

dequeue({[],[]}) -> error("dequeue:empty queue");
dequeue({[],YS}) -> {lists:nthtail(1, lists:reverse(YS)), []};
dequeue({[_|XS],YS}) -> {XS,YS}.

front({[],[]}) -> error("front:empty queue");
front({[],YS}) -> lists:last(YS);
front({[X|_],_}) -> X.

Table

-module(table).
-export([newTable/1, findTable/2, updTable/2]).
-export([newTableL/1, findTableL/2, updTableL/2]).


newTable(Assocs) ->
    lists:foldr(fun table:updTable/2, 
        fun(_) -> error("item not found in table") end,
        Assocs).

updTable({I,X}, F) -> 
    G = fun(J) ->
        case J =:= I of 
            true -> X;
            false -> F(J)
        end
    end,
    G.

newTableL(T) -> T.

findTableL([], _) -> error("item not found in table");
findTableL([{J,V}|_], I) when I =:= J -> V;
findTableL([_|R], I) -> findTableL(R, I).

updTableL(E, []) -> [E];
updTableL({I,_a}, [{J,_}|R]) when I =:= J -> [{I,_a}|R];
updTableL({I,_a}, [{J,_b}|R]) -> [{J,_a}|updTableL({I,_b}, R)].

Tree

-module(bintree).
-export([emptyTree/0, inTree/2, addTree/2, delTree/2]).
-export([buildTree/1, buildTree1/1, inorder/1]).


inTree(_, emptyBT) -> false;
inTree(V1, {V, _, _}) when V =:= V1 -> true;
inTree(V1, {V, LF, _}) when V1 < V -> inTree(V1, LF);
inTree(V1, {V, _, RT}) when  V1 > V -> inTree(V1, RT).


addTree(V1, emptyBT) -> {V1, emptyBT, emptyBT};
addTree(V1, {V, LF, RT}) when V1 =:= V -> {V, LF, RT};
addTree(V1, {V, LF, RT}) when V1 < V -> {V, addTree(V1, LF), RT};
addTree(V1, {V, LF, RT}) -> {V, LF, addTree(V1, RT)}.


buildTree1([]) -> emptyBT;
buildTree1(LF) -> 
    N = length(LF) div 2,
    L1 = lists:sublist(LF, N),
    [X|L2] = lists:nthtail(LF, N),
    {X, buildTree1(L1), buildTree(L2)}.

 
delTree(v1, emptyBT) -> eEmptyBT;



delTree(V1, {V, LF, emptyBT}) when V1 =:= V -> LF;
delTree(V1, {V, emptyBT, RT}) when V1 =:= V -> RT;
delTree(V1, {V, LF, RT}) when V1 < V -> {V, delTree(V1, LF), RT}; 
delTree(V1, {V, LF, RT}) when V1 > V -> {V, LF, delTree(V1, RT)};
delTree(V1, {V, LF, RT}) when V1 =:= V ->
    K = minTree(RT), {K, LF, delTree(K, RT)}.



minTree({V, emptyBT, _}) -> V;
minTree({ _, LF, _}) -> minTree(LF).
inorder(emptyBT) -> [];
inorder({V, LF, RT}) -> inorder(LF) ++ [V] ++ inorder(RT).

Union_find