2

我想知道是否有可用于 Logo 语言的一流字典数据结构的实现？我在 UCB 徽标或 FMS 徽标的文档中没有看到可用的。我看到有属性列表，但那些似乎不是一流的，而且看起来它们是线性查找关联列表。我正在寻找基于哈希或树的东西。似乎那里有很多历史标志，也许有人已经实现了这样的东西。此外，如果有人知道徽标代码的存储库，我将不胜感激指针（即徽标的 CPAN）。

4

2 回答 2

2

这是一个基于列表的真正简单的纯功能树实现。键可以是单词或数字。空列表是空字典。它不是自我平衡，因此在使用“dict_add”进行插入后，您必须自己调用“rebalance”。不要经常这样做，因为实施的“重新平衡”需要 O(n) 时间。一个过程“测试”会稍微练习一下。

to dict_lookup :dict :key
   if (empty? :dict) [output []]
   localmake "pair first :dict
   if (empty? :pair) [output []]
   localmake "test_k first :pair
   if (equal? :key :test_k) [output last :pair]
   output dict_lookup (ifelse (before? :key :test_k) [left_tree :dict] [right_tree :dict]) :key
end

to left_tree :dict
    output item 2 :dict
end

to right_tree :dict
    output item 3 :dict
end

to dict_add :dict :key :value
    localmake "new_pair (list :key :value)
    if (empty? :dict) [output (list :new_pair [] [])]
    localmake "old_pair first :dict 
    localmake "old_key first :old_pair

    localmake "l_tree left_tree :dict
    localmake "r_tree right_tree :dict

    if (equal? :key :old_key) [output (list :new_pair :l_tree :r_tree)] 
    ifelse (before? :key :old_key) [
        localmake "l_tree dict_add l_tree :key :value] [
        localmake "r_tree dict_add r_tree :key :value]
    output (list :old_pair :l_tree :r_tree)
end

to in_order :dict
    if (empty? :dict) [output []]
    output (sentence (in_order (left_tree :dict)) 
                     (list (first :dict))
                     (in_order (right_tree :dict)))
end

to draw_tree :dict :size
    if (empty? :dict) [label [[]] stop]
    rt 50 fd :size lt 50
        draw_tree (left_tree :dict) :size * 0.7 
    rt 50 bk :size lt 50
    label (first :dict)
    lt 50 fd :size rt 50 
        draw_tree (right_tree :dict) :size * 0.7
    lt 50 bk :size rt 50
end

to list_to_tree :l
    if (empty? :l) [output []]
    localmake "half int (count :l)/2
    localmake "firsts take :half :l
    localmake "rests drop :half :l
    output (list (first :rests) (list_to_tree :firsts) (list_to_tree bf :rests))
end

to take :n :l
    if (or (empty? :l) (:n < 1)) [output []]
    output fput (first :l) take :n-1 bf :l
end

to drop :n :l
    if (:n < 1) [output :l]
    output drop :n-1 bf :l
end

to rebalance :dict
   output list_to_tree in_order :dict
end

to testing
    localmake "test_dict []
    localmake "items [[apple 1] [ball 2] [banana 3] [cat 4] [zebra 5] 
                      [toy 6] [yak 7] [jump 8]]
    foreach :items [make "test_dict (dict_add :test_dict (first ?) (first bf ?))]
    cs pu
    lt 60 fd 500 setheading 180 pd 
        draw_tree :test_dict 200
    pu lt 90 fd 700 setheading 180 pd 
        draw_tree (rebalance :test_dict) 160
end
于 2014-12-24T00:02:26.763 回答
0

确实，在 FMSLogo 中，属性列表不是一等公民。但是，属性列表“名称”是一流的。FMSLogo 6.32.0 版也将属性列表实现为 AVL 树。这记录在这里：http: //sourceforge.net/p/fmslogo/feature-requests/94/

于 2015-04-08T05:11:27.870 回答