书名：数据结构（C语言描述）（第3版）+数据结构习题解答（C语言描述）（第3版）
定价：94.0
ISBN：9787121362248
作者：王晓东、王晓东
版次：1
出版时间：2020-06

内容提要：

数据结构（C语言描述）（第3版）

本书是国家精品课程教材，以***计算机科学与技术教学指导委员会发布的"高等学校计算机科学与技术本科专业规范”为依据，以基本数据结构为知识单元而编写。全书共分12章，包括引论、表、栈、队列、排序与选择、树、图、集合、符号表、字典、优先队列、并查集等。 全书采用C语言作为描述语言，内容丰富，叙述简明，理论与实践并重，每章设有应用举例和算法实验题，并为任课教师免费提供电子课件和课程实验用数据。 读者对象：可作为高等学校计算机、电子信息、信息与计算科学、信息管理与信息系统等专业的数据结构课程教材，也适合工程技术人员和自学者学习参考。  

数据结构习题解答（C语言描述）（第3版）

本书是国家精品课程配套辅导教材，以***计算机类专业教学指导委员会发布的“高等学校计算机科学与技术本科专业规范”为依据，以基本数据结构为知识单元而编写。全书共分10章，包括引论、表、栈、队列、排序与选择、树、散列表、优先队列、并查集、图等。全书采用C语言作为描述语言，内容丰富，叙述简明，理论与实践并重，是《数据结构（C语言描述）》（第3版）的配套教材。本书可作为高等学校计算机、电子信息、信息与计算科学、信息管理与信息系统等专业数据结构课程的辅导教材，也适合工程技术人员和自学者学习参考。

    

作者简介：

王晓东，男，1957年出生，山东人，党员，现任福建工程学院副院长，教授，博士生导师，福建省计算机学会理事长。先后担任福州大学计算机系主任、数学与计算机科学学院院长，2007年8月起担任泉州师范学院副院长。主讲课程：算法与数据结构、算法设计与分析、文献阅读与选题报告。

目录：

习题1  18

算法实验题1  19

第2 章 表  21

2.1 表的基本概念  21

2.2 用数组实现表  22

2.3 用指针实现表  26

2.4 用间接寻址方法实现表  30

2.5 用游标实现表  32

2.6 循环链表  37

2.7 双链表  39

2.8 表的搜索游标  43

2.8.1 用数组实现表的搜索游标  43

2.8.2 单循环链表的搜索游标 44

VI

2.9 应用举例  45

本章小结  47

习题2  47

算法实验题2  49

第3 章 栈  52

3.1 栈的基本概念  52

3.2 用数组实现栈  53

3.3 用指针实现栈  55

3.4 应用举例  57

本章小结  60

习题3  60

算法实验题3  62

第4 章 队列  64

4.1 队列的基本概念  64

4.2 用指针实现队列  64

4.3 用循环数组实现队列  67

4.4 应用举例  70

本章小结  74

习题4  74

算法实验题4  75

第5 章 排序与选择算法  78

5.1 简单排序算法  78

5.1.1 冒泡排序算法  79

5.1.2 插入排序算法  79

5.1.3 选择排序算法  80

5.1.4 简单排序算法的计算复杂性  80

5.2 快速排序算法  81

5.2.1 算法基本思想及实现  81

5.2.2 算法的性能  82

5.2.3 随机快速排序算法  83

5.2.4 非递归快速排序算法  83

5.2.5 三数取中划分算法  84

5.2.6 三划分快速排序算法  85

5.3 合并排序算法  86

5.3.1 算法基本思想及实现  86

5.3.2 对基本算法的改进  87

5.3.3 自底向上的合并排序算法  88

5.3.4 自然合并排序算法  88

5.3.5 链表结构的合并排序算法  89

5.4 线性时间排序算法  90

VII

5.4.1 计数排序算法  90

5.4.2 桶排序算法  91

5.4.3 基数排序算法  92

5.5 中位数与第k 小元素  94

5.5.1 平均情况下的线性时间选择算法  94

5.5.2 坏情况下的线性时间选择算法  95

5.6 应用举例  98

本章小结  100

习题5  100

算法实验题5  101

第6 章 树  104

6.1 树的定义  104

6.2 树的遍历  106

6.3 树的表示法  108

6.3.1 父结点数组表示法  108

6.3.2 儿子链表表示法  108

6.3.3 左儿子右兄弟表示法  108

6.4 二叉树的基本概念  109

6.5 二叉树的运算  111

6.6 二叉树的实现  112

6.6.1 二叉树的顺序存储结构 112

6.6.2 二叉树的结点度表示法 113

6.6.3 用指针实现二叉树  113

6.7 线索二叉树  118

6.8 二叉搜索树  119

6.9 线段树  128

6.10 序列树  134

6.11 应用举例  142

本章小结  147

习题6  147

算法实验题6  149

第7 章 散列表  154

7.1 集合的基本概念  154

7.1.1 集合的定义和记号  154

7.1.2 定义在集合上的基本运算  155

7.2 简单集合的实现方法  156

7.2.1 用位向量实现集合  156

7.2.2 用链表实现集合  158

7.3 散列技术  161

7.3.1 符号表  161

VIII

7.3.2 开散列  163

7.3.3 闭散列  164

7.3.4 散列函数及其效率  168

7.3.5 闭散列的重新散列技术 169

7.4 应用举例  170

本章小结  171

习题7  172

算法实验题7  173

第8 章 优先队列  176

8.1 优先队列的定义  176

8.2 优先队列的简单实现  177

8.3 优先级树和堆  177

8.4 用数组实现堆  179

8.5 可并优先队列  181

8.5.1 左偏树的定义  182

