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

计算机科学 > 编程 > 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

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

练习题：

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