多任务下的数据结构与算法.pdf

《多任务下的数据结构与算法（含1CD）》图书目录： 第1章 绪论 (1) 1.1 引言 (1) 1.2 C语言编程常见问题分析 (2) 1.2.1 参数校验问题 (3) 1.2.2 return语句的问题 (3) 1.2.3 while循环和for循环的问题 (4) 1.2.4 if语句的多个判断问题 (4) 1.2.5 goto语句问题 (5) 1.2.6 switch …case 和if … else if 的效率区别 (5) 1.3 任意数据类型处理 (7) 1.3.1 任意数据类型处理的设计方法 (7) 1.3.2 任意数据类型处理的实例 (8) 1.3.3 任意数据类型处理的回调函数封装 (9) 1.4 多任务介绍 (10 ) 1.4.1 多任务简介 (10) 1.4.2 锁的概念 (10) 1.4.3 Windows下常用多任务操作函数 (10) 1.4.4 Linux/Unix下常用多任务操作函数 (12) 1.4.5 VxWorks下常用多任务操作函数 (12) 1.4.6 多任务函数的封装 (13) 1.5 软件设计简介 (14) 1.5.1 软件设计历史简述 (14) 1.5.2 微观设计学原理简介 (15) 第2章 数组 (17) 2.1 栈 (17) 2.1.1 栈的基本概念 (17) 2.1.2 栈的编码实现 (18) 2.1.3 多任务栈的实现 (21) 2.2 队列 (24) 2.2.1 队列的基本概念和接口 (24) 2.2.2 环形队列(Queue) (25) 2.2.3 STL中的动态队列(STL∷deque) (29) 2.2.4 动态环形队列 (30) 2.2.5 各种队列的时间效率测试及分析 (35) 2.2.6 各种队列的适用范围 (36) 2.2.7 关于时间效率和空间效率的原则 (36) 2.3 排序表 (37) 2.3.1 排序算法介绍 (37) 2.3.2 快速排序算法 (38) 2.3.3 排序表的设计 (40) 2.3.4 非递归的快速排序算法 (43) 2.3.5 快速排序算法的复杂度分析 (47) 2.3.6 二分查找算法 (48) 2.4 实例：HOOK管理功能的实现 (49) 2.4.1 单个函数的HOOK实现 (49) 2.4.2 多个函数的HOOK实现 (50) 2.4.3 HOOK功能的应用简介 (55) 2.4.4 HOOK使用的注意事项 (56) 本章小结 (56) 习题与思考 (56) 第3章 链表 (57) 3.1 单向链表 (57) 3.1.1 单向链表的存储表示 (57) 3.1.2 单向链表的接口设计 (59) 3.1.3 单向链表的基本功能编码实现 (60) 3.2 单向链表的逐个节点遍历 (69) 3.2.1 单向链表逐个节点遍历基本概念 (69) 3.2.2 单向链表逐个节点遍历编码实现 (70) 3.3 单向链表的排序 (71) 3.3.1 插入排序 (71) 3.3.2 归并插入排序 (74) 3.3.3 基数排序 (79) 3.4 双向链表 (85) 3.4.1 双向链表的基本概念 (85) 3.4.2 双向链表的设计 (85) 3.4.3 双向链表的编码实现 (86) 3.5 使用整块内存的链表 (107) 3.5.1 整块内存链表的基本概念 (107) 3.5.2 整块内存链表的编码实现 (109) 3.6 实例：使用链表管理短信息系统的CACHE (113) 3.6.1 短信息系统的CACHE管理基本概念 (113) 3.6.2 短信息系统的发送和接收分析 (114) 3.6.3 短信息系统CACHE管理的编码实现 (115) 本章小结 (118) 习题与思考 (118) 第4章 哈希表 (119) 4.1 哈希表 (119) 4.1.1 哈希表的基本概念 (119) 4.1.2 哈希表的索引方法 (120) 4.1.3 哈希表的冲突解决方法 (123) 4.1.4 哈希表基本操作的源代码 (125) 4.2 哈希链表 (130) 4.2.1 哈希表和数组、链表的效率比较 (130) 4.2.2 时间效率和空间效率的关系 (131) 4.2.3 哈希链表的基本概念 (132) 4.2.4 哈希链表的操作 (133) 4.2.5 哈希链表的编码实现 (135) 4.3 实例：WebServer的动态CACHE文件管理 (143) 4.3.1 WebServer的动态CACHE文件管理基本概念 (143) 4.3.2 CACHE文件管理功能的设计 (144) 4.3.3 CACHE文件管理功能的编码实现 (145) 本章小结 (151) 习题与思考 (151) 第5章 树 (153) 5.1 普通树 (153) 5.1.1 普通树的描述方法 (153) 5.1.2 树的操作接口设计 (154) 5.1.3 树的遍历算法 (154) 5.1.4 树的编码实现 (157) 5.1.5 使用树的遍历算法来实现Xcopy功能 (163) 5.2 二叉树 (166) 5.2.1 二叉树的基本概念 (166) 5.2.2 二叉树的树梢及二叉树的高度 (166) 5.2.3 二叉树的描述方法 (167) 5.3 二叉排序树 (168) 5.3.1 二叉排序树的基本概念 (168) 5.3.2 二叉排序树的查找 (168) 5.3.3 二叉排序树的插入 (170) 5.3.4 二叉排序树的删除 (172) 5.3.5 二叉排序树的遍历 (176) 5.3.6 二叉排序树的旋转操作 (178) 5.4 AVL搜索树 (181) 5.4.1 AVL搜索树的基本概念 (181) 5.4.2 AVL搜索树的插入 (181) 5.4.3 AVL搜索树的删除 (184) 5.4.4 AVL树的源代码 (187) 5.5 红黑树 (205) 5.5.1 红黑树的基本概念 (205) 5.5.2 红黑树的插入操作 (206) 5.5.3 红黑树的删除操作 (209) 5.5.4 红黑树的编码实现 (214) 5.6 实例：搜索引擎的实现 (236) 5.6.1 搜索引擎的实现思路和方法 (236) 5.6.2 搜索引擎的时间效率和空间效率分析 (238) 5.6.3 高级搜索的实现 (240) 本章小结 (241) 习题与思考 (241) 第6章 复合二叉树 (243) 6.1 哈希红黑树 (243) 6.1.1 哈希红黑树的基本概念 (243) 6.1.2 哈希红黑树的查找 (245) 6.1.3 哈希红黑树的插入 (246) 6.1.4 哈希红黑树的删除 (248) 6.1.5 哈希红黑树的释放 (248) 6.1.6 哈希红黑树的遍历 (249) 6.1.7 哈希红黑树的编码实现 (249) 6.1.8 哈希红黑树的效率分析 (255) 6.2 哈希AVL树 (256) 6.2.1 哈希AVL树的基本概念 (256) 6.2.2 哈希AVL树的查找 (257) 6.2.3 哈希AVL树的插入 (258) 6.2.4 哈希AVL树的删除 (260) 6.2.5 哈希AVL树的释放 (261) 6.2.6 哈希AVL树的遍历 (261) 6.2.7 哈希AVL树的编码实现 (261) 6.2.8 复合数据结构的分类 (266) 6.3 抗DoS/DDoS攻击的实例 (267) 6.3.1 DoS/DDoS攻击的概念 (267) 6.3.2 常见DoS/DDoS攻击手段及防范策略 (268) 6.3.3 抗DoS/DDoS攻击的实现 (269) 6.3.4 抗DoS/DDoS攻击的编码实现 (269) 本章小结 (272) 习题与思考 (273) 第7章 图 (275) 7.1 图的基本概念和描述方法 (275) 7.1.1 图的基本概念 (275) 7.1.2 图的描述方法 (276) 7.2 Dijkstra最短路径算法 (277) 7.2.1 Dijkstra最短路径算法的描述 (277) 7.2.2 Dijkstra最短路径算法的过程图解 (277) 7.2.3 Dijkstra最短路径算法的编码实现 (278) 7.3 最小生成树算法 (282) 7.3.1 最小生成树算法的基本概念 (282) 7.3.2 最小生成树算法的过程图解 (282) 7.3.3 最小生成树的算法流程图 (283) 7.3.4 最小生成树算法的编码实现 (284) 7.4 深度优先搜索算法 (286) 7.4.1 深度优先搜索算法的描述 (286) 7.4.2 深度优先搜索算法的过程图解 (287) 7.4.3 深度优先搜索算法的流程图 (288) 7.4.4 深度优先搜索算法的编码实现 (289) 7.5 宽度优先搜索算法 (293) 7.5.1 宽度优先搜索算法的描述 (293) 7.5.2 宽度优先搜索算法的编码实现 (294) 7.6 无环有向图的分层算法 (297) 7.6.1 无环有向图的分层算法描述 (297) 7.6.2 无环有向图的分层算法过程图解 (298) 7.7 哈密顿圈算法 (299) 7.7.1 哈密顿圈算法的描述 (299) 7.7.2 哈密顿圈算法的过程图解 (300) 本章小结 (302) 习题与思考 (302) 第8章 多任务算法 (303) 8.1 读写锁 (303) 8.1.1 读写锁概念的引出 (303) 8.1.2 读写锁算法的分析和实现 (304) 8.1.3 读写锁的编码实现 (305) 8.2 多任务资源释放问题 (308) 8.2.1 子任务释放问题 (308) 8.2.2 多个子任务释放 (309) 8.2.3 多任务释放的实现 (309) 8.3 多任务下的遍历问题 (313) 8.3.1 链表在多任务下的遍历问题 (313) 8.3.2 多任务链表的设计和编码实现 (313) 8.3.3 多任务链表的遍历操作编码实现 (318) 8.3.4 多个任务同时遍历的情况 (321) 8.4 多任务二叉树的设计 (322) 8.5 消息队列 (327) 8.5.1 消息队列的基本概念 (327) 8.5.2 消息队列的设计和编码实现 (327) 8.6 实例：线程池调度的管理 (331) 8.6.1 线程池调度管理的基本概念 (331) 8.6.2 线程池调度管理的编码实现 (332) 本章小结 (335) 习题与思考 (335) 第9章 内存管理算法 (337) 9.1 动态等尺寸内存的分配算法 (337) 9.1.1 静态等尺寸内存分配算法的分析 (337) 9.1.2 动态等尺寸内存分配算法 (338) 9.2 内存垃圾收集算法 (351) 9.2.1 垃圾收集算法简介 (351) 9.2.2 用户层垃圾回收算法的实现 (352) 9.2.3 多任务下的垃圾收集 (360) 9.2.4 使用垃圾回收算法来做内存泄漏检查 (367) 9.3 实例：动态等尺寸内存管理算法的应用 (370) 9.3.1 Emalloc内存管理的概念 (370) 9.3.2 Emalloc内存管理的编码实现 (371) 9.3.3 Emalloc内存管理的使用方法 (375) 9.3.4 Emalloc内存管理的内存越界检查 (376) 本章小结 (378) 习题与思考 (378) 附 参考文献 (379) ) 1.4.1 多任务简介 (10) 1.4.2 锁的概念 (10) 1.4.3 Windows下常用多任务操作函数 (10) 1.4.4 Linux/Unix下常用多任务操作函数 (12) 1.4.5 VxWorks下常用多任务操作函数 (12) 1.4.6 多任务函数的封装 (13) 1.5 软件设计简介 (14) 1.5.1 软件设计历史简述 (14) 1.5.2 微观设计学原理简介 (15) 第2章 数组 (17) 2.1 栈 (17) 2.1.1 栈的基本概念 (17) 2.1.2 栈的编码实现 (18) 2.1.3 多任务栈的实现 (21) 2.2 队列 (24) 2.2.1 队列的基本概念和接口 (24) 2.2.2 环形队列(Queue) (25) 2.2.3 STL中的动态队列(STL∷deque) (29) 2.2.4 动态环形队列 (30) 2.2.5 各种队列的时间效率测试及分析 (35) 2.2.6 各种队列的适用范围 (36) 2.2.7 关于时间效率和空间效率的原则 (36) 2.3 排序表 (37) 2.3.1 排序算法介绍 (37) 2.3.2 快速排序算法 (38) 2.3.3 排序表的设计 (40) 2.3.4 非递归的快速排序算法 (43) 2.3.5 快速排序算法的复杂度分析 (47) 2.3.6 二分查找算法 (48) 2.4 实例：HOOK管理功能的实现 (49) 2.4.1 单个函数的HOOK实现 (49) 2.4.2 多个函数的HOOK实现 (50) 2.4.3 HOOK功能的应用简介 (55) 2.4.4 HOOK使用的注意事项 (56) 本章小结 (56) 习题与思考 (56) 第3章 链表 (57) 3.1 单向链表 (57) 3.1.1 单向链表的存储表示 (57) 3.1.2 单向链表的接口设计 (59) 3.1.3 单向链表的基本功能编码实现 (60) 3.2 单向链表的逐个节点遍历 (69) 3.2.1 单向链表逐个节点遍历基本概念 (69) 3.2.2 单向链表逐个节点遍历编码实现 (70) 3.3 单向链表的排序 (71) 3.3.1 插入排序 (71) 3.3.2 归并插入排序 (74) 3.3.3 基数排序 (79) 3.4 双向链表 (85) 3.4.1 双向链表的基本概念 (85) 3.4.2 双向链表的设计 (85) 3.4.3 双向链表的编码实现 (86) 3.5 使用整块内存的链表 (107) 3.5.1 整块内存链表的基本概念 (107) 3.5.2 整块内存链表的编码实现 (109) 3.6 实例：使用链表管理短信息系统的CACHE (113) 3.6.1 短信息系统的CACHE管理基本概念 (113) 3.6.2 短信息系统的发送和接收分析 (114) 3.6.3 短信息系统CACHE管理的编码实现 (115) 本章小结 (118) 习题与思考 (118) 第4章 哈希表 (119) 4.1 哈希表 (119) 4.1.1 哈希表的基本概念 (119) 4.1.2 哈希表的索引方法 (120) 4.1.3 哈希表的冲突解决方法 (123) 4.1.4 哈希表基本操作的源代码 (125) 4.2 哈希链表 (130) 4.2.1 哈希表和数组、链表的效率比较 (130) 4.2.2 时间效率和空间效率的关系 (131) 4.2.3 哈希链表的基本概念 (132) 4.2.4 哈希链表的操作 (133) 4.2.5 哈希链表的编码实现 (135) 4.3 实例：WebServer的动态CACHE文件管理 (143) 4.3.1 WebServer的动态CACHE文件管理基本概念 (143) 4.3.2 CACHE文件管理功能的设计 (144) 4.3.3 CACHE文件管理功能的编码实现 (145) 本章小结 (151) 习题与思考 (151) 第5章 树 (153) 5.1 普通树 (153) 5.1.1 普通树的描述方法 (153) 5.1.2 树的操作接口设计 (154) 5.1.3 树的遍历算法 (154) 5.1.4 树的编码实现 (157) 5.1.5 使用树的遍历算法来实现Xcopy功能 (163) 5.2 二叉树 (166) 5.2.1 二叉树的基本概念 (166) 5.2.2 二叉树的树梢及二叉树的高度 (166) 5.2.3 二叉树的描述方法 (167) 5.3 二叉排序树 (168) 5.3.1 二叉排序树的基本概念 (168) 5.3.2 二叉排序树的查找 (168) 5.3.3 二叉排序树的插入 (170) 5.3.4 二叉排序树的删除 (172) 5.3.5 二叉排序树的遍历 (176) 5.3.6 二叉排序树的旋转操作 (178) 5.4 AVL搜索树 (181) 5.4.1 AVL搜索树的基本概念 (181) 5.4.2 AVL搜索树的插入 (181) 5.4.3 AVL搜索树的删除 (184) 5.4.4 AVL树的源代码 (187) 5.5 红黑树 (205) 5.5.1 红黑树的基本概念 (205) 5.5.2 红黑树的插入操作 (206) 5.5.3 红黑树的删除操作 (209) 5.5.4 红黑树的编码实现 (214) 5.6 实例：搜索引擎的实现 (236) 5.6.1 搜索引擎的实现思路和方法 (236) 5.6.2 搜索引擎的时间效率和空间效率分析 (238) 5.6.3 高级搜索的实现 (240) 本章小结 (241) 习题与思考 (241) 第6章 复合二叉树 (243) 6.1 哈希红黑树 (243) 6.1.1 哈希红黑树的基本概念 (243) 6.1.2 哈希红黑树的查找 (245) 6.1.3 哈希红黑树的插入 (246) 6.1.4 哈希红黑树的删除 (248) 6.1.5 哈希红黑树的释放 (248) 6.1.6 哈希红黑树的遍历 (249) 6.1.7 哈希红黑树的编码实现 (249) 6.1.8 哈希红黑树的效率分析 (255) 6.2 哈希AVL树 (256) 6.2.1 哈希AVL树的基本概念 (256) 6.2.2 哈希AVL树的查找 (257) 6.2.3 哈希AVL树的插入 (258) 6.2.4 哈希AVL树的删除 (260) 6.2.5 哈希AVL树的释放 (261) 6.2.6 哈希AVL树的遍历 (261) 6.2.7 哈希AVL树的编码实现 (261) 6.2.8 复合数据结构的分类 (266) 6.3 抗DoS/DDoS攻击的实例 (267) 6.3.1 DoS/DDoS攻击的概念 (267) 6.3.2 常见DoS/DDoS攻击手段及防范策略 (268) 6.3.3 抗DoS/DDoS攻击的实现 (269) 6.3.4 抗DoS/DDoS攻击的编码实现 (269) 本章小结 (272) 习题与思考 (273) 第7章 图 (275) 7.1 图的基本概念和描述方法 (275) 7.1.1 图的基本概念 (275) 7.1.2 图的描述方法 (276) 7.2 Dijkstra最短路径算法 (277) 7.2.1 Dijkstra最短路径算法的描述 (277) 7.2.2 Dijkstra最短路径算法的过程图解 (277) 7.2.3 Dijkstra最短路径算法的编码实现 (278) 7.3 最小生成树算法 (282) 7.3.1 最小生成树算法的基本概念 (282) 7.3.2 最小生成树算法的过程图解 (282) 7.3.3 最小生成树的算法流程图 (283) 7.3.4 最小生成树算法的编码实现 (284) 7.4 深度优先搜索算法 (286) 7.4.1 深度优先搜索算法的描述 (286) 7.4.2 深度优先搜索算法的过程图解 (287) 7.4.3 深度优先搜索算法的流程图 (288) 7.4.4 深度优先搜索算法的编码实现 (289) 7.5 宽度优先搜索算法 (293) 7.5.1 宽度优先搜索算法的描述 (293) 7.5.2 宽度优先搜索算法的编码实现 (294) 7.6 无环有向图的分层算法 (297) 7.6.1 无环有向图的分层算法描述 (297) 7.6.2 无环有向图的分层算法过程图解 (298) 7.7 哈密顿圈算法 (299) 7.7.1 哈密顿圈算法的描述 (299) 7.7.2 哈密顿圈算法的过程图解 (300) 本章小结 (302) 习题与思考 (302) 第8章 多任务算法 (303) 8.1 读写锁 (303) 8.1.1 读写锁概念的引出 (303) 8.1.2 读写锁算法的分析和实现 (304) 8.1.3 读写锁的编码实现 (305) 8.2 多任务资源释放问题 (308) 8.2.1 子任务释放问题 (308) 8.2.2 多个子任务释放 (309) 8.2.3 多任务释放的实现 (309) 8.3 多任务下的遍历问题 (313) 8.3.1 链表在多任务下的遍历问题 (313) 8.3.2 多任务链表的设计和编码实现 (313) 8.3.3 多任务链表的遍历操作编码实现 (318) 8.3.4 多个任务同时遍历的情况 (321) 8.4 多任务二叉树的设计 (322) 8.5 消息队列 (327) 8.5.1 消息队列的基本概念 (327) 8.5.2 消息队列的设计和编码实现 (327) 8.6 实例：线程池调度的管理 (331) 8.6.1 线程池调度管理的基本概念 (331) 8.6.2 线程池调度管理的编码实现 (332) 本章小结 (335) 习题与思考 (335) 第9章 内存管理算法 (337) 9.1 动态等尺寸内存的分配算法 (337) 9.1.1 静态等尺寸内存分配算法的分析 (337) 9.1.2 动态等尺寸内存分配算法 (338) 9.2 内存垃圾收集算法 (351) 9.2.1 垃圾收集算法简介 (351) 9.2.2 用户层垃圾回收算法的实现 (352) 9.2.3 多任务下的垃圾收集 (360) 9.2.4 使用垃圾回收算法来做内存泄漏检查 (367) 9.3 实例：动态等尺寸内存管理算法的应用 (370) 9.3.1 Emalloc内存管理的概念 (370) 9.3.2 Emalloc内存管理的编码实现 (371) 9.3.3 Emalloc内存管理的使用方法 (375) 9.3.4 Emalloc内存管理的内存越界检查 (376) 本章小结 (378) 习题与思考 (378) 附 参考文献 (379)