数据结构(C语言描述)(第3版) 王晓东 著 下载 pdf 百度网盘 epub 免费 2025 电子书 mobi 在线

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

第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

习题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

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

暂无出版社相关信息，正在全力查找中！

暂无相关书籍摘录，正在全力查找中！

在线阅读地址：数据结构(C语言描述)(第3版) 王晓东 著在线阅读

在线听书地址：数据结构(C语言描述)(第3版) 王晓东 著在线收听

在线购买地址：数据结构(C语言描述)(第3版) 王晓东 著在线购买

暂无原文赏析，正在全力查找中！

前言

"前 言

以最少的成本、最快的速度、优选的质量开发出适合各种应用需求的软件，必须遵循软件

工程的原则，设计出高效率的程序。一个高效的程序不仅需要编程技巧，而且需要合理的数据

组织和清晰高效的算法。这正是计算机科学领域里数据结构与算法设计所研究的主要内容。

计算机科学是一种创造性思维活动，其教育必须面向设计。数据结构正是一门面向设

计，且处于计算机学科核心地位的教育课程。通过对数据结构知识的系统学习与研究，理解

和掌握数据结构与算法设计的主要方法，为独立完成软件设计和分析奠定坚实的理论基础，

对从事计算机系统结构、系统软件和应用软件研究与开发的科技工作者来说是必不可少的。

为了适应21 世纪我国培养各类计算机人才的需要，本课程结合我国高等学校教育工作的现

状，追踪国际计算机科学技术的发展水平，更新了教学内容和教学方法，以基本数据结构为

知识单元，系统介绍数据结构知识与应用，以期为计算机相关专业的学生提供一个扎实的数

据结构设计的知识基础。本课程的教学改革实践取得了丰硕的成果，课程已被评为国家精品

课程。

本书以ACM 和IEEE/CS Computing Curricula 课程体系及计算机科学与技术教学指

导委员会发布的“高等学校计算机科学与技术本科专业规范”中关于算法与数据结构的知识结

构和体系为依据编写，全书共分为10 章。

第 1 章为引论，介绍数据结构、抽象数据类型和算法等基本概念，并简要阐述了算法的计

算复杂性和对算法的描述。

第2～4 章依次介绍基于序列的抽象数据类型表、栈和队列。

第5 章介绍在实际应用中常用的排序与选择算法。

第6 章讨论反映层次关系的抽象数据类型树。

第7 章讨论散列表等实践中常用实现集合和符号表的方法。

第8 章讨论以有序集为基础的抽象数据类型优先队列及其实现方法。

第9 章讨论以不相交集合为基础的抽象数据类型并查集及其实现方法。

第10 章介绍非线性结构图及其算法。

考虑到学生的知识基础和课程体系需要，本书用C 语言作为描述语言，尽量使数据结构和

算法的描述简明、清晰。参考学时数为54～68。

数据结构是一门理论性强、实践难度较大的专业基础课程。为了使学生在深刻理解课程内

容的基础上，灵活运用所学的知识解决实际问题，我们在章首增加了学习要点提示，章末有本

章小结和难易适当的习题，并特别设计了算法实验题，以强化实践环节，要求学生课后通过上

机实验来完成。作者的教学实践表明，这类算法实验题对学生掌握课堂教学内容有很大帮助，

效果非常好。

国家精品资源共享课地址：http://www.icourses.cn/sCourse/course_2535.html。欢迎广大读者

访问教学网站，并提出宝贵意见，作者E-mail：wangxd＠fzu.edu.cn 。

IV

在本书编写过程中，得到了全国高等学校计算机专业教学指导委员会的关心和支持。福州

大学“211 工程”计算机与信息工程重点学科实验室和福建工程学院为本书的写作提供了优良

的设备和工作环境。傅清祥教授、吴英杰教授、傅仰耿博士和朱达欣教授参加了本书有关章节

的讨论，对本书第3 版的内容及各章节的编排提出了许多建设性意见。田俊教授认真审阅了全

书。在此，谨向每一位曾经关心和支持本书编写工作的人士表示衷心的感谢！

由于作者的知识和写作水平有限，书稿虽几经修改，仍难免有缺点和错误。热忱欢迎同行

专家和读者批评指正，以使本书不断改进，日臻完善。

作者"