第1章 概论

1.1什么是数据结构

1.2基本概念和术语

1.3算法和算法分析

1.3.1算法的定义及特性

1.3.2算法的设计要求

1.3.3算法效率的衡量方法

1.3.4算法的时间复杂度

1.3.5算法的空间复杂度

1.4抽象数据类型

习题

第2章 线性表

2.1线性表的类型定义

2.1.1线性表的概念

2.1.2线性表的抽象数据类型

2.2线性表的顺序表示和实现

2.2.1线性表的顺序表示

2.2.2顺序表基本运算的实现

2.3线性表的链式表示和实现

2.3.1线性表的链式表示

2.3.2单链表上基本运算的实现

2.4双链表

2.5循环链表

2.6线性表实现方法的比较

2.7算法设计举例

习题

第3章 栈和队列

3.1栈

3.1.1栈的类型定义

3.1.2顺序栈的表示和实现

3.1.3链栈的表示和实现

3.2栈的应用举例

3.2.1十进制数转换为其他进制数

3.2.2表达式中括号的匹配检查

3.2.3表达式求值

3.2.4利用栈消除递归

3.3队列

3.3.1队列的类型定义

3.3.2循环队列——队列的顺序表示和实现

3.3.3链队列——队列的链式表示和实现

3.4算法设计举例

习题

第4章 串

4.1串的基本概念

4.2串的表示和实现

4.2.1串的顺序存储结构

4.2.2串的链式存储结构

4.3串的模式匹配

4.3.1朴素的模式匹配算法

4.3.2 KMP算法

习题

第5章 数组

5.1数组的基本概念

5.2矩阵的压缩存储

5.2.1特殊矩阵

5.2.2稀疏矩阵

5.3算法设计举例

习题

第6章 树和二叉树

6.1树的概念

6.2二叉树的概念和性质

6.2.1二叉树的概念和抽象数据类型

6.2.2二叉树的性质

6.3二叉树的表示和实现

6.3.1二叉树的存储结构

6.3.2二叉树的遍历运算

6.3.3二叉树的其他基本运算

6.4树和森林

6.4.1树的存储结构

6.4.2树、森林和二叉树的相互转换

6.4.3树和森林的遍历运算

6.4.4树和森林的其他基本运算

6.5线索二叉树

6.5.1线索二叉树的概念

6.5.2线索二叉树的基本运算

6.6算法设计举例

习题

第7章 树和二叉树的应用

7.1表达式树

7.2哈夫曼树和哈夫曼编码

7.2.1哈夫曼树

7.2.2哈夫曼编码

7.3堆和优先级队列

7.3.1堆

7.3.2优先级队列

7.4并查集

7.5算法设计举例

习题

第8章 图

8.1图的概念

8.2图的存储结构

8.2.1邻接矩阵

8.2.2邻接表

8.2.3十字链表

8.2.4邻接多重表

8.3图的遍历

8.3.1深度优先遍历

8.3.2广度优先遍历

8.3.3图的连通分量和生成树

习题

第9章 图的应用

9.1最小生成树

9.1.1最小生成树的概念

9.1.2 Prim算法

9.1.3 Kruskal算法

9.2有向无环图及其应用

9.2.1拓扑排序

9.2.2关键路径

9.3最短路径

9.3.1单源点最短路径

9.3.2每对顶点之间的最短路径

习题

第10章 集合与查找

10.1基本概念

10.2静态查找表上的查找

10.2.1顺序查找

10.2.2折半查找

10.2.3分块查找

10.3动态查找表上的查找

10.3.1二叉查找树

10.3.2平衡二叉树

10.3.3 B树

10.3.4 B＋树

10.3.5字典树

10.4算法设计举例

习题

第11章 散列表

11.1散列表的概念

11.2构造散列函数的方法

11.2.1直接定址法

11.2.2折叠法

11.2.3数字分析法

11.2.4平方取中法

11.2.5除留余数法

11.3解决冲突的方法

11.3.1闭散列法

11.3.2开散列法

11.4散列表的实现

11.4.1闭散列表的表示和实现

11.4.2开散列表的表示和实现

11.4.3闭散列表与开散列表的比较

11.5散列表的查找性能分析

习题

第12章 排序

12.1排序的基本概念

12.2插入排序

12.2.1直接插入排序

12.2.2折半插入排序

12.2.3希尔排序

12.3交换排序

12.3.1冒泡排序

12.3.2快速排序

12.4选择排序

12.4.1直接选择排序

12.4.2堆排序

12.4.3锦标赛排序

12.5归并排序

12.6基数排序

12.7各种内部排序方法的比较

12.8外部排序

12.8.1置换选择排序

12.8.2多路归并排序

习题

附录A 上机实验参考题目

参考文献