数据结构与算法

第1章 概述

1. 1 数据结构的兴起与发展

1. 2 数据结构的研究对象

1. 3 数据结构的概念

1. 4 数据结构的图示

1. 5 数据结构的分类

1. 5. 1 集合

1. 5. 2 线性结构

1. 5. 3 树形结构

1. 5. 4 图状结构

1. 6 数据结构的存储

1. 6. 1 存储器表示

1. 6. 2 存储映像

1. 6. 3 基本存储方法

1. 7 数据结构的访问接口

1. 7. 1 访问接口与逻辑结构

1. 7. 2 基本操作的种类

1. 7. 3 基本操作的实现

1. 8 面向对象方法

1. 8. 1 对象与类

1. 8. 2 面向对象方法要素

1. 8. 3 面向对象方法的若干述评*

1. 8. 4 面向对象程序设计语言*

1. 9 面向对象与数据结构

1. 9. 1 面向对象与数据结构的关系

1. 9. 2 面向对象数据结构

1. 9. 3 数据结构的对象模型

本章小结

习题

第2章 程序设计基本策略与方法

2. 1 算法

2. 1. 1 算法的概念

2. 1. 2 算法的时间复杂度与空间复杂度

2. 1. 3 算法时间复杂度的度量

2. 2 穷举法

2. 3 递推法与迭代法

2. 3. 1 递推法

2. 3. 2 迭代法

2. 4 递归法

2. 4. 1 递归与递归程序的概念

2. 4. 2 递归程序设计要点

2. 4. 3 递归程序执行机理

2. 4. 4 Hanoi塔问题与运行图

2. 5 逐步求精法

2. 5. 1 基本思想

2. 5. 2 应用示例

2. 6 分治法

2. 6. 1 基本思想

2. 6. 2 平面分治法示例--顺序统计

2. 6. 3 迭代分治法示例--循环赛赛程安排*

本章小结

习题

第3章 线性表

3. 1 线性表的逻辑结构

3. 1. 1 基本概念

3. 1. 2 线性表抽象模型

3. 2 线性表的顺序存储结构

3. 2. 1 基本存储方法

3. 2. 2 面向对象描述

3. 3 异常处理与下标选择器*

3. 3. 1 异常处理

3. 3. 2 下标选择器

3. 4 线性表的链式存储--线性链表

3. 4. 1 链式存储方法

3. 4. 2 线性链表的面向对象描述

3. 4. 3 线性链表的面向对象实现

3. 5 几种特殊线性链表

3. 5. 1 带头结点的链表

3. 5. 2 循环链表

3. 5. 3 双向链表

3. 6 线性表应用示例

3. 6. 1 集合运算*

3. 6. 2 一元多项式相加

3. 6. 3 一元多项式的乘法*

本章小结

习题

第4章 特殊线性表--栈. 队列. 串

4. 1 栈

4. 1. 1 栈的逻辑结构

4. 1. 2 栈的顺序存储结构

4. 1. 3 栈的链式存储结构

4. 2 队列

4. 2. 1 队列的逻辑结构

4. 2. 2 队列的顺序存储结构

4. 2. 3 队列的链式存储结构

4. 3 串

4. 3. 1 串的逻辑结构

4. 3. 2 串的存储结构

本章小结

习题

第5章 数组与十字链表

5. 1 数组

5. 1. 1 数组的定义与运算

5. 1. 2 数组的存储结构与寻址问题

5. 1. 3 一维数组的存储与寻址

5. 1. 4 二维数组的存储与寻址

5. 1. 5 多维数组的存储与寻址

5. 1. 6 寻址公式的计算

5. 2 特殊数组*

5. 2. 1 对称矩阵

5. 2. 2 下／上三角矩阵

5. 3 稀疏矩阵

5. 3. 1 稀疏矩阵的逻辑表示

5. 3. 2 三元组表存储法

5. 3. 3 三元组表的操作

5. 3. 4 转置操作

5. 4 十字链表

5. 4. 1 存储方式

5. 4. 2 十字链表对象

5. 4. 3 基本操作的实现

本章小结

习题

第6章 树形结构

6. 1 树形结构的基本概念

6. 1. 1 树形结构的定义

6. 1. 2 基本术语

6. 2 二叉树

6. 2. 1 二叉树的基本概念

6. 2. 2 几种特殊二叉树

6. 2. 3

叉树的基本性质

6. 2. 4

叉树的遍历

6. 3

叉树的存储结构

6. 3. 1 顺序存储结构

6. 3. 2 链式存储结构

6. 4 二树对象模型

6. 4. 1

叉树结点对象

6. 4. 2 二叉树对象

6. 5 二叉树的遍历操作

6. 5. 1 前序遍历操作

6. 5. 2 中序遍历操作

6. 5. 3 后序遍历操作

6. 6

叉树的解析表示与存储结构之间的转化

6. 6. 1 双遍历结果转化为树

6. 6. 2 根据广义表表示创建树

6. 6. 3 根据存储结构创建广义表*

6. 6. 4 根据前序扩展序列创建树*

6. 7 二叉树的线索化

6. 7. 1 线索化的概念

6. 7. 2 线索化算法

6. 8 树与森林

6. 8. 1 树与森林的遍历

6. 8. 2 树. 森林与二叉树之间的转化

6. 8. 3 树的存储结构

6. 9 树对象模型*

6. 9. 1 树结点对象

6. 9. 2 树类

6. 10 树的应用示例--哈夫曼树

6. 10. 1 哈夫曼树的基本概念

6. 10. 2 哈夫曼树构造算法

6. 10. 3 哈夫曼树构造算法的实现

6. 10. 4 哈夫曼判定树

6. 10. 5 哈夫曼编码与数据压缩

