Introduction

This homework assignment gives you the opportunity to practice array of pointers, linked lists and self referential structures. There is a basic version and an extra credit version. If you want to attempt the extra credit version, I recommend you implement and have the basic version working first. The extra credit version builds upon the basic version, and the basic version is a safety.

Write a program that initializes two parallel arrays as follows:

char * String[] = { "Abbie", "Oakley", "Sylvia", "Uwe", "Ken", "Aaron", "Fabien" };

double GPA[] = {3.8, 3.0, 3.9, 2.0, 2.5, 4.0, 3.2};

Then the program takes the strings and GPAs from the arrays one by one, starting from element index 0, populates the studentRecord structure below and inserts the structure in a linked list which is initially empty. The structure should be inserted in the right location, so as to maintain the lexicographic order of the strings. The structures in the linked list are printed after every insertion, with the structures being printed in the order they appear in the list. Finally, after all the array elements are inserted, the program should print again the complete content of the linked list, with the structures being printed in the order they appear in the list. If your program is correct, the order in which the strings and GPAs are printed should be:

Aaron, 4.0, Abbie, 3.8, Fabien, 3.2, Ken, 2.5, Oakley, 3.0, Sylvia, 3.9, Uwe, 2.0.

Additional requirements

1. Follow the requirements in the Homework Notes.

2. To ensure consistency in the submissions, your program must do the following: Use this self referential structure struct studentRecord // Self referential structure used in linked list { char name[NAME_LENGTH + 1]; // set NAME_LENGTH to 10 double GPA; struct studentRecord * nextPtr; }; For convenience, it is recommended you use typedefs: typedef struct studentRecord Student; // Student is an alias for struct studentRecord typedef Student * studPtr; // studPtr is a pointer to Student

3. To create the Student self referential structures, your program must use malloc()

4. You must populate the linked list through a loop. You are not allowed to create the 7 Students of the list by writing 7 assignment statements, one for each Student in the list

5. Your program must work for any set of strings used as input, not just the ones given

6. You are allowed to use the strcmp() and strcpy() functions from the C library (see section 8.6, 8.7 of textbook or the Internet for details). You are only allowed to use functions and features of C that have already been taught in class, or in the hints provided. You will not get credit if you use existing functions in the C library not taught in class, unless explicitly told you are allowed.

7. Your program should implement the functions whose prototypes are given below

// Function prototypes

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

/* This function inserts newName and newGpa into the linked list pointed by *sPtr Walks through the list to find the right location for insertion Insertion is done in lexicographic order of the student's name Note: sPtr is a pointer to a pointer, and *sPtr points to the first Student of the list, or is NULL if the list is empty */

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

void insert(studPtr *sPtr, char * newName, double newGpa);

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

/* Print the Student pointed by myPtr

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

void printStudent(studPtr myPtr);

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

/* Prints the elements of the linked list pointed by myPtr */

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

void printList(studPtr myPtr);

8. Pseudocode for the program

1 - Create a linked list of self referential structures (each self referential structures is called Student) and initialize the list to empty

2 - Take the strings from String[] and the GPA from GPA[] one by one, and for each (string, GPA) do the following

Call insert

Call printList

3 Call printList

Lexicographic order of character strings

Let a and b two strings of characters. Assume first that they have the same number of characters:

a1a2 ... ak

b1b2 ... bk

Rule 1 - If at the first i where ai and bi differ, the character ai < bi, then a < b.

Rule 2 - If at the first i where ai and bi differ, the character ai > bi, then a > b.

Rule 3 - If ai = bi for all i <= k, a = b.

Now let us consider the case where the strings do not have the same number of characters. Assume a has k characters and b has m characters, where m > k.

Rule 1 - If at the first i where ai and bi differ, the character ai < bi, and i <= k, then a < b.

Rule 2 - If at the first i where ai and bi differ, the character ai > bi, and i <= k, then a > b.

Rule 3 - If ai = bi for all i <= k, then a < b

For example, consider the strings "Thomas" and "Thompson". The 5th character is the first that is different in the two strings ('a' vs. 'p'). Because 'a' < 'p', "Thomas" < "Thompson".

Another example is Thomas and Thom. Since all the first four characters match and Thom is shorter, Thom < Thomas.

You are allowed to use the strcmp() function from the C library that compares two strings according to the lexicographic order.

Extra Credit Version

You may earn up to 10 points extra credit if, in addition to the above, you implement the following. Your program should display a menu asking the user to choose (1, 2, 3, or 4). Option 4 is to quit. As long as the user does not choose to quit, the program loops over displaying the menu. Your program must also do input validation and print an error message if the user types anything other than 1, 2, 3 or 4, then display the menu again and ask the user to reenter the users choice.

1) Add a student to the list: The user is prompted to type a name and a GPA, then the program builds a structure, then inserts it in the list in the right location, according to the lexicographic ordering The list is then printed for verification

2) Delete a student from the list: The user is then prompted to type a name, and the program searches for the name. If the name is found, the program deletes the structure from the list The program prints a message: Deleted or Student not found. The list is then printed for verification. Delete is case insensitive. For example, if the user types fabien, Fabien will be deleted.

3) Search for a student: The user is then prompted to type a name, and the program searches for a student of that name The program prints a message: Found at location x in the list, where x is the location of the structure in the list (The first structure is at location 1) or Student not found. The list is then printed for verification. Search is case insensitive. For example, Uwe will be found if the user types UWE.

4) Quit

For the extra credit, you should implement these additional functions:

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

/* Displays the menu and returns the user's choice as an int */

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

int getUserChoice();

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

/* Searches for Student in the list by name and deletes it If student not found, return 0. Else, if deletion successful, return 1*/

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

int delete(studPtr *sPtr, Student myStud);

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

/* Searches for Student in the list by name If student is found, return the location of the student. For example, returns 2 if the student is second in the list. If the student is not found, returns 0. If the list is empty, returns -1 */

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

int search(studPtr curPtr, char *name);

Note: You are allowed to use the toupper() and tolower() functions from the C library. Google or refer to section 8.3 of the textbook for details.