本书共8章，内容包括绪论、线性表、栈和队列、数组、树、图、查找和排序等。书中给出了数据结构的增强现实案例。本书内容丰富、条理清晰，讲解摄入浅出，特色鲜明，实用性强，适合高等院校计算机和相关专业的本科生及研究生使用。

“数据结构”是计算机科学中的一门综合性专业基础课，是信息科学的核心课程，是研究非数值计算程序设计问题中计算机操作对象以及它们之间关系和操作的一门学科，也是计算机及相关专业硕士研究生入学考试的必考科目。通过对数据结构的学习，可以培养学生分析数据、组织数据的能力，对进一步学习相关专业的其他课程和开展计算机领域的各项工作，有着不可替代的作用。

“数据结构”课程的概念丰富，理论性、抽象性很强，本书是作者在总结长期教学经验基础上，通过合理规划教学内容编写而成。书中涵盖了高等学校数据结构教学实施方案和数据结构硕士研究生入学考试大纲中要求的全部知识点。全书分为8章，第1章为绪论，阐述数据、数据结构和算法等基本概念，特别强调算法分析的方法；第2～4章主要介绍线性表、栈和队列、数组和串等线性结构的定义、存储结构及相应运算方法和实现过程；第5章为树，介绍树和二叉树的概念与各种算法及其实现过程，重点介绍二叉树的各种遍历算法方法；第6章为图，介绍图的基本概念和图的各种算法及其实现过程；第7～8章讨论查找和排序的各种实现方法和性能分析。

随着虚拟技术的普及应用，将增强现实（AR）技术应用于数据结构学习是一种满足交互式和体验式的新教学方法。本书基于AR技术，将数据结构抽象化教学案例与手机AR相结合，构建虚实交互的学习环境。实践表明，“AR+数据结构”有助于培养学生的学习兴趣，进而激发学生的创新能力和应用能力。基于手机AR的数据结构可视化案例可以在操作对象上叠加辅助信息，引导学生完成案例学习，观察操作结果，这对于培养学生的发散思维能力起到重要作用，可以有效解决当前时空受限、教学成效不突出等问题。

为了方便学生学习和上机实验，我们还出版了与本教程配套的《基于MFC的可视化数据结构》实验指导教材，两者构成一个完成的教学系列。本书给出的所有算法和程序均在Visual C++ 2015环境下调试通过。同时，本书提供了全面丰富的教学资源，其中包括教学PPT，源程序代码和增强现实APP。〖1〗数据结构(AR版)〖3〗〖3〗在本书编写过程中，得到了所在学院的同事的热心帮助和支持，参加本书编写、程序调试、习题收集、内容审校等工作的老师有吴双元、李莉、朱丹丹、范江波、金洲、张建兵、朱丽萍、王智广等，在此向他们表示衷心的感谢！

由于作者水平有限，本书仍可能存在错误和不足之处，敬请读者批评指正。

  编者

2019年9月

增强现实APP

 第1章绪论/1

1.1数据结构的重要性1

1.2数据结构基本术语2

1.3数据的逻辑结构4

1.4数据的存储结构5

1.5算法的基本概念5

1.6算法分析与度量6

1.6.1算法的评价标准6

1.6.2算法效率的度量7

1.7总结与提高13

1.8习题一13

第2章线性结构/16

2.1线性表及逻辑结构16

2.2线性表的顺序存储18

2.2.1顺序存储18

2.2.2顺序表的存储结构描述19

2.2.3顺序结构上的运算19

2.3线性表的链式存储26

2.3.1线性链表26

2.3.2线性链表的存储结构描述27

2.3.3线性链表的基本运算28

2.3.4线性链表操作的性能分析35

2.4顺序表与链表的比较35

2.5循环链表36

2.6双向链表37

2.7应用举例42

2.7.1顺序表的应用：  大整数求和42

2.7.2单链表的应用：  一元多项式加法运算44〖1〗数据结构(AR版)〖3〗〖3〗2.8总结与提高48

