912 DSA

A C++ implementation of 912 DSA.

Contents

• Introduction
• Todo
• Installation
• Build
  • Dependency
  • Using script
  • Manual
• License

Introduction

This is a code implementation of 912 DSA, which is a data structure course offered by Tsinghua University.

• video: DSA
• book: Data Structures in C++

Todo

• Tree
  • B Tree
  • Red-Black Tree
  • Kd Tree
• Dict
  • Hash Table
  • Skip List
    • Quadlist

ID	Chapter	Implementation
1	Introduction	Fibonacci
2	Vector	Vector, Bitmap, BitmapQuickInit
3	List	ListNode, List
4	Stack and Queue	StackInterface, Stack, LinkedStack,StackExample, Queue
5	Binary Tree	BinTreeNode, BinTree
6	Binary Search Tree	BST, AVL
7	BST Applications	/
8	Advanced BST	SplayTree, BTree, RBTree
9	Dictionary	/
10	Graph	Graph,GraphMatrix,GraphList
11	Graph Applications	/
12	Priority Queue	/
13	String	/
14	Sorting	/
NaN	Other	Iterator

Installation

git clone --recurse-submodules https://github.com/hnlcf/912-dsa.git

cd 912-dsa

Build

Dependency

Tools

• cmake
• python

Library

Using catch2 for testing which managed by git submodules.

• catch2

Using script

1. CMake build and ctest

python tools.py --all

2. Catch2 test

python tools.py --catch2

Manual

1. CMake config

mkdir -p build && cd build

cmake -DCMAKE_BUILD_TYPE=Release ..

2. Build

cmake --build . --config Release --parallel 12

3. Run ctest

ctest -C Release --verbose

License

MIT