Documentation

文档

Overview

《数据结构：思想与实现（第2版）》（翁惠玉，俞勇） 第6章 树

文件结构

注意：本章所有文件的编码都是UTF-8

Compiling

将./include文件夹加入IncludePath，编译./src文件夹中的单个源文件。

cd ./DS_Ch6
mkdir bin
g++ ./src/test0.cc -o ./bin/test0.exe -g -Wall -Wextra -Wshadow -static-libgcc -fexec-charset=GBK -std=c++17 -I ./include
./bin/test0.exe

cd ./DS_Ch6
run_test.bat

References and notes

  1. 从绝对路径解析文件所在目录：find_last_of，用于test0.cc
  2. 用C/C++调用DOS命令删除文件，用于test0.hh
  3. Returns the processor time consumed by the program：clock，用于test0.hh
  4. 获取当前时间：localtime，用于test0.hh
  5. 用堆栈消除递归的一般方法，用于binaryTree.hh
  6. 不要类内初始化struct的成员！否则无法使用列表初始化，除非定义构造函数。用于binaryTree.hh(braced-initializer-list)。
  7. 多加括号以避免优先级问题。例如优先级 && > ||，在g++编译选项开启-Wextra时，可能出现 warning: suggest parentheses around '&&' within '||'。详见gcc官方文档：-Wparentheses
  8. 二叉树遍历的非递归实现是用堆栈消除递归的一般方法的简化情况。教材给出的方法可视作一般方法的简单情况，于是此方法统一了教材给出的递归消除方案。用于binaryTree.hh
    • 连续递归调用，可归为一个stage，按反序一次性进栈。
    • 有限次连续tail recursions不必分stage，直接按反序进栈即可
  9. 类的非静态数据成员不能作成员函数的默认实参：原因。
  10. 函数模板的特定实例作类模板的特定实例的友元：类模板内的友元声明是否可省略模板实参？binaryTree.hh
    • 结论：可以。类模板定义内，类模板名引用处的模板实参默认同类定义使用的模板实参。例如：
    friend bool operator==</*T, Comparator*/>(const binaryTree /*<T, Comparator>*/ &lhs, const binaryTree /*<T, Comparator>*/ &rhs);
friend void printBinaryTree</*T, Comparator*/>(const binaryTree /*<T, Comparator>*/ &bin_tree, const typename binaryTree /*<T, Comparator>*/ ::value_type &flag, std::ostream &out);
  11. 类的拷贝/移动构造/赋值运算符重载函数
  12. 关于类的前向声明 核心是从编译器的角度思考：顺序编译到此条语句时，是否有足够的信息完成编译？ 参考资料：
  13. std::move()的后果：实参变右值，语句执行完毕后被析构，变成过期对象。

Homework

Contact me