数据结构实训教程PDF电子书下载

第1章 线性表 1

1.1 实训知识准备 1

1.1.1 顺序表 1

1.1.2 链表 4

1.2 实训案例分析 8

1.2.1 学生成绩管理 8

1.2.2 求两个集合的差 13

1.2.3 顺序表归并 15

1.2.4 一元多项式相加 17

1.3 实训项目一 21

1.3.1 顺序表操作验证 21

1.3.2 单链表操作验证 21

1.4 实训项目二 21

1.4.1 有序表插入 21

1.4.2 求两集合交集 21

习题 22

1.5.2 单链表的应用 22

1.5.1 约瑟夫(Joseph)问题 22

1.5 实训项目三 22

第2章 栈和队列 24

2.1 实训知识准备 24

2.1.1 栈 24

2.1.2 队列 27

2.2 实训案例分析 31

2.2.1 算术表达式转换为波兰表达式 31

2.2.2 算术表达式求值 33

2.2.3 利用队列解决分油问题 39

2.2.4 迷宫问题 42

2.3 实训项目一 46

2.3.1 栈操作的验证 46

2.3.2 队列操作的验证 46

2.5.2 双端队列操作 47

2.5 实训项目三 47

2.5.1 队列元素倒置 47

2.4.1 判别表达式中括弧是否正确配对 47

2.4 实训项目二 47

2.4.2 公用栈问题 47

习题 48

第3章 串和数组 49

3.1 实训知识准备 49

3.1.1 串及其存储结构 49

3.1.2 数组 53

3.2.1 中心串对称问题 57

3.2 实训案例分析 57

3.2.2 文字研究助手 59

3.2.3 稀疏矩阵相加 66

3.2.4 矩阵相乘 70

3.2.5 稀疏矩阵相乘 72

3.5.1 三元组表示矩阵的相加 76

3.5 实训项目三 76

3.4.2 统计子串在字符串中出现的次数 76

3.4.1 删除串中的字符 76

3.4 实训项目二 76

3.3.2 三元组表示矩阵的转置 76

3.3.1 字符串操作验证 76

3.3 实训项目一 76

3.5.2 求两条对角线元素乘积 77

习题 77

第4章 树 79

4.1 实训知识准备 79

4.1.1 树 79

4.1.2 二叉树 81

4.1.3 线索二叉树 84

4.1.4 二叉排序树 86

4.1.5 哈夫曼树 87

4.2 实训案例分析 88

4.2.1 借助二叉排序树实现排序 88

4.2.2 哈夫曼树的构造 90

4.2.3 标识符的处理 93

4.2.4 哈夫曼编码 97

4.4.2 求二叉树的高度 101

4.4 实训项目二 101

4.4.1 按层次遍历二叉树 101

4.3.1 二叉树的基本操作 101

4.3 实训项目一 101

4.3.2 二叉树的线索化 101

4.5 实训项目三 102

4.5.1 求根结点到指定结点之间的路径 102

4.5.2 求二叉树中指定两个结点的共同祖先 102

习题 102

5.1 实训知识准备 104

5.1.1 基本知识 104

第5章 图 104

5.1.2 图的基本操作 107

5.2 实训案例分析 109

5.2.1 连通无向图的非递归遍历 109

5.2.2 求无向图中通过给定顶点的简单回路 113

5.2.3 医院选址问题 116

5.2.4 求最小生成树 119

5.3 实训项目一 122

5.3.1 以邻接矩阵为存储结构的图的遍历 122

5.5 实训项目三 123

5.4.2 判别在有向图中是否存在给定两顶点之间的路径 123

5.5.1 求图中距顶点v的最短路径长度最大的一个顶点 123

5.3.2 以邻接表为存储结构的图的遍历 123

5.4.1 求有向图中顶点的入度和出度 123

5.4 实训项目二 123

5.5.2 拓扑排序 124

习题 124

第6章 查找 125

6.1 实训知识准备 125

6.1.1 线性表的查找 125

6.1.2 树表的查找 126

6.1.3 散列表的查找 127

6.2 实训案例分析 128

6.2.1 线性表的查找 128

6.2.2 树表的查找 133

6.2.3 散列表的查找 137

6.3 实训项目一 140

6.3.1 线性表的顺序查找 140

6.3.3 线性表的分块查找能 141

6.3.2 有序线性表的查找 141

6.4 实训项目二 142

6.4.1 树表的查找与插入 142

6.4.2 树表的查找与删除 143

6.4.3 树表的判定 144

6.5 实训项目三 144

6.5.1 散列表的线性探测查找 144

6.5.2 散列表的随机探测查找 144

习题 145

6.5.3 散列表的拉链法查找 145

6.5.4 散列表的动态查找 145

第7章 排序 146

7.1 实训知识准备 146

7.1.1 插入排序 146

7.1.2 交换排序 147

7.1.3 选择排序 147

7.1.4 归并排序 147

7.1.5 基数排序 147

7.2.1 双向起泡排序 148

7.2 实训案例分析 148

7.2.2 插入排序 150

7.2.3 二组归并排序 152

7.2.4 递归的快速排序 153

7.2.5 基数排序 155

7.3 实训项目一 157

7.3.1 双向选择排序 157

7.4 实训项目二 158

7.4.1 选择性排序一 158

7.3.2 奇偶起泡排序 158

7.4.2 选择性排序二 159

7.5 实训项目三 159

7.5.1 归并排序一 159

7.5.2 归并排序二 159

7.6 实训项目四 159

7.6.1 非递归的快速排序 159

7.6.2 快速查找 160

7.6.3 基数排序 160

习题 160

主要参考文献 161