Illustrate

• This projects aims to implement and utilize basic Data Structure and Algorithm

Gallery

• sort implemented mostly used sort algorighms
• kmp Knuth-Morris-Pratt, basic and improved methods
• conhash implemented consistent hash, together with rbtree
• kernelList do an illustration explanation for kernel list as well as an usage demo
• hashTable gave an basic example using kernel hlist
• trieTree is for Trie Tree
• mThread is a summarization for Multi Thread Programming using kernel pthread
• and many other solutions came up with me or modified from the web

build for all

then all binaries will be under ./bin

# cd Algorithm
make -j
source env.sh

or you can also compile each demo separately, take sort as example

# under Algorithm/
cd sort/
make -j

../bin/sort_demo

Concept of Sort

Complexity of Time

Github did not support style label of html, so I had to use pic here

Demonstrate

Concept of KMP

Next Array

you may know well about the next array from this figure

Demonstrate

cd kmp/
make -j

../bin/kmpdemo
basic kmp:
str = BBCABCDABABCDABCDABDET
pattern = BCDABDE
-1 0 0 0 0 1 0
Index = 14

optimized kmp:
str = BBCABCDABABCDABCDABDET
pattern = BCDABDE
-1 0 0 0 1 1 0
Index = 14

Red-Black Tree

Consistent Hash

Kernel Hash List

Kernel List

Multi Thread Programming

Trie Tree

Notice

Need set env variables before execute binary (Mac need not do this)

export LD_LIBRARY_PATH=./lib:$LD_LIBRARY_PATH

or just

source env.sh

Header directory Inc use soft link, making each template itself can be used as standalone

# example
ll ./inc

common.h@ -> ../common/common.h
kmp.h@ -> ../kmp/kmp.h
md5.h@ -> ../rbtree/md5.h
rbtree.h@ -> ../rbtree/util_rbtree.h
sort.h@ -> ../sort/sort.h

Each template will generate dynamic library, for shared use

# example
ldd lib/libsort.so
        linux-vdso.so.1 =>  (0x00007ffdd0929000)
        libcommon.so => ./lib/libcommon.so (0x00002afbcd8e0000)     --> mylib
        libstdc++.so.6 => /lib64/libstdc++.so.6 (0x00002afbcdae3000)
        libm.so.6 => /lib64/libm.so.6 (0x00002afbcddeb000)
        libgcc_s.so.1 => /lib64/libgcc_s.so.1 (0x00002afbce0ed000)
        libc.so.6 => /lib64/libc.so.6 (0x00002afbce303000)
        /lib64/ld-linux-x86-64.so.2 (0x00002afbcd4b2000)

License

The MIT License (MIT)