2.9习题二49

第3章栈和队列/51

3.1栈51

3.1.1栈的定义51

3.1.2栈的顺序存储结构52

3.1.3栈的链式存储结构57

3.1.4栈的特性分析63

3.2队列65

3.2.1队列的定义65

3.2.2循环队列66

3.2.3链式队列70

3.2.4双端队列74

3.3栈和队列的应用76

3.3.1括号匹配76

3.3.2表达式求解78

3.3.3队列在层次遍历中的应用86

3.4递归87

3.4.1递归的概念87

3.4.2递归算法的设计89

3.4.3转化递归算法为非递归算法91

3.5总结与提高95

3.6习题三95

第4章数组和字符串/98

4.1数组的定义98

4.2数组的顺序存储结构99

4.2.1一维数组的顺序存储100

4.2.2多维数组的顺序存储100

4.3矩阵的压缩存储104

4.3.1特殊矩阵的压缩存储105

4.3.2三对角矩阵的压缩存储106

4.3.3稀疏矩阵的压缩存储107

4.4稀疏矩阵的运算116

4.4.1稀疏矩阵的转置116

4.4.2稀疏矩阵的乘法119

4.5字符串124

4.5.1串的基本概念124

4.5.2串的存储结构124

4.5.3串的模式匹配算法126

4.6总结与提高133

4.7习题四133

第5章树/136

5.1树的定义及基本术语136

5.2N叉树138

5.2.1N叉树的概念138

5.2.2N叉树的性质139

5.3二叉树140

5.3.1二叉树的定义及性质140

5.3.2二叉树的基本操作142

5.4二叉树的存储结构143

5.4.1顺序存储结构143

5.4.2链式存储结构143

5.5二叉树的操作146

5.5.1二叉树的递归遍历146

5.5.2二叉树构造函数149

5.5.3二叉树析构函数150

5.5.4递归遍历算法的应用举例150

5.5.5由遍历序列恢复二叉树153

5.5.6二叉树遍历的非递归算法154

5.6线索二叉树158

5.6.1线索二叉树的定义158

5.6.2中序线索二叉树的建立和遍历160

5.6.3中序线索二叉树插入166

5.6.4中序线索二叉树删除170

5.6.5前序与后序线索二叉树174

5.6.6线索二叉树算法的应用举例174

5.7二叉排序树176

5.7.1二叉排序树的基本概念176

5.7.2二叉排序树的插入178

5.7.3二叉排序树的删除180

5.7.4二叉排序树查找分析184

5.7.5二叉排序树算法的应用举例187

5.8平衡二叉树188

5.8.1平衡二叉树基本概念188

5.8.2平衡化旋转188

5.8.3平衡二叉树的插入191

5.8.4平衡二叉树的删除194

5.8.5平衡二叉树算法的应用举例198

5.9树、森林与二叉树的关系207

5.9.1树的存储结构207

5.9.2森林与二叉树的转换211

5.9.3树与森林的遍历213

5.10Huffman树及其应用215

5.10.1带权路径长度的概念215

5.10.2Huffman树的构造216

5.10.3Huffman树结构定义及算法实现218

5.10.4Huffman编码219

5.11总结与提高222

5.12习题五223

第6章图/227

6.1图的基本概念227

6.1.1图的基本概念与术语227

6.1.2图的基本操作230

6.2图的存储结构232

6.2.1邻接矩阵232

6.2.2邻接表236

6.2.3有向图的十字链表表示240

6.2.4无向图的邻接多重表表示245

6.3图的遍历248

6.3.1深度优先搜索249

6.3.2广度优先搜索251

6.4生成树254

6.4.1MST性质254

6.4.2Kruskal算法255

6.4.3Prim算法261

6.5路径规划264

6.5.1最短路径265

6.5.2Dijkstra算法265

6.5.3Floyd算法269

6.6拓扑排序272

6.7关键路径278

6.8总结与提高288

6.9习题六288

