使用面向对象理论、泛型编程思想、C++语言中重载、继承、接口、多态和模板等技术，实现相关的数据结构和常规算法，打造了一个可复用的数据结构类私有库。其中创建了线性表的顺序存储、数组、单/双向/循环链表、栈、队列、通用树、二叉树、图等模板；递归、排序、kmp、八皇后问题等算法的实现；顶层弗列、单一继承树、异...

使用数列中的元素和元素间的关系建立图模型 [重要] 图中顶点的附加数据为对应的数列元素值 图中的边按照如下方式建立 当数列中的某个元素与后序元素存在不下降关系时 从该元素对应的顶点到后继元素对应的顶点存在一条有向边 边的权值固定为 1

定义一个 n 阶方阵序列： A-1， A0,..., An-1 其中： A-1[i][j] = Edge[i][j] Ak[i][j] = min{ Ak-1[i][j], Ak-1[i][k] + Ak-1[k][j]} k = 0, 1, ..., n-1

参考：图论最短距离(Shortest Path)算法动画演示-Dijkstra(迪杰斯特拉)和Floyd(弗洛伊德) 最短路径的概念 如果从有向图中某一顶点（起始顶点）到达另一顶点（终止顶点）的路径不止一条，那么如何找到一条路径使得此路径各边上的权值总和达到最小？ 问题 给定一个带权有向图 G 与起始顶点 v ，求从 v 到 G 中其它顶点的最...

参考：最小生成树(Kruskal(克鲁斯卡尔)和Prim(普里姆))算法动画演示 最小生成树的特征 选取的边是图中权值较小的边 所有边连接后不构成回路 问题 既然最小生成树关心的是如何选择 n-1 条边，那么是否可以直接以边为核心进行算法设计？ 简单尝试 由 4 个顶点构成的图，选择 3 条权值最小的边 需要解决的问题 如何判断新选...

参考：最小生成树(Kruskal(克鲁斯卡尔)和Prim(普里姆))算法动画演示 运营商的挑战 在下图标出的城市间架设一条通信线路 要求： 任意两个城市间都能够通信 将假设成本降至最低 问题：如何在图中选择 n-1 条边使得 n 个顶点间两两可达，并且这 n-1 条边的权值之和最小？ 最小生成树 仅使用图中的 n-1 条边连接图中的 n 个...

原料：class LinkStack<T>; 步骤： 将起始顶点压入栈中 弹出栈顶顶点 v， 判断是否已经标记（比较：转2； 未标记：转3） 标记顶点， 并将顶点 v 的邻接顶点压入栈中 判断栈是否为空（非空：转2； 空：结束）

图的选择 MatrixGraph vs ListGraph 如何选择 ？ 时间复杂度的对比分析 小结论 MatrixGraph 适用于内存资源富足的场合（性能较好） ListGrap 适用于内存资源受限的场合 （节省空间） 图的遍历 从图中的某一顶点出发，沿着一些边访问图中的其它顶点，使得每个顶点最多被访问一次。 注：从某个顶点出发进行遍历，不一定能...

邻接矩阵法中的残留问题 {代码...} MatrixGraph 无法动态 添加 / 删除 顶点！！！ 资源耗费大；N = 1000, 邻接矩阵的体积为 4 * 1000 * 1000 字节；因此，图对象创建时的体积约为 4MB ！！！ 基本思想 为了进一步提高空间使用率，可以考虑使用链表替代数组，将邻接矩阵换为邻接链表。 邻接链表法 图中的所有顶点按照编号...

基本思想 用一维数组存储顶点：描述顶点相关的数据 用二维数组存储边：描述顶点间的关系和权 邻接矩阵法 设图 A = (V, E) 是一个有 n 个顶点的图，图的邻接矩阵为 Edgen, 则： 注：解决工程问题时，习惯于对图中的每个顶点进行编号；当需要权值时，取 W 非空表示结点间有连接。 无向图邻接矩阵法 无向图的邻接矩阵是对称...

图的定义 图是由顶点集合（Vertex）及顶点间的关系集合（Edge）组成的一种数据结构 : Graph = (V, E) V = {X | X ∈ 某个数据对象} 是顶点的有穷非空集合E = {(x, y) | x, y ∈ V} 是顶点之间关系的有穷集合 图的分类 思考：G1,G2,G3,G4 都是图吗？有什么异同？可以继续分类吗？ 无向边 顶点 x 和 y 之间的边没有方向，则...

面试题 一 单结点删除描述：编写一个函数用于删除二叉树中的所有单度结点要求：结点删除后，其唯一的子结点替代它的位置 情形1：结点中包含指向父结点的指针 定义功能：delOdd1(node) 删除 node 为根结点的二叉树中的单度结点 编程实验：单度结点的删除 {代码...} 输出： {代码...} 情形2：结点中只包含左右孩子指针 定...

将二叉树转换为双向链表的过程（非线性 → 线性） 能够反映某种二叉树的遍历次序（结点的先后访问次序） 利用结点的 right 指针指向遍历中的后继结点 利用结点的 left 指针指向遍历中的前驱结点

SharedPointer<BTree<T>> clone() const 克隆当前树的一份拷贝 返回值为堆空间中的一颗新二叉树（与当前树相等）

先序遍历 （Pre-Order Traversal） 中序遍历 （In-Order Traversal） 后序遍历 （Post-order Traversal）

二叉树的遍历 （Traversing Binay Tree） 是指从根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次，且仅被访问一次。

二叉树的属性操作 二叉树中结点的数目 定义功能： count(node) 在 node 为根结点的二叉树中统计结点数目 编程实验：二叉树中结点的数目 {代码...} 二叉树的高度 定义功能：height(node) 获取 node 为根结点的二叉树的高度 编程实验：二叉树的高度 {代码...} 二叉树的度数 定义功能：degree(node) 获取 node 为根结点的二...

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

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

基于数据元素值的查找 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 能够包含任意多个指向后继结点的指针 实现书结构的所有操作（增，删，查，等）