Introduction

A library that implements various data structures and algorithms in C.

The data structures implemented are:

• Disjoint-set data structure (Union-Find).
• Linked list data structure.
• Doubly linked list data structure.
• Stack implementations based on:
  • Resizing arrays
  • Linked lists
• Queue implementations based on:
  • Fixed size arrays
  • Resizing arrays
  • Linked lists
• Set implementations based on:
  • Binary Search Trees
  • Tries

The algorithms implemented are:

• Various sorting algorithms:
  • Insertion sort
  • Bubble sort
  • Selection sort
  • Shellsort
  • Merge sort
  • Quicksort

Also, some programs are included which use those data structures and solve some classic problems. These programs are:

• Testing an expression for balanced parentheses.
• Checking whether a grid percolates or not.
• Calculating the running median of a list of integers

Installation

The library is written against C11, so a conforming compiler is needed, like gcc or clang. Also, for the programs, an implementation conforming to POSIX.1-2008 is required. Currently the project has been tested with GCC version 7.3.0 on Ubuntu 18.04.

The project uses CMake as the build system. In order to build it, run the following commands:

mkdir cmake-build-debug
cd cmake-build-debug
cmake ..
make

Bibliography

• Algorithms, 4th Edition
• Introduction to Algorithms, 3rd Edition
• Δομές Δεδομένων, Ιωάννης Μανωλόπουλος
• Libalv