0

連絡先情報 [名前、電話番号] を保存するのに最適なデータ構造は何ですか?

Trieは、名前が与えられたときに電話番号を検索するのに役立ちます。
電話番号を指定して人の名前を検索したい場合はどうなりますか。つまり、電話番号がわかっている場合、どうすれば名前を見つけることができますか?
そのような検索に tri は効率的ですか?

4

1 に答える 1

1

はい、試してみてください。各レベルで文字列の文字をキーとして使用する代わりに、電話番号のビットを使用できます (整数として格納している場合)。速度上の理由から、一度に 3 ビットまたは 4 ビットを使用することを決定する場合があります。

これは、現在の ID 情報を格納するトライ構造体と、子トライ構造体へのポインターの配列を持つことで機能します。

struct phone_number_trie {
   struct contact_info *info;
   struct phone_number_trie *children[4]; //  or 2, 8 or 16 etc.
};

たとえば、ルートが であるツリーに電話番号 '83' (1100011バイナリ) を格納するroot場合、下位 2 ビット (たとえば& 3) をマスクして、電話番号の残りのビットを使用して11再帰します。(つまり、右に 2 シフトします)。次のインデックスは、 、そして になります (つまり、 を指すことになります)。この時点で、電話番号には設定されたビットが残っていないため、挿入する適切な場所が見つかりました。root->children[3]110000101root->children[3]->children[0]->children[2]->children[1]

( Patricia trieの使用も検討できますが、これは実装が非常に困難です。)

于 2012-06-18T02:30:26.487 に答える