data-structures-cpp

Six data structures written in C++, each in its own subfolder with its own commit history.

quickstart

git clone https://github.com/arikthehacker/data-structures-cpp.git
cd data-structures-cpp
sudo apt-get install -y build-essential
make run

make run builds the hash table and loads the sample products.txt, then prints the menu below. Each subfolder also builds on its own (cd hash-table && make), and make test builds all six, runs a scripted session against each, and diffs the output.

menu

Each program is menu-driven. Their startup menus:

linked-list:

Testing Menu:
1. Add Venue
2. Display All Venues
3. Add Activity to Venue
4. Display All Activities for a Venue
5. Display Venues Open on a Day
6. Remove Venue
7. Exit
Choose an option: 

stack-queue:

********** Game Stack and Series Queue Menu **********
1. Push a new game onto the stack
2. Pop a game from the stack
3. Peek at the top game in the stack
4. Display all games in the stack
5. Enqueue a new series to the queue
6. Dequeue a series from the queue
7. Peek at the front series in the queue
8. Display all series in the queue
9. Exit
******************************************************
Enter your choice: 

hash-table (after loading a products file):

============================================
           CS Etsy Shop Manager
============================================
1. View all products
2. Find products by category
3. Add a new product
4. Remove products by Seller ID
5. Buy a product
6. Check sold items by Seller ID
7. Retrieve product details
8. Visualize the hash table
9. Exit
============================================
Enter your choice: 

bst:

Menu: [1] Add  [2] Display  [3] Remove  [4] Retrieve  [5] Price Range  [6] Height  [7] Clear [8] Exit 
Next action (1-8): 

product-catalog:

=== Main Menu ===
1. Load Inventories from Files
2. Enter Items Manually
3. Start Shopping
4. Exit
Enter your choice: 

player-list:

===== Welcome to Bloons TD! =====
1) start game
2) exit
> 

how it works

linked-list/      a linked list of venues, each with its own list of activities
stack-queue/      a stack and a queue
hash-table/       a separate-chaining hash table (a small product catalog)
bst/              a binary search tree
product-catalog/  a product hierarchy and shopping cart on an array of linked lists
player-list/      a templated doubly linked list

The hash table uses a polynomial rolling hash with a prime multiplier, then separate chaining for collisions:

unsigned long hashValue = 0;
unsigned long primeMultiplier = 31;
for (int i = 0; lowerKey[i] != '\0'; i++)
    hashValue = (hashValue * primeMultiplier) + lowerKey[i];
return hashValue % tableSize;

Each program is menu-driven and reads choices from standard input. Every subfolder has a sample-input.txt (a scripted session) and an expected-output.txt that make test checks against.