Before you begin...

Make a copy of your boggle.c file as boggle2.c by invoking the command 
johnKerry@sf3:~[120]$ cp boggle.c boggle2.c
Part 2 is to be modified using boggle2.c and submitted at the end of the session.

Overview - A better dictionary implementation

In Part 1, we noticed that implementing the dictionary using a linked list where each node contains only one word is very inefficient. The objective of this lab is to improve on the design of the dictionary. A linked list will still be used; however, each node now stores an array of 1000 words.

Getting Started

We need to create a new structure that is a modification of the existing WordNode structure. Note that we cannot simply modify the existing structure because it is also used by the list of words that is found during the playing of the game. This new structure is partially defined as follows: 
   #define MAX_WORDS  1000

   typedef struct WordArrStruct WordArrNode;
   typedef WordArrNode *WordArray;
   struct  WordArrStruct {
      char *words[MAX_WORDS];
      WordArray next;
      /* Fill in other members if required */
   };
If you are not familiar with the usage of WordArray, then you can use WordArrNode * instead. In the main function, you will change the declaration of dict to 
   WordArray dict; /*   WordArrayNode *dict;   */

Modify the ReadDictionary function such that the first one thousand words is stored in the words array of the first node, the following one thousand words is stored in the words array of the second node, and so on. Here we assume that the words read from the dictionary file is sorted, so the words array in a node should also be sorted. You only create new nodes when deemed necessary. As an example, in order to store 25143 words, you will eventually need a linked list of 26 nodes in which the array words in each of the first 25 nodes is fully occupied, while the corresponding array in the last node stores only 143 words.

Hint: In part 1, you dynamically allocated one array of characters for each word in a node. Here, you will need to allocate multiple such arrays, one for each of the elements of the string array words.

Moreover, you will need to modify the search for an occurrence of a word in the new dictionary linked list. You need to modify the function header of PlayBoggle function accordingly, and replace the statement 

   if (WordInList(dict,word))
with 
   if (WordInDict(dict,word))
Implement the function WordInDict with the appropriate function prototype and function header. This function should perform the following tasks.
  1. Perform a linear search on the linked list and find out which node holds the array that is likely to contain the word.
  2. In the node determined above, perform a binary search on the array to locate the word. You will need to write another BinarySearchWord function.
  3. The function will return 1 if the word is found; and 0 otherwise.

You are allowed to define your own functions if necessary to make your implementation more modular.