数据结构与算法分析（C++实现）（计算机系列教材）

图书标准信息

• 作者 张千帆、莫嘉铭、王翀 著
• 出版社 清华大学出版社
• 出版时间 2020-11
• 版次 1
• ISBN 9787302564379
• 定价 65.00元
• 装帧 平装
• 开本 16开
• 页数 360页
• 字数 533千字

【内容简介】

本书按照循序渐进的原则介绍线性表、栈、队列、串、树、图等数据结构的逻辑结构、存储结构和数据运算，对于经典算法使用C++构造可执行的程序，帮助读者利用最少的时间和空间资源编写出z优秀最合理的程序。本书可以作为高等院校信息管理与信息系统专业、软件专业、计算机专业的本科教材，也可以作为其他理工科专业的选修教材。教师可以根据本学校的专业特点、学生情况和教学学时，选讲部分章节的内容。

【作者简介】

张千帆，基金委A类期刊外审专家，中国建筑第三工程局有限公司企业管理咨询顾问。2017年获得华中科技大学优秀教职工，2016年获得湖北省大学生暑期社会实践先进工作者、2011年获得湖北省教育系统先进女教职工、2012年和2007年获得华中科技大学教学质量一等奖、2007年获得华中科技大学教学竞赛一等奖。

 

1992-1996年就读于华中科技大学（原华中理工大学）信息管理与信息系统专业，1996年获得工学学士学位，1999年于华中科技大学管理学院获得管理科学与工程硕士学位，2003年于华中科技大学管理学院获得管理科学与工程博士学位，2005年于华中科技大学自动控制系博士后出站。1999年毕业留校任教至今，一直工作在教学一线，具有扎实的学术功底和突出的教学能力，独立主讲本科生和研究生课程，其中主讲4门本科生课程《数据结构》、《管理信息系统》、《《数据库技术及应用》、管理统计学》。作为本科“数据结构”课程组组长和MBA“互联网环境中的组织管理”课程组组长，坚持组织新课开设和课程研讨。

 

主持“信息管理专业边界再设计研究”和“大型实践教学模式与管理类本科实验教学中心建设研究”湖北教改项目2项。

 

【目录】

 

目录

 

第1章绪论1

 

1.1数据结构与程序设计1

 

1.1.1学习数据结构的意义1

 

1.1.2数据与数据结构2

 

1.1.3数据结构的类型4

 

1.2抽象数据类型5

 

1.2.1C++中的数据类型6

 

1.2.2抽象数据类型与C++特性6

 

1.3算法分析10

 

1.3.1问题、算法与程序10

 

1.3.2算法效率的度量10

 

本章小结14

 

 

第2章线性表15

 

2.1线性表的基本概念15

 

2.1.1线性表的定义与特点15

 

2.1.2线性表的存储结构15

 

2.2顺序表的算法实现17

 

2.2.1顺序表的创建和插入19

 

2.2.2顺序表内结点的查找23

 

2.2.3顺序表内元素的删除28

 

2.3单链表的算法实现30

 

2.3.1单链表的结点结构和一般形式30

 

2.3.2单链表的创建和插入32

 

2.3.3单链表内数据元素的查找37

 

2.3.4单链表内数据元素的删除40

 

2.3.5单链表的合并43

 

2.4双向链表的算法实现47

 

2.4.1双向链表的结点结构和一般形式47

 

2.4.2双向链表的创建和插入49

 

2.4.3双向链表内元素的查找53

 

2.4.4双向链表内元素的删除55

 

2.5循环链表的算法实现57

 

2.5.1循环链表的结点结构和一般形式57

 

2.5.2循环链表的创建58

 

2.6线性表的应用――一元多项式的存储和相加63

 

2.6.1一元多项式的存储和相加的实现方式63

 

2.6.2一元多项式的存储和相加的实现65

 

2.7STL的使用68

 

2.7.1STL简介68

 

2.7.2STL应用实例68

 

本章小结69

 

 

第3章栈与队列71

 

3.1栈的基本概念71

 

3.1.1栈的定义与特点71

 

3.1.2栈的两类存储结构71

 

3.2顺序栈的算法实现72

 

3.2.1顺序栈的建立和顺序栈入栈72

 

3.2.2顺序栈出栈74

 

3.3队列的基本概念76

 

3.3.1队列的定义与特点76

 

3.3.2队列的存储结构77

 

3.4顺序队列的算法实现78

 

3.4.1顺序队列的建立和顺序队列入队79

 

3.4.2顺序队列出队80

 

3.5循环队列的算法实现83

 

3.5.1循环队列的建立和循环队列入队83

 

3.5.2循环队列出队85

 

3.6链队列的算法实现87

 

3.6.1链队列的建立和链队列入队87

 

3.6.2链队列出队88

 

3.7栈和队列的应用――算术表达式的转化和求值89

 

本章小结96

 

 

第4章串97

 

4.1串的基本概念97

 

4.1.1串的定义与特点97

 

4.1.2串的存储结构98

 

4.2串的算法实现100

 

4.2.1串赋值算法100

 

4.2.2求子串算法102

 

4.2.3串比较算法104

 

4.2.4串连接算法106

 

