CIS 313 Winter 1997
Introduction to Information Structures
Programming Assignment #1
There are three main objectives of this programming assignment:
- Learning the concept of template in C++
- Learning a simple data structure hash table
- Learning how to write simple Makefile
See Chapter 3 (pages 99-115) for the concept of template.
Hash Table
The basic idea of a hash table is to store each data item using the
item itself to generate an index into the table. It is tempting to use
the actual item as the index (assuming a natural translation scheme
between the items and integers; for instance, seven digit integers for
seven digit telephone numbers), but that might require the table to
be entirely too large. Such a large table becomes inefficient because
in a typical application most of its entries will never be used. The
solution is to compute a function on the data that maps onto a smaller
set of keys that could index into the table.
Each entry in the hash table is commonly referred to as a bucket.
A key indexing a bucket that is already filled causes what is
called a collision. There is a number of ways of dealing with
collisions (collision resolution).
In this assignment you will
deal with collisions by treating each element of the table as the head
of a linked list which stores each data item that would be mapped into
that location. The main table will consist of an array of 20
elements, each of which is a header to a linked list representing that
bucket.
For a more general introduction to hash table, see Chapter
19 (pages 609-633), especially 19.5: Separate Chaining.
Makefile
For a brief introduction to make, see
Introduction to make
or you can read the manual in the room 100 Deschutes.
Assignment
The assignments consists of two parts.
In the first part you will familiarize yourselves with the use of
templates in C++. Your source code will be written in two
files, Hash.h and Hash.cpp. You will use g++ to
compile your source files. In the second part you will experiment
with make. Your code will be subdivided into four modules
(Main, Insert, Remove and Find) and stored in four different files
(Main.cpp, Insert.cpp, Remove.cpp, and Find.cpp). You should use make
to compile your code.
(The assignment is divided into two parts
because the g++ compiler has problems with the distribution of modules
to different files when templates are used. We suggest that you
don't use templates in the second part unless your compiler supports
the above handling of code.)
In this assignment, the interface of the hash table class and Makefile
are given. You can change the class interface (for example, add or delete
variables and member functions in the class definition) to suit your
needs. You should complete the following:
- Write the three functions listed in the hash table interface:
IsFound, Insert and Remove.
- To test your implementations, for a hash function of
your own, insert 100 randomly generated
integers into the hash table. Next, delete the 100 integers.
(Notice, that you must save the integers that you are inserting so you
know what to delete).
You should turn in:
- Printout of the program with a script file that shows various
test results. (The programs should be submitted with very clear
documentation. The grading is based on the correctness of the
program, clarity of the programming, and the experiments.)
- Manual page that describes how to execute your program, including
links to your source code.
HashTable class Interface
// HashTable class interface
//
// Etype: must have zero-parameter and copy constructor,
// operator= and operator!=
// CONSTRUCTION: with (a) no initializer;
// Copy constructon of HashTable objects is DISALLOWED
// Deep copy is supported
//
// ******************PUBLIC OPERATIONS*********************
// int Insert( Etype X ) --> Insert X
// int Remove( Etype X ) --> Remove X
// int IsFound( Etype X ) --> Return 1 if X would be found
// ******************ERRORS********************************
// Predefined exception is propogated if new fails
#ifndef __HashTable
#define __HashTable
template
class HashTable
{
public:
HashTable( );
~HashTable( );
int Insert( const Etype & X ); // Insert X to the harsh table
int Remove( const Etype & X ); // Return 1 if found, 0 if not
int IsFound( const Etype & X ); // Return 1 if found
private:
struct HashEntry
{
Etype Element; // The item
HashEntry *Next; // Pointer to next entry
HashEntry( ): Next( 0 ) { }
HashEntry( const Etype & E ) :
Element( E ), Next( 0 ) { }
};
enum { DefaultSize = 20 };
int ArraySize; // The size of this array
int CurrentSize; // The number of non-empty items
int Found; // To indicate whether the element is found
HashEntry Array[DefaultSize]; // The array of elements
HashEntry *Pos; // Position of the element
// Some interal routines
void FindPos( const Etype & X ); // Find the position of the element.
};
#endif
Sample Makefile
CFLAGS =
CC = g++
COMPILE = -c
DEST = .
HDRS = Hash.h
LD = g++
LDFLAGS =
.SUFFIXES: .cpp .o
.cpp.o:
$(CC) $(COMPILE) $<
# external libraries should be defined to the LIBS variable
# if you need to pass g++ any other variables, assign a new variable the options you want
# example: OPTIONS = -lm (load math library)
# then add $(OPTIONS) to the end of the list of variables following the
# $(PROGRAM) variable
LIBS =
MAKEFILE = Makefile
OBJS = Main.o Insert.o Remove.o Find.o
PROGRAM = Hash
SRCS = Main.cpp Insert.cpp Remove.cpp Find.cpp
# This is the all dependency stating that all means to check everything in the variable
# PROGRAM which is another dependency decribed later
all: $(PROGRAM)
# This is the PROGRAM dependency that implicitly will look at all the .o files
# and make sure that they are current. If not, it will recompile them using the form
# g++ -c OBJS -o SRCS
# If you need to add variables or options insert them in the next line at the end
$(PROGRAM): $(OBJS)
@echo "Linking $(PROGRAM) ..."
@$(LD) $(LDFLAGS) $(OBJS) -o $(PROGRAM)
@echo "done"
$(OBJS): $(HDRS)
clean:; @rm -f $(OBJS) core
###