第7章查找/292

7.1基本概念292

7.2线性表查找293

7.2.1顺序查找293

7.2.2线性链表上的顺序查找295

7.3折半查找法296

7.3.1一般的折半查找法296

7.3.2次优查找树：  折半查找的改进方法299

7.4索引查找305

7.4.1索引顺序表与分块查找305

7.4.2多级索引结构与m叉查找树307

7.4.3B树的概念308

7.4.4B树上的查找310

7.4.5B树上的插入312

7.4.6B树上的删除316

7.4.7B树析构函数322

7.4.8B树层序遍历输出322

7.4.9B树操作应用举例324

7.4.10B+树324

7.5散列表及其查找325

7.5.1散列的概念326

7.5.2散列函数设计326

7.5.3处理冲突的方法329

7.5.4散列表查找性能分析341

7.6总结与提高342

7.7习题七343

第8章排序/345

8.1基本概念345

8.2插入排序346

8.2.1直接插入排序347

8.2.2折半插入排序349

8.2.3希尔排序350

8.3交换排序352

8.3.1冒泡排序352

8.3.2快速排序354

8.4选择排序359

8.4.1简单选择排序360

8.4.2堆排序361

8.5归并排序366

8.5.1二路归并366

8.5.2二路归并递归排序算法368

8.6分配排序369

8.6.1桶排序369

8.6.2基数排序370

8.6.3关键字分解370

8.6.4链式基数排序371

8.7内部排序算法比较378

8.7.1排序方法的下界378

8.7.2各种内排序方法的比较379

8.8总结与提高382

8.9习题八382

参考文献/384

第1章面向对象程序设计概述/1

1.1面向过程程序设计1

1.2面向对象程序设计5

1.2.1面向对象程序设计的思想5

1.2.2面向对象的基本概念6

1.2.3面向对象程序设计的优点9

1.3面向对象的软件开发10

1.4图书馆图书借阅管理系统的面向对象分析与设计12

1.4.1面向对象分析12

1.4.2面向对象设计15

本章小结16

习题17

第2章面向过程程序设计概述/18

2.1从C语言到C++18

2.2简单C++程序19

2.3C++对C语言的扩充25

2.3.1C++的输入输出25

2.3.2C++对C语言数据类型的扩展26

2.3.3常变量26

2.3.4指针28

2.3.5引用38

2.3.6函数44

2.3.7名字空间53

2.3.8字符串变量56

2.3.9复数变量60

2.4C++程序的编写和实现63

本章小结64

习题64第3章类与对象/66

3.1类的声明和对象的定义66

3.1.1类和对象的概念及其关系66

3.1.2类的声明67

3.1.3对象的定义68

3.2类的成员函数70

3.2.1成员函数的性质70

3.2.2在类外定义成员函数70

3.2.3inline成员函数71

3.2.4成员函数的存储方式72

3.3对象成员的访问74

3.3.1通过对象名和成员运算符来访问对象的成员74

3.3.2通过指向对象的指针来访问对象的成员74

3.3.3通过对象的引用来访问对象的成员75

3.4构造函数与析构函数76

3.4.1构造函数76

3.4.2析构函数80

3.4.3构造函数和析构函数的调用次序81

3.5对象数组85

3.6对象指针88

3.6.1指向对象的指针88

3.6.2指向对象成员的指针88

3.6.3this指针90

3.7对象与const92

3.7.1常对象92

3.7.2常对象成员93

3.7.3指向对象的常指针94

3.7.4指向常对象的指针94

3.7.5对象的常引用96

3.8对象的动态创建与释放97

3.9对象的赋值与复制98

3.9.1对象的赋值98

3.9.2对象的复制102

3.9.3对象的赋值与复制的比较105

3.10向函数传递对象105

3.11图书馆图书借阅管理系统中类的声明和对象的定义108

本章小结115

习题115

第4章继承与派生/118

4.1继承与派生的概念118

4.2派生类的声明119

