This article is about a collection of common Computer Science algorithms which may be used in C projects. The C Programming Language has a much smaller Standard Library as compared to other more modern programming languages such as Java or Python. This C Algorithms library provides a basic set of mathematical functions, string manipulation, type conversions, and file and console-based I/O. It does not include a standard set of “container types” like the C++ Standard Template Library. Similarly, many common data structures and algorithms are missing from C Standard Library.
This library is a collection of such algorithms to attempt to alleviate this problem.
The source code of the following algorithms is available in this library.
- Array List – Array List supports dynamic arrays that can grow as needed. Standard arrays in C are of a fixed length.
- AVL Tree – An AVL tree is balanced binary search tree. Named after their inventors, Adelson-Velskii and Landis, they were the first dynamically balanced trees to be proposed.
- Binary Heap – A binary heap is a complete binary tree which satisfies the heap ordering property. The ordering can be one of two types: the min-heap property: the value of each node is greater than or equal to the value of its parent, with the minimum-value element at the root.
- Binomial Heap – Binomial Heap is to extension of Binary Heap that provides faster union or merge operation together with other operations provided by Binary Heap. A Binomial Heap is a collection of Binomial Trees.
- Bloom Filter – A Bloom filter is a space-efficient probabilistic data structure that is used to test whether an element is a member of a set.
- Compare Int – Comparison functions for a pointer to an integer.
- Compare Pointer – Comparison functions for a generic void pointer
- Compare String – Comparison functions for strings
- Hash Int – Hash function for a pointer to an integer
- Hash Pointer – Hash function for a generic pointer
- Hash String – Hash functions for strings
- Hash Table – Hash table implementation – A hash table (hash map) is a data structure which implements an associative array abstract data type, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.
- List – A doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes.
- Queue – Queue is a container of entities (a linear collection) that are inserted and removed according to the first-in first-out (FIFO) principle.
- RB Tree – A red-black tree is a binary search tree which has the following red-black properties: Every node is either red or black. Every leaf (NULL) is black. If a node is red, then both its children are black. Every simple path from a node to a descendant leaf contains the same number of black nodes.
- SList – In a singly linked list, each node in the list stores the contents and a pointer or reference to the next node in the list. It does not store any pointer or reference to the previous node.
- Sorted Array – A sorted array is an array data structure in which each element is sorted in numerical, alphabetical, or some other order, and placed at equally spaced addresses in computer memory.
- Trie – Trie is an efficient information retrieval data structure that is used to store a dynamic set or associative array where the keys are usually strings. Using Trie, search complexities can be brought to optimal limit (key length).
The latest release, v1.2.0, can be found here. The documentation for the current C algorithms release is also available.
The current source code can be found in the Git repository.
The code is licensed under the ISC license (a simplified version of the BSD license that is functionally identical). As such, it may legitimately be reused in any project, whether Proprietary or Open Source.
Recommended Articles