Project Presentation

Introduction

This project covers some basic Dynamic Data Structures implemented as pure, generic ADT:s, coded in ANSI C. Makefiles for building a library, both for Windows/Linux are included.
You can even download a tarball to build/install the library from source, the usual way, under Linux.

• Singly-linked list
• Doubly-linked list
• Circular, singly-linked list
• Stack
• Queue
• Set
• Chained hash table
• Open-addressed hash table
• Heap
• Priority queue
• Binary search tree
• AVL tree
• Graph

Algorithms

Moreover, I've included some Graph Algorithms (Breadth-First-Search, Depth-First-Search, Minimal Spanning Tree, Dijkstra's Shortest Path and Traveling Salesman Path) in file algo.h and algo.c. These algorithms are not part of the library, though - so you have to link them into your project, if needed.

Source

Original and major parts of the code written by Kyle Loudon, in his book "Mastering Algorithms with C", published at O'Reilly Company.
Minor adjustments and extensions added by Dan Levin.

Author

Kyle Loudon and Dan Levin

Date

Tue Apr 07, 2015

Version

0.51 (To ChangeLog)

Demos

The demos are trying to test and show most of the public interface of the ADT:s - accordingly:

• demo01.c - testing/showing Singly-linked List ADT..
• demo02.c - testing/showing Doubly-linked List ADT..
• demo03.c - testing/showing Stack and Queue ADT..
• demo04.c - testing/showing Chained Hash Table ADT..
• demo05.c - testing/showing Heap and Priority Queue ADT..
• demo06.c - testing/showing Binary Search Tree ADT..
• demo07.c - testing/showing AVL Tree ADT..
• demo08.c - testing/showing Circular, Singly-linked List ADT..
• demo09.c - testing/showing Set ADT..
• demo10.c - testing/showing Open-addressed Hash Table ADT..
• demo11.c - testing/showing basic Graph ADT editing, BFS(Breadth-First-Search) - and DFS(Depth-First-Search)
• demo12.c - testing/showing interactive Graph editing..
• demo13.c - testing/showing Graph Algorithms, such as MST(=Minimal Spanning Tree), DSP(=Dijkstra's Shortest Path) and TSP(=Traveling Salesman Path).
• demo14.c - a more extensive Graph ADT application, using Dijkstra's Shortest Path algorithm. A (distance-low-cost) criss-cross flight within EU.

Testing

All demos have been tested on both Windows and Linux. Memory leak detection/tracing was done with Valgrind (Linux).

ToDo

• Publishing version 1.0 (probably next version uploaded to GitHub..)
• Adding a function - AVLTREEhard_remove() - which physically removes a node from an AVL Tree. Ok - no performance gain - but a personal coding challenge ;-)
• Extending and fine-tuning Project Documentation - still some issues to fix here..
• Fixing some bugs, that probably might turn up. Here I hope for feedback from you - after having tested the library :-)