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

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

練習題：

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