Какова наилучшая структура данных для хранения контактной информации [имя, номер телефона]?Как сохранить контактную информацию
Trie может быть полезен для поиска номера телефона, если имя дано.
Что делать, если я хочу найти имя человека, учитывая его номер телефона. например, как я могу найти имя, когда узнаю номер телефона?
Действительно ли эффективен для такого поиска?
Да, это хорошо. Вместо того, чтобы использовать символы в строке в качестве ключа на каждом уровне, вы можете использовать биты в телефонном номере (если вы храните их как целые числа). По соображениям скорости вы можете использовать 3 или 4 бита за раз.
Это будет работать с помощью структуры trie, которая хранит текущую идентификационную информацию, а затем массив указателей на дочерние структуры trie.
struct phone_number_trie {
struct contact_info *info;
struct phone_number_trie *children[4]; // or 2, 8 or 16 etc.
};
E.g. сохраняя номер телефона «83» (который равен 1100011 в двоичном формате) в дереве, где корень равен root, вы можете замаскировать нижние 2 бита (например, & 3), которые равны 11, поэтому вы можете перечислить в root->children[3] с оставшимися битами номера телефона 11000 (т.е. сдвиньте его вправо 2). Следующие индексы будут 0, а затем 10, а затем 1 (так что вы указали бы на root->children[3]->children[0]->children[2]->children[1]). На данный момент у вас нет установленных битов в вашем номере телефона, поэтому вы нашли нужное место для вставки.
(Вы можете также рассмотреть вопрос об использовании Patricia trie, но это значительно сложнее реализовать.)
Я прочитал дерево Патрисии. Но это не решает мою проблему. Моя проблема заключается в том, что делать, когда пользователь хочет искать по номеру телефона, а также искать по имени. –
(Patricia trie - это только то, что вы хотите очень быстро найти (это намного сложнее реализовать, чем обычное trie).) Вы должны просто иметь trie, который отображает имена в 'contact_info' и тот, который отображает номер телефона на' contact_info's (т. е. две попытки), поэтому при вставке вы выделяете свою структуру 'contact_info' и устанавливаете соответствующий указатель в каждом из попыток указать на эту структуру, а затем вы можете просто искать в соответствующем trie. (Ответит ли это на ваш вопрос?) – huon
Да. Конечно. Но разве вы не думаете, что мы закончим тем, что будем хранить одни и те же данные дважды? Есть ли у нас способ уменьшить пространство? –
ли искать только операцию, которую нужно поддерживать? – dirkgently
Нет, кроме поиска, я также хочу легко вставить записи. –