基于数据元素值的查找 BTreeNode<T> *find(const T &value) const; 基于结点的查找 BTreeNode<T> *find(TreeNode<T> node) const;

BTree 为二叉树结构，每个结点最多只有两个后继结点 BTreeNode 只包含四个固定的公有成员（1数据、1前驱指针、2后驱指针） 实现树结构的所有操作（增，删，查，等）

性质 1 在二叉树的第 i 层最多有 2i-1 个结点(i >= 1)。 第一层最多有 21-1 = 1 个结点 第二层最多有 22-1 = 2 个结点 第二层最多有 23-1 = 4 个结点 ... 性质 2 高度为 k 的二叉树最多有 2k-1 个结点(k >= 0)。 如果有一层，最多有 1 = 21-1 = 1 个结点 如果有两层，最多有 1 + 2 = 22 - 1 = 3 个结点 如果有三层...

通用树结构的回顾 双亲孩子表示法 每个结点都有一个指向其双亲的指针 每个结点都有若干个指向其孩子的指针 另一种树结构模型 孩子兄弟表示法 每个结点都有一个指向其第一个孩子的指针 每个结点都有一个指向其第一个右兄弟的指针 孩子兄弟表示法的特点 能够表示任意的树形结构 每个结点包含一个数据成员和两个指针成员 孩...

在树中定义一个游标 (GTreeNode<T> *) 遍历开始前将游标指向根结点 (root()) 获取游标指向的数据元素 通过结点的 child 成员移动游标

