Background

Your team was tasked to manipulate records of all the employees at Carleton. The design team decided to use a linked list to accomplish the task. Your role is to code the required set of linked list functions. One of your teammates was tasked to code a test program for testing the code set of functions. Thus, you cannot deviate from the function definitions.

The following information is kept for each employee:

First Name

Family Name

Id

The design calls for the following structure

#define NAME_LENGTH 32

typedef struct personalInfo {

struct personalInfo *next;

unsigned int id; char firstName[NAME_LENGTH];

char familyName[NAME_LENGTH];

} PersonalInfo;

Provided Files

linked_list.h this file contains the definition of the linked link functions

linked_list.c this file contains the code of the linked list functions

main.c an example code for testing the linked list functions. Note that this is not a comprehensive set. A more comprehensive test program may be provided later.

Bubblesort.o a sorting file that can be used to test the removeDuplicates() function.

Makefile a makefile for generating the code

Compiling the test program:

In order to try the test program you will need to compile and link the test program with your code and the bubblesort function. For example use

gcc -g main.c linked_list.c bubble_sort.o

Coding Instructions:  

Add comments to code as provided in the slides given in class

No usage of global variables. All data must be passed or received via function parameters.

Each node in the linked list must be allocated independently of other nodes.

Test your program with valgrind to ensure that no memory leakage occurs.

This assignment will most likely be tested automatically using test program(s). Namely, your file linked_list.c and linked_list.h will be linked together with test programs. Therefore,

you cannot deviate from the function definitions. You are allowed however, to add additional functions (helper functions) to the file linked_list.c. These functions will not be tested.

6. Make sure that all pointers are initialized to NULL or set to NULL as needed.

Suggestions

Test functions - all functions with the exception of the functions in Part II will be quite short 2-10 lines of code. As you code design and implement test functions to ensure that your code covers all cases (e.g., head == NULL).

Part I Tasks (90 points)

In this part of the assignment you will code several basic functions used to manipulate a linked list. The files linked_list.c and linked_list.h contain the functions and their declarations. You will have to complete the body of the function. The description of each function in the linked_link.c file provides detailed information about the functionality of each function including input and output parameters and return value.

Code the following functions

1. Insertion Functions (18 points)

1.1. (6 points) Insert to list as the first node Purpose - create a new node and add it to the list as the first element Function declaration: PersonalInfo *insertToList(PersonalInfo **head, unsigned int id, char *firstName, char *familyName)

1.2. (6 points) Insert to list after a given record Purpose - create a new node and add it to the list after the given record Function declaration: PersonalInfo *insertAfter(PersonalInfo *node, unsigned int id, char *firstName, char *familyName)

1.3. (6 points) Insert a node at the end of the list Purpose - create a new node and add it at the end of the list Function declaration: PersonalInfo *insertLast(PersonalInfo **head, unsigned int id, char *firstName, char *familyName)

2. Search Functions (10 points)

2.1. (5 points) Search by name Purpose - search for the first node with the matching firstName Function declaration: PersonalInfo *searchByName(PersonalInfo *head, char *firstName)

2.2. (7 points) Search by id (5 points) Purpose - search for the first node with the matching id Function declaration: PersonalInfo *searchById(PersonalInfo *head, unsigned int id)

3. (35 points) Delete Functions 3.1. (6 points) Delete

Purpose - delete the first node/record from the list Function declaration:

int deleteFromList(PersonalInfo **head, unsigned int *id, char *firstName, char *FamilyName);

3.2. (10 points) Search by name and delete the node Purpose - delete the first node with the matching firstName

Function declaration: int deleteNodeByName(PersonalInfo **head, char *firstName, char *FamilyName, unsigned int *id)

3.3. (7 points) Delete the last node in the list Purpose - delete the last node in the list

Function declaration: int deleteLast(PersonalInfo **head, unsigned int *id, char *firstName, char *FamilyName)

3.4. (6 points) Delete After Purpose - delete the record after the given record

Function declaration: int deleteAfter(PersonalInfo *node, unsigned int *id, char *firstName, char *FamilyName)

3.5. (6 points) Delete the list and all the nodes Purpose - deletes all nodes from the list

Function declaration: void deleteList(PersonalInfo **head)

4. (5 points) Printing Functions 4.1. (0 points) Print a node

Purpose This function is already coded. Do not change it. Function declaration:

void printNode(PersonalInfo *node)

4.2. (5 points) Print the list Purpose - prints all the records in the list

Function declaration: void printList(PersonalInfo *head)

5. (10 points) Counting Functions 5.1. (5 points) Count the number of records in the list Purpose - counts the number of records in the list

Function declaration:

int listSize(PersonalInfo *head)

5.2. (5 points) Count specific records Purpose - counts the number of nodes in the list where the first name matches the provided key firstName

Function declaration: int countRecords(PersonalInfo *head, char *firstName)

6. (12 points) Miscellaneous Functions 6.1. (12 points) Remove Duplicate Records Delete

Purpose - removes all duplicates records from the list.

