Monash University > CSSE > CSE1303 > Part A> Pracs > Prac A6

CSE1303 Computer Science
Semester 2, 2003
Part A
Prac A6 : Hash Tables

This prac covers material from lectures A14 to A15 and Tutorial A6.

Project

To write a simple spell checker.

Background

In this prac will use a Hash Table to implement a simple spell checker. The idea behind the program is to read a dictionary into a Hash Table, then check every word in a nominated file to see whether it is in the Hash Table. Any word not found will be assumed to be misspelt and will be printed.

Preparation (3 marks if completed before class)

The marks for Preparation will be awarded only if the preparation is complete before the start of the class.

1. Using the following function,

   unsigned hash(char* s)
   {
     int i = 0;
     unsigned value = 0;
   
     while (s[i] != '\0')
     {
       value = (value + 13 * s[i]) % 11;
       i++;
     }
     return value;
   }
   

   calculate the hash values of the following names:

   Nell, Jareth, Gabriel, Sarah, Susan, Lee, Michelle, Toby, Samantha, Daniel

2. Why are unsigned variables being used in the previous hash function?

3. Write a C program which uses a Hash Table, of size 11, and the above hash function, to store character strings. You must use the linear probing implementation.

   Note: You must use dynamic memory for your strings. This means your Hash Table will be an array of char* (ie. char* table[11];
   This also means that for the advanced question you will need to change your Hash Table to be char** table; for dynamic of re-sizing.

   Also make sure you initialise all of these strings to NULL before you use the Hash Table.

Question 1: (3 marks)

Write C program which uses a Hash Table of size, 24593, the following hash function:

#define TABLESIZE 24593
#define PRIME 12289

unsigned hash(char* s)
{
  int i = 0;
  unsigned value = 0;

  while (s[i] != '\0')
  {
    value = (value + PRIME*s[i]) % TABLESIZE;
    i++;
  }
  return value;
}

and has a menu with the following options:

1. Read which asks the user for a filename, opens the file, and stores all the character strings in the file in the Hash Table Search: which asks the user for a character string, and then prints a message indicating whether or not the string is contained in the Hash Table.
2. List which prints out all the character strings stored in the Hash Table.
3. Quit which allows the user to quit the menu and exit the program.

Important: You must use the linear probing implementation.
You must also free any memory allocated dynamically.

Question 2: (4 marks)

Change the program you wrote in Question 1, so that instead of a menu the program does the following steps:

1. Read in all the words stored in the file dict.txt, which can found at http://www.csse.monash.edu.au/courseware/cse1303/parta/prac/a6/, and store these words in the Hash Table.
2. Ask the user for a filename and open the file.
3. Read in each line of the file. For any line which contains a misspelt word (i.e. one not in the Hash Table), print out the line number together with all the words misspelt on that line.

Advanced Questions: (2 marks)

In the above implementation of a Hash Table the size of the table was fixed. In this part of the prac we extend the implementation so that the size of the table is dynamic.

Questions:

1. In your implementation of a Hash Table add the operation resize(), which changes the size of the Hash Table. This operation will require a parameter newSize, which will be the size of the new Hash Table.

   Note: When you change the size of the Hash Table you will need to insert all the items from the old Hash Table into the new Hash Table.

2. You will need to change the hash function when you change the size of the Hash Table. This means TABLESIZE will become a variable. For this part you may assume that only the TABLESIZE changes, and that the parameter PRIME remains constant.

   Note: Make sure you deallocate any memory you no longer require.

3. Change the program you wrote in Question 2, so that PRIME is now a variable, the initial size of the Hash Table is 11, and the PRIME is initially set to 7. Then, each time the table gets full, increase the size of table and the PRIME variable to be the next prime in the following list:
   7, 11, 23, 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593

[ Top | Home ]

Last modified: Thursday 26 June 2003 14:45:30