Erlang程式设计与问题解决/资料结构

维基教科书,自由的教学读本


资讯相关科系教导一种入门的程式语言之后,都会跟著教资料结构。资料结构包含有基础结构、如阵列和链接串列 ( linked list ) ,以及高层结构如堆叠、伫列、树和图等等。本章对基础结构做一些探讨。之后几章会讨论伫列、堆叠、与树。

以下,依序讨论 Erlang 的链接串列与阵列。

链接串列[编辑]

链接串列,是用局部串连的规格,将许多小的资料项目连接成一串资料。

[ 資料區塊 | 鏈接指標-]----> [ 資料區塊 | 鏈接指標-]---->

Erlang 的列表就是链接串列。对于这件事实,在此用一些推导过程来说明。以下的推导要说明: Erlang 的列表就是链接串列。因此,在 Erlang 语言上,不需要讨论如何实作链接串列。

首先,由于列表与值组都可以把一些资料单位放在一起,构成大的资料结构,于是我们用列表来做链接串列。链接串列的一个元素,称为节点,包函资料与链接。以下是链接串列的第一个节点:

[ SomeThing | []]

链接指标定为 [] 代表链接串列的尾端。

可以有一个链接串列的建构式,产生一个无资料的串列:

create_llist() ->
    [].

链接串列需要增添资料,相关函数为:

add_to_llist(Node, LList) ->
    [Data|_] = Node,
    Link = LList,
    [Data|Link].

可以从链接串列删除资料。由于 Erlang 没有指标可做物件的识别项,我们定义节点的资料部份划分为 [识别项,资料,资料,...] :

remove_from_llist(_, []) ->
    [];
remove_from_llist(ID, [[ID|Data]|LList]) ->
    LList;
remove_from_llist(ID, [Node|LList]) ->
    [Node|remove_from_llist(ID, LList)].

于是,可以有一个函数将一列 [[识别项,资料 ... ],[识别项,资料 ... ], ... ] 的资料制做为链接串列:

create_llist([]) ->
    create_llist();
create_llist([[ID|Data]|List]) ->
    add_to_llist(
        [ [ID|Data]|[] ],
        create_llist(List)
    ).

试做一个链接串列:

> create_llist([[1,a,b],[2,b,c],[3,c,d] ]).
[[1,a,b],[2,b,c],[3,c,d] ]

由此例见到,以 Erlang 列表实作链接串列,得到的结果跟列表本身相同。

事实上, Erlang 平台已经使用了相当多的链接串列做实作。而在语言方面,列表确实拥有链接串列的性质。所以,用 Erlang 做资料处理可说相当方便。

阵列[编辑]

Erlang 没有阵列,但可以用列表模拟阵列操作。 Erlang 有 array 模组提供以阵列格式操作资料。另外, Erlang/OTP 提供 ets 与 dets 子系统,可做资料的随机存取;前者是用在记忆体中做资料的储存管理,后者是在档案系统中做资料的储存管理。

阵列的性质是:由许多键值与物件的配对,构成一组阵列。阵列的键值通常是连续数字。因此,可以用以下程式,将资料从列表转换为阵列。

-module(arr).
-compile(export_all).

create_array([]) ->
    [];
create_array(Xs) ->
    zip(lists:seq(0,length(Xs)-1), Xs).

zip([], _) ->
    [];
zip([X|Xs], [Y|Ys]) ->
    [{X,Y}|zip(Xs,Ys)].
> arr:create_array([a,b,c,d]).
[{0,a},{1,b},{2,c},{3,d}]

然后可以有 ith/2 取第 i 个元素。

ith(N, [{N,X}|_]) ->
    X;
ith(N, [_|Xs]) ->
    ith(N, Xs).
> arr:ith(1,arr:create_array([a,b,c,d])).
b

不过,这样并没有实作随机存取的阵列。

练习题:
请试试用以上的阵列实作,实作一般程序式语言所讨论的气泡排序法。