b) You have been hired to write a ‘phonebook’ application for a small company. T
ID: 3845624 • Letter: B
Question
b) You have been hired to write a ‘phonebook’ application for a small company. The phonebook stores names of company employees and their associated phone- numbers. Given an employee name it should be possible to retrieve the employee’s phone number. It should also be possible to add a name and associated number when a new employee joins the company; and to delete a name and number when the named employee leaves the company.
i) Explain how you might implement the phonebook application using a doubly-linked list, paying attention to the operations for getting the phone number for a given name and adding and deleting employee phone numbers. [10 marks]
ii) Suppose the company becomes very successful and grows to the point where it has many thousands of employees. Is the implementation based on a doubly linked list adequate? Give reasons for your answer. [5 marks]
Explanation / Answer
a)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/*
This structure contains a template for records.
* Each record holds a Name, Phone number, and pointer to the next
* item in the list.
*/
struct entry {
int entry_number;
char *employee_name;
char *employee_number;
struct entry *prev;
struct entry *next;
};
/* Linked List pointers to head and current items */
struct entry *head = NULL;
struct entry *tail = NULL;
char MENU() {
char input;
printf("* Menu * ");
printf("A: Add employee ");
printf("P: retrieve employee number ");
printf("D: Delete employee ");
printf("Q: Quit ");
printf(" Enter Choice: ");
input = getchar(); //get character input
getchar(); //flush the newline/carrage return
return input;
}
/*
* Function: getInput
*
* Description: Grabs an input string from the user and stores it
* into a dynamically allocated memory location.
*
* Variables: char* - String to output to the user describing what to input
*
* Return: A pointer to the string location in memory
*/
char *getInput(char *outputString) {
char *userInput = NULL;
size_t inputBuffer = 0;
int inputCount = 0;
//allocate the userInput
//userInput = (char *)malloc(inputBytes+1);
//not needed with the getline function since it
//automatically calls realloc to manage the memory
printf("%s", outputString);
inputCount = getline(&userInput, &inputBuffer, stdin);
//remove the newline character from the string
userInput[inputCount-1] = '';
//return the user input
return userInput;
}
/*
* Function: insert_employee
*
* Descprition: Allocates a new record then stores the user input
* for the record name and phone number. This new item is then added to
* the end of the list.
*/
void insert_employee(){
struct entry *newentry = NULL;
//allocate memory for the new record
newentry = (struct entry*)malloc(sizeof(struct entry));
//get input and store it into each record variable
newentry->employee_name = getInput("employee Name: ");
newentry->employee_number = getInput("employee Phone Number: ");
newentry->next = NULL;
//set this item as the start of a new list or
//add it to the end of an existing list
if(head == NULL) {
newentry->entry_number = 1;
newentry->prev = NULL;
head = newentry;
tail = head;
}
else {
newentry->entry_number = tail->entry_number + 1;
newentry->prev = tail;
tail->next = newentry;
tail = tail->next;
}
}
/*
* Function: print employee number
* Description: Prints the entry associated with the pointer passed in
*/
void printOneRecord(struct entry *currentPointer){
printf("*** Record: %d *** ", currentPointer->entry_number);
printf("Name: %s ", currentPointer->employee_name);
printf("Phone: %s ", currentPointer->employee_number);
}
/*
* Function: searchRecords
*
* Description: Searchs the list comparing each records name entry
* with a search string. When a match is found the pointer to that
* entry is returned.
*
* Return: pointer to the found list entry or NULL if nothing is found
*/
struct entry *searchRecords(char* searchName){
struct entry *listPointer = NULL;
int temp;
//if head is null then the list is empty
if(head == NULL) {
printf("Records empty ");
}
else {
listPointer = head; //start at the beginning
//loop through the list looking for a match
//if a match is found return the pointer
//if not print an error and return NULL
while(listPointer != NULL) {
if(strcmp(listPointer->employee_name, searchName) == 0) {
return listPointer;
}
else {
listPointer = listPointer->next;
}
}
printf("Record %s not found ", searchName);
}
return NULL;
}
/*
* Function: deleteemployee
* Description: Delete entry referenced by pointer.
*/
void deleteOneRecord(struct entry *listPointer) {
if(head == tail) {
//delete single item list
head = NULL;
tail = NULL;
}
else if(listPointer == head) {
//delete head
head = listPointer->next;
head->prev = NULL;
}
else if(listPointer == tail) {
//delete tail
tail = listPointer->prev;
tail->next = NULL;
}
else {
//delete non head/tail record
listPointer->next->prev = listPointer->prev;
listPointer->prev->next = listPointer->next;
}
//free the memory location
free(listPointer);
}
/*
* Function: cleanupList
* Description: Moves through a linked list freeing all memory locations
*/
void cleanupList() {
struct entry *tempPointer = NULL;
//loop through the list clearing each record
while(head != NULL) {
tempPointer = head;
head = head->next;
free(tempPointer);
}
}
/*
* Function: main
*
* Description: Handles menu options and calls all function
*/
int main() {
char menuInput = '';
struct entry *tempPointer = NULL;
char *searchName;
//loop through the program until the user selects Q
do {
//get the user input
menuInput = MENU();
//work on the user input
switch(menuInput) {
case 'a':
case 'A': //add a record to the list
printf("Adding User... ");
insert_employee();
break;
case 'p':
case 'P': //search by name matching
printf("Finding Record... ");
if(head == NULL) {
printf("Empty List ");
}
else {
searchName = getInput("Search Name: ");
tempPointer = searchRecords(searchName);
//if the pointer is null, nothing was returned
//so don't try to print
if(tempPointer != NULL) {
printOneRecord(tempPointer);
tempPointer = NULL;
}
}
break;
case 'd':
case 'D'://delete a record
printf("Deleting Record... ");
if(head == NULL) {
printf("Empty List ");
}
else {
searchName = getInput("Delete Name: ");
tempPointer = searchRecords(searchName);
//if the pointer is null, nothing was returned
//so don't try to print
if(tempPointer != NULL) {
deleteOneRecord(tempPointer);
tempPointer = NULL;
}
}
break;
case 'q':
case 'Q': //quit the program loop
printf("Goodbye! ");
cleanupList();
break;
default:
printf("ERROR: Invalid Menu Option ");
break;
}
}
while(menuInput != 'q' && menuInput != 'Q');
return 0;
}
b)yes,it is adequate. since we are allocating memory dynamically and not storing any unnecessary data, the storage space used is less. so even though employees increase, this program can be implemented. here even the input from the user is taken into a variable to which memory is allocated dynamically and that memory is managed.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.