《数据结构》求取 ⇩

目录1

第一章 绪论1

1.1 数据结构的产生和发展1

1.2 什么是数据结构2

1.3 基本术语3

1.4 算法和算法的描述5

1.4.1 算法5

1.4.2 算法的描述5

1.4.3 算法分析6

习题一8

第二章 线性表和数组10

2.1 线性表及其基本运算10

2.2 线性表的顺序存贮结构11

2.3 线性表的链式存贮结构——单链表14

2.3.1 单链表14

2.3.2 单链表的运算16

2.3.3 循环链表18

2.4 线性表的链式存贮结构——双向链表19

2.5 多项式相加22

2.6 数组和数组的顺序存贮结构25

2.6.1 数组25

2.6.2 数组的顺序存贮结构26

2.7 矩阵的压缩存贮28

2.7.1 特殊矩阵的压缩存贮28

2.7.2 稀疏矩阵的压缩存贮29

2.8 栈35

2.8.1 栈的定义及其运算35

2.8.2 栈的顺序存贮结构37

2.8.3 多栈共享邻接空间38

2.8.4 栈的链式存贮结构42

2.9 算术表达式求值43

2.10 队列45

2.10.1 队列的定义及其运算45

2.10.2 队列的链式存贮结构45

2.10.3 队列的顺序存贮结构48

2.10.4 其它队列51

3.2 串的存贮结构54

3.1 串的基本概念54

习题二………………………………………………… … ……（51 ）54

第三章 串54

3.2.1 串值的存贮55

3.2.2 串名的存贮映象56

3.3 串的基本运算及其实现57

3.3.1 串的基本运算57

3.3.2 串的基本运算的实现58

3.4 文本编辑63

习题三64

第四章 树66

4.1 树的概念与存贮表示66

4.1.1 树的基本概念66

4.1.2 树的存贮表示68

4.2 二叉树70

4.2.1 二叉树的概念70

4.2.2 二叉树的性质71

4.2.3 二叉树的存贮表示74

4.3 遍历二叉树75

4.3.1 前序遍历76

4.3.2 中序遍历78

4.3.3 后序遍历80

4.4 线索二叉树83

4.5 树、森林与二叉树的转换及遍历90

4.5.1 树的二叉树表示90

4.5.2 森林与二叉树的转换91

4.6.3 哈夫曼码93

4.5.3 树、森林的遍历93

4.6 哈夫曼（Huffman）树及其应用94

4.6.1 路径长度94

4.6.2 哈夫曼树95

习题四100

第五章 图102

5.1 基本术语102

5.1.1 图102

5.1.4 完全图103

5.1.2 顶点的度103

5.1.3 子图103

5.1.5 路径和回路104

5.1.6 连通图与连通分量105

5.1.7 树图105

5.1.8 网络106

5.2 图的存贮表示106

5.2.1 邻接矩阵106

5.2.2 邻接表108

5.3.1 深度优先搜索法110

5.3 图的遍历与求图的连通分量110

5.3.2 宽度优先搜索法113

5.3.3 求图的连通分量114

5.4 生成树和最小（代价）生成树116

5.4.1 无向连通图的生成树116

5.4.2 网络的最小（代价）生成树116

5.4.3 最小生成树问题的解法117

5.5 最短路径119

5.5.1 单源最短路径问题120

5.5.2 每对顶点间的最短路径问题123

5.6 拓扑排序和最长路径125

5.6.1 拓扑排序125

5.6.2 关键路径129

习题五133

第六章 查找135

6.1 基本概念135

6.2 顺序查找136

6.2.1 数组的顺序查找137

6.2.2 线性链表顺序查找138

6.3 有序数组的查找139

6.3.1 二分查找139

6.3.2 线性插值查找142

6.3.3 分区查找143

6.4 二叉排序树查找145

6.4.1 二叉排序树的查找算法146

6.4.2 二叉排序树的结点插入算法147

6.4.3 二叉排序树的结点删除算法148

6.4.4 二叉排序树查找算法分析150

6.5 哈希查找152

6.5.1 哈希函数与哈希表153

6.5.2 构造哈希函数的常用方法154

6.5.3 冲突处理156

习题六160

第七章 排序161

7.1 什么是排序161

7.2.1 冒泡排序162

7.2 内部排序162

7.2.2 选择排序164

7.2.3 插入排序166

7.2.4 归并排序168

7.2.5 堆排序171

7.2.6 快速排序175

7.2.7 基数排序180

7.3 存贮设备183

7.3.1 磁带184

7.3.2 磁盘185

7.4 外部排序186

7.4.1 磁带归并排序186

7.4.2 初始归并段的产生191

7.4.3 磁盘排序193

7.4.4 最佳归并树193

习题七195

8.1 文件的基本概念197

第八章 文件197

8.2 顺序文件198

8.3 索引文件200

8.4 索引顺序文件201

8.5 直接存取文件202

8.6 链接文件和多重链表文件204

8.7 倒排文件205

习题八206

参考文献207

学习指导与实验209