【初心者歓迎】C/C++室 Ver.50【環境依存OK】

【初心者歓迎】C/C++� ..

239:デフォルトの名無しさん
08/03/03 07:59:34
複数ある単語から文字列中最初にマッチする物を探す用途で、
こんなのを考えてみたのですが、こういう2分木辞書ってなんて
名前になるんでしょうか？
サフィックスツリー？(これよりもっと複雑なようですが)

typedef std::map<char, Node> Tree;
//char に単語の1文字が入る

struct Node {
　Node *pChild;　//次の文字ノード
　int No;　　　　　　//登録番号、兼、非末端(-1)
}

単語がab,ba,ac,abcとあるなら、子ノードの繋がりが下記のようになる。
先頭　　　<a,-1>　　　　　　　<b,-1>
　　　　　　／　＼　　　　　　　／
　　　　<b,0>　　<c,3>　　　<a,1>
　　　　／
　　<c,3>

次ページ

続きを表示

1を表示