本章小结

习题

第7章 图结构

7. 1 图的基本概念

7. 1. 1 图的概念

7. 1. 2 图的基本操作

7. 2 图的对象抽象模型

7. 2. 1 图结点抽象模型

7. 2. 2 图的边对象抽象模型

7. 2. 3 图抽象对象模型

7. 3 图的存储结构

7. 3. 1 邻接矩阵法

7. 3. 2 邻接表

7. 3. 3 十字链表*

7. 3. 4 邻接多重表*

7. 4 图的遍历

7. 4. 1 概述

7. 4. 2 深度优先遍历

7. 4. 3 深度优先遍历的性质

7. 4. 4 广度优先遍历

7. 4. 5 广度优先遍历的性质

7. 5 拓扑排序

7. 5. 1 拓扑序列与AOV网

7. 5. 2 拓扑排序算法与实现

7. 6 AOE网与关键路径

7. 6. 1 AOE网与关键路径的概念

7. 6. 2 关键路径的识别

本章小结

习题

第8章 广义表

8. 1 广义表的逻辑结构

8. 1. 1 基本概念

8. 1. 2 广义表逻辑图

8. 1. 3 广义表的遍历

8. 1. 4 基本特性

8. 1. 5 基本操作

8. 2 广义表的存储结构

8. 2. 1 基本存储方法

8. 2. 2 链式结构的高级语言描述

8. 3 广义表对象模型*

8. 3. 1 广义表元素接口

8. 3. 2 广义表接口

8. 4 广义表的分支单链表对象*

8. 4. 1 结点对象

8. 4. 2 分支单链表对象

8. 5 广义表操作的实现*

8. 5. 1 一般问题

8. 5. 2 遍历操作

8. 5. 3 广义表统计计数

8. 5. 4 广义表的串行化与逆串行化

8. 5. 5 广义表的复制与求尾

8. 6 广义表结构的应用

8. 6. 1 多元多项式的表示

8. 6. 2 层次结构的表示

本章小结

习题

第9章 检索结构

9. 1 概述

9. 1. 1 检索的概念

9. 1. 2 检索结构

9. 1. 3 检索算法的时间与空间复杂度分析

9. 1. 4 检索算法的判定树

9. 2 线性结构的检索

9. 2. 1 顺序检索

9. 2. 2 折半检索

9. 2. 3 斐波刀口契检索*

9. 2. 4 插值检索*

9. 3 线性索引结构

9. 3. 1 概述

9. 3. 2 稠密索引

9. 3. 3 分块索引

9. 4 树形索引结构与二叉排序树

9. 4. 1 树形索引结构概述

9. 4. 2 二叉排序树的概念

9. 4. 3 二叉排序树的检索

9. 4. 4 二叉排序树的插入*

9. 4. 5 二叉排序树的删除*

9. 4. 6 二叉排序树的分析与最优二叉排序树*

9. 5 平衡二叉排序树*

9. 5. 1 基本概念

9. 5. 2 若干性质

9. 5. 3 局部平衡调整算法

9. 6 B树

9. 6. 1 B树的概念

9. 6. 2 B树的存储结构

9. 6. 3 B树的基本操作

9. 6. 4 B树的检索方法

9. 6. 5 B树的插入

9. 6. 6 B树的删除

9. 6. 7 B 树

9. 6. 8 B树对象模型

9. 7 散列结构

9. 7. 1 概念

9. 7. 2 散列技术中的主要问题

9. 7. 3 散列过程

9. 7. 4 散列函数的设计

9. 7. 5 冲突解决

本章小结

习题

第10章 外存与文件组织

10. 1 外存结构

10. 1. 1 外存简介

10. 1. 2 磁带结构

10. 1. 3 磁盘结构

10. 2 文件

10. 2. 1 文件的概念

10. 2. 2 文件操作与存取方式

10. 2. 3 文件的物理组织

10. 2. 4 缓冲技术

10. 3 顺序文件

10. 4 索引文件

10. 5 ISAM*

10. 5. 1 ISAM的概念

10. 5. 2 ISAM结构的操作

10. 6 VSAM

10. 6. 1 VSAM的概念

10. 6. 2 VSAM结构的操作

10. 7 散列方式

10. 8 多索引文件

10. 8. 1 多重表文件

10. 8. 2 倒排文件

本章小结

习题

第11章 排序算法

11. 1 概述

11. 2 插入排序

11. 2. 1 直接插入排序

11. 2. 2 其他插入排序算法

11. 3 交换排序

11. 3. 1 冒泡排序,

11. 3. 2 冒泡算法的改进

11. 3. 3 快速排序*

11. 4 选择排序

11. 4. 1 直接选择排序

11. 4. 2 堆排序

11. 5 归并排序

11. 5. 1 二路合并

11. 5. 2 多段二路合并

11. 5. 3 二路归并排序

11. 6 外排序简介

本章小结

习题

第12章 算法设计基本方法

12. 1 回溯法与限界剪枝法

12. 1. 1 基本思想

12. 1. 2 迷宫问题

12. 1. 3 稳定婚姻问题*

12. 1. 4 n皇后问题

12. 1. 5 限界剪枝法简介*

12. 2 动态规划法

12. 2. 1 动态规划法要素与最优性原理

12. 2. 2 最长公共子序列

12. 2. 3 流水线调度问题*

12. 2. 4 多源最短路径的Floyd算法

12. 2. 5 0-1背包问题

12. 3 贪心法

12. 3. 1 基本思想

12. 3. 2 背包问题

12. 3. 3 Prim最小生成树算法

12. 3. 4 Kruskal最小生成树算法

12. 3. 5 单源最短路径

12. 3. 6 贪心法要素总结

本章小结

习题

词汇索引

参考文献