8.5.2 用左偏树实现可并优先队列  182

8.6 应用举例  185

本章小结  190

习题8  190

算法实验题8  191

第9 章 并查集  194

9.1 并查集的定义及其简单实现  194

9.2 用父结点数组实现并查集  195

9.3 应用举例  198

本章小结  201

习题9  201

算法实验题9  202

第10 章 图  205

10.1 图的基本概念  205

10.2 抽象数据类型图  208

10.3 图的表示法  209

10.3.1 邻接矩阵表示法  209

10.3.2 邻接表表示法  209

10.3.3 紧缩邻接表表示法  210

10.4 用邻接矩阵实现图  211

10.4.1 用邻接矩阵实现赋权有向图  211

10.4.2 用邻接矩阵实现赋权无向图  213

10.4.3 用邻接矩阵实现有向图  213

10.4.4 用邻接矩阵实现无向图  213

10.5 用邻接表实现图  214

IX

10.5.1 用邻接表实现有向图  214

10.5.2 用邻接表实现无向图  217

10.5.3 用邻接表实现赋权有向图  218

10.5.4 用邻接表实现赋权无向图  221

10.6 图的遍历  222

10.6.1 广度优先搜索  222

10.6.2 深度优先搜索  224

10.7 短路径  225

10.7.1 单源短路径  225

10.7.2 Bellman-Ford 短路径算法  228

10.7.3 所有顶点对之间的短路径  230

10.8 无圈有向图  231

10.8.1 拓扑排序  231

10.8.2 DAG 的短路径  233

10.8.3 DAG 的长路径  234

10.8.4 DAG 所有顶点对之间的短路径  234

10.9 小支撑树  235

10.9.1小支撑树性质  235

10.9.2 Prim 算法  235

10.9.3 Kruskal 算法  237

10.10 图匹配  239

10.11 应用举例  241

本章小结  243

习题10  244

算法实验题10  245

参考文献  250

目  录
第1章  引论 1
习题1 1
算法实验题1 7
算法实验题1.1  哥德巴赫猜想问题 7
算法实验题1.2  连续整数和问题 8
算法实验题1.3  随机决策森林问题 9
算法实验题1.4  与1共舞数字问题 13
第2章  表 15
习题2 15
算法实验题2 35
算法实验题2.1  向量分类问题 35
算法实验题2.2  *长极差段问题 38
算法实验题2.3  条形图轮廓问题 39
算法实验题2.4  序列分割问题 41
第3章  栈 45
习题3 45
算法实验题3 59
算法实验题3.1  *大全1子矩阵问题 59
算法实验题3.2  大牌明星问题 61
算法实验题3.3  反向字符串输出问题 61
算法实验题3.4  亲兄弟问题 62
第4章  队列 65
习题4 65
算法实验题4 80
算法实验题4.1  组队列问题 80
算法实验题4.2  双栈队列问题 82
算法实验题4.3  环形公路旅行问题 84
算法实验题4.4  逆序表问题 85
第5章  排序与选择 89
习题5 89
算法实验题5 102
算法实验题5.1  交换排序问题 102
算法实验题5.2  DNA排序问题 103
算法实验题5.3  输油管道问题 104
算法实验题5.4  *优服务次序问题 106
算法实验题5.5  动态中位数问题 106
第6章  树 109
习题6 109
算法实验题6 123
算法实验题6.1  层序列表问题 123
算法实验题6.2  *近公共祖先问题 124
算法实验题6.3  区间覆盖问题 128
算法实验题6.4  同构二叉树问题 129
算法实验题6.5  后序中序遍历问题 131
算法实验题6.6  动态子序列问题 132
第7章  散列表 135
习题7 135
算法实验题7 138
算法实验题7.1  *长连续自然数段问题 138
算法实验题7.2  *长双调子序列问题 139
算法实验题7.3  *早*右元素问题 140
算法实验题7.4  换数游戏 141
算法实验题7.5  Fibonacci问题 142
算法实验题7.6  相似三角形问题 143
第8章  优先队列 145
习题8 145
算法实验题8 149
算法实验题8.1  多机调度问题 149
算法实验题8.2  堆雪人问题 150
算法实验题8.3  环形跑道问题 151
算法实验题8.4  二叉搜索堆问题 153
第9章  并查集 157
习题9 157
算法实验题9 160
算法实验题9.1  二进制方程问题 160
算法实验题9.2  网络连通问题 163
算法实验题9.3  任务安排问题 164
算法实验题9.4  无向图的连通分支问题 165
第10章  图 167
习题10 167
算法实验题10 177
算法实验题10.1  *小现金流问题 177
算法实验题10.2  赋权有向图中心问题 179
算法实验题10.3  *长简单路径问题 180
算法实验题10.4  计算机网络问题 182
算法实验题10.5  差分约束问题 183
算法实验题10.6  有截止时间的工作排序问题 184
参考文献 187

第1 章 引论 1

1.1 算法及其复杂性的概念 1

1.1.1 算法与程序 1

1.1.2 算法复杂性的概念 1

1.1.3 算法复杂性的渐近性态3

1.2 算法的表达与数据表示 5

1.2.1 问题求解 5

1.2.2 表达算法的抽象机制 5

1.3 抽象数据类型 8

1.3.1 抽象数据类型的基本概念 8

1.3.2 使用抽象数据类型的好处 9

1.4 数据结构、数据类型和抽象数据类型  10

1.5 用C 语言描述数据结构与算法  11

1.5.1 变量和指针  11

1.5.2 函数与参数传递  12

1.5.3 结构  13

1.5.4 动态存储分配  14

1.6 递归  15

1.6.1 递归的基本概念  15

1.6.2 间接递归  17

本章小结  18