具有指針的命令式OCaml數據結構？

大家好，

在我的課堂上，我們被告知要執行二叉搜索樹OCaml中，使用功能和命令式編程。我們正在使用Pascal進行ADT和實現，這是一種使用指針的過程語言。

這是數據結構的樣子：

# Pascal 
type 
    tKey  = integer; 
    tPos  = ^tNode; 
    tNode  = record 
      key   : tKey; 
      left, right : tPos; 
      end;  
    tBST = tPosT;

我們也給出了一些基本的BST操作。下面是一個例子，如果可以幫助：

# Pascal 
procedure add_key(VAR T : tBST; k:tKey); 
var new, parent, child : tBST; 
begin 
    createNode(new); 
    new^.key := k; 
    new^.left := nil; 
    new^.right := nil; 

    if T=nil then 
     T := new 
    else begin 
     parent := nil; 
     child := T; 
     while (child <> nil) and (child^.key <> k) do begin 
    parent := child; 
    if k < child^.key then 
     child := child^.left 
    else 
     child := child^.right; 
     end; 

     if (child = nil) then 
    if k < parent^.key then 
     parent^.left := new 
    else 
     parent^.right := new; 
     { duplicates are ignored } 
    end; 
end;

這是我的功能（如果讓任何意義）數據結構的樣子：

type key = 
    Key of int;; 

type bst = 
    Empty 
    | Node of (key * bst * bst);;

不過，我有大麻煩使用OCaml的命令方面。我必須使它看起來與Pascal實現類似，我不知道OCaml中數據結構和指針的可能性，因爲我一直使用遞歸等進行編程。我在考慮使用多個「let」，if和else，但我不知道如何定義我的數據結構。希望對此有很大的貢獻。

來源

2017-09-26 deko

據我瞭解，你將有一個類型是這樣的：

type key = int 

type t = Empty | Node of t * key * t

但你的附加功能不應該是這樣的：

let rec add x t = 
    match t with 
    | Empty -> 
     Node (Empty, x, Empty) 
    | Node (l, v, r) -> 
     let c = compare x v in 
     if c = 0 then t 
     else if c < 0 then Node (add x l, v, r) 
     else Node (l, v, add x r)

因爲這是唯一的功能。

也許你可以你的類型更改爲：

type t = Empty | Node of t ref * key * t ref

並嘗試add功能適應這種類型。

來源

2017-09-26 12:14:51 Lhooq

請問什麼是elt？它是用來抽象節點的值嗎？是的，基本上你所說的是發生了什麼事情。我的類型必須儘可能地像pascal一樣。不僅是它的工作方式。我會嘗試你的類型，並繼續調查。 – deko

壞的複製/粘貼;-)我更新了我的答案，因爲它應該是'key' – Lhooq

具有指針的命令式OCaml數據結構？

回答

相關問題