введите адресную книгу телефона - обратный указатель

Question

Теперь я пытаюсь создать структуру данных для реализации телефонной книги Adreess. Скажите, что есть две информации: имя, номера телефонов. Одно и то же имя может иметь более одного номера. Теперь я хотел бы придумать структуру данных, которая поможет мне получить номер, присвоенный имени, и получить имя, учитывая число. Я должен сделать это в наименьшее возможное время. Я думал о сохранении карты (имя к номеру), а затем для определенного номера каким-то образом обратного индекса на эту карту, а затем найти имя. Я не совсем уверен, что это лучший способ сделать это. Можете ли вы предложить идеальную структуру данных. Будет использовать некоторую обратную ссылку. Если да, то как я могу использовать его в этом контексте.

Answer 1

Вы можете использовать пару словарей (ака карт): один для поиска чисел с именами (name -> List<number>) и один для поиска имен с использованием номеров (number -> name).

Answer 2

Предполагая, что желательно использовать префиксные совпадения, я бы предложил использовать Patricia trie. Предполагая, что имя и номер телефона никогда не могут столкнуться - т. Е. У вас не будет никого с именем 435-9876 в вашем каталоге, - тогда вы можете вставлять пары с индексированным номером телефона в trie, а также с парами, индексированными по имени. Если по какой-то странной причине возможны коллизии имен номеров, вы можете добавить специальный символ для префикса телефонных номеров, чтобы они могли столкнуться.

Вставка будет стоить O (ы)
Lookups будет стоить O (ы)
, где s является длиной/вставленного ключа поиска строки.

Это решение также позволит вам поддерживать автоматическое заполнение стиля оболочки Linux, где вы можете определить, сколько записей есть, которые соответствуют определенному имени, как набранное, или даже отображать все соответствия по требованию.

EDIT:

Патрисия Trie, как обычный дерева, за исключением, что ветви в Patricia происходят только синтаксического дерева, когда есть, по крайней мере, два различных ключа обмена префикс, который не был отделен от предыдущей ветви.

1. Внутренние узлы указывают индекс, по которому ключи отличаются, а листовые узлы хранят фактические ключи.
   
2. Все дочерние узлы совместно используют родительский префикс.
   
3. Ветви от узла «помечены» символом, который встречается в позиции, указанной родителем.
   
4. Ребенок не может указывать меньший индекс, чем его родитель.

Таким образом, если Jane и Jamie являются единственными ключами, хранящимися в trie, у них есть три узла - родитель представляет общий префикс «Ja», одна ветвь ведет к поддереву, содержащему все строки, начинающиеся с «Jan», - и поскольку есть только один, он хранится в листовом узле «Джейн», в то время как другая ветвь ведет к поддереву, содержащему все строки, начинающиеся с «Jam», опять же, когда они являются только одним.

  [2] 
    n    m 
'Jane'   'Jamie' 

Если вы добавите Джеймс, вы получите

  [2] 
    n    m 
'Jane'    [3] 
       e    i 
      'James'  'Jamie' 

А затем добавить Jamelia

  [2] 
    n    m 
'Jane'    [3] 
       e    i 
       [4]   'Jamie' 
      l  s 
     'Jamelia' 'James' 

Searching проста. Начиная с корня, указан указанный индекс. Если ни один из детей не помечен фактическим значением, указанным в нашем примере, например, если поиск Джаспера выполняется, поскольку символ в позиции 2 равен s, а не n или m, поиск возвращает, что значение не существует. В противном случае следует следовать соответствующей ветке, пока не будет найдено значение, доказано, что его нет, или несколько совпадений остаются. Например. поиск замятия останавливается в узле с надписью [3]. Существует несколько совпадений узлов, но клавиши Jam нет. В этом случае вы можете пересечь поддеревье, внедренное в [3], для создания списка частичных совпадений. Обратите внимание, что это применимо только в том случае, если вы выполняете частичные совпадения, если был указан весь ключ, результат поиска «Jam» не будет соответствовать.

Стоимость поиска в порядке длины ключа, ов потому что, как вы можете видеть, что есть в большинстве сек уровней, прежде чем ключ либо найден или показано, чтобы не быть там. Аналогично, стоимость вставки также находится в порядке длины ключа, который нужно вставить, поскольку вставка выполняется путем выполнения поиска, а затем добавление ветвления ветви в самый длинный префикс в дереве.

Вы можете найти реализацию java here и то, что похоже на реализацию на C++ here.

Я никогда не использовал ни одну из реализаций, на которые я указал вам, поэтому не могу ручаться за их правдивость. Если вы решите реализовать структуру данных самостоятельно, я бы посоветовал вам использовать двоичный алфавит, так что это немного проще! Here - статья, описывающая алгоритм.

Answer 3

Я бы сохранил две (хэш-карты).

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

Map<String,Set<String>> NamesToNumbers; 

Вторая карта будет иметь номера телефонов в качестве ключей, а имена - значения.

Map<String,String> NumbersToNames; 

Кроме того, я бы создать простой класс с этими двумя картами, как частных членов, цель этого класса будет держать две карты в синхронизации, и передавать все положить(), удалить() и т.д. вызывает обе карты в правильном формате Key/Value.

псевдопользователей код, как идентификатор написать метод положить() в простом классе:

public void put(String Name,String PhoneNumber) 
{ 

Set NumbersForName = NamesToNumbers.get(Name); 
if (NumbersForName == null) 
    { 
    NumbersForName = new Set(); 
    NamesToNumbers.put(Name,NumbersForName); 
    } 

NumbersForName.put(PhoneNumber); 
NumbersToNames.put(PhoneNumber,Name); 

} 

Стоимость Ищут будет O (1), а стоимость вставки будет O (1), если нет хеш-коллизии.

Если вы используете Java 5+, вы должны проверить Google Collections, у них отличный класс Bi-map, который по сути является тем, что я пытаюсь описать.

Answer 4

Я создал концептуальную базу данных с помощью имен x Число пар. Каждая пара получает идентификатор.Если вы не можете гарантировать, что Джон Смит не будет жить в двух разных местах, вам нужен уникальный идентификатор.

поэтому у вас есть (в Perl)

$db{$id} = [name, number] 

Затем накладку с двумя хэши, которые возвращают наборы идентификаторов.

$name_index[$name] = [$id1, $id2, $id3] 
$number_index[$number] = #as above 

Для обновления потребуется определенное количество ошибок, но результаты будут быстро возвращены.

Вы можете сделать это на любом языке, который имеет конструкцию хеша/карты.