4.3串的模式匹配算法实现107

 

4.3.1串的朴素模式匹配算法107

 

4.3.2改进的模式匹配算法109

 

本章小结114

 

 

第5章数组和广义表115

 

5.1数组的基本概念115

 

5.1.1数组的定义与特点115

 

5.1.2数组的存储结构116

 

5.2特殊矩阵的压缩存储117

 

5.3矩阵的算法实现120

 

5.4广义表的基本概念126

 

5.4.1广义表的定义与图形表示126

 

5.4.2广义表的存储结构127

 

5.5广义表的算法实现128

 

本章小结134

 

 

第6章树和二叉树135

 

6.1树的基本概念135

 

6.1.1树的定义与基本术语135

 

6.1.2树的表示形式和存储结构136

 

6.2二叉树的基本概念140

 

6.2.1二叉树的定义与性质140

 

6.2.2二叉树的存储结构142

 

6.2.3树、森林和二叉树的转换144

 

6.2.4二叉树的遍历146

 

6.3二叉树算法实现147

 

6.3.1二叉树的建立147

 

6.3.2递归的二叉树前序遍历、中序遍历、后序遍历150

 

6.3.3非递归的二叉树前序遍历153

 

6.3.4非递归的二叉树中序遍历155

 

6.3.5非递归的二叉树后序遍历157

 

6.4哈夫曼树及其应用161

 

6.4.1哈夫曼树与哈夫曼编码161

 

6.4.2哈夫曼算法实现162

 

本章小结168

 

 

第7章图169

 

7.1图的基本概念169

 

7.1.1图的定义和术语169

 

7.1.2图的表示与存储结构173

 

7.2图的构造算法实现176

 

7.2.1图的基本类定义176

 

7.2.2构造顺序表存储的图179

 

7.2.3构造邻接表存储的无向图与有向图182

 

7.2.4构造十字链表存储的有向图188

 

7.2.5构造邻接多重表存储的无向图193

 

7.3图的遍历算法实现197

 

7.3.1深度优先遍历算法198

 

7.3.2广度优先遍历算法200

 

7.4最小生成树算法实现204

 

7.4.1普里姆算法205

 

7.4.2克鲁斯卡尔算法209

 

7.5图的应用216

 

7.5.1拓扑排序216

 

7.5.2关键路径220

 

7.5.3最短路径――迪杰斯克拉算法225

 

7.5.4最短路径――弗洛伊德算法229

 

本章小结234

 

 

第8章查找235

 

8.1查找的基本概念235

 

8.1.1查找的相关术语235

 

8.1.2查找表结构236

 

8.2顺序表查找算法实现236

 

8.3有序顺序表的折半查找算法实现240

 

8.4索引顺序表的分块查找算法实现245

 

8.4.1索引表245

 

8.4.2分块查找算法实现246

 

8.5二叉排序树及其算法实现250

 

8.5.1二叉排序树及其查找过程250

 

8.5.2二叉排序树建立及插入结点的过程251

 

8.5.3二叉排序树删除结点的过程251

 

8.5.4二叉排序树的算法实现253

 

8.6平衡二叉树及其算法实现258

 

8.6.1平衡二叉排序树及其构造258

 

8.6.2平衡二叉排序树算法实现261

 

8.7B彩骷捌渌惴ㄊ迪268

 

8.7.1B彩268

 

8.7.2B彩鞯牟檎269

 

8.7.3B彩鞯牟迦269

 

8.7.4B彩鞯纳境271

 

8.7.5B彩鞯乃惴ㄊ迪273

 

8.8哈希查找的算法实现282

 

8.8.1哈希表282

 

8.8.2哈希函数的构造方法282

 

8.8.3哈希冲突的处理方法283

 

8.8.4哈希表的算法实现285

 

本章小结289

 

 

第9章排序290

 

9.1排序的基本概念290

 

9.1.1排序相关术语介绍290

 

9.1.2常用的内部排序算法类型简介291

 

9.2插入排序的算法实现292

 

9.2.1直接插入排序292

 

9.2.2希尔排序295

 

9.3交换排序的算法实现299

 

9.4选择排序的算法实现303

 

9.4.1直接选择排序303

 

9.4.2堆排序306

 

9.5归并排序的算法实现313

 

9.6基数排序的算法实现316

 

9.7各种内部排序方法的比较321

 

9.7.1时间性能321

 

9.7.2空间性能321

 

9.7.3排序方法的稳定性322

 

9.8外部排序322

 

本章小结322

 

 

第10章综合案例323

 

10.1背景介绍323

 

10.2问题分解323

 

10.2.1旅行商问题323

 

10.2.2动态规划325

 

10.2.3带酒店选择的旅行商问题328

 

10.3总结与思考331

 

 

附录A文件夹结构332

 

 

附录BUML类图334

 

B.1第2章线性表的相关类图334

 

B.2第3章栈与队列的相关类图336

 

B.3第4章串的相关类图337

 

B.4第5章数组和广义表的相关类图338

 

B.5第6章树和二叉树的相关类图339

 

B.6第7章图的相关类图341

 

B.7第8章查找的相关类图344

 

B.8第9章排序的相关类图346

 

 

参考文献347