Data Structure for phone book

Question

Possible Duplicate:
storing 1 million phone numbers

How to design a data structure for a phone address book with 3 fields name, phone number , address

one must be able to search this phone book on any of the 3 fields

Hash table wouldn't work because all the three fields should hash to the same value which is i think impossible. I thought about trie and other data structures too but couldn't think of a proper answer.

Answer 1

You Should use TRIE data Structure for Implementing Phonebook. TRIE is an ordered tree data structure that uses strings as keys. Unlike Binary Trees, TRIE does not store keys associated with the node.

Good example

Answer 2

You could accomplish this with a single hash table or other type of associative array (if you wanted to). For each person, just have three keys in the table (name, address, phone) all pointing to the same record.

Answer 3

I think a combination of a trie (each phone book entry is one leaf) and two skip lists (one for each name and address) could turn out to be effective.

Just assign each node one set of pointers to move along the name axis, and one set of pointers to move along the address axis (that is, to traverse the skip lists).

Answer 4

You can't exactly sort something in three ways at the same time. Nor can you feasibly build a single hash table which allows lookup with only a third of the key.

What you probably want to do is basically what databases do:

• Store one (possibly unsorted) master list of all your records.
• For each column you want to be able to search on, build some kind of lookup structure which returns a pointer/index into the master list.

So, for example, you build a flat array of {name, phone, address} structs in whatever order you want, and then for each row, put a (phone -> row#) mapping into a hash table. Non-unique columns could hash to a list of row numbers, or you could put them in a binary tree where duplicate keys aren't an issue.

As far as space requirements, you basically end up storing every element twice, so your space requirement will at least double. On top of this you've got the overhead from the data structures themselves; keeping three hash tables loaded at ~70% capacity, your storage requirements increase by at least 2.4 times.

You can do away with one of these auxiliary lookup structures by keeping your main table sorted on one of the columns, so you can search on it directly in O(logN). However, this makes inserting/deleting rows very expensive (O(N)), but if your data is fairly static, this isn't much of an issue. And if this is the case, sorted arrays would be the most space-efficient choice for your auxiliary lookups as well.

Answer 5

in a phone book, the telephone number should be unique, address is unique, but the name could be duplicated.

so perhaps you can use hash table combine with linked list to approach this.

you can use any one or combination of the 'name, address, phone number' as hash key, if you simply use name as hash key, then linked list is needed to store the duplicated entries.

in this approach, search based on the hash key is O(1) efficiency, but search based on the other two will be O(n).

Answer 6

C or C++ or C#?

Use a list of classes

    public class PhoneBook
{
    public string name;
    public string phoneNumber;
    public string address;
}

place this in a list and you have a phone book

Answer 7

In C, I think a struct is the best option.

typedef struct _Contact Contact;

struct _Contact
{
    char* name;
    char* number;
    char* address;
};

Contact* add_new_contact( char* name, char* number, char* address )
{
    Contact* c = (Contact*) malloc( sizeof( Contact ) );
    c->name = name;
    c->number = number;
    c->address = address;
    return c;
}

Contact* phone_book [ 20 ];  /* An array of Contacts */

Use the standard string functions ( <string.h> or if using a C++ compiler, <cstring> ) or something like the glib for searching the names, numbers etc.

Here's a simple example:

Contact* search_for_number( Contact* phone_book[], const char* number )
{
    register int i;
    for( i = 0; i < sizeof( phone_book ); i++)
    {
       if ( strcmp( phone_book[i]->number, number ) == 0 ) return phone_book[i];
    }
    return NULL;
}

There is also a good, helpful code example over here.

Alternatively

You may be able to use linked lists, but since C or the C standard library doesn't provide linked-lists, you either need to implement it yourself, or to use a third-party library.

I suggest using the g_linked_list in the glib.