c++ - 連想配列/マップ/ハッシュテーブルのデータ構造を実装する方法（一般的におよびC ++で）

Question

さて、私は小さな電話帳アプリケーションを作成していて、マップを使用することが使用するのに最適なデータ構造であると判断しましたが、どこから始めればよいのかわかりません。（データ構造を最初から実装する必要があります-学校の仕事）

Answer 1

試行は、キーが短い文字列であるマップを実装するのに非常に効率的です。ウィキペディアの記事はそれをかなりよく説明しています。

重複に対処するには、ツリーの各ノードに重複一致のリンクされたリストを格納するだけです

これがトライの基本構造です

struct Trie {
   struct Trie* letter;
   struct List *matches;
};

文字の malloc(26*sizeof(struct Trie)) で、配列があります。句読点をサポートしたい場合は、文字配列の最後に追加してください。

構造体リストを定義しません。

Answer 2

最も簡単な解決策: アドレス エントリを含むベクターを使用し、そのベクターをループして検索します。

マップは通常、バイナリ ツリー (バランスをとるために赤/黒のツリーを探します) またはハッシュ マップとして実装されます。どちらも些細なことではありません: ツリーには編成、メモリ管理、およびバランスのためのオーバーヘッドがあり、ハッシュ マップには優れたハッシュ関数が必要ですが、これも些細なことではありません。しかし、どちらの構造も楽しいので、どちらかを実装することで多くの洞察を得ることができます (または両方を実装することをお勧めします :-))。

また、ベクター リストにデータを保持し、マップにベクターへのインデックス (またはエントリへのポインター) を含めることも検討してください。そうすれば、複数のインデックスを簡単に作成できます。たとえば、名前用に 1 つ、電話番号用に 1 つなどです。両方でエントリを検索します。

そうは言っても、標準ライブラリが提供するデータ構造を実際のタスクに使用することを強くお勧めしたいだけです:-)

Answer 3

開始するための簡単な方法は、キー用と値用の 2 つのベクトルを使用するマップ クラスを作成することです。項目を追加するには、1 つの項目にキーを挿入し、別の項目に値を挿入します。値を見つけるには、すべてのキーをループするだけです。これが機能したら、より複雑なデータ構造を使用することを考えることができます。