未完待续
个人学习数据结构的一些代码（C++）教材和课程是根据清华大学邓俊辉老师的数据结构教程(课程链接)，代码在CLion中编写（只是为了方便输入）。代码大部分是参考邓老师提供的源码和书上的代码，加强记忆自己敲了一边，也添加了一些自己对课后习题的解答。
代码中的很多算法和数据结构的构造十分经典，我也根据自己的学习从新归纳整理了下
//copyright and some information of Junhui DENG
/*********************************************************************
* Data Structures in C++
* ISBN: 7-302-33064-6 & 7-302-33065-3 & 7-302-29652-2 & 7-302-26883-3
* Junhui DENG, deng@tsinghua.edu.cn
* Computer Science & Technology, Tsinghua University
* Copyright (c) 2006-2013. All rights reserved.
***********************************************************************/-
-
`get()`: 获取当前Fib项; `next()`: 转至下一个Fib项;
prev(): 转至前一个Fib项目 -
迭代法`long long fibI( int n)`( $O(n)$ ); 二分递归`long long fib(int n)`( $O(2^n)$ ); 线性递归
long long fib(int n, long long &prev)($O(n)$ )
-
-
Chapter_1_unrun_code: 习题程序
-
Fun1_7: 包含循环、分支、子函数调用，甚至递归算法的样例程序
-
Fun1_12: 统计整数二进制展开中数位1的总数 (两种方法) (邓老师提供里测试代码countones)
-
Fun1_13: 幂函数$2^n$算法 (蛮力递归版本
$O(2^r)$ )//r为输入比特长度 -
Fun1_14: 幂函数$2^n$算法(优化迭代版本)
$O(r)$ //r为输入比特长度 -
Fun1_15: 计算数组区间A[lo, hi）的最大值 ( 二分递归 )
-
1_25_gcdCN: 最大公约数为题
九章算术 “中华更相减损数”gcdCN: $O( log(a+b) )$ 欧式算法gcd: $O( log(a*b) )$ -
1_26_shift2: 将数组左循环k位
-
1_27_Ackermann: 计算Ackermann函数值
-
1_29_Hailstone: Hailstone 序列
-
-
Vector数据结构极其相关方法
-
main.cpp: 测试程序 (iussues unsolved)
-
Vector.h: vector模板类
-
Vector_implementatiom.h: 引入vector各方法的实现头文件
-
T &operator[](Rank r) const// 重载下标操作符[]，可以通过vecotr[]访问向量中的元素
-
vector_assignment.h:
Vector<T> & operator = ( Vector<T> const& )//重载下标操作符=，可以通过vecotr[]访问向量中的元素 -
vector_constructor_by_copying.h
void copyFrom(T const *A, Rank lo, Rank hi)//复制数组区间A[lo,hi]
-
- `void expand() //空间不足时扩容(翻倍)
-
void shrink()// 填装因子过小时压缩(减半)
-
Rank insert ( Rank r, T const& e )// 插入元素
-
T remove ( Rank r)// 删除秩为r的元素
-
Rank insert ( Rank r, T const& e )//插入元素
-
int remove ( Rank lo, Rank hi)// 删除秩在区间[lo, hi)内的元素
-
int disordered() const// 判断向量是否以排序，返回向量中逆序相邻元素对的总数
-
Rank find(T const &e, Rank lo, Rank hi) const// 无序向量区间查找
-
Rank binSearch ( T* A, T const& e, Rank lo, Rank hi )// 二分查找算法（版本A）：在有序向量的区间[lo, hi)内查找元素e，0 <= lo <= hi <= _size，3个判断条件e=V[mid], e.g.
-
Rank binSearch ( T* A, T const& e, Rank lo, Rank hi )// 二分查找算法（版本B），2个判断条件e<V[mid], e.g.
-
Rank binSearch ( T* A, T const& e, Rank lo, Rank hi )// 二分查找算法（版本A）：2个判断条件e<V[mid], e.g.，有多个命中元素时，总能保证返回秩最大者
-
Rank fibSearch ( T* A, T const& e, Rank lo, Rank hi )// Fibonacci查找算法（版本A）：在有序向量的区间[lo, hi)内查找元素e，0 <= lo <= hi <= _size
-
Rank fibSearch ( T* A, T const& e, Rank lo, Rank hi )// Fibonacci查找算法（版本A）：在有序向量的区间[lo, hi)内查找元素e，0 <= lo <= hi <= _size，3个判断条件(包含等于)，利用fibonacci是的左右分支更为平衡
-
Rank fibSearch ( T* A, T const& e, Rank lo, Rank hi )// Fibonacci查找算法（版本A）：2个判断条件(不含等于)，利用fibonacci是的左右分支更为平衡
-
Rank search(T const &e, Rank lo, Rank hi) const// 随机选用binary search或者fibonacci search
-
void traverse ( void (* ) ( T& ) )// 遍历（使用函数指针，只读或局部修改）
template <typename VST> void traverse ( const VST& )// 遍历（使用函数对象，可全局修改）
-
void unsort ( Rank lo, Rank hi)// 等概率随机置乱区间[lo, hi)
-
void unsort ( Rank lo, Rank hi)// 向量区间[lo, hi)排序，随机选取排序算法
-
bool bubble ( Rank lo, Rank hi )// 冒泡排序一趟扫描，有序标志位
Rank bubbleB ( Rank lo, Rank hi )// 冒泡排序一趟扫描改进(习题2-25)，记录向右最后一个逆序元素Rank bubbleC ( Rank lo, Rank hi )// 冒泡排序一趟扫描改进(习题2-25)，记录向左最后一个逆序元素(右向左扫描)
-
void bubbleSort(Rank lo, Rank hi)// 冒泡排序
void bubbleSortB(Rank lo, Rank hi)// 冒泡排序一趟扫描改进B(习题2-25)void bubbleSortC(Rank lo, Rank hi// 冒泡排序一趟扫描改进C(习题2-25)
-
void selectionSort ( Rank lo, Rank hi )//选择排序
-
void merge(Rank lo, Rank mi, Rank hi)// 归并算法
void mergeUniquify(Rank lo, Rank mi, Rank hi)// 归并去重算法
-
vector_partition_a.h // 向量快速排序轴点构造算法a
-
vector_partition_a1.h // 向量快速排序轴点构造算法a1，与a等价
-
vector_partition_b.h // 向量快速排序轴点构造算法b，可优化处理多个关键码雷同的退化情况
-
vector_partition_b2.h // 向量快速排序轴点构造算法b1，等价b
-
vector_partition_c.h // 向量快速排序轴点构造算法c，尽可能保持稳定
-
vector_heapSort.h // 向量快速排序轴点构造算法c，尽可能保持稳定
-
int Vector<T>::uniquify()// 有序向量重复元素剔除算法
-
int deduplicate()// 删除无序向量重复元
int deduplicateB()// 删除无序向量重复元，算法B，按互异元素块int deduplicate( Rank lo, Rank hi)// 删除无序向量重复元素O(nlogn)
-
void increase(Vector<T>& V)//元素+1，函数对象方法
-
void decrease(Vector<T>& V)//元素-1，函数对象方法
-
void _double(Vector<T> & V)//元素*2，函数对象方法
-
Rank expSearch(T const &e, Rank lo, Rank hi) const//指数查找习题
-
Rank intpSearch(T const &e, Rank lo, Rank hi) const//差值查找2-24
-
saddleback(int A[n][n], int x)// saddleback search 马鞍查找(伪代码)
-
-
bitmap结构及方法
- bitmap.h // 位图Bitmap类
- bitmap_o1_init_set_only.h // 位图Bitmap类：以空间作为补偿，节省初始化时间（仅允许插入，不支持删除）
- bitmap_o1_init.h // 位图Bitmap类：以空间作为补偿，节省初始化时间（既允许插入，亦支持删除）
- Eratosthenes.h // 筛选法求素数
- List 结构及方法
-
main.cpp结构及方法
-
list_test.h结构及方法
-
List.h List模板类
-
listNode.h List节点模板类（双向链表形式实现）
-
listNode_implementation.h List节点方法
-
ListNodePosi(T) ListNode<T>::insertAsSucc(T const &e)// 将e紧随节点之后插入于当前节点所属列表（设有哨兵尾节点trailer）
-
ListNodePosi(T) ListNode<T>::insertAsPred(T const &e)// 将e紧靠当前节点之前插入于当前节点所属列表（设有哨兵头节点header）
-
List_implementation.h List方法实现头文件
-
T& List<T>::operator[] (Rank r) cosnt// 操作符重载寻秩访问（低效率 O(n) ）
-
void List<T>::init()// 列表初始化，头尾哨兵初始化
-
void List<T>::copyNodes(ListNodePosi(T) p, int n)// 依次作为末节点插入，自p起n项
-
List<T>::List(ListNode<T> *p, int n)// 复制列表中自位置p起的n项List<T>::List(List<T> const& L)// 整体复制列表LList<T>::List(List<T> const& L, Rank r, int n)// 复制L中自第r项起的n项（assert: r+n <= L._size）
-
List<T>::~List()// 析构函数
-
int List<T>::disordered() cosnt// 统计逆序相邻元素对的总数
-
ListNode<T> * List<T>::search(T const &e, int n, ListNode<T> *p) const// 在有序列表内节点p（可能是trailer）的n个（真）前驱中，找到不大于e的最后者
-
ListNode<T> * List<T>::insertAsFirst(T const &e)// e当作首节点插入ListNode<T> * List<T>::insertAsLast(T const &e)// e当作末节点插入ListNode<T> * List<T>::insertPred(T const &e)// e当作p的后继插入ListNode<T> * List<T>::insertSucc(T const &e)// e当作p的后继插入
-
List<T>::remove(ListNode<T> *p)// 删除合法节点p，返回其数值
-
int List<T>::clear()// 清空列表
-
void List<T>traverse(void (*visit)(T &))// 链表遍历（函数指针）void List<T>traverse(const VST & visit )// 链表遍历（函数对象）
-
void List<T>::sort(ListNode<T> *p, int n)// 随机调用3种排序算法：插入、选择和归并
-
void List<T>::insertonSort(ListNode<T> *p, int n)// 链表的插入排序算法：对起始于位置p的n个元素排序
-
ListNode<T> * List<T>::selectMax(ListNode<T> *p, int n)// 从起始于位置p的n个元素中选出最大者
-
void List<T>::selectionSort(ListNode<T>*p, int n)// 链表选择排序算法：对起始于位置p的n个元素排序
-
void List<T>::merge(ListNode<T>* &p, int n, List<T> &L, ListNode<T>* q, int m )// 链表归并（p, q）
-
void List<T>::mergeSort(ListNode<T>* &p, int n)// 链表归并排序
-
List<T>::deduplicate()// 无序链表去重
-
int List<int>::uniquify()// 有序链表去重
-
void List<T>::reverse()// 前后倒置1
-
void List<T>::reverse()// 前后倒置2
-
void List<T>::reverse()//前后倒置3
-
int josehus(int n, int k)// 习题3-19
-
-
convsrsion: 进制转换
- convert.h // 利用栈进行进制转换
- convertB.h // 十进制正整数n到base进制的转换（递归版）
-
Stack: 栈类及方法
- main.cpp // 测试程序
- stack_test.h // 测试头文件
- Stack.h // 栈类
- stack@vector.h // 以向量为基类，派生出的栈
void push (T const& e)// 入栈T pop()// 出栈T& top()// 取顶
- stack@list.h // 以列表为基类，派生出栈模板类
void push (T const& e)// 入栈T pop()// 出栈T& top()// 取顶
- parn_code_4_5.cpp // 习题4-5括号匹配
- stackPermutation_4_3.cpp // 习题4-3
-
Queue: 队列类及方法
- main.cpp // 测试程序
- Queue_test.h // 测试头文件
- Queue.h // 队列类
void enqueue(T const& e)// 入队：尾部插入T dequeue()// 出队：首部删除T & front()// 队首
-
RPN: 逆波兰表达式
- main.cpp // 测试程序
char * removeSpace( char* s)// 删除s[]中的空格
- rpn.h // 逆波兰表达式方法
- priority.h // 运算符优先级设置
- caculation.cpp // 计算
float calcu(float a, char op, float b)// 二元运算float calcu (char op, float b)// 一元运算（阶乘）
- displayprogress.cpp // 显示表达式处理进展
- readnumber.cpp
void readNumber( char*& p, Stack<float>& stk)// 将起始于p的子串解析为数值，并存入操作数栈
- priority.cpp
Operator optr2rank (char op)// 由运算符转译出编号char orderBetween(char op1, char op2)// 比较两个运算符之间的优先级
- append2rpn.cpp
void append ( char*& rpn, float opnd)// 将运算数接到RPN尾部void append(char*& rpn, char optr)// 将运算符接至RPN末尾
- rpn.cpp
float evaluate (char *S, char*& RPN)// 对（已剔除白空格的）表达式S求值，并转换为逆波兰式RPN
- main.cpp // 测试程序
-
queen_stack: n皇后问题
- main.cpp // n皇后迭代版测试
- queen_stack.h // 方法头文件
- queen.h // 皇后类
- place_queens.cpp // N皇后算法（迭代版）：采用试探/回溯的策略，借助栈记录查找的结果
- display_progress.cpp
void displayRow ( Queen& q )// 打印当前皇后（放置于col列）所在行void displayProgress ( Stack<Queen>& S, int nQueen )// 在棋盘上显示搜查的进展
-
laby: 迷宫问题
- string pattern match测试程序(match函数未定义)
- string_pm_test.h: 测试头文件
- string_pm_test.cpp: 测试主函数
- Brute-force算法：两种，复杂度相同
- KMP算法
-
int match ( char* P, char* T )//kmp算法
-
int* buildNext ( char* P )//构造模式串P的next表
-
int* buildNext ( char* P )//改进next表，去重
-
_share和_unprint文件为邓老师的测试辅助文件，注释掉了部分内容，随着更新会逐步取消相关注释
UNFINISHED!!!
The code of Data Structures in C++(Junhui Deng, tshinghua university)
The code are code are programed in CLion. Not all the file were compiled.
This repo mainly for record the work I have done. Some codes provided by Prof. Deng is really clever and they could be good reference in future.
Citation
//copyright and some information of Junhui DENG
/*********************************************************************
* Data Structures in C++
* ISBN: 7-302-33064-6 & 7-302-33065-3 & 7-302-29652-2 & 7-302-26883-3
* Junhui DENG, deng@tsinghua.edu.cn
* Computer Science & Technology, Tsinghua University
* Copyright (c) 2006-2013. All rights reserved.
***********************************************************************/-
-
Fibonacci sequence (class)：
`get()`: Get current fibonacci value; `next()`: Get next fibonacci value;
prev(): Get previous fibonacci value -
Iteration `long long fibI( int n)`( $O(n)$ ); Binary Recursion `long long fib(int n)`( $O(2^n)$ ); Linear Recursion
long long fib(int n, long long &prev)($O(n)$ )
-
-
Chapter_1_unrun_code: exercise
-
Fun1_7: A program contains loop, branch, subfunction and recursion
-
Fun1_12: Count the total number of digits 1 in the binary expansion of an integer (Two methods) ( also contained in countones sourcecodes provided by Prof. Deng )
-
Fun1_13: Caculate power function
$2^n$ ( brute force recursion$O(2^r)$ )//r donates the bit length of input data -
Fun1_14: Caculate power function
$2^n$ ( iteration$O(r)$ )//r donates the bit length of input data -
Fun1_15: Caculate the max value in A[lo, hi）( binary recursion )
-
1_23_Hanoi: Hanoi problem
-
1_25_gcdCN: Greatest Common Divisor (GCD)
The Nine Chapters on the Mathematical Art “中华更相减损术” gcdCN: $O( log(a+b) )$ Euclid algorithm, gcd: $O( log(a*b) )$ -
1_26_shift2: move k bits of an array from right to left
-
1_27_Ackermann: Caculate Ackermann function
-
1_29_Hailstone: Hailstone sequence
-