我有一個我正在做的項目，主要目標是將一個單詞列表（以及它們中的大多數15k +）加載到數據結構中，然後對該列表進行搜索結構體。我做了一個小小的研究，並且據我所知，哈希表最適合這種情況（如果我錯了，請糾正我的錯誤，我也會試着嘗試）如何在不使用STL的情況下實現C++字典數據結構
這是棘手的部分：我不能使用任何STL這個項目。所以據我所知，我將不得不編寫自己的哈希表類或找到一個非常有用的哈希表類。我理解表格是如何在基本層面上工作的，但我不確定自己足夠了解自己寫的整個表格。
我環顧了Google，找不到任何合適的示例代碼。
我的問題是沒有人知道如何做到這一點在c + +和/或哪裏我可以找到一些代碼開始。我需要3個基本功能：插入，搜索，刪除。
事情要記住，而你想一想：
http://wikipedia-clustering.speedblue.org/trie.php
似乎上面的鏈接已關閉的時刻。
替代鏈接： https://web.archive.org/web/20160426224744/http://wikipedia-clustering.speedblue.org/trie.php
鏈接失敗2016-12-29 – 2016-12-29 19:07:43
@StephenWoodbridge替代鏈接添加回答。希望有所幫助 – fizzbuzz 2017-03-17 12:30:09
std::unordered_map不是STL
我認爲，字符串數組排序+二進制搜索應該是相當有效的。
不是在所有的限制完全清楚，但假設你不能從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 2012-02-18 21:59:04
由於這看起來像功課，我沒有提供答案，但我會提示一個散列表不是你要找的數據結構。 – Thomas 2012-02-18 22:03:48
我知道如何在C++中完成它，但是我將使用STL並在5分鐘內完成。你能詳細說明你爲什麼不能使用STL的要求嗎？ – DXM 2012-02-18 22:46:57