算法与数据结构

第1章 算法与数据结构概述 1

1．1 为什么要学习数据结构 1

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

1．3 数据的逻辑结构 3

1．3．1 结点的类型 4

1．3．2 结构的分类 4

1．3．3 结构和结点 5

1．4 数据的存储结构 5

1．4．1 顺序的方法 5

1．4．2 链接的方法 5

1．4．3 索引的方法 5

1．4．4 散列方法 6

1．5 数据的运算 6

1．6 算法(Algorithm)及其表示 6

1．6．1 算法 6

1．6．2 算法的表示 7

1．7 算法与数据结构的选择和评价 11

第2章 简单数据结构 13

2．1 线性结构 13

2．1．1 线性表 13

2．1．2 堆栈(stack) 17

2．1．3 队列(queue) 34

2．2 链表 45

2．2．1 线性链表的基本概念 46

2．2．2 线性链表的存储分配 47

2．2．3 线性链表的基本操作 48

2．2．4 堆栈的单链形式 65

2．2．5 队列的单链形式 69

2．2．6 线性链表的应用 70

2．2．7 线性表的其他链接存储表示 72

2．3 双向链表 73

2．3．1 双向链表的基本概念 74

2．3．2 双向链表的基本操作；插入及删除 75

2．3．3 双向链表的实现 77

2．3．4 双向链表的删除操作的实现 80

2．3．5 双向链表的应用实例 81

2．3．6 对称表 89

2．4 动态存储管理 91

2．4．1 动态存储管理概述 91

2．4．2 可利用空间表的表示方式 92

2．4．3 可利用空间表分配的3种情况 92

2．4．4 回收过程 96

第3章 排序 98

3．1 基本概念 98

3．1．1 排序码与排序 98

3．1．2 排序的方法 99

3．1．3 排序算法评价 99

3．2 插入排序 99

3．2．1 直接插入排序 99

3．2．2 二分法插入排序 102

3．2．3 表插入排序 107

3．2．4 Shell排序 108

3．3 选择排序 111

3．3．1 直接选择排序 112

3．3．2 树形选择排序 114

3．3．3 堆排序 115

3．4 交换排序 115

3．4．1 起泡排序 115

3．4．2 快速排序 117

3．5 分配排序 121

3．5．1 分配排序概述 121

3．5．2 基数排序 122

3．6 归并排序 128

3．6．1 归并排序概述 128

3．6．2 路归并排序 128

3．7 各种排序方法的比较 130

4．2 顺序检索 131

4．1 基本概念 131

第4章 检索 131

4．3 二分法检索 132

4．4 分块检索 134

4．5 散列表的检索 135

4．5．1 散列检索的基本概念 135

4．5．2 散列函数的选择 136

4．5．3 碰撞的处理 138

4．6 基于属性的检索 144

4．6．1 倒排表 144

4．6．2 多重表 145

第5章 树结构 148

5．1 树结构的概念 148

5．1．1 树的逻辑结构的描述 148

5．1．2 二叉树的概念 150

5．1．3 树和二叉树的相互转换 151

5．2 周游树结构 152

5．2．1 周游树结构的概念与方法 153

5．2．2 周游树结构的性质与应用 155

5．3 树结构的存储 155

5．3．1 链式存储 155

5．3．2 穿线树 157

5．3．3 顺序存储 158

5．4 树的应用实例 162

5．4．1 二叉排序树(binary sort tree) 162

5．4．2 Huffman树 168

5．4．3 判定树 170

5．4．4 决策树 170

5．4．5 堆排序 172

5．5 树的运算实用程序举例 175

5．5．1 使用数组建立二叉树及其周游 175

5．5．2 用前序及对称序序列构造树 178

5．5．3 堆排序 180

5．5．4 决策问题的编程实现 188

5．5．5 Huffman树的编程实现 190

5．5．6 最佳二叉排序树的实现 200

第6章 图结构 220

6．1 图(graph)的概念 220

6．2 图的存储表示法 221

6．2．1 图的相邻矩阵表示法 221

6．2．2 图的邻接表表示法 222

6．2．3 图的邻接多重表表示法 224

6．3 图的周游及生成树 225

6．3．1 按深度方向周游 226

6．3．2 按宽度方向周游 227

6．3．3 图的最小生成树 228

6．4 最短路径 230

6．4．1 求一个结点到其他各个结点的最短路径 230

6．4．2 求每一对结点之间的最短路径 232

6．5 拓扑排序 234

6．5．1 拓扑排序的基本概念 235

6．5．2 拓扑排序的方法 236

6．6 关键路径 238

第7章 多维数组、稀疏矩阵和广义表 242

7．1 多维数组 242

7．1．1 多维数组概述 242

7．1．2 下三角矩阵 244

7．1．3 三对角矩阵 245

7．2 稀疏矩阵 246

7．2．1 顺序存储 246

7．2．2 链接存储 248

7．2．3 散列存储 250

7．3 广义表 250

7．3．1 广义表(List)的基本概念 250

7．3．2 广义表的存储 252

作业 256

一、程序设计作业 256

二、综合作业 261

三、书面作业 263