Assignment
This assignment gives you the opportunity to practice array of pointers, linked lists and self referential structures.
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 - Make sure you meet all the requirements to avoid losing points
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 you are explicitly told you are allowed.
Suggestions for implementation
1 - Your program can 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);
2. 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
Reference implementations
You are allowed to use and adapt as needed the example implementations for a linked list (insert, printList, etc.) in the Unit7-1 lecture slides.
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.
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 user's 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 may want to 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.