Data Structures

Implementations for data structures as used in Computer Science courses at Duke are kept here. Many of these data structures require the use of a vector class. We use the class Vector defined in "vector.h" on acpub and cs systems at Duke. A link is also given below.

This page is under construction, more data structures will be added as they're tested. All the implementations here have been tested in either (or both) CPS 100/100E and CPS 108.

Templates

Note, to use templates with g++ in a multi-file program requires the use of a per-program template.cc file. A rudimentary explanation on using templates is available.

The vector.h file is also accessible.

Stacks/Queues

Based on vectors so these stack/queue classes have no upper limit on size.

stack.h and stack.cc
a rudimentary test program teststack.cc

queue.h and queue.cc
a rudimentary test program testqueue.cc

Priority Queues

This is a heap-based priority queue, templated on two parameters: one is the class being stored, and one is the class that is used to prioritize. The latter must have a < operator (see the test program).

pqueue.h and pqueue.cc
a rudimentary test program testpq.cc

Maps

These classes are being re-written so that the iterator classes are included as part of the respective map classes. The simplest approach to doing this is to add, for example, the line below to hmap.h

   #include "hiterator.h"

(and similarly for the other map implementations)

Here are the abstract base classes for map and iterator

Here's a file that tests/uses the classes below usewords.cc

Here are different implementations of these classes.

uvmap.h
uvmap.cc
uviterator.h
uviterator.cc
Binary Search tree implementation
bstmap.h
bstmap.cc
btiterator.h
btiterator.cc
Hash implementation
hmap.h
hmap.cc
hiterator.h
hiterator.cc

Owen L. Astrachan

Last modified: Fri Dec 12 15:25:19 EST 1997