Lab 5: Search, and Linked Lists

1
APS 105 — Computer Fundamentals
Lab 5: Search, and Linked Lists
The goal of this laboratory is to practice the material on linked lists. You will be writing a C program that
maintains a personal phone book. This lab is conducted in two weeks.
Instructions:
• Your final solution is marked by your TA during the second lab period. There is a partial mark that
will be assigned during the first period and the remaining marks will be assigned during the second
period.
Objective
In this lab the task is to write a program that maintains a personal phone book. The program allows to:
§ Add and Delete entries from the phone book,
§ Search the phone book for a specific entry by last name or by phone number, and
§ Print out the entire entries in the phone book.
The data in the phone book is maintained by storing in memory with the use of a singly linked list, with
one list node per entry. Each node contains members for storing a person’s family name, first name, address,
and the phone number. Use strings to store this information. The linked list must be kept in increasing
alphabetical order, sorted by family name. There are no duplicate entries with the same family name
allowed in the phone book.
This program should be menu driven, with the user being offered a choice of the following commands
described below:
§ Insert a new entry into the phone book.
The program should prompt the user for a new family name and first name, an address and a phone
number. This information should be placed in a new node that has been created dynamically using
the malloc function. And then the node should be inserted at the proper place within the linked list
so to maintain an increasing alphabetical order by the family name. If a node with the given family
name is already in the phone book, an error message should be produced, and the new node should
not be inserted into the linked list. (Note: only identical family names would result in a error
message and rejection of the entry.)
§ Delete an entry from the phone book.
The program should prompt the user for the family name to be deleted and then delete the node
containing that family name from the linked list that stores the phone book. If no node with the
given family name is found in the phone book, an error message should be printed.
§ Search for a family name in the phone book.
The program should print the family name, first name, address and phone number of the entry, with
each piece of information on a separate line. If no node with the given family name is found in the
phone book, an error message should be printed.
§ Search for a phone number in the phone book.
The program should print the family name, first name, address and phone number of the entry, with
each piece of information on a separate line. If no node with the given phone number is found in
the phone book, an error message should be printed.
§ Print the phone book.
2
Print the list in alphabetical order by the family name, first name, address and phone number of
each entry, with each piece of information on a separate line. An extra blank line should be printed
between each phone book entry.
§ Quit the program.
When the program is given the quit command, it should delete all of the nodes in the linked list
by using calls to the free function. It should then try to print the linked list.
Your task is to write a complete C program that maintains a personal phone book. Your C program must
go in a file named lab5.c.
You must use a skeleton file that is from a complete program and is called lab5_Skeleton.c. This file is
posted under Files/Labs/Lab5_6 on the course website.
The skeleton program includes all of the C statements required to implement the menu driven parts of the
program. It also includes a few helpful functions for reading data and printing messages. All you need to
do is to implement the instructions for working with the linked list that stores the personal phone book.
The following steps are recommended:
§ Read the whole skeleton program carefully. Take note of the provided functions for reading
strings, printing names, addresses and phone numbers, and for printing error messages. Use of these
functions makes it easier for you to satisfy the tester and marker programs.
§ Figure out how to express the required phone book information in a node. Add a struct definition
for a linked list node to the program.
§ Add the function for inserting a node into the linked list. Your function will need to read the family
name, first name, address, and phone number for the entry. Test your program by trying to insert
nodes into the linked list. Try to insert nodes with both new and duplicate family names.
§ Add a function for printing the linked list. Test your program by inserting entries into the linked
list and then printing them out. Check if the results are in an increasing alphabetical order by the
family names.
§ Add a function that searches the linked list for a given family name and then either prints the
appropriate entry or, if a node is not found, prints an error message.
§ Add a function that searches the linked list for a given phone number and then either prints the
appropriate entry or, if a node is not found, prints an error message.
§ Add the statements that need to be executed when the Quit command is entered. These statements
should delete the linked list by using calls to the free function. To check your work, print the linked
list after the elements have been deleted.
§ Add a function for deleting a phone book entry. It will need to search the linked list for a given
family name, delete the appropriate node from the linked list and then use the free function to
release the memory used to store the node. If the given family name is not found in the phone book,
print an error message.
It is recommended that you test your program after attempting to complete each step. This way, if your
program is no longer working properly then you can quickly determine which statements are more likely
causing the error. Complete each step before moving on to the next one.
Sample Output from Executing the Program
Here is a sample output from an execution of the program that you are to write. There is one space after
each colon (:).
Personal Phone Book Maintenance Program.
Commands are I (insert), D (delete), S (search by name),
 R (reverse search by phone #), P (print), Q (quit).
3
Command?: I
family name: James
first name: LeBron
address: 1600 Pennsylvania Avenue
phone number: 202-456-1111
Command?: P
My Personal Phone Book:
James
LeBron
1600 Pennsylvania Avenue
202-456-1111
Command?: I
family name: James
first name: Lyle
address: 40 St. George St
phone number: 416-978-3965
An entry for <James> is already in the phone book!
New entry not entered.
Command?: S
Enter family name to search for: James
The family name <James> was found in the phone book.
James
LeBron
1600 Pennsylvania Avenue
202-456-1111
Command?: R
Enter phone number to search for: 202-456-1111
The phone number <202-456-1111> was found in the phone book.
James
LeBron
1600 Pennsylvania Avenue
202-456-1111
Command?: S
Enter family name to search for: Jordan
The family name <Jordan> is not in the phone book.
4
Command?: R
Enter phone number to search for: 202-555-1212
The phone number <202-555-1212> is not in the phone book.
Command?: D
Enter family name for entry to delete: Curry
The family name <Curry> is not in the phone book.
Command?: D
Enter family name for entry to delete: James
Deleting entry for family name <James> from the phone book.
Command?: P
The phone book is empty.
Command?: Q
The phone book is empty.
Good Luck!