4.3派生类的构成120

4.4派生类中基类成员的访问属性121

4.4.1公用继承121

4.4.2私有继承123

4.4.3保护成员和保护继承125

4.4.4成员同名问题127

4.5派生类的构造函数和析构函数129

4.5.1派生类构造函数129

4.5.2派生类析构函数132

4.6多重继承134

4.6.1声明多重继承的方法134

4.6.2多重继承派生类的构造函数与析构函数134

4.6.3多重继承引起的二义性问题137

4.6.4虚基类139

4.7基类与派生类对象的关系143

4.8聚合与组合146

4.9图书馆图书借阅管理系统中继承与聚合的应用148

本章小结165

习题166

第5章多态性与虚函数/168

5.1什么是多态性168

5.2向上类型转换169

5.3功能早绑定和晚绑定171

5.4实现功能晚绑定——虚函数171

5.4.1虚函数的定义和作用172

5.4.2虚析构函数175

5.4.3虚函数与重载函数的比较177

5.5纯虚函数和抽象类177

5.6图书馆图书借阅管理系统中的多态性180

本章小结187

习题188

第6章友元与静态成员/189

6.1封装的破坏——友元189

6.1.1友元函数189

6.1.2友元类194

6.2对象机制的破坏——静态成员195

6.2.1静态数据成员196

6.2.2静态成员函数198

6.3图书馆图书借阅管理系统中友元与静态成员的应用201

本章小结202

习题202

第7章运算符重载/205

7.1为什么要进行运算符重载205

7.2运算符重载的方法207

7.3重载运算符的规则208

7.4运算符重载函数作为类的成员函数和友元函数210

7.4.1运算符重载函数作为类的成员函数210

7.4.2运算符重载函数作为类的友元函数214

7.5几种常用运算符的重载217

7.5.1单目运算符“++”和“--”的重载217

7.5.2赋值运算符“=”的重载221

7.5.3流插入运算符“<<”和流提取运算符“>>”的重载223

7.6不同类型数据间的转换227

7.6.1系统预定义类型间的转换227

7.6.2转换构造函数228

7.6.3类型转换函数231

7.7图书馆图书借阅管理系统中的运算符重载233

本章小结238

习题239

第8章泛型编程/240

8.1函数模板240

8.1.1函数模板的定义241

8.1.2函数模板的实例化243

8.1.3模板参数244

8.1.4函数模板重载248

8.2类模板251

8.2.1类模板的定义252

8.2.2类模板的实例化253

8.2.3类模板参数256

8.3STL简介259

8.3.1容器 259

8.3.2迭代器269

8.3.3算法271

8.3.4函数对象273

8.4图书馆图书借阅管理系统中的泛型编程276

本章小结282

习题282

第9章输入输出/285

9.1C++的输入输出概述285

9.1.1C++的输入输出285

9.1.2C++的输入输出流286

9.2C++的标准输入输出流288

9.2.1C++的标准输出流288

9.2.2C++的标准输入流291

9.3输入输出运算符297

9.3.1输入运算符297

9.3.2输出运算符298

9.3.3输入与输出运算符的重载298

9.4C++格式输入输出299

9.4.1用流对象的成员函数控制输入输出格式299

9.4.2用控制符控制输入输出格式302

9.5文件操作与文件流304

9.5.1文件的概念304

9.5.2文件流类及文件流对象304

9.5.3文件的打开与关闭305

9.5.4对文本文件的操作306

9.5.5对二进制文件的操作308

9.6图书馆图书借阅管理系统中的文件操作312

本章小结313

习题313

第10章异常处理/315

10.1C++异常处理概述315

10.2C++异常处理的实现316

10.3异常与函数322

10.3.1在函数中处理异常322

10.3.2在函数调用中完成异常处理323

10.3.3限制函数异常324

10.4异常与类324

10.4.1构造函数、析构函数与异常处理324

10.4.2异常类327

10.5图书馆图书借阅管理系统中的异常处理330

