algs4cplusplus
algs4cplusplus copied to clipboard
Published
20 hours ago •
AceCoooool
AceCoooool
Algorithms, 4th edition textbook code (using c++)
Algorithms
Algorithms, 4th edition textbook code (using c++)
official java code: Algorithms, 4th Edition
Note：
- based on STL Library
- using C++17
- Not support drawing
- Welcome to point out the error, and pull better code
TODO
- [ ] check ch1
- [ ] check ch2
- [ ] check ch3
- [ ] check ch4
- [ ] check ch5
- [ ] add ch6
Tutorial: run demo code
terminal
# for example
cd ch1
g++ 1_BinarySearch/main.cpp -o binary
./binary
IDE(clion)
You sholud Edit the Configurations：（Due to the relative file path）
Working directory: youroot/algs4cplusplus/ch1
ch1. Fundamentals
| REF | PROGRAM | DESCRIPTION / C++DOC | REF | PROGRAM | DESCRIPTION / C++DOC |
|---|---|---|---|---|---|
| - | BinarySearch.h | binary search | - | RandomSeq.cpp | random numbers in a given range |
| - | Average.cpp | average of a sequence of numbers | - | Cat.cpp | concatenate files |
| - | Knuth.h | Knuth shuffle | - | Counter.h | counter |
| - | StaticSETofInts.h | set of integers | - | Whitelist.cpp | whitelist client |
| - | Vector.h | Euclidean vector | - | Date.h | date |
| - | Transaction.h | transaction | - | Point2D.h | point |
| - | RectHV.h | axis-aligned rectangle | - | Interval1D.h | 1d interval |
| - | Interval2D.h | 2d interval | - | Accumulator.h | running average and stddev |
| 1.1 | ResizingArrayStack.h | LIFO stack (resizing array) | 1.2 | LinkedStack.h | LIFO stack (linked list) |
| - | Stack.h | LIFO stack | - | ResizingArrayQueue.h | FIFO queue (resizing array) |
| 1.3 | LinkedQueue.h | FIFO queue (linked list) | - | Queue.h | FIFO queue |
| - | ResizingArrayBag.h | multiset (resizing array) | 1.4 | LinkedBag.h | multiset (linked list) |
| - | Bag.h | multiset | - | Stopwatch.h | timer (wall time) |
| - | StopwatchCPU.h | timer (CPU time) | - | LinearRegression.h | simple linear regression |
| - | ThreeSum.h | brute-force three sum | - | ThreeSumFast.h | faster three sum |
| - | DoublingTest.h | doubling test | - | DoublingRatio.cpp | doubling ratio |
| - | QuickFindUF.h | quick find | - | QuickUnionUF.h | quick union |
| 1.5 | WeightedQuickUnionUF.h | weighted quick union | - | UF.h | union-by-rank with path halving |
ch2. Sorting
| REF | PROGRAM | DESCRIPTION / C++DOC | REF | PROGRAM | DESCRIPTION /C++DOC |
|---|---|---|---|---|---|
| 2.1 | Insertion.h | insertion sort | - | InsertionX.h | insertion sort (optimized) |
| - | BinaryInsertion.h | binary insertion sort | 2.2 | Selection.h | selection sort |
| 2.3 | Shell.java | shellsort | 2.4 | Merge.java | top-down mergesort |
| - | MergeBU.h | bottom-up mergesort | - | MergeX.h | optimized mergesort |
| - | Inversions.h | number of inversions | 2.5 | Quick.h | quicksort |
| - | Quick3way.h | quicksort with 3-way partitioning | - | QuickX.h | optimized 2-way quicksort |
| - | QuickBentleyMcIlroy.h | optimized 3-way quicksort | - | TopM.cpp | priority queue client |
| 2.6 | MaxPQ.h | max heap priority queue | - | MinPQ.h | min heap priority queue |
| - | IndexMinPQ.h | index min heap priority queue | - | IndexMaxPQ.h | index max heap priority queue |
| - | Multiway.h | multiway merge | 2.7 | Heap.h | heapsort |
ch3. Searching
| REF | PROGRAM | DESCRIPTION / C++DOC | REF | PROGRAM | DESCRIPTION /C++DOC |
|---|---|---|---|---|---|
| - | FrequencyCounter.cpp | frequency counter | 3.1 | SequentialSearchST.h | sequential search |
| 3.2 | BinarySearchST.h | binary search | 3.3 | BST.h | binary search tree |
| 3.4 | RedBlackBST.h | red-black tree | 3.5 | SeparateChainingHashST.h | separate chaining hash table |
| 3.6 | LinearProbingHashST.h | linear probing hash table | - | ST.h | ordered symbol table |
| - | SET.h | ordered set | - | DeDup.cpp | remove duplicates |
| - | WhiteFilter.cpp | whitelist filter | - | BlackFilter.cpp | blacklist filter |
| - | LookupCSV.cpp | dictionary lookup | - | LookupIndex.cpp | index and inverted index |
| - | FileIndex.cpp | file indexing | - | SparseVector.h | sparse vector |
ch4. Graphs
| REF | PROGRAM | DESCRIPTION / C++DOC | REF | PROGRAM | DESCRIPTION / C++DOC |
|---|---|---|---|---|---|
| - | Graph.h | undirected graph | - | GraphGenerator.java | generate random graphs |
| - | DepthFirstSearch.h | depth-first search in a graph | - | NonrecursiveDFS.h | DFS in a graph (nonrecursive) |
| 4.1 | DepthFirstPaths.h | paths in a graph (DFS) | 4.2 | BreadthFirstPaths.h | paths in a graph (BFS) |
| 4.3 | CC.h | connected components of a graph | - | Bipartite.h | bipartite or odd cycle (DFS) |
| - | BipartiteX.h | bipartite or odd cycle (BFS) | - | Cycle.h | cycle in a graph |
| - | EulerianCycle.h | Eulerian cycle in a graph | - | EulerianPath.h | Eulerian path in a graph |
| - | SymbolGraph.h | symbol graph | - | DegreesOfSeparation.cpp | degrees of separation |
| - | Digraph.h | directed graph | - | DigraphGenerator.h | generate random digraphs |
| 4.4 | DirectedDFS.h | depth-first search in a digraph | - | NonrecursiveDirectedDFS.h | DFS in a digraph (nonrecursive) |
| - | DepthFirstDirectedPaths.h | paths in a digraph (DFS) | - | BreadthFirstDirectedPaths.h | paths in a digraph (BFS) |
| - | DirectedCycle.h | cycle in a digraph | - | DirectedCycleX.h | cycle in a digraph (nonrecursive) |
| - | DirectedEulerianCycle.h | Eulerian cycle in a digraph | - | DirectedEulerianPath.h | Eulerian path in a digraph |
| - | DepthFirstOrder.h | depth-first order in a digraph | 4.5 | Topological.h | topological order in a DAG |
| - | TopologicalX.h | topological order (nonrecursive) | - | TransitiveClosure.h | transitive closure |
| - | SymbolDigraph.h | symbol digraph | 4.6 | KosarajuSharirSCC.h | strong components (Kosaraju–Sharir) |
| - | TarjanSCC.h | strong components (Tarjan) | - | GabowSCC.h | strong components (Gabow) |
| - | EdgeWeightedGraph.h | edge-weighted graph | - | Edge.h | weighted edge |
| - | LazyPrimMST.h | MST (lazy Prim) | 4.7 | PrimMST.h | MST (Prim) |
| 4.8 | KruskalMST.h | MST (Kruskal) | - | BoruvkaMST.h | MST (Boruvka) |
| - | EdgeWeightedDigraph.h | edge-weighted digraph | - | DirectedEdge.h | weighted, directed edge |
| 4.9 | DijkstraSP.h | shortest paths (Dijkstra) | - | DijkstraUndirectedSP.h | undirected shortest paths (Dijkstra) |
| - | DijkstraAllPairsSP.h | all-pairs shortest paths | 4.10 | AcyclicSP.h | shortest paths in a DAG |
| - | AcyclicLP.h | longest paths in a DAG | - | CPM.cpp | critical path method |
| 4.11 | BellmanFordSP.h | shortest paths (Bellman–Ford) | - | EdgeWeightedDirectedCycle.h | cycle in an edge-weighted digraph |
| - | Arbitrage.cpp | arbitrage detection | - | FloydWarshall.h | all-pairs shortest paths (dense) |
| - | AdjMatrixEdgeWeightedDigraph.h | edge-weighted graph (dense) |
ch5. Strings
| REF | PROGRAM | DESCRIPTION / C++DOC | REF | PROGRAM | DESCRIPTION / C++DOC |
|---|---|---|---|---|---|
| - | Alphabet.java | alphabet | - | Count.java | alphabet client |
| 5.1 | LSD.h | LSD radix sort | 5.2 | MSD.h | MSD radix sort |
| - | InplaceMSD.h | In-place MSD radix sort1 | 5.3 | Quick3string.h | 3-way string quicksort |
| - | AmericanFlag.h | American flag sort1 | - | AmericanFlagX.h | non-recursive American flag sort1 |
| 5.4 | TrieST.h | multiway trie symbol table | - | TrieSET.h | multiway trie set |
| 5.5 | TST.h | ternary search trie | 5.6 | KMP.h | substring search (Knuth–Morris–Pratt) |
| 5.7 | BoyerMoore.h | substring search (Boyer–Moore) | 5.8 | RabinKarp.h | substring search (Rabin–Karp) |
| 5.9 | NFA.h | NFA for regular expressions | - | GREP.cpp | grep |
| - | BinaryDump.cpp | binary dump |
Metadata
16
Stars
4
Forks
Watchers
Owner
AceCoooool
Metadata
Algorithms, 4th edition textbook code (using c++)