全く制限のすべてに明確な、しかし、あなたがSTDから何かを使用することができないと仮定していない、あなたはに以下のような単純なクラスを書くことができ仕事をしなさい。バケツの配列を使用してデータを格納し、ハッシュ関数を使用して文字列を0 ... MAX_ELEMENTSの範囲の数値に変換します。各バケットにはリンクされた文字列のリストが保持されるため、情報を再度取得できます。典型的にはo（1）挿入と検索。
もっと効果的な解決策として、固定長配列ではなくベクトルを使用したいと思うかもしれないことに注意してください。エラーチェックやその他の改善も最小限に抑えられていますが、これが始めるはずです。
注記独自の文字列ハッシュ関数を実装する必要があります。ネット上でこれらを十分に見つけることができます。
class dictionary
{
struct data
{
char* word = nullptr;
data* next = nullptr;
~data()
{
delete [] word;
}
};
public:
const unsigned int MAX_BUCKETS;
dictionary(unsigned int maxBuckets = 1024)
: MAX_BUCKETS(maxBuckets)
, words(new data*[MAX_BUCKETS])
{
memset(words, 0, sizeof(data*) * MAX_BUCKETS);
}
~dictionary()
{
for (int i = 0; i < MAX_BUCKETS; ++i)
delete words[i];
delete [] words;
}
void insert(const char* word)
{
const auto hash_index = hash(word);
auto& d = words[hash_index];
if (d == nullptr)
{
d = new data;
copy_string(d, word);
}
else
{
while (d->next != nullptr)
{
d = d->next;
}
d->next = new data;
copy_string(d->next, word);
}
}
void copy_string(data* d, const char* word)
{
const auto word_length = strlen(word)+1;
d->word = new char[word_length];
strcpy(d->word, word);
printf("%s\n", d->word);
}
const char* find(const char* word) const
{
const auto hash_index = hash(word);
auto& d = words[hash_index];
if (d == nullptr)
{
return nullptr;
}
while (d != nullptr)
{
printf("checking %s with %s\n", word, d->word);
if (strcmp(d->word, word) == 0)
return d->word;
d = d->next;
}
return nullptr;
}
private:
unsigned int hash(const char* word) const
{
// :TODO: write your own hash function here
const unsigned int num = 0; // :TODO:
return num % MAX_BUCKETS;
}
data** words;
};
どのような言葉ですか？彼らは長さが約10文字で、最初は関連性がありますか、フルテキスト検索を行う長いテキストですか？ – ipc
これは宿題のように見えるので、私は答えをあげているわけではありませんが、ハッシュテーブルはあなたが探しているデータ構造ではないことを私は理解しています。 – Thomas
私はC++でそれを行う方法を知っていますが、代わりにSTLを使用して5分で完了させます。なぜあなたはSTLを使えないのかというあなたの要求を詳しく説明できますか？ – DXM