Подходящая структура данных для поиска номера телефона человека, учитывая его имя?

Question

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

Answer 1

текст ниже отвечает на ваш вопрос.

В информатике хеш-таблица или хеш-карта - это структура данных, которая использует хеш-функцию для сопоставления идентифицирующих значений, известных как ключи (например, имя человека) , к связанным с ним значениям (например, его телефон номер) . Таким образом, хеш-таблица реализует ассоциативный массив. Хеш Функция используется для преобразования ключа в индекс (хэш) элемент массива (слот или корзина), где соответствующее значение искать.

текст из вики: хеш-таблица.

есть некоторые дальнейшие обсуждения, такие как столкновение, хэш-функции ... проверьте страницу вики для деталей.

Answer 2

Я уважаю и люблю хеш-таблицы :), но даже сбалансированное бинарное дерево подойдет для вашего приложения телефонной книги, если в худшем случае сложность логарифмическая, и вам не нужно иметь хорошие хэш-функции, коллизии и т. Д., Которые больше подходят для огромных объемы данных.

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

Answer 3

Мне было интересно, почему в одном из ответов не появилось «Пытки», Tries подходит для данных телефонной книги.

Кроме того, экономия места по сравнению с HashTable при той же стоимости (почти) эффективности извлечения (при условии алфавита постоянного размера и имен постоянной длины)

Пытается такжеоблегчить 'Prefix Matches' иногда требуется при поиске.

Answer 4

Словарь динамический и быстрый.

Answer 5

Почему бы не использовать односвязный список?Каждый узел будет иметь имя, номер и информацию о ссылке.

Один недостаток заключается в том, что поиск может занять некоторое время, поскольку вам придется обходить весь список от ссылки к ссылке.Вы можете упорядочить список во время самой вставки узла!

PS: Чтобы сделать поиск немного быстрее, сохраняйте ссылку на середину списка.Поиск может продолжаться слева или справа от списка на основе значения поля «имя» в этом узле.Обратите внимание, что для этого требуется двусвязный список.

Answer 6

Вам нужен словарь, в котором вы используете имя в качестве ключа, а номер в качестве сохраняемых данных. Проверьте это: http://en.wikipedia.org/wiki/Dictionary_%28data_structure%29