Here is the code done in C

/*** PROBLEM 5.3: Insertion Sort ***/

/* Determines if the word is already in the list. If it is, then the number of * occurrences for that word is incremented. If it isn't, then a new node is * created for the word and inserted into the list at the correct alphabetic * location. Returns a pointer to the head of the list, which is either the * original head or a node containing the word (if the word occurs before the * original head's word or if the original head is NULL). */ struct node *insert_word(struct node *head, const char *word) { /* WRITE THIS FUNCTION */ return NULL; }

/* Gets the name of the book file from the user and reads the file line-by-line. * Under the assumption that there is exactly one word per line and that all * punctuation has been removed, this function builds a doubly-linked list * of the words in alphabetical order, keeping track (as part of a node's * payload) how many times each word occurs in the file. */ struct node *build_list() { const char *filename = get_input("Enter the name of the book file"); /* WRITE THE REST OF THIS FUNCTION */ return NULL; }

/*** PROBLEM 5.4: Respond to Challenge ***/

/* Given an alphabetically sorted list of words with the number of occurrences * of each word, and given the challenge_word, will return the response word * based on the following rules: * - If the number of occurrences is an even number then the response word is * that many places *before* challenge_word in the list * - If the challenge_word is fewer than that number of places from the head * of the list, then the response word is the word at the head of the list * - If the number of occurrences is an odd number then the response word is * that many places *after* challenge_word in the list * - If the challenge_word is fewer than that number of places from the tail * of the list, then the response word is the word at the tail of the list * - If challenge_word is not present in the list, then the response is * " is not present!" */ char *respond(const struct node *list, const char *challenge_word) { /* WRITE THIS FUNCTION */ return NULL; }

/*** main ***/

/* Prompts the user and reads the user's input from stdin. */ char *get_input(const char *prompt) { char *input = malloc(MAXIMUM_WORD_LENGTH); printf("%s: ", prompt); fgets(input, MAXIMUM_WORD_LENGTH, stdin); input[strlen(input) - 1] = '\0'; // eliminates the undesired newline character return input; }

int main() { struct node *list = build_list(); char *challenge_word = get_input("Enter the challenge word"); printf("Response word: %s ", respond(list, challenge_word)); return 0; }

5.3 Insertion Sort The insertion sort algorithm reads an input and then traverses a sorted list to find the proper location in the sorted list for the input. The input is then inserted into the list at that location. For this problem, the user will be prompted to enter the name of a book, which will be the filename of a file that contains all of the book's words. All punctuation has already been removed from the files, and each line in the file contains exactly one word. In problem5.c, write the code to read the file one line at a time. For each word, convert it to lowercase, and then traverse the list to find the appropriate place for the word. (Note that there will not be a list to traverse when your code reads the first word!) If the word is not in the list then create a node for that word and insert it into the list at the correct location. If there is already a node containing that word, then increment that node's variable that tracks the number of occurrences. If your program requires more than a few seconds to build the list, there is a bug in your code. 5.4 Respond to a Challenge After the word list is complete (after you have inserted all words in the file), the user will be prompted to enter the challenge word. In problem5.c, write the code to traverse the word list to find that word. (Do not copy the is_even() function into problem5.c; we will link to the function in problem3.c.) If the word is not present in the list, output (word) is not present!" where (word) is the challenge word. If the word is in the list then use the number of occurrences recorded in that word's node to find the response word as described in the challenge-and-response rules, and output that word. If your program does not provide the response word nearly instantaneously, there is a bug in your code. 5.3 Insertion Sort The insertion sort algorithm reads an input and then traverses a sorted list to find the proper location in the sorted list for the input. The input is then inserted into the list at that location. For this problem, the user will be prompted to enter the name of a book, which will be the filename of a file that contains all of the book's words. All punctuation has already been removed from the files, and each line in the file contains exactly one word. In problem5.c, write the code to read the file one line at a time. For each word, convert it to lowercase, and then traverse the list to find the appropriate place for the word. (Note that there will not be a list to traverse when your code reads the first word!) If the word is not in the list then create a node for that word and insert it into the list at the correct location. If there is already a node containing that word, then increment that node's variable that tracks the number of occurrences. If your program requires more than a few seconds to build the list, there is a bug in your code. 5.4 Respond to a Challenge After the word list is complete (after you have inserted all words in the file), the user will be prompted to enter the challenge word. In problem5.c, write the code to traverse the word list to find that word. (Do not copy the is_even() function into problem5.c; we will link to the function in problem3.c.) If the word is not present in the list, output (word) is not present!" where (word) is the challenge word. If the word is in the list then use the number of occurrences recorded in that word's node to find the response word as described in the challenge-and-response rules, and output that word. If your program does not provide the response word nearly instantaneously, there is a bug in your code