树是一种非线性数据结构 树是由 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;

位置 {linux-2.6.39}includelinuxlist.h 依赖 #include <linux/types.h> #include <linux/stddef.h> #include <linux/poison.h> #include <linux/prefetch.h>

Linux 内核中常用的两个宏定义 {代码...} 见招拆招 - 第一式：编译器做了什么？ offsetof 用于计算 TYPE 结构体中 MEMBER 成员的偏移位置 {代码...} 编译器清楚的知道结构体成员的偏移位置 通过结构体变量首地址与偏移量定位成员变量 编程实验： offsetof 原理剖析 {代码...} 结论 计算成员变量与其结构体变量首地址的偏...

单链表的另一个缺陷 单向性 只能从头结点开始高效访问链表中的数据元素 缺陷 如果需要逆序访问单链表中的数据元素将及其低效 {代码...} 双向链表 设计思路 在 “单链表” 的结点中增加一个指针 pre，用于指向当前结点的前驱结点。 双向链表的继承层次结构 LinkList 的定义 {代码...} 编程实验：双向链表的实现 文件：DualL...

概念上 任意数据元素都有一个前驱和一个后继 所有的数据元素的关系构成一个逻辑上的环 实现上 循环链表是一种特殊的单链表 尾结点的指针域保存了首结点的地址

课程目标 完成 SharedPointer 类的具体实现 SharedPointer 设计要点 类模板 通过计数机制( ref )标识堆内存 堆内存被指向时：ref++ 指针被置空时：ref-- ref == 0 时：释放堆内存 计数机制原理剖析 SharedPointer 类的声明 {代码...} 智能指针的比较 由于 SharedPointer 支持多个对象同时指向同一片堆空间；因此，必须支...

Poniter 是智能指针的抽象父类（模板） 纯虚析构函数 virtual ~Pointer() = 0 重载 operator-> () 重载 operator* ()

ISSUE_1 创建对象时的空指针问题 strdup 源代码: {代码...} 问题：strdup 未对空指针做处理。 {代码...} ==> {代码...} [修复] 文件：Exception.cpp {代码...} ISSUE_2 LinkList 中数据元素删除 {代码...} 输出：[Qt]说明：Qt中析构函数抛出的异常，无法被外部捕获 {代码...} 输出：[vs] {代码...} 问题：单链表状态...

单链表的一个缺陷 触发条件 长时间使用单链表对象频繁增加和删除元素 可能的结果 堆空间产生内存碎片，导致系统运行缓慢 新的线性表 设计思路 在“单链表”的内部增加一片预留的空间，所有的Node对象都在这片空间中动态创建和动态销毁 静态单链表的继承层次结构 静态单链表的实现思路 通过类模板定义静态单链表（StaticLin...

在单链表的内部定义一个游标(Node *m_current) 遍历开始前将游标指向位置为0的数据元素 获取游标指向的数据元素 通过结点的 next 指针移动游标

可以为线性表(List)增加一个查找操作 int find(const T &e) const; 参数： 待查找的数据元素 返回值 >=0: 数据元素第一次在线性表中出现的位置 -1: 数据元素不存在

课程目标 完成链式存储结构线性表的实现 LinkList 设计要点 类模板，通过头结点访问后继结点 定义内部结点类型 Node,用于描述数据域和指针域 实现线性表的关键操作（增，删，查，等） LinkList 的定义 {代码...} 编程实验：链表的实现 文件：LinkList.h {代码...} 文件：main.cpp {代码...} 输出： {代码...} 问题 头结...