Duplicate records are determined by their first name. Note that the linked list is given in sorted order by the first name. This implies that if two employees have the same first name then the corresponding records would appear one after the other in the linked list.

Function declaration: void removeDuplicates(PersonalInfo *head)

bubble_sort.h

.

/* File name is bubble_sort.h Purpose: file contains a prototype for a bubble sort function Created By Doron Nussbaum Modifications: November 2017 - minor modifications Copyright 2017 */

#ifndef BUBBLE_SORT_2401_HEADER #define BUBBLE_SORT_2401_HEADER 1 /************************************************************************/ // INCLUDE FILES

#include "linked_list.h"

/************************************************************************/ // FUNCTION PROTOTYPES

void bubbleSort(PersonalInfo **head);

#endif

linked_list.h

/* File name is linked_list.h Purpose: file contains functions for manipulating singly linked list Created By Doron Nussbaum Modifications: November 2017 - minor modifications Copyright 2017 */

#ifndef LINKED_LIST_2401_HEADER #define LINKED_LIST_2401_HEADER 1

/************************************************************************/ // DEFINESD

#define NAME_LENGTH 32

/************************************************************************/

// STRUCTURES

typedef struct personalInfo { struct personalInfo *next; unsigned int id; char firstName[NAME_LENGTH]; char familyName[NAME_LENGTH]; } PersonalInfo;

/************************************************************************/ // FUNCTION PROTOTYPES

// Insert Functions PersonalInfo *insertToList(PersonalInfo **head, unsigned int id, char *firstName, char *familyName);

PersonalInfo *insertAfter(PersonalInfo *node, unsigned int id, char *firstName, char *familyName);

PersonalInfo *insertLast(PersonalInfo **head, unsigned int id, char *firstName, char *familyName);

// Search Functions

PersonalInfo *searchByName(PersonalInfo *head, char *firstName);

PersonalInfo *searchById(PersonalInfo *head, unsigned int id);

// Delete Functions int deleteFromList(PersonalInfo **head, unsigned int *id, char *firstName, char *familyName);

int deleteLast(PersonalInfo **head, unsigned int *id, char *firstName, char *familyName);

int deleteAfter(PersonalInfo *node, unsigned int *id, char *firstName, char *familyName);

int deleteNodeByName(PersonalInfo **head, char *firstName, char *lastName, unsigned int *id);

void deleteList(PersonalInfo **head);

// Print Functions void printNode(PersonalInfo *node);

void printList(PersonalInfo *head);

// Counting Functions int listSize(PersonalInfo *head);

int countRecords(PersonalInfo *head, char *firstName);

// Miscellaneous Functions

void removeDuplicates(PersonalInfo *head);

#endif

main.c

#include "stdio.h" #include "stdlib.h" #include "string.h"

#include "linked_list.h" #include "bubble_sort.h"

#define CONTINUE {printf("hit to continue "); getchar();}

void populatePerson(char *firstName, char *familyName, int *id);

