树  0.1
数据结构_第6章
Documentation

文档

Overview

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

文件结构

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

  • ./include: 头文件
  • ./src: 测试例程
  • ./doc: HTML和LATEX文档
cd ./path/to/projectRoot
./doc/html/index.html

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
  • 例2 编译并执行所有测试
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](https://gcc.gnu.org/onlinedocs/gcc/Warning-Options.html#Warning-Options)
  8. 二叉树遍历的非递归实现是[用堆栈消除递归的一般方法](https://www.codeproject.com/Articles/418776/How-to-replace-recursive-functions-using-stack-and)的简化情况。教材给出的方法可视作一般方法的简单情况，于是此方法统一了教材给出的递归消除方案。用于[binaryTree.hh`](include/binaryTree.hh)
    • 连续递归调用，可归为一个stage，按反序一次性进栈。
    • 有限次连续tail recursions不必分stage，直接按反序进栈即可
  9. 类的非静态数据成员不能作成员函数的默认实参：原因。

  10. 函数模板的特定实例作类模板的特定实例的友元：类模板内的友元声明是否可省略模板实参？binaryTree.hh

    • 结论：可以。类模板定义内，类模板名引用处的模板实参默认同类定义使用的模板实参。例如：

    ```cpp 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

  • 第六章作业：
  • 简答题1~10，12
  • 程序设计题1~6，7~9可以用伪码或者文字表示，鼓励正式代码，课下自行思考13~15。

Contact me