CS 2213/2211  Advanced Programming  Spring 2005  Recitation 13:  Hashing     Week 13: Apr 19-21  Due (on time): 2005-04-26  23:59:59  Due (late):        2005-05-01  23:59:59

Recitation 13 should be submitted following directions at: submissions with deadlines 2005-04-26  23:59:59 (that's Tuesday, 26 April 2005, 11:59:59 pm) for full credit. 2005-05-01  23:59:59 (that's Sunday, 1 May 2005, 11:59:59 pm) for 75% credit.

• Hash functions and hash arrays.
• The open addressing approach to hashing.
• Deletion from a hash table.

The license plate numbers will be in a file on your computer, along with a count of the number of times they parked without paying. Your program will first load this file into an array, using hashing for insertion. Then you will enter a list of license plates as they come up during the day, some old, some new, that need to be looked up in the array. At the end of the day, when you quit the program, it should write out the latest version of this license plate data.

When you enter a license plate number, the program should tell you how many times they have parked without paying.

In addition to entering a license plate number, you need to be able to delete an entry entirely (in case they finally paid for parking), and you need to be able to quit in an orderly way, so that the system can save its latest version to a file.

• In this recitation, a license plate number can be any string of non-whitespace characters.

• Your program should make use of a struct similar to the following, for license plate numbers and for the number of times parked without paying:

  
  struct hnode {
     char *license; /* license plate number */
     int num;       /* number of times parked without paying */
  };
  

• Internally, you should use a hash table that is an array of pointers to the struct above. The size of this table should be given by

  
  #define HSIZE 13      /* size of hash table */
  

  This size is very small to allow me to see that your hashing algorithm is working reasonably. The use of a hash table here is for practice, and this application would not especially call for a hash table. If the table is declared globally, its elements will all be NULL pointers by default.

• You should use the following hash function:

  
  #define HMULT 19
  static int hash(char *s) {
     int hashval;
     for (hashval = 0; *s != '\0'; s++)
        hashval = (*s + HMULT*hashval) % HSIZE;
     return hashval;
  }
  

  I want a uniform hash function so that I can assess your program better.

• When looking up an item, get the hash address as an index, which must be greater than or equal to 0, and less than HSIZE. Then use open addressing, moving on to the next higher address, and moving from address HSIZE-1 back to 0. Keep moving until you find either a NULL entry or the item you are looking for.

• Your program should first read the following items from a file, say named licenses. You should read these and insert them into the hash table, using a hash of the first field for insertion.

  
  UBT878 1
  KGB209 1
  TEA311 3
  MUK772 1
  XYZ333 2
  

• Then your program should ask for you to enter either a license plate number or one of the commands quit or delete. (Of course these words can't be valid license plate numbers.) In case a license plate number is entered, your program should look it up. If it in new, it should be inserted with a num of 1. If it is already present, the num field should be incremented by 1. In either case the program should report how many times this license plate number has been on a car that didn't pay (a number greater than 0).

• If the command is delete, then the program should ask for a number to delete, and should delete in the way you must do with a hash table (as will be discussed in class).

• If the command is quit, then the program must first write the hash table back to the same file from which it was read. Then it should quit.

• Your program should be organized as a file hash.c that has all code related to the hash table and its maintenance. There should be a appropriate header file hash.h. Then a file license.c should have the main function and all the top-level functionality. Without looking inside the file hash.c, you should have not way to find out the particular strategy used for representing the license plate number data.

• In addition to its other functions, the file hash.c should have a function dump that will print the hash table as shown below, for debugging.

• Here is a sample session without deletes: session1.html.
• Here is a sample session with deletes: session2.html.

Contents of email submission for Recitation 13: Last Name, First Name; Course Number; Recitation Number. a. Source for files hash.h, hash.c, and license.c b. Follow the sample session 1, without deletions. c. Follow the sample session 2, with deletions. Note: It's not required that your program have identical output to mine in the two sessions. There are a number of reasons why the output might differ.