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

单链表的转置 编程实验：单链表的转置 {代码...} 输出： {代码...} 单向排序链表的合并 编程实验：单向排序链表的合并 {代码...} 输出： {代码...} 汉诺塔问题 将木块借助 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 {代码...} 输出： {代码...} 问题 头结...

顺序存储结构线性表的最大问题 插入和删除需要移动大量的元素！ 链式存储的定义 为了表示每个元素与其直接后继元素之间的逻辑关系；数据元素除了存储本身的信息外，还要存储其直接后继的信息。 ai 和 ai+1 是线性表中的两个相邻数据元素；在物理内存中无相邻关系。 联系存储逻辑结构 基于链式存储结构的线性表中，每个结...

课程目标 完成 DynamicArray 类的具体实现 DynamicArray 设计要点 类模板 动态确定内部数组空间大小 实现函数返回数组长度 拷贝构造和赋值操作 DynamicArray 类的声明 {代码...} 编程实验：动态数组的实现 {代码...} 文件：main.cpp {代码...} 输出： {代码...} 问题: DynamicArray 类中的函数实现存在重复的逻辑，如何...

课程目标 完成 Array 类的具体实现 完成 StaticArray 类的具体实现 需求分析 创建数组类代替原生数组的使用 数组类包含长度信息 数组类能够主动发现越界访问 Array 要点设计 抽象类模板，存储空间的位置和大小由子类完成 重载数组操作符，判断访问下标是否合法 提供数组长度的抽象访问函数 提供数组对象间的复制操作 Arr...

SqlList中，最耗时的是插入和删除操作，因为要进行移位，尤其当数据元素是自定义类类型，并且类非常庞大时耗时尤为明显。因此，分析一段代码的效率，不能够只看时间复杂度（大O表示法），大O表示法仅为参考指标，而非绝对指标。还需要具体情况具体分析，当前算法是否真的满足需求。由此也证明顺序存储表不适合类类型的元...

课程目标 完成 StaticList 类的具体实现 完成 DynamicList 类的具体实现 StaticList 设计要点 类模板 使用原生数组作为顺序存储空间 使用模板参数决定数组大小 {代码...} 编程实验：StaticList 的实现 文件：StaticList.h {代码...} 文件：main.cpp {代码...} 输出： {代码...} DynamicList 设计要点 类模板 申请连续堆...

课程目标 完成顺序存储结构线性表的抽线实现 SqlList 设计要点 抽象类模板，存储空间的位置和大小由子类完成 实现顺序存储结构线性表的关键操作（增，删，查，等） 提供数组操作符，方便快速获取元素 {代码...} 编程实验：顺序存储线性表 SqlList.h {代码...} To be continued 思考：StaticList 和 DynamicList 如何实现...