本章小结332

习题333

第11章图形界面设计/334

11.1基于对话框的图形界面C++程序设计334

11.2基于单文档的图形界面C++程序设计345

11.3图书馆图书借阅管理系统的图形界面设计364

本章小结 364

习题365

参考文献/366第1章C语言程序设计概述/1

1.1程序设计语言1

1.1.1“存储程序”原理1

1.1.2程序设计语言的发展3

1.1.3语言处理程序4

1.2C语言的发展和特点5

1.3C语言的语法单位6

1.3.1C语言的基本符号6

1.3.2关键字6

1.3.3标识符6

1.3.4C语言语句8

1.4C语言程序的基本结构8

1.4.1简单的C语言程序介绍8

1.4.2C程序的结构与书写规则11

1.5程序设计与算法13

1.5.1程序设计13

1.5.2算法概述14

1.5.3算法的描述15

1.5.4结构化程序设计方法19

1.6C语言程序的上机调试20

1.6.1C语言的编译环境与运行程序的步骤20

1.6.2Turbo C开发环境21

1.6.3WinTC系统上机操作方法26

1.6.4Visual C++ 6.0系统上机操作方法28

本章小结34

习题34

上机实训36

实训项目: C语言开发环境的使用与程序调试 37

第2章数据类型、运算符与表达式/39

2.1C语言数据类型与数据的存储39〖1〗C语言程序设计实用教程〖3〗〖3〗2.1.1C语言的数据类型39

2.1.2数据在内存中的存储形式41

2.2变量与常量43

2.2.1常量43

2.2.2变量47

2.3C语言的运算符和表达式53

2.3.1概述53

2.3.2算术运算符和算术表达式55

2.3.3关系运算符和关系表达式57

2.3.4逻辑运算符和逻辑表达式58

2.3.5赋值运算符和赋值表达式60

2.3.6条件运算符和条件表达式61

2.4不同类型数据间的混合运算63

2.5位运算64

2.5.1位逻辑运算64

2.5.2位移运算65

2.5.3位运算赋值运算符65

2.6常用数学库函数的使用66

本章小结67

习题68

上机实训70

第3章顺序结构程序设计/72

3.1C语言简单语句72

3.2数据的输入与输出73

3.3格式化输入与输出75

3.3.1格式化输出函数printf()75

3.3.2格式化输入函数scanf()80

3.4字符数据的输入与输出84

3.4.1字符输出函数putchar()84

3.4.2字符输入函数getchar()85

3.5顺序结构程序设计举例87

本章小结90

习题90

上机实训93

第4章选择结构程序设计/95

4.1if语句95

4.1.1单分支if语句95

4.1.2双分支if语句96

4.1.3if语句的嵌套97

4.2switch语句100

4.3选择结构程序设计举例102

本章小结106

习题107

上机实训110

第5章循环结构程序设计/112

5.1循环的概念112

5.2for语句113

5.3while语句117

5.4do…while语句119

5.5break与continue语句121

5.5.1break语句121

5.5.2continue语句123

5.6循环的嵌套124

5.7程序举例126

本章小结128

习题128

上机实训134

第6章数组/136

6.1概述136

6.2一维数组137

6.2.1一维数组的定义137

6.2.2一维数组的引用138

6.2.3一维数组的初始化139

6.2.4应用举例141

6.3二维数组145

6.3.1二维数组的定义145

6.3.2二维数组的引用147

6.3.3二维数组的初始化147

6.3.4二维数组的应用举例148

6.4字符数组与字符串150

6.4.1字符数组150

6.4.2字符串152

6.4.3字符串处理函数153

本章小结156

习题157

上机实训160

第7章函数/162

7.1函数的定义与调用162

7.1.1函数的分类162

7.1.2函数定义的一般形式164

7.1.3函数的调用167

7.1.4函数的参数传递168

7.2函数的嵌套调用与递归调用172

7.2.1函数的嵌套调用172

7.2.2函数的递归调用173