树中结点的数目 定义功能：count(node) 在 node 为根结点的树中统计结点数目 树结点数目的计算示例 count(A) = count(B) + count(C) + count(D) + 1 编程实验：树中结点的数目 {代码...} 树的高度 定义功能：height(node) 获取 node 为根结点的树的高度 树的高度示例 height(A) = MAX{ height(B), height(C), height(D) ...

基于数据元素的删除 SharedPointer<Tree<T>> remove(const T &value) 基于结点的删除 SharedPointer<Tree<T>> remove(TreeNode<T> *node)

清除操作的定义 void clear() 将树中所有的结点清除（释放堆中的结点） 树中数据元素的清除 清除操作功能的定义 free(node) 清除 node 为根结点的树 释放树中的每一个结点 编程实验：清除树中的结点 文件：GTree.h {代码...} 问题 树中的结点可能来源于不同的存储空间，如何判断堆空间中的结点并释放？ {代码...} 问题分...

插入新结点 bool insert(TreeNode<T> *node); 插入数据元素 bool insert(const T &value, TreeNode<T> *parent);

基于数据元素值的查找 GTreeNode<T> *find(const T &value) const; 基于结点的查找 GTreeNode<T> *find(TreeNode<T> *node) const;

GTree 为通用树结构，每个结点可以存在多个后继结点 GTreeNode 能够包含任意多个指向后继结点的指针 实现书结构的所有操作（增，删，查，等）

树是一种非线性数据结构 树是由 n(n>=0) 个结点组成的有限集合 如果 n = 0, 称为空树； 如果 n > 0, 则： 有一个特定的称之为根(root)的结点 根结点只有直接后继，但没有直接前驱 除根以外的其它结点划分为m(m>=0)个互不相交的有限集合T0,T1,...,Tm-1,每个集合又是一颗树，并且称之为根的子树(sub tree)

应用一 排序类(Sort(与数组类(Array)的关系 新增的成员函数 编程实验：排序类与数组类的关系 文件：Array.h {代码...} 文件：Sort.h {代码...} 文件：main.cpp {代码...} 输出： {代码...} 应用二 问题 当待排数据元素为体积庞大的对象时，如何提高排序的效率？ {代码...} 问题分析 排序过程中不可避免的需要进行交换操...

将 3 个有序序列归并为一个新的有序序列，称为 3 路归并 将 N 个有序序列归并为一个新的有序序列，称为 N 路归并 将多个有序序列归并为一个新的有序序列，称为多路归并

每次从后向前进行 （假设为第 i 次），j = n-1, n-2,...,i;两两比较 V[j-1] 和 V[j] 的关键字；如果发生逆序，则交换 V[j-1] 和 V[j]。

每次（例如第 i 次， i = 0,1,...,n-2） 从后面 n-i 个待排的数据元素中选出关键字最小的元素，作为有序元素序列 i 个元素。

例：将下列关键字序列52,49,80,36,14,58,61,23,97,75调整为:14,23,36,49,52,58,61,75,80,97

程序运行后有一个特殊的内存区供函数调用使用 用于保存函数中的形参，局部变量，临时变量，等 从起始地址开始往一个方向增长（如：高地址->低地址） 有一个专用 "指针" 标识当前已使用内存的 "顶部"

单链表的转置 编程实验：单链表的转置 {代码...} 输出： {代码...} 单向排序链表的合并 编程实验：单向排序链表的合并 {代码...} 输出： {代码...} 汉诺塔问题 将木块借助 B 柱由 A 柱移动到 C 柱每次只能移动一个木块只能出现小木块在大木块之上 汉诺塔问题分解 将 n-1 个木块借助 C 柱由 A 柱移动到 B 柱 将最底层的唯...

将原问题分解为规模较小的问题进行处理 分解后的问题与原问题类型完全相同，但规模较小 通过小规模问题的求解，能够轻易求得原问题的解 问题的分解是有限的（递归不能无限进行） 当边界条件不满足时，分解问题（递归继续进行） 当边界条件满足时，直接求解（递归结束）

int indexOf(const char *s) const; int indexOf(const String &s) const;

问题 如何在目标字符串 S 中，查找是否存在子串 P？ 朴素解法 {代码...} 朴素算法的一个线索优化 因为，pa != pb 且 pb == sb;所以，Pa != sb;结论，字串 p 右移 1 位比较，没有意义且低效。 优化示例 伟大的发现: KMP算法 KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它...

char &operator [] (int i); char operator [] (int i) const; 注意事项 当 i 的取值不合法时，抛出异常 合法范围： (0 <= i) && (i < m_length)

无缝实现 String 对象与 char *字符串的互操作 操作符重载函数需要考虑是否支持 const 版本 通过 C 语言中的字符串函数实现 String 的成员函数

准备两个栈用于实现队列： stack_in 和 stack_out 当有新元素入队时：将其压入 stack_in 当需要出队时： stack_out() == 0 : 将 stack_in 中的元素逐一弹出并压入 stack_out stack_out.size() > 0 : 将 stack_out 的栈顶元素弹出

顺序队列的问题 当数据元素为类类型，StaticQueue 的对象在创建时会多次调用元素类型的构造函数，影响效率！ 文件：main.cpp {代码...} 输出： {代码...} 队列的链式存储实现 链式队列的设计要点 类模板，抽象父类 Queue 的直接子类 在内部使用链式结构实现元素的存储 只在链表的头部和尾部进行操作 编程实验：基于 Link...

创建队列 (Queue()) 销毁队列 (~Queue()) 清空队列 (clear()) 进队列 (add()) 出队列 (remove()) 获取队头元素 (front()) 获取队列的长度 (length())

顺序栈的问题 当存储的元素类型为类类型，StaicStack 的对象在创建时会多次调用元素类型的构造函数，影响效率！ 文件:main.cpp {代码...} 输出： {代码...} 原因： T m_space[N]; 链式栈的存储实现 链式栈的设计要点 类模板，抽象父类 Stack 的直接子类 在内部组合使用 LinkList 类，实现栈的链式存储 只在单链表成员对...

创建栈 (Stack()) 销毁栈 (~Stack()) 清空栈 (clear()) 进栈 (push()) 出栈 (pop()) 获取栈顶元素 (top()) 获取栈大小 (size())

使用 Linux 内核链表实现 DTLib 中的双向循环链表 template <typename T> class DualCircleList;