DataStructures is a collection of data structures implemented using the C++ programming language and some C++11 features. The structures created in this project are all fully templated and made to be as general, efficient, and reliable as possible. This is a personal project developed to improve my understanding of the fundamental data structures, but if you are interested in contributing to this project please email me ([email protected]) and we can work something out. All code in this project is currently unlicensed, but feel free to use, distribute, or poke fun at anything you wish.
Note - The project is not currently build ready, and can''t be used as a library for your use. Certain self-containted parts, like the graphs, are working and tested, those could be manually included into a project.
git clone https://github.com/jhallard/DataStructures.git
cd DataStructures
cmake CMakeLists.txt
makeGraphs are one of the most powerful and all-encompasing data structures known to man, and they are the source for some of the most interesting problems in computer science. This project contains a few different graph implementations, all of which come with their own implementation of BFS, DFS, min-cut, dijkstra''s, and other popular graph algorithms. Below is a listing of the various flavors of graphs that are implemented.
/Graphs/GraphInterface/ : The interface class from which all of graph implementations in this project derive. /Graphs/GraphAdjList/UndirectedGraph/ : An implementation of a undirected graph that uses a series of adjacency lists to internally represent the graph structure. /Graphs/GraphAdjList/DirectedGraph/ : An implementation of a undirected graph that uses a series of adjacency lists to internally represent the graph structure.The graphs are pretty much finished and have been tested extensively, I''m currently working on improving the runtime performance for some of the core algorithms, like Dijkstra''s and Minimum-Spanning-Tree. They both come with a decent-sized group of unit tests, which cover a large percentage of the main functionality of the graphs.
I''m currently implementing some programs that can generate a wide-array of connected graphs, which I will then put on the internet for others to use for testing purposes. Look for this in the near future.
Dictionaries/HashDictionary/ : This data structure represents a dictionary that uses hashing to insert and locate items. To resolve collisions, we use chaining with linked lists. I first implemented this for a data structures class around the spring of 2014, but I have recently begun to add changes and make improvements./Graphs/ GraphAdjList/UndirectedGraph/ - A templated, undirected graph that uses a vector of adjacency lists to represent the graph internally.DirectedGraph/ - A templated, directed graph that also uses adjacency lists to represent the graph.GraphAdjMat//Dictionaries/HashDictonary - A templated dictionary that uses chaining to resolve collisions. BUGS - Contains a list of bugs and possible enhancements for each project.In the future I plan to implement at least the following data structures :
PriorityQueue - I will most likely try to implement a priority queue in a few different ways, including binary and fibonacci heaps.Tree - I would like to implement a few different tree flavors, included binary, AVL, Red/Black, n-ary, and possibly others. The current implementation of BinaryTree is only partially mine, the code was supplied by a textbook but was incomplete (would not compile), I completed it and added more features, but I would like to start my own from scratch.Deque - A deque can be used as a stack, a queue, or a deque, so implementing this one data structure would be quite useful. The priority queue can possibly derive from this class and just override the insetion and deletion functions.