数据结构

第1章 绪论 1

1．1 数据结构的发展历史 1

1．2 数据结构的基本坟语和概念 2

1．3 关于算法描述和算法分析 2

习题 4

第2章 线性表及其应用 5

2．1 线性表的定义和基本运算 5

2．2 线性表的右序存储结构 6

2．3 线性表的链式存储结构 7

2．3．1 线性链表 7

23．2 循环链表 10

2．3．3 双向链表 10

2．4 线性表应用实例——多项式相加 12

习题 15

第3章 栈、队列和数组 16

3．1 栈 16

3．1．1 栈的定义及基本运算 16

3．1．2 栈的存储结构及基本运算的实现 16

3．1．3 栈的应用 18

3．2 队列 23

3．2．1 队列的定义及基本运算 23

3．2．2 队列的存储结构及基本运算的实现 23

3．2．3 队列的应用 25

3．3 数组 26

3．3．1 数组的定义和运算 26

3．3．2 数组的顺序存储结构 26

3．3．3 稀疏数组 27

3．3．4 数组的应用 29

习题 31

4．1 串的基本概念 32

第4章 串 32

4．2 串的存储结构 33

4．2．1 右序存储结构 33

4．2．2 链式存储结构 33

4．2．3 利用堆结构、进行动态存储分配 34

4．3 串的基本操作 35

4．3．1 串的联接 35

4．3．2 求子串 35

4．3．3 判断两个串是否相等 36

4．3．4 插入子串和删除子串 36

4．3．5 求子串位置的定位函数 37

4．4 串的应用 38

习题 40

5．1．1 树的定义 41

第5章 树型结构 41

5．1 树型结构的基本概念 41

5．1．2 基本术语 42

5．2 二叉树 42

5．2．1 二叉树的定义和基本性质 42

5．2．2 二叉树的存储结构 45

5．2．3 二叉树的遍历 46

5．3 树、森林与二叉树的关系 49

5．3．1 、树的存储结构 49

5．3．2 森林与二叉树的转换 51

5．3．3 树和森林的遍历 52

5．4 树的应用 53

5．4．1 算术表达式求值 53

5．4．2 哈夫曼树 55

习题 62

6．1 图结构的基本概念 64

第6章 图结构 64

6．2 图的存储结构 67

6．2．1 邻接矩阵 67

6．2．2 邻接表 69

6．2．3 邻接多重表 70

6．3 图的遍历及求图的连通分量 70

6．3．1 深度优先搜索 71

6．3．2 广度优先搜索 73

6．3．3 求图的连通分量 74

6．4 生成树和最小（代价）生成树 77

6．5 最短路径 84

6．5．1 从某个源点到其它各顶点的最短路径 84

6．5．2 每一对顶点间的最短路径 87

6．6．1 有向无环图 89

6．6 有向无环图及其应用 89

6．6．2 拓扑排序 90

6．6．3 关键路径 95

习题 100

第7章 查找 103

7．1 右序表的查找 103

7．1．1 右序查找 103

7．1．2 折半查找 104

7．1．3 索引顺序表的查找 107

7．2 树表的查找 108

7．2．1 二叉排序树 108

7．2．2 平衡二叉树 113

7．2．3 B树 117

7．3．1 什么是哈希表 123

7．3 哈希表及其查找 123

7．3．2 构造哈希函数的基本方法 124

7．3．3 处理冲突的几种方法 125

7．3．4 哈面表的查找及其效率分析 127

习题 128

第8章 排序 130

8．1 一般概念 130

8．2 插入排序 131

8．2．1 直接插入排序 131

8．2．2 折半插入排序 133

8．2．3 2-路插入排序 134

8．2．4 希尔排序 136

8．3 交换排序 138

8．3．1 起泡排序 138

8．3．2 快速排序 141

8．4 选择排序 143

8．4．1 简单选择排序 144

8．4．2 堆排序 145

8．5 归并排序 148

8．5．1 两个有序序列的归并 148

8．5．2 归并排序 149

8．6 有关内部排序方法的讨论 151

8．6．1 排序速度 152

8．6．2 排序方法的稳定性 152

8．6．3 排序过程中的数据移动 153

8．7 外部排序 153

8．7．1 多路平衡归并 153

8．7．2 磁带归并排序 158

习题 160