位置 {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 如何实现...

顺序存储的定义 线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表中的数据元素。 实际思路 可以用一维数组来实现顺序存储结构 存储空间：T *m_array; 当前长度： int m_length; {代码...} 顺序存储结构的元素获取操作 判断目标是否合法 将目标位置作为数组下标获取元素 {代码...} 顺序存储结构的元...

生活中的智慧 幼儿园老师总会让小朋友以同样的排队秩序出行。 线性表（List）的表现形式 零个或多个数据元素组成的集合 数据元素在位置上是有序排列的 数据元素的个数是有限的 数据元素的类型必须相同 线性表（List）的抽象定义 线性表是具体有相同类型的 n(>=0)个数据元素的有限序列 (a0, a1, ..., an-1) ai 是表项...

Exception 类继承自 Object 堆空间中创建异常对象失败时，返回NULL指针 新增 InvalidOperationException 异常类 成员函数调用时，如果状态不正确则抛出异常 SmartPointer 类继承自 Object 类 堆空间中创建智能指针对象失败时，返回NULL指针

当代软件架构实践中的经验 尽量使用单重继承的方式进行系统设计 尽量保持系统中只存在单一的继承树 尽量使用组合关系代替继承关系 不幸的事实 C++ 语言的灵活性使得代码可以存在多个继承树 C++ 编译器的差异使得同样的代码可能表现不同的行为 new 操作如果失败会发生什么？ 老版编译器：返回空 新版编译器：抛出异常 创...

异常的类型可以是自定义类类型 对于类类型异常的匹配依旧是至上而下严格匹配 赋值兼容性原则在异常匹配中依然适用 一般而言 匹配子类异常的 catch 放在上部 匹配父类异常的 catch 放下下部 现代C++库必然包含充要的异常类 异常类是数据结构类所依赖的”基础设施“！ 异常类功能定义 异常类 功能定义 ArithmeticException ...

C++ 内置了异常处理的语法元素 try...catch... try 语句处理正常代码逻辑 catch 语句处理异常代码逻辑 try 语句中的异常由对应的 catch 语句处理

内存泄漏（臭名昭著的Bug） 动态内存申请堆空间，用完后不归还 C++ 语言中没有垃圾回收的机制 指针无法控制所指堆空间的生命周期 当代C++软件平台中的智能指针 指针生命周期结束时主动释放堆空间 一片堆空间最多只能由一个指针标识 杜绝指针运算和指针比较 智能指针的设计方案 通过类模板描述指针的行为 能够定义不同类...

数据结构课程的特点 专注数据元素之间的关系 专注于特定结构之上的算法 数据结构课程并不关注数据元素的具体类型。 问题：如何为数据结构的学习选择合适的语言 经验分享：支持泛型编程的语言最适合数据结构课程的学习 泛型编程的概念 不考虑具体数据类型的编程方式 对于Swap函数可以考虑下面的泛型写法 {代码...} Swap ...

先从概念上形象的理解数据元素之间的关系 思考这种关系能够解决什么问题 考虑基于这种关系能够产生哪些算法 理解和熟悉最终的算法 选择一种熟悉的语言，编码实战

常见的时间复杂度 常见时间复杂度的比较 当算法的时间复杂度为 O(2n)(n为指数)，O(n!),或O(nn)(n为指数)时，即使n的值很小，实际的程序运行时间也是不可接收的。 算法的最好与最坏情况 意义：当算法在最坏情况下仍然能满足需求时，可以推断，算法的最好情况和平均情况都能满足需求。 算法分析示例 {代码...} 注意：数据...

结论：判断一个算法的效率时，操作数量中的常数项和其他次要项常常可以忽，只需要关注最高阶次项就能得出结论。 问题：如何用符号定性的判断算法的效率? 算法的复杂度（定性描述） 时间复杂度 算法运行后对时间需求量的定性描述 空间复杂度 算法运行后对空间需求量的定性描述 注意：数据结构课程重点关注的是算法的效率...

比较不同算法对同一组输入数据的运行处理时间 缺陷 为了获得不同算法的运行时间必须编写相应程序 运行时间严重依赖硬件及运行时的环境因素 算法的测试数据选取相当困难

学员间的对话 木暮：我发现三井真是牛，只用一行就实现了strlen 宫城：那么强！他是怎么做的呢？ 木暮：不知道，我看了一下，没看懂。。。 宫城：牛人就是牛人啊！ 问题：程序是否越短越好？是否别人看不懂就证明自己很厉害？ 数据结构与算法 数据结构静态的描述了数据元素之间的关系 高效的程序设计需要在数据结构的基...