Lab3: Dictionary Array

Due Date: Tue, 17 Feb 2008 by 23:59

Background:

Lab3 will implement a dictionary that is implemented via a dynamically allocated array of dynamically allocated char pointers. You will apply all that you have learned so far about arrays, pointers, passing pointers, malloc and free.

What You'll Need

Here is some demo code that declares an array of char pointers (char**) in main such as you will need. It also shows you how to pass the address of that array's pointer to a function that mallocs the array of pointers and loads the array from an input file. You can copy it from /afs/qatar/course/15/123/dist/lab3-starter.c

Study this demo code carefully. It is important to understand that all the strings are hanging from the pointers in the array. Also pay attention to the syntax. Notice that when we wish to assign something into one of the pointers in the array we use (*array)[index] and that we MUST parenthesize (*array). Why?

You should use the input files that are provided below (all can be copied from /afs/qatar.cmu.edu/usr9/yeng/15123/Lab3/data/):

• 10-words.txt (test file of 10 words - use this first!)
• 105-words.txt (test file of 105 words)
• 42K-words.txt
• 172K-words.txt DON'T use this one until you are SURE you're done!

Start with the small ones first (in particular, you should use 10-words.txt to make sure basic functionality works before going on to write the double-capacity function, which you can then test with 105-words.txt and beyond.

Assignment:

In your main, you must pass the array to a loadDictionary() function that will open the input file, read in all the strings, and then close the input file. Your load must also update the wordCount. As you read in words from the file, keep the dictionary in sorted (lexical) order at all times. You may not load the entire array in original order and then call a sort afterwards. Keeping an array sorted in this manner is called insert-in-order.

Your initial allocation for the array should be space for 50 pointers. If the array ever gets full (i.e., wordCount equals current capacity), and there's a word to insert, you will double the capacity of the array (i.e., malloc a new array of twice the current size, copy the strings over into the front half of the newly allocated array, and free the space used by the old array. This is what Java does when it runs out of room in an array.

After loading the dictionary into the array, you must call a menu() function that offers the user a list of operations to interact with the dictionary. The menu offered the user should look something like this:

Choose: 'P'rint, 'S'earch, 'I'nsert, 'R'emove, 'C'ount, 'Q'uit :

and the meaning of the operations are:

'P'         A little bit of formatting required here:  call printDictionary()
            to print out as many words as will fit on a 80 char line separated
            by a space, without going over 80 chars then go to the next line
            and repeat until all the words in the dictionary are printed.
'S'earch    Prompt for a word, e.g., foo, then call searchWord(). After
            returning from the call to searchWord() print something like:
            "foo found" OR "foo NOT found".
'I'nsert    Prompt for a word and insert it into the dictionary at the proper
            position to maintain order. Do not store duplicate words in the
            dictionary. This option should report back to the user something
            like "foo inserted" OR "foo ignored (duplicate)".
'R'emove    Prompt for a word then call removeWord() to delete it.  This option
            should report back to the user something like "foo removed" OR
            "foo ignored (not found)".
'C'ount	    Prints the current wordCount to the console.
'Q'uit      Print message that program is ending and dictionary will be sent
            to the output file specified on command line. Then call
            saveDictionary() to save the contents of the dictionary to the
            output file. It is to be saved in exactly the same format
            as the input file, i.e., one word per line.

Other requirements for Lab 3

• The user should provide the names of the input file and the output file as command-line arguments, for example,

  ./a.out 10-words.txt dictionary.txt
  

• Do not use any additional data structures in your attempt to be clever/fast on the load.

• Each menu operation MUST be encapsulated in its own function. Of course, you can have more functions if you feel you need them.

• You should document your code as best you can. You should especially document anything that is "clever" or unusual.

• Do not write 2 different insert() functions. Just write one function that does not care whether the string came from the input file, or whether it came from the user in the 'I' menu function. The insert function itself should not write the found / not found message. Let it return a value and check the value after the call. This avoids console output during the initial load.

• Do not use strcpy to shuffle the words during insertion. Instead, copy the pointers!

• You must NEVER create any garbage.

Design Document

You must turn in a preliminary design document no later than the Thursdat recitation before the assignment is due - the earlier you turn this in to Tessa, the better feedback you can get on your design. You also must turn in a final (revised to reflect any changes) design document with your final code.

Handing in your Solution

Same like last time. You will need to hand in your C Program file and the text file. Early is Monday midnight, (+10% bonus), Tuesday midnight is on time, Wednesday midnight is the end of the late period (-10% penalty).