0

Go 言語で Trie データ構造を作ろうとしたのですが、なぜか References 問題で行き詰まってしまいました。http://play.golang.org/p/ASSGF5Oe9R

// Package main provides ...
package main

import "fmt"

type RootTrie []Trie

type Trie struct {
    subtrie []Trie
    index   byte
}

func (trie *Trie) Insert(data string) *Trie {
    if data != "" {
        if trie.index == 0 {
            trie.index = data[0]
        }
        if next := trie.containsIndex(data[1:]); next != nil {
            //Problem Point
            fmt.Println(string(data[1]), "found follwing", string(data[0]))
            next.Insert(data[1:])
        } else {
            nt := &Trie{}
            trie.subtrie = append(trie.subtrie, *nt.Insert(data[1:]))
        }
    }

    return trie
}
func (trie *Trie) containsIndex(next string) *Trie {
    if next != "" {
        for _, st := range trie.subtrie {
            if st.index == next[0] {
                return &st
            }
        }
    }
    return nil
}

func main() {
    t := &Trie{}
    t = t.Insert("hanyang")
    fmt.Println("result:", t)
    t = t.Insert("hanyKk")
    fmt.Println("result:", t)
    t.Insert("hanyK")
}

私が入れた2番目の「挿入」では、次の問題が発生します。//Problem Point

次に連結したトライを検索する方法を作っcontainsIndexたところ、実際にうまく検索できました。しかし、与えられたnextプロパティを更新するとcontainsIndex、その母構造体には影響しませんでしtrieた。

私が理解していないのは、 を返すときに参照型を指定したことですcontainsIndexが、それでも「コピーされた値」が好きでしたtrie。

ありがとう！

4

1 に答える 1

3

問題はメソッド containsIndex にあります。デフォルトでは、 Golangrangeはスライス内の各要素のコピーを作成し、この値のコピーをst(この例では) に割り当てます。通常、スライス内の要素への参照を保持するには、元のスライスとそのインデックスを使用する必要があります。あなたの場合、メソッド containsIndex は次のようになります。

func (trie *Trie) containsIndex(next string) *Trie {
    if next != "" {
        for i, st := range trie.subtrie {
            if st.index == next[0] {
                return &trie.subtrie[i]
            }
        }
    }
    return nil
}
于 2014-12-30T08:33:40.100 に答える