Как реализовать ассоциативную структуру данных массива / карты / хеш-таблицы (в целом и в C ++)

Question

Что ж, я делаю небольшое приложение для телефонной книги, и я решил, что использование карт будет наилучшей структурой данных, но я не знаю, с чего начать. (Должен реализовать структуру данных с нуля - школьная работа)

Answer 1

Попытки довольно эффективны для реализации карт, в которых ключи представляют собой короткие строки. Статья в Википедии объясняет это довольно хорошо.

Чтобы иметь дело с дубликатами, просто заставьте каждый узел дерева хранить связанный список дубликатов

Вот базовая структура для дерева

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

malloc (26 * sizeof (struct Trie)) для буквы и у вас есть массив. если вы хотите поддержать пунктуацию, добавьте их в конец массива букв.

совпадения могут быть связанным списком совпадений, реализованным, как вам угодно, я не буду определять struct List для вас.

Answer 2

Самое простое решение: используйте вектор, содержащий ваши адресные записи, и выполните цикл по вектору для поиска.

Карта обычно реализуется либо в виде двоичного дерева (для балансировки ищите красные / черные деревья), либо в виде хэш-карты. Оба они не тривиальны: деревья имеют некоторые накладные расходы на организацию, управление памятью и балансировку, хэш-картам нужны хорошие хэш-функции, которые также не являются тривиальными. Но обе структуры забавны, и вы получите глубокое понимание, внедрив одну из них (или лучше обе: -)).

Также рассмотрите возможность сохранить данные в списке векторов и позволить карте содержать индексы для вектора (или указатели на записи): тогда вы можете легко иметь несколько индексов, например, один для имени и один для телефонного номера, так что вы можете искать записи по обоим.

При этом я просто настоятельно рекомендую использовать структуры данных, предоставляемые стандартной библиотекой, для реальных задач: -)

Answer 3

Простой способ начать работу - создать класс карты, который использует два вектора - один для ключа и один для значения. Чтобы добавить элемент, вы вставляете ключ в одно, а значение в другое. Чтобы найти значение, вы просто перебираете все ключи. Как только у вас все получится, вы можете подумать об использовании более сложной структуры данных.