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

不過,這樣並沒有實作隨機存取的陣列。

練習題:
請試試用以上的陣列實作,實作一般程序式語言所討論的氣泡排序法。