$23.99
Assignment #6 Solution
Hash Table Implementation of a Concordance
In this assignment there will be a programming portion and a written portion.
PROGRAMMING
For this assignment, you will complete the hash-map with chaining as specified by the provided header file. Chapter 12 and worksheet 38 will be good resources for completing this assignment. After completing the hash-map implementation you
will write a concordance program in your main.c. A concordance counts the number of occurrences of each word in a document. For this assignment, we will work with text files.
There are three files to work with for the programming portion:
main.c is where you will write the concordance code.
hashMap.h the header file which defines structs and public functions for your hash table and, explains the purpose of each function. Notice that there is a variable HASHING_FUNCTION which determines which hashing function should be used in hashMap.c Your code should check this value to determine which hashing function to use. HASHING_FUNCTION==1 means use stringHash1 and HASHING_FUNCTION==2 means use stringHash2.
hashMap.c a mostly empty implementation file which you will fill in with your code.
Makefile Remember to rename this from Makefile.txt to makefile when you
'save as'.
You will be making changes to main.c and hashMap.c. Do not make changes to hashMap.h
There are three functions provided to you:
getWord(FILE*) will parse out the next word from the file for you. Read the description of the function in the comments inside main.c for more information.
stringHash1(char*) is the first function you will use for converting a key into an integer hash index. This function is located in the provided hashMap.c.
stringHash2(char*) is the second function for computing an integer hash index, part of your job will be to explain why stringHash2 is better then stringHash1. This function is located in the provided hashMap.c.
There is some code in the main function for giving you timing information as well. You should not need to change anything in order to use it. The purpose of the timing information will be made clear in the questions section.
The worksheets and the function explanations should provide the information needed to complete this assignment, except for some more details on what a concordance is.
Concordance
The job of the concordance is to count how many times each word occurs in a document. You will implement a concordance using a hash table implementation of the Map interface. In this implementation, the hash table will store hashLinks which consist of a key, value, and pointer to the next link in the chain. The keys are the words and the values are the number of occurrences of each word.
You are provided with a function to retrieve words from a FILE pointer. It is your job to open this file (fopen()) and close this file (fclose()) but the reading of the file will be handled for you inside of getWord. For help with fopen() and fclose() see
the slides posted on the schedule for the recitation day.
Your concordance will run a loop until the end of the file is reached. In the loop, you will:
1. Read in a word with getWord().
2. If the word is already in your hash table then increment it's number of occurrences.
3. If the word is not in your hash table then insert it with an occurrence count of
1.
After processing the text file into your concordance you will print all the words in your hash table. Please print the words in the following form with only one word on each line:
for the input file of: It was the best of times, It was the worst of times.
best: 1
It: 2 was: 2 the: 2 of: 2 worst: 1 times: 2
You may choose any order in which to print the words.
Challenge- Extra credit ( 10 points)
There are a lot of uses for a hashMap, and one of them is for implementing a spell-checker. All you need to get started is a dictionary.
Dictionary spellcheck.c
Inside spellcheck.c you will find some code to get you started, but it should look very much like main.c
Written Questions
Your written questions will be handed in electronically, preferably as comments on the TEACH turn-in page, just cut and paste from your preferred editor.
1. Give an example of two words that would hash to the same value using
stringHash1() but would not using stringHash2().
2. Why does the above make stringHash2() superior to stringHash1()?
3. When you run your program on the same input file but one run using stringHash1() and on the other run using stringHash2(). Is it possible for your size() function to return different values?
4. When you run your program on the same input file using stringHash1() on one run and using stringHash2() on another, is it possible for your tableLoad() function to return different values?
5. When you run your program on the same input file with one run using stringHash1() and the other run using stringHash2(), is it possible for your emptyBuckets() function to return different values?
6. Is there any difference in the number of 'empty buckets' when you change the table size from an even number, like 1000 to a prime like 997 ?
7. Using the timing code provided to you. Run you code on different size hash tables. How does affecting the hash table size change your performance?
Rubric for assignment 6: (Total 100 points)
Compile and Style: 20 points
Concordance: 20 hash map: 50
Written questions: 10
Extra Credit Challenge (SpellChecker): 10
What to submit
1. main.c
2. hashMap.c
3. spellcheck.c (optional)
4. The answers to the written questions as either a teach comment or .pdf
