RETHINK C

Relearn and rethink C Programming Language, including some of data structures and algorithms.

The code is licensed under the MIT license, copyright by hutusi.com.

Some of the code inspired (copied) by Simon Howard's c-algorithms, like ArrayList, etc. This project also reused his alloc-testing framework for memory testing.

RETHINK-C aims to build a reuseable codebase for C Programming Language.

How to build & test

Requirements:

• Editor/IDE: VS Code is recommended.
• GCC on Mac, Linux or Windows. (Recommend msys2 + MingW on Windows.)
• CMake.
• Clang-Format.

build & test:

• build

cd build
cmake ..
make

• test:

make test

Goals / Achievements

Basic Data Structures

• ArrayList, Stack arraylist.h arraylist.c
• LinkedList list.h list.c
• Queue queue.h queue.c
• BitMap bitmap.h bitmap.c
• Muti-dimensional Matrix matrix.h matrix.c
• Hash Table hash_table.h hash_table.c hash.h hash.c

Trees

• Binary Search Tree bstree.h bstree.c
• AVL Tree avltree.h avltree.c
• Red Black Tree rbtree.h rbtree.c
• Binary Heap heap.h heap.c
• Fibonacci Heap, Binomial Heap
• Skip List skip_list.h skip_list.c
• B+ Tree

Graphs

• Adjacency Matrix graph.h graph.c
• Adjacency List sparse_graph.h sparse_graph.c
• Union-Find
• BFS & DFS graph.h##bfs(), ##dfs()
• Topological sorting (Kahn) sparse_graph_topo_sort()
• Floyd
• Dijkstra dijkstra.h dijkstra.c
• Minimum spanning trees: Prim, Kruskal
• A-star

String & Text

• Text (similar to string in C++). text.h text.c
• BigNum integer bignum.h bignum.c
• BigNum decimal
• KMP (Knuth-Morris-Pratt) algorithm kmp.h kmp.c
• BM (Boyer-Moore) algorithm bm.h bm.c
• Sunday algorithm sunday.h sunday.c
• Trie Tree trie.h trie.c
• Aho–Corasick algorithm ac.h ac.c
• DAT (Double-Array Trie)
• Huffman coding huffman.h huffman.c

Sorting

• Quick Sort arraylist.c##arraylist_sort()
• Merge Sort list.c##list_sort()
• Heap Sort heap.h heap.c

Math

• Matrix multiplication
• Eratosthenes sieve (prime numbers) prime.h prime.c

Distance Measures

• Euclidean distance distance.h##euclidiean_distance()
• Manhattan distance
• Hamming distance

MISC

• Bloom filter