int main(int argc, char* argv[]) { char firstName[NAME_LENGTH]; char familyName[NAME_LENGTH]; int id; struct personalInfo *empHead = NULL; struct personalInfo *p = NULL, *q = NULL; int i; int rc = 0; for (i = 0; i < 20; i++) { // add code for testing populatePerson(firstName, familyName, &id); insertToList(&empHead, id, firstName, familyName); }

printList(empHead);

printf("test SearchById "); q = p = searchById(empHead, 111); if(p == NULL) { printf("search by id failed "); } else { printNode(p); } CONTINUE; if (p != NULL) { for (i = 0; i < 4; i++) { populatePerson(firstName, familyName, &id); p = insertAfter(p, id, firstName, familyName); } } printList(empHead);

// test delete after rc = deleteAfter(q, &id, firstName, familyName); printf("deleteAfter rc = %d ",rc); printList(empHead); CONTINUE;

p = searchById(empHead, 111); if (p != NULL) { printf(" found name to delete "); printNode(p); strncpy(firstName, p->firstName, NAME_LENGTH); deleteNodeByName(&empHead, firstName, familyName, &id); }

bubbleSort(&empHead);

printf(" sorted list "); printList(empHead);

// getchar();

printf(" remove duplicates "); removeDuplicates(empHead); printList(empHead); deleteList(&empHead); // getchar();

return 0; }

/***************************************************************************/ /* purpose: the function populate the personal info

input/output struct personalInfo *p - allocated memory to the struct pointer which the function assigns values.

*/

void populatePerson(char *firstName, char *familyName, int *id) { static int initRand = 0; int j; char *first[5] = { "John", "Don", "Edna", "Bev", "Miya" }; char *family[5] = { "Broker", "Smith", "Tower", "Little", "Bronson" };

if (!initRand) { srand(1557); initRand ++; } // populate the first name using a random i ndex to the first name array j = rand() % 5; // copy the first name to the structure pointed by p using strcpy strncpy(firstName, first[j], NAME_LENGTH);

// populate the first name using a random i ndex to the first name array j = rand() % 5; // copy the family name to the structure pointed by p using strcpy strncpy(familyName, family[j], NAME_LENGTH);

// populate the student id using the random numnber in the range of 0-4096 *id = rand() % 150;

}

linked_list.c

/* File name is linked_list.c Purpose: file contains functions for manipulating singly linked list Created By Doron Nussbaum 2016 Modifications: November 2017 - minor modifications Copyright 2017 */

/******************************************************************/ // INCLUDE

#include "stdio.h" #include "stdlib.h" #include "string.h" #include "linked_list.h"

/************************************************************************/ // Define

/************************************************************************/

/* Purpose: insert a new node into the list as the first element input id - id of person firstName - first name of person familyName - family name of person

input/output head - head of linked list

return A pointer to the node that was allocated.

NULL - if the operation was not successful

*/

PersonalInfo *insertToList(PersonalInfo **head, unsigned int id, char *firstName, char *familyName) { // add code

}

/************************************************************************/ /* Purpose: insert a new node into the list after the given node

Input node - the node after which the new node must be added to the list id - id of person firstName - first name of person familyName - family name of person

return A pointer to the node that was allocated.

NULL - if the operation was not successful

*/

PersonalInfo *insertAfter(PersonalInfo *node, unsigned int id, char *firstName, char *familyName) { // add code

}

/************************************************************************/ /* Purpose: create a new node and insert it into the end of the list Input head - the head of the list id - id of person firstName - first name of person familyName - family name of person

return A pointer to the node that was allocated.

NULL - if the operation was not successful

*/

PersonalInfo *insertLast(PersonalInfo **head, unsigned int id, char *firstName, char *familyName) { // add code

}

/************************************************************************/ /* Purpose: search for the first node with the matching firstName Input head - the head of the list firstName - first name of person

return a pointer to the node that was found. NULL - if no node was found or list empty

*/

PersonalInfo *searchByName(PersonalInfo *head, char *firstName) { // add code

}

/************************************************************************/ /* Purpose: search for the first node with the matching id Input head - the head of the list id - id of person person

return a pointer to the node that was allocated.

NULL - if no node was found or list empty

*/

PersonalInfo *searchById(PersonalInfo *head, unsigned int id) { // add code }

/***************************************************************/

/* Purpose: delete the first node from the list Input head - the head of the list

output head - the head of the list firstName - first name of delted record familyName - family name of deleted recrod id - id of deleted record

return

0 if node was deleted 1 if node was not deleted or list is empty

*/

int deleteFromList(PersonalInfo **head, unsigned int *id, char *firstName, char *familyName)

{

// add code

}

/***************************************************************/

/* Purpose: delete the last node from the list Input head - the head of the list

output head - the head of the list firstName - first name of delted record familyName - family name of deleted recrod id - id of deleted record

return

0 if node was deleted 1 if node was not deleted or list is empty

*/

int deleteLast(PersonalInfo **head, unsigned int *id, char *firstName, char *familyName)

{

// add code

}

/************************************************************************/

/* Purpose: delete the record after the given node Input node - a node in the list

output firstName - first name of delted record familyName - family name of deleted recrod id - id of deleted record

return 0 if node was deleted 1 if node was not deleted (either input node is NULL or input node was the lastnode in the list)

*/

int deleteAfter(PersonalInfo *node, unsigned int *id, char *firstName, char *familyName)

{ // add code

}

/************************************************************************/

/* Purpose: delete the first node with the matching firstName Input head - the head of the list firstName - first name of person

output head - the head of the list firstName - first name of delted record familyName - family name of deleted recrod id - id of deleted record

return 0 if node was deleted 1 if node was not found (e.g., list is empty, no such node exists)

*/

int deleteNodeByName(PersonalInfo **head, char *firstName, char *familyName, unsigned int *id) { // add code

} /************************************************************************/ /* Purpose: deletes all nodes from the list input/output head - the head of the list

*/

void deleteList(PersonalInfo **head) { // add code

}

/************************************************************************/ /* Purpose: prints the fields of a node input: node - a pointer to a given node

*/

void printNode(PersonalInfo *node) { printf("%-20s %-20s %7d ",node->firstName, node->familyName, node->id);

}

/************************************************************************/ /* Purpose: prints all the records in the list

input head - the head of the list */

void printList(PersonalInfo *head) { // add code

}

/************************************************************************/ /* Purpose: counts the number of nodes in the list input head - the head of the list

return the number of nodes in the list

*/

int listSize(PersonalInfo *head) { // add code

}

/************************************************************************/ /* Purpose: counts the number of nodes in the list with a matching firstName input head - the head of the list

return the number of nodes in the list that match the firstName

*/

int countRecords(PersonalInfo *head, char *firstName) { // add code

}

/************************************************************************/ /*

Purpose: removes all duplicates records from the list. Duplicate records are determined by their first name. You can assume that the listed is sorted by first name.

input head - the head of the list

*/

void removeDuplicates(PersonalInfo *head) { // add code

}