rethink-c
rethink-c copied to clipboard
A reuseable codebase for C Programming Language.
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