Не совсем ясно обо всех ограничениях, но, если вы не можете использовать что-либо из 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;
};