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

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

Trees

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

Graphs

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

String & Text

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

Sorting

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

Math

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

Distance Measures

• [x] Euclidean distance distance.h##euclidiean_distance()
• [ ] Manhattan distance
• [ ] Hamming distance

MISC

• [ ] Bloom filter