目录

第1章绪论

1.1数据结构有什么用

1.2基本概念

1.2.1数据

1.2.2数据结构

1.2.3数据类型

1.3算法及性能分析

1.3.1算法

1.3.2算法描述

1.3.3性能分析

小结

习题1

第2章线性表

2.1基本概念

2.1.1线性表的概念

2.1.2抽象数据类型

2.2顺序表

2.2.1基本概念

2.2.2插入与删除操作

2.2.3数据类型及算法描述

2.3动态链表

2.3.1基本概念

2.3.2单链表

2.3.3双向链表

2.4静态链表

2.4.1基本概念

2.4.2存储结构

2.4.3基本操作

2.5集合的线性表实现

2.5.1用线性表存储集合元素

2.5.2位图

2.5.3并查集

2.6应用案例

小结

习题2

第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.1串

4.1.1基本概念

4.1.2存储结构

4.1.3模式匹配

4.2数组

4.2.1基本概念和存储结构

4.2.2特殊矩阵的压缩存储

4.3广义表

4.3.1基本概念

4.3.2存储结构

小结

习题4

第5章树

5.1基本概念

5.1.1树的定义

5.1.2树的基本术语

5.2二叉树

5.2.1二叉树的定义

5.2.2二叉树的基本形态

5.2.3满二叉树和完全二叉树

5.2.4二叉树的性质

5.2.5二叉树的顺序存储结构

5.2.6二叉树的链式存储结构

5.3二叉树的遍历

5.3.1按层次遍历

5.3.2先序遍历、中序遍历和后序遍历

5.3.3由遍历序列重构二叉树

5.3.4二元运算表达式与二叉树的遍历

5.3.5非递归遍历

5.3.6通过遍历对二叉树进行处理

5.4线索二叉树

5.4.1线索二叉树的基本概念

5.4.2线索二叉树的构建

5.4.3线索二叉树的遍历

5.5树和森林

5.5.1树和森林的存储结构

5.5.2树和森林与二叉树之间的相互转换

5.5.3树和森林的遍历

5.5.4通过遍历对树和森林进行处理

5.5.5基于森林的并查集

5.6哈夫曼树

5.6.1基本概念

5.6.2哈夫曼树的构建

5.6.3哈夫曼编码与解码

5.7应用案例

小结

习题5

第6章图

6.1基本概念

6.2图的存储结构

6.2.1邻接矩阵

6.2.2邻接表

6.2.3十字链表

6.3图的遍历

6.3.1深度优先搜索

6.3.2广度优先搜索

6.4图的连通性

6.4.1路径

6.4.2生成树

6.4.3可达分量与连通分量

6.4.4最小生成树

6.5最短路径

6.5.1迪杰斯特拉算法

6.5.2弗洛伊德算法

6.6有向无环图

6.6.1拓扑排序

6.6.2关键路径

6.7应用案例

6.7.1迷宫问题

6.7.2华容道游戏

小结

习题6

第7章查找

7.1基本概念

7.2顺序查找

7.3折半查找

7.4索引顺序查找

7.5二叉排序树与平衡二叉树

7.5.1二叉排序树

7.5.2平衡二叉树

7.6B树

7.6.1B树的定义

7.6.2B树的操作

7.7哈希查找

7.7.1基本概念

7.7.2哈希函数

7.7.3解决冲突的方法

7.7.4插入、删除与扩容

小结

习题7

第8章排序

8.1基本概念

8.2插入排序

8.2.1直接插入排序

8.2.2折半插入排序

8.2.3希尔排序

8.3交换排序

8.3.1冒泡排序

8.3.2快速排序

8.4选择排序

8.4.1简单选择排序

8.4.2树状选择排序

8.4.3堆排序

8.5归并排序

8.6基于比较的排序方法的对比

8.7计数排序和基数排序

8.7.1计数排序

8.7.2基数排序

8.8外排序

小结

习题8

参考文献