Princeton University
COS 217: Introduction to Programming Systems

Assignment 2: An Efficient Symbol Table ADT


The purpose of this assignment is to help you learn more about advanced C programming, creating ADTs, and the GNU/UNIX programming tools.


Recall the symbol table concept, as described in Assignment 1. A hash table is a particularly efficient way to implement a symbol table. Section 2.9 of The Practice of Programming (Kernighan and Pike), chapter 8 of C Interfaces and Implementations (Hanson), and chapter 14 of Algorithms in C, Parts 1-4 (Sedgewick) describe hash tables.

Your Task

As with Assignment 1, your task in this assignment is to create a generic ADT named SymTable, each of whose instances is a symbol table. Your SymTable ADT should be the same as the one from Assignment 1, except:

Note that subsequent assignments may ask you to create programs that are clients of your SymTable ADT.

The SymTable Interface

The SymTable interface should be the same as it was in Assignment 1. In particular, recall that:

The SymTable Implementation

The SymTable implementation should be the same as for Assignment 1, except for these substantial changes:

The hash table should use a reasonable hash function. See the lecture notes for an example. See p. 578 of the Sedgewick textbook for an alternative. 

Initially the hash table should contain 509 buckets. 

The SymTable_free function should free all memory occupied by the given SymTable. That includes the memory occupied by the SymTable structure, its bindings array, its bindings, and its keys. The SymTable_remove function should free the memory occupied by the removed binding and its key.

Implementing those changes is worth 90% of the assignment. To receive full credit for the assignment, you also should implement this change:


We encourage you to develop on arizona, using Emacs to create source code and gdb to debug.

A minimal test program is available in the file /u/cs217/Assignment2/testsymtable.c. You may use it as a starting point for creating your own test programs.

Create a "readme" text file that contains:

Submit your work electronically on arizona via the command:

/u/cs217/bin/submit 2 symtable.h symtable.c readme


As always, we will grade your work on functionality and design, and will consider understandability to be an important aspect of good design. To encourage good coding practices, we will compile using "gcc -Wall -ansi -pedantic" and take off points based on warning messages during compilation.