实用数据结构PDF电子书下载

第1章 概述 1

1.1什么是数据结构 2

1.2数据结构的相关概念和术语 8

1.3算法 10

1.3.1算法的概念 10

1.3.2算法的特性 13

1.3.3用类C语言描述算法 14

1.3.4算法的度量 15

1.4本章小结 18

习题1 18

第2章 线性表及线性表的顺序存储 20

2.1线性表的定义 21

2.1.1线性表的实例 21

2.1.2线性表的定义和基本操作 22

2.1.3线性表的数学定义和逻辑图 22

2.2线性表的顺序存储结构（顺序表） 23

2.3顺序表基本算法实现 25

2.3.1线性表内容与线性表长度分别存储的算法实现 25

2.3.2线性表内容与线性表长度存储在一个结构体中的算法实现 32

2.3.3线性表中的元素是字符串的算法实现 36

2.4顺序表的查找 39

2.4.1顺序查找 39

2.4.2二分查找 40

2.4.3顺序查找与二分查找的效率分析 41

2.5插入与删除操作的效率分析 42

2.5.1在顺序表的第i个位置（逻辑位置）插入一个元素 42

2.5.2插入算法的移动次数 44

2.5.3删除算法的移动次数 44

2.6顺序表应用举例 44

2.7本章小结 52

习题2 52

第3章 线性表的链式存储 56

3.1线性表的链式存储结构 57

3.1.1为什么要使用链式存储结构 57

3.1.2单链表的数据定义 59

3.2基于单链表的算法实现 60

3.2.1单链表的基本算法实现 60

3.2.2单链表中插入运算的进一步讨论 65

3.3单链表应用举例 68

3.4链式存储的其他方法 74

3.5基于带表头结点的单循环链表算法实现 76

3.5.1带表头结点的单循环链表的基本算法实现 76

3.5.2带表头结点的单循环链表的应用举例 80

3.5.3带表头结点与不带表头结点的单循环链表的比较 81

3.6双向链表基本算法实现 84

3.7顺序存储方式与链式存储方式的比较 89

3.8本章小结 90

习题3 91

第4章 哈希表与索引表 95

4.1查找的基本概念 96

4.2哈希表 97

4.2.1哈希表的基本概念 97

4.2.2冲突的产生 98

4.2.3可以选择的哈希函数 99

4.2.4解决冲突的方法 102

4.2.5基本算法的实现 104

4.2.6哈希表存储方法的性能分析 110

4.2.7哈希表应用举例 111

4.3索引表 113

4.3.1索引表的构成 113

4.3.2索引表的查找 116

4.3.3分块查找 118

4.4各种查找算法的效率分析 119

4.5本章小结 120

习题4 121

第5章 栈与队列 124

5.1栈 125

5.1.1栈的实例 125

5.1.2栈的基本概念 126

5.1.3用顺序表存储栈的基本算法 126

5.1.4用单链表存储栈的基本算法 131

5.1.5栈应用举例 134

5.2队列 138

5.2.1队列的实例 138

5.2.2队列的基本概念 138

5.2.3用顺序表存储队列的基本算法 140

5.2.4用顺序表存储循环队列的基本算法 144

5.2.5用单链表存储队列的基本算法 148

5.2.6队列应用举例 152

5.3本章小结 159

习题5 160

第6章 内排序 163

6.1排序的基本概念 164

6.1.1简单选择排序的算法思想和实现 164

6.1.2排序的相关概念 167

6.2插入排序 168

6.2.1直接插入排序思想和算法实现 168

6.2.2折半插入排序思想和算法实现 170

6.2.3希尔排序思想和算法实现 172

6.2.4插入排序算法效率分析 175

6.3交换排序 176

6.3.1冒泡排序思想和算法实现 176

6.3.2快速排序思想和算法实现 179

6.3.3交换排序算法效率分析 183

6.4归并排序 183

6.5各种排序算法的比较和分析 187

6.6本章小结 188

习题6 189

第7章 树与二叉树 192

7.1树与二叉树的基本概念 193

7.1.1树与二叉树实例 193

7.1.2树与二叉树的定义 194

7.1.3树与二叉树的相互转换 195

7.2二叉树的基本操作和实现 197

7.2.1二叉树的存储结构 197

7.2.2二叉树的建立 200

7.2.3二叉树的遍历 202

7.3应用举例：堆排序 206

7.4哈夫曼树 210

7.4.1哈夫曼树与哈夫曼编码 210

7.4.2算法实现 212

7.5二叉搜索树 215

7.5.1二叉搜索树的定义 215

7.5.2二叉搜索树基本操作实现 216

7.5.3应用举例 223

7.6本章小结 225

习题7 225

第8章 图 230

8.1图的基本概念 231

8.1.1图的实例 231

8.1.2图的定义和术语 232

8.2图的存储结构 233

8.2.1图的邻接矩阵表示 234

8.2.2图的邻接表表示 237

8.2.3图的十字链表表示 239

8.3图的操作和实现 241

8.3.1图的建立 242

8.3.2图的遍历 245

8.4图的应用——拓扑排序 252

8.4.1拓扑排序的思想 252

8.4.2拓扑排序实现 255

8.5图的应用——最小生成树 257

8.5.1最小生成树的构造方法 257

8.5.2构造最小生成树的算法实现 259

8.6本章小结 263

习题8 264

参考文献 267