CS 153 Data Structures I
Program 12
Hash Table on Disk
Due Date: November 30, 2000, during your teams scheduled time.
If you would Like to demo your program before Thursday, you can do so byscheduling
an appointment with a TA.
Emphasis:
-
How to hash a character string
-
How to handle hash collisions
-
How to read/write direct access files
Discussion - Part A
You will initially read a file of approximately
30,000 words that represent the total vocabulary used by Shakespear.
This file may be found at http://www.umr.edu/~adekock/Shakespear.txt.
As you read each word you will 'hash' the word and write it to an appropriate
location in a pre-initialized hash file. After the hash file has
been constructed you will allow a the user to query the hash file via a
Query button/edit box arrangement reporting back with a Messagebox whether
or not the specified word was found in the file. A SUMMARY button
will report in a list box a set of statistics on the hash file.
Since this is the last program for the semester
and we especially want every group to get at least some credit. You
will receive a 90% for correctly doing only Part A.
Program Requirements - Part A:
You may write all of the functions as members of
the ...Dlg class OR you may define a HashFile class if you choose.
Place buttons on your GUI to:
-
Initialize - the Hash file
-
Build - the Hash file
-
Query - the Hash file
-
Summarize - the arrangement of the Hash file
The following are the required functions:
-
void Initialize(int arg); //write an empty struct into the 1st arg
locations of the hash file
-
void Build(); //read each word from Shakespear and write
it to the hash file
-
bool Query(char * arg); //does arg exist in the hash
file?
-
void Summarize(); //
-
how many of the 1st 256 slots are empty
-
how many structs appear in the overflow area
-
how many words appear in the hash file
-
how long is the longest chain
-
which word begins the longest chain
Do NOT attempt to display all 30,000 words in a ListBox.
The time that that takes will surprise you!
Discussion - Part B
This part of the program will allow the Hash File
to be updated. You will add a Delete button and an Insert button
to your GUI.
Also doing all of Part B correctly will yield a score
of 110%
Program Requirements - Part B:
A deleted word my exist in either the Home
slot for that word or in the overflow area. If it is in the Home
area then the 1st collision-mate should be brought back to occupy the
Home slot. If it is in the overflow area then the linked list
of collision-mates must be updated and the freed slot returned to available
pool.
A new word is handled just like the original 30,000
were.
Place buttons on your GUI to:
-
Delete - a word from the hash file
-
Insert - a new word into the Hash file
-
Summerize - also reports how many holes exist in the overflow area
Make sure you have preconditions, post conditions and a one-line description
of your program with every function prototype. (in the header file!)
Make sure you comment variables which are not self explanatory.
Make sure you comment logical blocks of code.
Don't comment every line of your code.