Lab4: Dictionary Hash Table

Due Date: Tue 03 Mar 2008 by 23:59

Background:

Lab 4 is an improvement to Lab 3. We will build another dictionary, but we will use a hash table consisting of an array of linked lists to do so. You will break up your program into multiple source files. We will also break up our source code into separate source and header files.

The input files are the same as for Lab 3.

Assignment:

The behavior of this program is to be identical to that of Lab 3. We will have the same menu, and the same input format. The only difference will be the underlying implementation will be a hash table with collisions resolved in a linked list (chaining) rather than a dynamic array. As a result, you must re-implement the insert, search, remove, print and any other code that uses the underlying data structure. Of course, since we're using a hash table, the Print and Save functions will no longer display the items in sorted order - that's fine.

Your hash function for a word will be a very common one - take the sum of the ASCII value of each character in the word multiplied by its position in the word, and mod that sum by the number of slots in the array (1000). As an example, the word coder would be hashed to position 70 (99 (ASCII 'c') * 0 (position) + 111 * 1 + 100 * 2 + 101 * 3 + 114 * 4 = 1070, which, mod 1000, is 70).

Your main file will have NO linked list functions defined in it (e.g., insert, search, remove). So what functions will be defined in your main file? Well, main, obviously, but also menu and the pretty-print. Basically, any function that does not operate on a single list goes in the main file. This means main will declare the hash table (a 1000-element array of pointers), pass it into buildTable() and then menu() to handle all the functionality of the remainder of the program. Main will be very short. Your loadArray() function now becomes a buildTable() function. And you may need some new functions (like initTable() and hash()). Your list element struct will probably be named ListNode or something like that. Here is a suggested struct definition:

typedef struct list_node {
	char *word;  /* MUST be a char * (not compile-time array) */
	struct list_node *next;
} ListNode;

You must put your ListNode definition in linkedList.h (see below). Don't paste this struct def into main!

SOURCE CODE DECOMPOSITION:

• linkedList.h
  • define your node struct
  • prototypes of *ALL* list functions
  • must be wrapped in a proper #ifndef   #endif block
  
  
• linkedList.c
  • must #include "linkedList.h"
  • definitions of *ALL* functions prototyped in linkedList.h
  
  
• main file called lab4.c (contains ONLY the main/menu functions)
  • must #include "linkedList.h"
  • declare the hash table (array of pointers to ListNode's (i.e., ListNode *)
  • must pass the array into buildTable(...)
  • call menu(...) to read and execute user commands which will then call list routines

Handing in your Solution

Same like last time. Early is Monday midnight, (+10% bonus), Tuesday midnight is on time, Wednesday midnight is the end of the late period (-10% penalty).