0

我正在尝试用 Javascript 实现 Trie，这很容易，但我的对象似乎遇到了障碍。

节点结构如下：

var node = {
    children: []
}

Children 是一个由字符串中的字母映射的节点数组。所以字符串“Test”看起来像这样：

root = {
  children: [
      't' => {
          children: [
              'e' => {
                   children: [
                       's' => {
                            children: [
                                 't' => {
                                      children: []
                                  }
                            ]
                        }
                   ]
               }
          ]
      }
  ]
};

所以每个子数组的长度应该为 1，但如果做类似alert(this._root.children.length);我得到零的事情。关于为什么会发生这种情况的任何想法？

这是我实现的其余部分：

function Trie() {
    this._root = {
        children: []
    };
}

Trie.prototype = {

    //restore constructor
    constructor: Trie,

    add: function (str){
        var curr = this._root,
            prev,
            currchar;
        // For each character in the string
        for(var i = 0, j = str.length; i < j; i++) {
            // Insert only lowercase letters for efficiency
            currchar = str.toLowerCase().charAt(i);
            prev = curr;
            curr = prev.children[currchar];
            // Traverse until we hit a non-existant node
            if(typeof(curr) == "undefined") {
                // Make a new node
                prev.children[currchar] = {
                    children: []
                };
                curr = prev.children[currchar];
            }
        }
    }
4

3 回答 3

2

您正在向数组实例对象添加属性，而不是向数组添加元素。该length属性仅包括数组元素，不包括数组实例对象的属性。

var a = [23, 42];
console.log(a.length); // 2
a['foo'] = 'bar';
console.log(a.length); // 2
a[2] = 1337;
console.log(a.length); // 3

编辑： 您可以改为像这样构造节点：

var node = {
    children: {},
    length: function () {
        var i = 0;
        var k;

        for (k in this.children) {
            if (this.children.hasOwnProperty(k)) {
                i++;
            }
        }
        return i;
    }
};

当然，这是低效的。相反，您应该在其原型上定义一个具有 length 方法的 Node 类。或者，定义一个add更新长度属性的方法。

于 2011-06-14T21:01:48.333 回答
2

我认为问题在于您使用 javasrcipt 数组作为关联数组（如在其他语言中发现的那样）。在 javascript 中，“关联”数组是没有长度属性的对象。普通数组具有数字索引。

与问题无关，但您可能会发现这很有用。

于 2011-06-14T21:07:06.140 回答
-1

也许你想要

str.toLowerCase().charCodeAt(i)

代替

str.toLowerCase().charAt(i)

如果str是"f1"，则您添加到子数组的属性是"f"并且"1"应该导致一个具有名为的属性f和长度为 0 的数组，以及另一个具有长度2和属性的子数组1。

要仅获取数字属性，您应该确保您的属性名称是有效的数组索引——可以用 31 位表示的正整数。

通过使用charCodeAtinstead of charCode，您将获得属性名称102and49而不是"f"and 1。

于 2011-06-14T20:54:55.827 回答