7.3变量的作用域和存储类别175

7.3.1变量的作用域175

7.3.2变量的存储类别177

7.4内部函数与外部函数178

7.4.1内部函数179

7.4.2外部函数179

7.5程序的多文件结构180

7.6程序举例185

本章小结189

习题189

上机实训192

第8章编译预处理/194

8.1宏定义命令194

8.2文件包含200

8.3条件编译203

本章小结205

习题205

上机实训209

第9章指针/210

9.1地址与指针类型210

9.1.1地址及取地址运算210

9.1.2指针类型与指针运算211

9.2指针变量213

9.2.1指针变量的定义213

9.2.2指针变量的运算214

9.3指针与数组217

9.3.1指向数组元素的指针217

9.3.2用指针法引用数组元素218

9.3.3多维数组与指针220

9.4指针与字符串224

9.5指针与函数227

9.5.1指针变量作函数的参数227

9.5.2指向函数的指针变量232

9.5.3指针型函数235

9.6指针型数组237

9.7多级指针240

本章小结241

习题242

上机实训245

第10章结构体、共用体和枚举类型/247

10.1结构体类型247

10.1.1结构体类型的定义247

10.1.2结构体变量的说明与引用249

10.1.3位段253

10.2结构体数组255

10.2.1结构体数组的定义与初始化255

10.2.2应用举例257

10.3结构体与指针259

10.3.1结构体类型的指针变量259

10.3.2指向结构体数组的指针261

10.3.3结构体类型变量作函数的参数262

10.4动态数据结构与链表264

10.4.1链表的相关概念264

10.4.2动态内存分配函数265

10.4.3链表的建立与操作267

10.5共用体272

10.5.1共用体类型的定义与变量说明272

10.5.2共用体变量的引用273

10.6枚举类型275

10.7用typedef说明一种新类型名277

本章小结280

习题280

上机实训283

第11章文件操作/285

11.1C语言文件概述285

11.2文件的打开与关闭288

11.3文件的读写291

11.3.1字符的输入和输出291

11.3.2格式化输入和输出294

11.3.3字符串的输入和输出298

11.4随机文件的读写301

11.4.1文件的定位301

11.4.2fread函数与fwrite函数302

11.5出错检测函数305

11.5.1ferror()函数305

11.5.2clearerror()函数305

本章小结306

习题307

上机实训311

第12章课程设计/313

12.1课程设计的目的313

12.2课程设计的选题与实施过程314

12.2.1选题314

12.2.2实施过程314

12.3课程设计报告的内容315

12.4课程设计参考题目315

本章小结321

综合项目实训321

附录AC常用库函数/325

附录B全国计算机等级考试二级C语言考试大纲/333

附录C计算机二级C语言考试模拟题/336

模拟题参考答案350

附录D习题参考答案/351第1章习题解答351

第2章习题解答353

第3章习题解答354

第4章习题解答356

第5章习题解答359

第6章习题解答364

第7章习题解答367

第8章习题解答371

第9章习题解答372

第10章习题解答375

第11章习题解答378

参考文献/382

（1）本书利用增强现实AR技术构建虚实交互的数据结构学习环境，更好地激发学生的兴趣和积极性，为数据结构教学提供更多信息技术手段，有助于进一步提高教学质量。

（2）本书强调理论教学和实践应用能力的提高，对于基础理论知识的阐述由浅入深、通俗易懂。书中对每个算法分析，均尽量做到图文并茂、条理清晰、循序渐进，力求使读者更容易理解和掌握。

（3）本书与《基于MFC的可视化数据结构》相互配套，针对每个算法，作者均基于Visual C++ 2015程序设计语言给予完整实现，读者根据这些完整的代码，可以方便地实现相应的可视化展示。

连远锋 中国石油大学（北京）计算机系副教授，主要研究方向为机器视觉和算法设计。主要为本科生教授数据结构（15年以上）和数值分析课程，为研究生讲授机器视觉、人工神经网络等课程。