Phone Directory Implementation in C++
By Ramneeq SodhiHere we are going to make our own C++ program to make a phone directory. So what is a phone directory and how to create it? A phone directory is a collection of data, which consists of names of people and their phone numbers. To create a phone directory, we will use a data structure trie. Its search complexity is equal to that of the key length. The nodes of trie contain alphabets and these nodes are connected to further tries thus they form a tree. When a word is finished, we mark it as finished in a trie as shown in the diagram.
C++ Program to create phone directory
#include <bits/stdc++.h>
using namespace std;
// global declaration of contact list
string contactList[] = {"phantom" , "phone","phul"};
struct TrieNode
{
// every trie Node contains a Map 'child'
// in which each alphabet points to another trie node
unordered_map<char,TrieNode*> child;
// 'lastLetter' is true if the node represents
// end of a contact
bool lastLetter ;
// Constructor
TrieNode()
{
// Initializing all nodes as null
for (char i = 'a'; i <= 'z'; i++)
child[i] = NULL;
lastLetter = false;
}
};
// Making root NULL for ease so that it doesn't
// have to be passed to all functions.
TrieNode *root = NULL;
// Add contacts int trie node
void AddContact(string s)
{
int length = s.length();
// 'head' is used to iterate the Trie Nodes
TrieNode *head = root;
for (int i = 0; i < length; i++)
{
// Check if the s[i] is already present in
// Trie
TrieNode *nextNode = head->child[s[i]];
if (nextNode == NULL)
{
// If not found then create a new TrieNode
nextNode = new TrieNode();
// Insert into the Map
head->child[s[i]] = nextNode;
}
// Move the head, to point to next
// Trie Node
head = nextNode;
// If its the last character of the string 's'
// then mark 'lastLetter' as true
if (i == length - 1)
head->lastLetter = true;
}
}
// This function simply displays all contacts in
//phone directory.
// teaverse current node. String 'pre'
// stands for string corelating to the path from
// root to currentNode.
void showContactsTil(TrieNode *currentNode, string pre)
{
// Checking if string 'pre' ends here
// If yes then display the string till now
if (currentNode->lastLetter)
cout << pre << endl;
// Find the Nodes adjecent to the current
// Node and then recursively call the function
for (char i = 'a'; i <= 'z'; i++)
{
TrieNode *next = currentNode->child[i];
if (next != NULL)
showContactsTil(next, pre + (char)i);
}
}
//this function show contacts
//as user inputs a letter, for example
//if user inputs "phu" then first it will show
//all contacts starting from p then from ph
//and finally from phu if no contact is present
//then is will tell no result is found.
void showContacts(string str)
{
TrieNode *previousNode = root;
string pre = "";
int length = str.length();
// Display the contact List for string formed
// after entering every character
int i;
for (i=0; i<length; i++)
{
// 'pre' stores the string formed so far
pre += (char)str[i];
// Get the last character entered
char lastChar = pre[i];
// Find the Node corelating to the last
// character of 'pre' which is pointed by
// prevNode of the Trie
TrieNode *currentNode = previousNode->child[lastChar];
// If nothing found, then break the loop as
// no more prefixes are going to be present.
if (currentNode == NULL)
{
cout << "No result found "<<" " << pre
<< endl;
i++;
break;
}
cout << "Suggesions for" <<" "<< pre<<" "
<< "are "<< endl;
showContactsTil(currentNode, pre);
// Change prevNode for next pre
previousNode = currentNode;
}
for (; i<length; i++)
{
pre += (char)str[i];
cout << "no contact found for"<<" " << pre
<< endl;
}
}
// Insert all the Contacts into the Trie
void insertInDirectory(string contacts[],int n)
{
// Initialize root Node
root = new TrieNode();
// Insert each contact into the trie
for (int i = 0; i < n; i++)
AddContact(contacts[i]);
}
int main()
{
// Size of the Contact List
int n = sizeof(contactList)/sizeof(string);
insertInDirectory(contactList, n);
string Search = "phum";
showContacts(Search);
return 0;
}
function implementation
- InsertInDirectory
this function names in the phone directory - AddContact
this function adds the contact to directory - showContacts
this function displays contact letter by letter suppose user gives an input “p” it will show all contacts starting from “p“if the user then gives input as u then it will show all contacts starting from “pu”. - showContactsTil
this function displays all contacts from the phone directory starting from a pedicular prefix.
Implementation
To add contacts, we have made a global string array in which we can add contacts. Then we have called a function “InsertInDirectory” this function runs a loop and adds one string at a time from the array to the phone directory by calling the function “AddContact”. To search a contact, we have created a search string, the program will be going to search then, this string in phone directory letter by letter and going to display all the contacts letter by letter, as explained above.
To search we will call the function showContacts this will first check if there is a contact present starting from the 1st letter of the search string if yes then it will call showContactsTil, this function will show all the contacts starting from the letter.
For example-:
let’s assume the phone directory has two contacts {Ram, Raghav} and the search string is {Rishabh}.
So “showContact” first will check if there are any contacts starting from “R” if yes (as in our case) then it will call “showContactsTil” and this function will show all the contacts staring form “R”. Then “showContact” will check is there any contact which starts from “Ri”, as there is no contact starting from “Ri” thus it will return no contacts are found.
Output
Noe it’s time to run our code. Below is the result that we will see after running our code:
Suggestions based on p are phantom phone phul Suggestions based on ph are phantom phone phul Suggestions based on phu are phul No contact Found for phum
Leave a Reply