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

第1章 绪论 1

1.1数据结构的定义 1

1.2有关概念和术语 2

1.3抽象数据类型 3

1.3.1数据类型 3

1.3.2抽象数据类型 3

1.4算法和算法分析 3

1.4.1算法及特性 3

1.4.2算法设计的要求 4

1.4.3算法描述 4

1.4.4算法性能分析与评价 4

习题1 5

第2章 线性表 7

2.1线性表的逻辑结构 7

2.1.1线性表的定义 7

2.1.2线性表的基本操作 7

2.2线性表的顺序表示和实现 8

2.2.1顺序表 8

2.2.2顺序表基本运算的实现 8

2.2.3顺序表应用举例 10

2.3线性表的链式表示和实现 10

2.3.1单链表 11

2.3.2单链表上基本运算的实现 11

2.3.3循环链表 15

2.3.4双向链表 15

2.3.5单链表应用举例 16

2.4顺序表和链表的比较 18

习题2 19

第3章 栈和队列 22

3.1栈 22

3.1.1栈的定义及基本运算 22

3.1.2栈的存储结构 22

3.2栈的应用举例 25

3.3队列 29

3.3.1队列的定义及基本运算 29

3.3.2队列的存储结构及运算 30

3.4队列应用举例 34

习题3 35

第4章 串 40

4.1串及基本运算 40

4.1.1串的基本概念 40

4.1.2串的基本运算 40

4.2串的定长顺序存储及基本运算 41

4.2.1串的定长顺序存储 41

4.2.2定长顺序串的基本运算 42

4.2.3模式匹配 43

习题4 47

第5章 数组、特殊矩阵和广义表 49

5.1多维数组 49

5.1.1数组的概念 49

5.1.2数组的存储结构 49

5.2特殊矩阵及压缩存储 50

5.2.1对称矩阵 50

5.2.2三角矩阵 51

5.2.3带状矩阵 52

5.3稀疏矩阵 53

5.3.1稀疏矩阵的三元组表存储 53

5.3.2稀疏矩阵的十字链表存储 56

5.4广义表 58

5.4.1广义表的定义和基本运算 58

5.4.2广义表的存储结构 59

5.4.3广义表基本操作的实现 61

习题5 64

第6章 树和二叉树 66

6.1树的概念与定义 66

6.1.1树的定义 66

6.1.2树的相关概念 66

6.2二叉树 67

6.2.1二叉树的定义 67

6.2.2二叉树的主要性质 67

6.3二叉树的存储结构与基本操作 69

6.3.1二叉树的存储 69

6.3.2二叉树的基本操作及实现 70

6.4二叉树的遍历 72

6.4.1二叉树的遍历方法及递归实现 72

6.4.2由遍历序列恢复二叉树 76

6.4.3二叉树遍历算法的应用 77

6.5线索二叉树 79

6.5.1线索二叉树的定义及结构 79

6.5.2线索二叉树的基本操作实现 80

6.6赫夫曼树及应用 82

6.6.1赫夫曼树的基本概念 82

6.6.2赫夫曼树在编码问题中的应用 83

习题6 85

第7章 图 88

7.1图的基本概念 88

7.1.1图的定义 88

7.1.2图的相关术语 88

7.2图的存储表示 90

7.2.1邻接矩阵 90

7.2.2邻接表 91

7.3图的遍历 93

7.3.1深度优先搜索 93

7.3.2广度优先搜索 94

7.4生成树和最小生成树 96

7.4.1生成树的概念 96

7.4.2 Prim算法 96

7.4.3 Kruskal算法 98

7.5最短路径 99

7.5.1从一个源点到其他各点的最短路径 99

7.5.2每一对顶点之间的最短路径 102

7.6有向无环图及其应用 103

7.6.1 AOV网与拓扑排序 103

7.6.2 AOE网与关键路径 105

习题7 109

第8章 查找 116

8.1基本概念与术语 116

8.2基于线性表的查找 117

8.2.1顺序查找法 117

8.2.2折半查找 118

8.2.3分块查找 120

8.3基于树的查找 121

8.3.1二叉排序树 121

8.3.2平衡二叉树 125

8.4哈希表查找 129

8.4.1哈希函数的构造 130

8.4.2处理冲突的方法 131

8.4.3哈希表的查找过程及性能分析 132

习题8 133

第9章 内部排序 136

9.1基本概念 136

9.2插入排序 137

9.2.1直接插入排序 137

9.2.2折半插入排序 137

9.2.3希尔排序 138

9.3交换排序 139

9.3.1冒泡排序 139

9.3.2快速排序 140

9.4选择排序 142

9.4.1直接选择排序 142

9.4.2堆排序 143

9.5归并排序 145

9.6基数排序 146

9.6.1多关键码排序 147

9.6.2链式基数排序 147

9.7条种内部排序方法的比较 150

习题9 150

习题参考答案 153

附录 170

程序1顺序表的运算 170

程序2单链表的运算 172

程序3两个栈共享空间 174

程序4循环队列的入队和出队 176

程序5链队列的入队和出队 178

程序6数制转换 180

程序7二叉树的建立及中序遍历（递归） 182

程序8二叉树的建立及中序遍历（非递归） 184

程序9二叉查找树的静态查找 187

程序10二叉查找树（二叉排序树）的建立及遍历 189

程序11折半查找 191

程序12直接插入排序和冒泡排序 193

参考文献 195