第1篇 数据结构篇 2
第1章 线性表 2
1.1 线性表的定义和基本操作 2
1.1.1 线性表的逻辑定义与特征 2
1.1.2 线性表的基本操作 3
1.2 顺序存储结构的存储结构和实现 5
1.3 链式存储结构的存储结构和实现 14
1.3.1 线性链表 15
1.3.2 双向链表 27
1.3.3 循环链表 35
1.3.4 静态链表 36
1.4 线性表的应用 40
1.4.1 有序表的运算应用 40
1.4.2 线性表的遍历应用 42
第2章 栈、队列和数组 44
2.1 栈的概念和实现 44
2.1.1 栈的基本操作 46
2.1.2 顺序栈的定义和实现 47
2.1.3 链栈的定义和实现 51
2.2 栈的应用 54
2.3 队列的概念和实现 59
2.3.1 队列的基本操作 60
2.3.2 循环队列的定义和实现 62
2.3.3 链队列的定义和实现 68
2.4 队列的应用 70
2.5 数组的概念和实现 72
2.5.1 特殊矩阵 72
2.5.2 稀疏矩阵 74
第3章 树和二叉树 80
3.1 树的基本概念 80
3.2 二叉树 82
3.2.1 二叉树的定义 82
3.2.2 二叉树的性质 84
3.2.3 二叉树的存储结构 87
3.2.4 二叉树的遍历 89
3.2.5 线索二叉树 92
3.3 树与森林 95
3.3.1 树的性质 95
3.3.2 树的存储结构 96
3.3.3 树、森林与二叉树的转换 100
3.3.4 树与森林的遍历 101
3.4 树的应用 103
3.4.1 等价类的问题 103
3.4.2 哈夫曼树和哈夫曼编码 107
第4章 图 112
4.1 图的概念和相关术语 112
4.2 图的存储 115
4.2.1 邻接矩阵及其实现 117
4.2.2 邻接表及其实现 120
4.3 图的遍历 124
4.3.1 深度优先搜索 125
4.3.2 广度优先搜索 129
4.4 图的基本应用及其复杂度分析 133
4.4.1 最小生成树定义 133
4.4.2 最短路径 138
4.4.3 拓扑排序 140
4.4.4 关键路径 143
第5章 查找 147
5.1 查找概念 147
5.2 静态查找法 148
5.2.1 顺序表查找 148
5.2.2 有序表查找 150
5.2.3 静态树表查找 154
5.2.4 索引顺序表查找 157
5.3 动态查找法 159
5.3.1 二叉排序树 159
5.3.2 平衡二叉树 169
5.3.3 B-树 174
5.4 哈希表及其查找 183
5.4.1 哈希函数构造方法 184
5.4.2 冲突解决办法 186
5.4.3 哈希表的查找及其性能分析 190
第6章 内部排序 192
6.1 排序的基本概念 192
6.2 插入排序 193
6.2.1 直接插入排序 193
6.2.2 折半插入排序 196
6.2.3 希尔排序 197
6.3 交换排序 200
6.3.1 冒泡排序 200
6.3.2 快速排序 203
6.4 选择排序 207
6.4.1 简单选择排序 207
6.4.2 堆排序 209
6.5 二路归并排序 213
6.6 基数排序 216
6.6.1 多关键字排序 216
6.6.2 链式基数排序 217
6.7 各种内部排序算法比较与选择 220
6.7.1 内部排序算法的比较 220
6.7.2 内部排序算法的选择 221
第2篇 操作系统篇 224
第7章 操作系统概述 224
7.1 操作系统的概念 224
7.2 操作系统的特征 226
7.3 操作系统的功能 227
7.4 操作系统提供的服务 228
7.4.1 程序启动与结束 228
7.4.2 系统调用与中断 232
7.5 操作系统的发展与分类 240
7.5.1 操作系统的发展 240
7.5.2 操作系统的分类 242
第8章 进程管理 244
8.1 进程管理概述 244
8.2 进程与线程 245
8.1.1 进程的概念 245
8.1.2 进程的状态与转换 248
8.1.3 进程控制 250
8.1.4 进程组织 252
8.1.5 进程通信 252
8.1.6 线程概念与多线程模型 254
8.2 处理机调度 256
8.2.1 调度时机与过程 256
8.2.2 典型调度算法 258
8.3 进程同步 259
8.3.1 实现临界区互斥的基本方法 260
8.3.2 信号量 264
8.3.3 管程 265
8.3.4 经典同步问题 265
8.3.5 死锁 266
第9章 内存管理 270
9.1 内存管理的概念 270
9.1.1 内存的概念与作用 270
9.1.2 内存管理的功能与任务 272
9.1.3 程序装入与连接 278
9.1.4 内存保护 279
9.2 交换与覆盖 279
9.2.1 覆盖技术 279
9.2.2 交换技术 280
9.3 连续分配管理方式 281
9.3.1 单一连续分配 281
9.3.2 分区分配 283
9.4 非连续分配管理方式 288
9.4.1 分页管理方式 288
9.4.2 分段管理方式 291
9.4.3 段页式管理方式 295
9.5 虚拟内存管理 296
9.5.1 请求分页管理方式 296
9.5.2 页面置换算法 303
9.5.3 页面分配策略 304
9.5.4 抖动 306
第10章 文件管理 307
10.1 外存储器 307
10.2 文件系统基础 309
10.2.1 文件概述 309
10.2.2 文件结构 312
10.2.3 目录结构 315
10.2.4 文件共享 320
10.2.5 文件保护 321
10.3 文件系统的实现 322
10.3.1 文件系统层次结构 322
10.3.2 目录的实现 328
10.3.3 文件的实现 334
10.4 磁盘组织与管理 344
10.4.1 磁盘结构 345
10.4.2 磁臂调度算法 347
10.4.3 磁盘的管理 350
第11章 输入输出管理 352
11.1 I/O管理概述 352
11.1.1 I/O设备 352
11.1.2 I/O管理目标与功能 361
11.1.3 I/O应用接口 364
11.1.4 I/O控制方式 366
11.1.5 设备管理功能的结构与过程 372
11.2 I/O核心子系统 377
11.2.1 高速缓存与缓冲区 377
11.2.2 设备分配与回收 379
11.2.3 假脱机技术 380
11.2.4 出错处理 381
参考文献 382