#include #include #include

// define employee structures

#define NAME_LENGTH 16

typedef struct name { char firstName[NAME_LENGTH]; char familyName[NAME_LENGTH]; } Name;

typedef struct emp{ unsigned int id; float salary; Name name; } Employee;

// define employee operations

void printEmployee(Employee *emp) { printf("%-16s %-16s %8d %8.2f ", emp->name.firstName, emp->name.familyName, emp->id, emp->salary);

}

void initEmployee(Employee *emp, char *firstName, char *familyName, unsigned int id, float salary) { strncpy(emp->name.firstName, firstName, NAME_LENGTH - 1); strncpy(emp->name.familyName, familyName, NAME_LENGTH - 1); emp->id = id; emp->salary = salary;

}

// define linked liststructures

typedef struct listNodeStruct ListNode;

struct listNodeStruct { Employee *data; ListNode *next; // next node in the linked list };

// define linked list operations

/***********************************************************/ /* Purpose: adds a record as the first node of the linked list input: head - head of the list data - a pointer to an Employee record

Output head - the updated head of the list

Return 0 - if data was successfully added to the list 1 - if node was not added to the list */

int addNode(ListNode **head, Employee *data) {

ListNode *p = NULL;

// Step 1 allocate memory for the node and initialize all pointers to NULL // if an error then return 1

// Step 2 assign the employee record to data

// Step 3 update the next field of the new node to point to the first node in the list as a "next" node

// Step 4 update the list head to point to the new node. // return(0);

}

/***********************************************************/ /* Purpose: prints the list from the first node to the last node input: head - head of the list

Output None

Return None */

void printList(ListNode *head) {

// while list is not empty // print the node (using the printEmployee() function from employee.c) // advance to the next node

}

/***********************************************************/ /* Purpose: prints the list from the first node to the last node using recursiion input: head - head of the list

Output None

Return None */

void printListRecursive(ListNode *head) {

// check bounary conditions (list is not empty)

// do work - print the first node using the function printEmployee()

// make recursive call with the next node

}

/***********************************************************/ /* Purpose: prints the third last record in the list input: head - head of the list

Output None

Return 0 if successful 1 if an error occur (e.g., list does not have three nodes) */

int printThirdLast(ListNode *head)

{

// check bounary conditions - here the recursion stops when the // third last node record is reached. Note that the list may // not have three nodes

// if the third last node was reached then print the data // else make recursive call // return the result of the recursive call return(0);

}

/***********************************************************/ /* Purpose: prints the list in reverse from the last node to the first node using recursiion input: head - head of the list

Output None

Return None */

void printListInReverse(ListNode *head) {

// check bounary conditions

// make recursive call

// do work

}

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

Output head - the updated head of the list data - the data that was stroed in the record

Return none */

void deleteNode(ListNode **head, Employee **data) {

ListNode *p = NULL;

*data = (*head)->data; // Step 1 // if the list is empty then // set data to NULL // return // else set p to the point to the first node

// Step 2 assign the data in the node to the output data

// Step 3 set the head to point to the next node in the list

// Step 4 free the node pointed to by p and set p to NULL

} /***********************************************************/

int main(void) { int i; Employee employee[5]; Employee *data = NULL;

initEmployee(&employee[0], "Joe", "Clark", 567890345,100345); initEmployee(&employee[1],"Brian", "Mulroney", 567890767, 178983); initEmployee(&employee[2],"Jean", "Chretien", 567345890, 190329); initEmployee(&employee[3],"Paul", "Martin", 567899528, 192456); initEmployee(&employee[4],"Kim", "Campbell", 567436582, 192234);

printf("array of employees "); for (i = 0; i

ListNode *empHead = NULL;

// add five nodes for (i = 0; i

printf(" Printing the list from the first node to the last node "); printList(empHead);

printf(" Recursive printing of list "); printListRecursive(empHead); printf(" Reverse printing of list "); printListInReverse(empHead);

printf(" Printing the third last node in the list "); printThirdLast(empHead); // delete five nodes /* for (i = 0; i 3.1 Introduction In this part you will implement several basic linked list functions. The linked list is designed to manipulate and store employee records. Here we term the field that holds the employee information "data". The reason is that in general one would implement a generic linked list that can be used with any data type (using void *). Get myLinkedList.c in which you are given employee structures and operations as well as the linked list structures and the main function. You have to complete the following six functions for the linked list: a. addNode-adds a record as the first node of the linked list b. printList- print the list from the first node to the last node c. printListRecursive print the nodes from first to last using recursion d. printThirdLast -print the third node from the end of the list e. printListinReverse -prints the list in reverse from the node to the first node using recursion deleteNode- delete the first node from the linked list. f. 3.2 Task 1 Implement the function addNode). This function should add the new employee to the linked list as the first node seudo cod Follow the pseudo code in the course slides ListNode *p NULL; // Step 1 allocate memory for the node and initialize all the pointers to NULL // Step 2 assign the employee record to data // Step 3 update the next field of the new node to point to the first node in the list as a next node // Step 4 update the list head to point to the new node Check your code using valgrind. Valgrind should show that five blocks of code were used Step 1 Step 2 Step 3 tep 4 3.3 Task 2 Implement the function printList). This function should print the linked list from the first node to the last node This function should be implemented using the iterative approach of traversing the list. This is a simple "for" loop. The function needs to traverse the list until it reaches the sentinel condition. Here the sentinel is a NULL. The sentinel indicates that end of the list when the pointer "next" is null. Note, that here one can take advantage of the fact that the parameter "head" is a call by value and therefore its value can be changed without any side effects outside the function. Be sure to use the printEmployee function in employee.c Pseudo code // While list is not empty //Print the node using the printEmployee() function // advance to the next node 3.4 Task 3 Implement the function printListRecursive(). This function should print the linked list from the first element of the list to the last element in the list. This function should be implemented as a recursive function. Pseudo code // Check boundary condition (list is not empty) /Do work -Print the first node using the function printEmployee) Call the function recursively with the next node Note, printing the list in reverse order can be easily achieved by changing the order of the "do work" step and the "recursive call" step Print the list in reverse order using the function printListinReverse). 3.5 Task 4 Implement the function printThirdLas). This function should print the node in the linked list that is the third last. For example: if the linked list consists of H--2->5->47-29->1->lll then the function should print 7 This function should be implemented using the recursive approach of traversing the list. Namely it should be a recursive function. Test your function using lists of length 0, 1, 2, 3, and 5 Note that here the boundary conditions are somewhat more complex because one must ensure that the list has at least three nodes. If the list has less than three nodes then the function should return a 1 otherwise the function should return a 0 Take a few minutes to determine the tests that check if a list has at least three nodes. Check your solution against the one described below. Note that using the ideas of solution below will allow you to determine if the list has exactly three nodes Pseudo code // If the list has less than three nodes return a // If the list has exactly three nodes then //print the first node using the function printEmployee(0 /return a 0 ll else Il Call the function again with the next node /return the result of recursive call Testing if the list has less than three nodes: 1. Check if the list is empty (head is NULL) 2. Check if the list has only one node-check if the next" field of the first node is NULL (e.g., head->next is NULL) 3. Check if the list has only two nodes - check if the "next" field of the second node is NULL (e.g., head->next->next is NULL)