Tags : Git_Readme
A tiny stl for c++ to memorize data structures and algorithms.
##Vector.h Vector< typename Te>value; ###API
| API | Info |
|---|---|
| size() | return vector's size |
| get(const rank) | return element's value |
| put(const rank,const element) | change element's value |
| insert(const rank,const element) | insert a value |
| remove(const rank) | del |
| disordered() | return ordered or not |
| sort() | quicksort |
| find(const element) | return element with max rank |
| search(const element) | return element LSQ than e with max rank |
| deduplicate() | remove the deduplicate element (disordered vector) |
| uniquify() | remove the deduplicate element(ordered vector) |
| traverse() | traverse the vector and edit every element |
| [],=,==,>,<,>=,<= | operaters |
###Tips:
| Function | Tips |
|---|---|
| extand() | 扩容的条件和方式 |
| shrink() | 注意return的条件 |
| find() | 从后向前 |
| search() fib,bin | Fib类的构造和用法 |
| uniquify() | 注意O(n)复杂度,扫描一遍即可 |
| deduplicate() | 扫描每个元素的前置元素以保证清除彻底 |
| traverse() | 函数指针和函数对象的应用 |
##List.h
List< typename Te>value;
API:
| API | Info |
|---|---|
| Rank size() const | 规模 |
| bool empty() const | 判空 |
| T& operator[] ( Rank r ) const | 重载，支持循秩访问（效率低） |
| ListNodePosi(T) first() const | 首节点位置 |
| ListNodePosi(T) last() const | 末节点位置 |
| bool valid ( ListNodePosi(T) p ) | 判断位置p是否对外合法 |
| bool disordered() const | 判断列表是否已排序 |
| ListNodePosi(T) find ( T const& e ) const | 无序列表查找 |
| ListNodePosi(T) find ( T const& e, int n, ListNodePosi(T) p ) const | 无序区间查找 |
| ListNodePosi(T) search ( T const& e ) const | 有序列表查找 |
| ListNodePosi(T) search ( T const& e, int n, ListNodePosi(T) p ) const | 有序区间查找 |
| ListNodePosi(T) selectMax ( ListNodePosi(T) p, int n ) | 在p及其n-1个后继中选出最大者 |
| ListNodePosi(T) selectMax() { return selectMax ( header->succ, _size ) | 整体最大者 |
| ListNodePosi(T) insertAsFirst ( T const& e ) | 将e当作首节点插入 |
| ListNodePosi(T) insertAsLast ( T const& e ) | 将e当作末节点插入 |
| ListNodePosi(T) insertA ( ListNodePosi(T) p, T const& e ) | 将e当作p的后继插入 |
| ListNodePosi(T) insertB ( ListNodePosi(T) p, T const& e ) | 将e当作p的前驱插入 |
| ListNodePosi(T) push_back(T const& e) | 将e推入结尾 |
| T remove ( ListNodePosi(T) p ) | 删除合法位置p处的节点,返回被删除节点 |
| void merge ( List& L ) { merge ( first(), size, L, L.first(), L._size ) | 全列表归并 |
| void sort ( ListNodePosi(T) p, int n ) | 列表区间排序 |
| void sort() { sort ( first(), _size ) | 列表整体排序 |
| int deduplicate() | 无序去重 |
| int uniquify() | 有序去重 |
| void reverse() | 前后倒置（习题） |
| void traverse ( void (* ) ( T& ) ) | 遍历，依次实施visit操作（函数指针，只读或局部性修改） |
##Stack.h Stack< typename Te>value; *MinStack< typename Te>value; *MaxStack< typename Te>value; *MinQueue< typename Te>value; *MaxQueuek< typename Te>value;
API:
| API | Info |
|---|---|
| bool empty() | return this stack is empty or not |
| int size() | return the size of this stack |
| void push(T const&e) | push an element into stack |
| T pop() | pop an element out of stack |
| T top() | return top element of stack |
| T max() | *return max element of stack |
| T min() | *return min element of stack |
| *in MaxStack.h |
##Queue.h Queue< typename Te>value; API:
| API | Info |
|---|---|
| size() | return _size |
| empty() | return if empty or not |
| void enqueue ( T const& e ) | 入队：尾部插入 |
| T dequeue() | 出队：首部删除 |
| T& front() | 返回队首 |
##BinTree.h
Bintree< typename Te>value;
API:
| API | INFO |
|---|---|
| int size() const | 规模 |
| bool empty() const | 判空 |
| BinNodePosi(T) root() | 树根 |
| BinNodePosi(T) insertAsRoot ( T const& e ) | 插入根节点 |
| BinNodePosi(T) insertAsLC ( BinNodePosi(T) x, T const& e ) | e作为x的左孩子（原无）插入 |
| BinNodePosi(T) insertAsRC ( BinNodePosi(T) x, T const& e ) | e作为x的右孩子（原无）插入 |
| BinNodePosi(T) attachAsLC ( BinNodePosi(T) x, BinTree* &T ) | T作为x左子树接入 |
| BinNodePosi(T) attachAsRC ( BinNodePosi(T) x, BinTree* &T ) | T作为x右子树接入 |
| int remove ( BinNodePosi(T) x ) | 删除以位置x处节点为根的子树，返回该子树原先的规模 |
| BinTree* secede ( BinNodePosi(T) x ) | 将子树x从当前树中摘除，并将其转换为一棵独立子树 |
| void travLevel ( VST& visit ) { if ( _root ) _root->travLevel ( visit ) | 层次遍历 |
| void travPre ( VST& visit ) { if ( _root ) _root->travPre ( visit ) | 先序遍历 |
| oid travIn ( VST& visit ) { if ( _root ) _root->travIn ( visit ) | 中序遍历 |
| void travPost ( VST& visit ) { if ( _root ) _root->travPost ( visit ) | 后序遍历 |
| bool operator < ( BinTree const& t ) | 比较器（==,>,<,>=,<=） |
| void dbgPrint() | 打印二叉树（竖着看） |
###Tips:
| Function | Tips |
|---|---|
| travLevel() | 把每层的节点依次压入队列 |
| travIn() | 不断迭代到左侧最深叶子处(访问)，然后返回直接后继(访问)，再按本算法处理右子树 |
| travPre() | 不断访问左孩子，把右孩子压入栈中，左侧到底后弹出栈顶，按本算法处理栈顶，直至为空 |
| travPost() | 递归实现 |
##Graph.h GraphList< typename Tv, typename Te >value; GraphMatrix< typename Tv, typename Te >value;
###API:
| API | INFO |
|---|---|
| void BFS ( int, int& ) | （连通域）广度优先搜索算法 |
| void DFS ( int, int& ) | （连通域）深度优先搜索算法 |
| void BCC ( int, int&, Stack& ) | （连通域）基于DFS的双连通分量分解算法 |
| bool TSort ( int, int&, Stack* ) | （连通域）基于DFS的拓扑排序算法 |
| void PFS ( int, PU ) | （连通域）优先级搜索框架 |
| virtual int insert ( Tv const& ) = 0 | 插入顶点，返回编号 |
| virtual Tv remove ( int ) = 0 | 删除顶点及其关联边，返回该顶点信息 |
| virtual Tv& vertex ( int ) = 0 | 顶点v的数据（该顶点的确存在） |
| virtual int inDegree ( int ) = 0 | 顶点v的入度（该顶点的确存在） |
| virtual int outDegree ( int ) = 0 | 顶点v的出度（该顶点的确存在） |
| virtual int firstNbr ( int ) = 0 | 顶点v的首个邻接顶点 |
| virtual int nextNbr ( int, int ) = 0 | 顶点v的（相对于顶点j的）下一邻接顶点 |
| virtual VStatus& status ( int ) = 0 | 顶点v的状态 |
| virtual int& dTime ( int ) = 0 | 顶点v的时间标签dTime |
| virtual int& fTime ( int ) = 0 | 顶点v的时间标签fTime |
| virtual int& parent ( int ) = 0 | 顶点v在遍历树中的父亲 |
| virtual int& priority ( int ) = 0 | 顶点v在遍历树中的优先级数 |
| virtual bool exists ( int, int ) = 0 | 边(v, u)是否存在 |
| virtual void insert ( Te const&, int, int, int ) = 0 | 在顶点v和u之间插入权重为w的边e |
| virtual Te remove ( int, int ) = 0 | 删除顶点v和u之间的边e，返回该边信息 |
| virtual EType& type ( int, int ) = 0 | 边(v, u)的类型 |
| virtual Te& edge ( int, int ) = 0 | 边(v, u)的数据（该边的确存在） |
| virtual int& weight ( int, int ) = 0 | 边(v, u)的权重 |
| void bfs ( int ) | 广度优先搜索算法 |
| void dfs ( int ) | 深度优先搜索算法 |
| void bcc ( int ) | 基于DFS的双连通分量分解算法 |
| Stack* tSort ( int ) | 基于DFS的拓扑排序算法 |
| void prim ( int ) | 最小支撑树Prim算法 |
| void dijkstra ( int ) | 最短路径Dijkstra算法 |
| template void pfs ( int, PU ) | 优先级搜索框架 |
##BSTree.h BSTree < typename T > value; ###API:
| API | INFO |
|---|---|
| virtual BinNodePosi(T) &search(const T&e) | 搜索 |
| virtual BinNodePosi(T) insert(const T&e) | 插入 |
| virtual bool remove(const T&e) | 删除 |
AVLTree < typename T > value;
| API | INFO |
|---|---|
| BinNodePosi(T) insert (const T&e) | 插入 |
| bool remove(const T &e) | 删除 |
##Time.h TIME t1; ###API:
| API | INFO |
|---|---|
| TIME(const TIME &t) | 拷贝构造函数 |
| TIME operator =(const TIME &t) | 等号重载 |
| TIME operator - (const TIME &d) | 减号重载 |
| void print() | 打印时间 |
| void set_time() | 设置时间为当前时间 |
###Ex.
TIME t1,t2,t3;
t1.set_time();
//...comments...
t2.set_time();
t3 = t2 - t1;
t3.print();
###Hashtable.h Hashtable<typename KEY,typename VALUE> ht; ##API:
| API | INFO |
|---|---|
| int size() | return size |
| void insert(KEY,VALUE) | insert elements |
| VALUE find(KEY) | return values |