Implement a Phone Directory | DSA in C++ - Software Development PDF Download

Introduction

A phone directory is a common data structure used to store and manage contact information such as names and phone numbers. In this article, we will learn how to implement a phone directory in C++ using data structures and algorithms. We'll cover the basic concepts, provide example code, explain its functionality, and conclude with some sample problems to solidify your understanding.

Basic Overview of Phone Directory

A phone directory is a collection of contacts, typically organized by names or any other identifying key, along with their associated phone numbers. The primary operations performed on a phone directory include adding new contacts, searching for contacts, updating existing contacts, and deleting contacts.

Implementing the Phone Directory

There are several ways to implement a phone directory in C++. Let's explore three common approaches:

Using an Array of Structures

In this approach, we use an array of structures to store contact information. Each structure represents a contact, containing fields for name and phone number. The array provides an index-based lookup for efficient search operations.

Using a Linked List

In a linked list implementation, each node of the list represents a contact. The nodes contain fields for name and phone number, along with a pointer to the next node. This approach allows for dynamic memory allocation and flexible insertion and deletion of contacts.

Using a Hash Table

A hash table implementation utilizes a hash function to convert the contact's key (e.g., name) into an index in an array. Each array index holds a linked list of contacts with the same hash value. This approach provides fast average-case search, insert, and delete operations.

Sample Code and Explanation

Array of Structures Implementation

#include <iostream>

#include <string>

const int MAX_CONTACTS = 100;

struct Contact {

    std::string name;

    std::string phoneNumber;

};

Contact phoneDirectory[MAX_CONTACTS];

int numOfContacts = 0;

void addContact(const std::string& name, const std::string& phoneNumber) {

    if (numOfContacts < MAX_CONTACTS) {

        phoneDirectory[numOfContacts].name = name;

        phoneDirectory[numOfContacts].phoneNumber = phoneNumber;

        numOfContacts++;

        std::cout << "Contact added successfully.\n";

    } else {

        std::cout << "Phone directory is full.\n";

    }

}

void searchContact(const std::string& name) {

    for (int i = 0; i < numOfContacts; i++) {

        if (phoneDirectory[i].name == name) {

            std::cout << "Contact found: " << phoneDirectory[i].name << " - "

                      << phoneDirectory[i].phoneNumber << "\n";

            return;

        }

    }

    std::cout << "Contact not found.\n";

}

// Additional functions like updateContact and deleteContact can be added

int main() {

    addContact("John Doe", "1234567890");

    addContact("Jane Smith", "9876543210");

    searchContact("John Doe");

    searchContact("Alice Johnson");

    return 0;

}

Output:

Contact added successfully.

Contact added successfully.

Contact found: John Doe - 1234567890

Contact not found.

Explanation:

• We define a structure 'Contact' with 'name' and 'phoneNumber' fields.
• An array 'phoneDirectory' of structures is used to store the contacts.
• The 'addContact' function adds a new contact to the phone directory if space is available.
• The 'searchContact' function iterates through the contacts and displays the contact details if found.
• In the 'main' function, we add two contacts and search for them.

Linked List Implementation:

#include <iostream>

#include <string>

struct Contact {

    std::string name;

    std::string phoneNumber;

    Contact* next;

};

Contact* phoneDirectory = nullptr;

void addContact(const std::string& name, const std::string& phoneNumber) {

    Contact* newContact = new Contact;

    newContact->name = name;

    newContact->phoneNumber = phoneNumber;

    newContact->next = phoneDirectory;

    phoneDirectory = newContact;

    std::cout << "Contact added successfully.\n";

}

void searchContact(const std::string& name) {

    Contact* current = phoneDirectory;

    while (current != nullptr) {

        if (current->name == name) {

            std::cout << "Contact found: " << current->name << " - "

                      << current->phoneNumber << "\n";

            return;

        }

        current = current->next;

    }

    std::cout << "Contact not found.\n";

}

// Additional functions like updateContact and deleteContact can be added

int main() {

    addContact("John Doe", "1234567890");

    addContact("Jane Smith", "9876543210");

    searchContact("John Doe");

    searchContact("Alice Johnson");

    return 0;

}

Output:

Contact added successfully.

Contact added successfully.

Contact found: John Doe - 1234567890

Contact not found.

Explanation:

• We define a structure 'Contact' with 'name', 'phoneNumber', and 'next' (pointer to the next contact) fields.
• The 'addContact' function creates a new contact node, assigns the input values, and inserts it at the beginning of the linked list.
• The 'searchContact' function traverses the linked list and displays the contact details if found.
• In the 'main' function, we add two contacts and search for them.

Hash Table Implementation:

#include <iostream>

#include <string>

#include <unordered_map>

std::unordered_map<std::string, std::string> phoneDirectory;

void addContact(const std::string& name, const std::string& phoneNumber) {

    phoneDirectory[name] = phoneNumber;

    std::cout << "Contact added successfully.\n";

}

void searchContact(const std::string& name) {

    if (phoneDirectory.count(name) > 0) {

        std::cout << "Contact found: " << name << " - " << phoneDirectory[name] << "\n";

    } else {

        std::cout << "Contact not found.\n";

    }

}

// Additional functions like updateContact and deleteContact can be added

int main() {

    addContact("John Doe", "1234567890");

    addContact("Jane Smith", "9876543210");

    searchContact("John Doe");

    searchContact("Alice Johnson");

    return 0;

}

Output:

Contact added successfully.

Contact added successfully.

Contact found: John Doe - 1234567890

Contact not found.

Explanation:

• We use the 'unordered_map' container from the C++ Standard Library to implement the hash table.
• The 'addContact' function adds a new contact to the hash table, associating the name with the phone number.
• The 'searchContact' function checks if the name exists in the hash table and displays the contact details if found.
• In the 'main' function, we add two contacts and search for them.

Sample Problems and Solutions:

Problem 1: Implement a function to update the phone number of an existing contact in the phone directory.

void updateContact(const std::string& name, const std::string& newPhoneNumber) {

    if (phoneDirectory.count(name) > 0) {

        phoneDirectory[name] = newPhoneNumber;

        std::cout << "Contact updated successfully.\n";

    } else {

        std::cout << "Contact not found.\n";

    }

}

Problem 2: Implement a function to delete a contact from the phone directory.

void deleteContact(const std::string& name) {

    if (phoneDirectory.erase(name) > 0) {

        std::cout << "Contact deleted successfully.\n";

    } else {

        std::cout << "Contact not found.\n";

    }

}

Conclusion

In this article, we explored different approaches to implementing a phone directory in C++. We covered array of structures, linked list, and hash table implementations. Each approach has its own advantages and trade-offs. By understanding these implementations and their associated functions, you can efficiently store and manage contact information in your own phone directory applications.