数据结构：C++语言描述
苏仕华 刘燕君 刘振安（中国科学技术大学）　编著

市面上讲述数据结构的教材很多，采用的描述语言从早期的Basic到后来的Pascal，再到近期的C和C++，提供了丰富的描述方法。 本书作者一直从事数据结构的教学，并编写过采用不同语言描述的数据结构教材，而且在教学中不断探索，一直想找到更好的描述方法，解决算法描述中受限于数据类型的问题。 本书尝试使用C++语言提供的模板描述算法，这样既接近自然语言，又不再需要考虑具体的数据类型，从而可以把精力集中在对算法的描述上，很好地解决了上述难题。

本书特点
使用模板描述算法，实现参数化类型，使得对算法的描述更接近自然语言，更容易理解。
使用类类型来定义和处理数据，实现数据共享，简化算法设计。
例题典型并提供验证程序，还配有实验和习题，编写了与教材配套的课程设计，帮助学生加深对相关知识的理解。
为了帮助学生考研，在附录中给出了考研指导，提供了一些复习方法、考试技巧以及真题练习和参考答案，指导学生做好考研准备。
为方便教学，提供全部源程序及PPT，有需求的教师可登录华章网站（www.hzbook.com）下载。

数据结构不仅是计算机软件和计算机应用专业的核心课程，也是很多电子信息类专业举足轻重的基础课程，它已经成为很多专业的考研内容，所以学好本课程至关重要。
　　数据结构课程早期使用Basic语言描述，后来使用Pascal语言描述，Pascal语言曾经占据很长时间。如今由于C语言和C++语言的迅猛发展，又开拓了新的描述方法。
　　本书作者一直从事数据结构的教学，编写过使用不同语言的数据结构教材，而且在教学中不断探索，一直想找到更好的描述方法——希望不受数据类型的限制，能更方便地描述数据结构。但C语言限定不同数据类型的数据不能混用，所以在使用C语言描述算法时，必须针对具体的数据类型（如整数、实数和字符等），这就给算法描述带来很多不便。C++语言虽然有类，但类也与数据类型有关。而C++语言提供的模板则很好地解决了这一难题。
　　使用模板描述算法，既接近自然语言，又不需要考虑具体的数据类型，从而可以把精力集中在对算法的描述上。因此本教材尝试使用模板描述算法，并希望能起到抛砖引玉的作用。本教材有如下几个特点：
　　使用模板描述算法，实现参数化类型，使得对算法的描述更接近自然语言，更容易理解。
　　使用类类型来定义和处理数据，实现数据共享，简化算法设计。
　　例题典型，且配有实验和习题，有助于对课文的理解。
　　全书的例题均配有验证程序，并提供全部源程序及PPT，以方便学习和教学。
　　为帮助学生学习，编写了与教材配套的课程设计。课程设计的章与教材对应，并给出该章学习的重点和难点，配有典型例题、实验解答和课程设计题目。
　　为帮助学生考研，专门在附录部分提供了考研指导帮助复习。
　　本书编写采取分工负责、集体讨论的方式。苏仕华执笔第1、6、8、10章及附录，刘燕君执笔第3、4、5、7、9章，刘振安执笔第2、11章并负责统稿。编写本书时，正值刘燕君老师去亚洲大学做博士后研究工作，得到导师逢甲大学张真诚教授及亚洲大学资讯学院黄明祥院长的支持，他才得以完成所承担的写作任务，在此表示衷心感谢。中国科学技术大学软件学院院长陈国良院士及南京大学计算机系陈本林教授在百忙之中审阅了书稿并提出一些宝贵意见，特此感谢。写作中还参考了大量资料，这些资料有的列入参考文献中，还有些没有列入，在此对这些作者表示感谢。
　　由于我们才疏学浅，本书中的不妥之处在所难免，敬请读者不吝赐教，给予指正为盼。
　　联系方式：zaliu@ustc.edu.cn。

　　　　作者
　　　　2013年8月于中国科学技术大学

计算机\数据结构

市面上讲述数据结构的教材很多，采用的描述语言从早期的Basic到后来的Pascal，再到近期的C和C++，提供了丰富的描述方法。
　　本书作者一直从事数据结构的教学，并编写过不同语言的数据结构教材，而且在教学中不断探索，一直想找到更好的描述方法，解决算法描述中受限于数据类型的问题。
　　本书尝试使用C++语言提供的模板描述算法，这样既接近自然语言，又不再需要考虑具体的数据类型，从而可以把精力集中在对算法的描述上，很好地解决了上述难题。
本书特点：
● 使用模板描述算法，实现参数化类型，使得对算法的描述更接近自然语言，更容易理解。
● 使用类类型来定义和处理数据，实现数据共享，简化算法设计。
● 例题典型并提供验证程序，还配有实验和习题，编写了与教材配套的课程设计，帮助学生加深对相关知识的理解。
● 为了帮助学生考研，专门单列一章考研指导，给出了一些复习方法、考试技巧以及真题练习和参考答案，指导学生做好考研准备。
● 为方便教学，提供全部源程序及PPT，有需求的教师可登录华章网站（www.hzbook.com）下载。

前言
第1章　数据结构概论1
　1.1　引言1
　1.2　基本概念和常用术语2
　1.3　算法的描述和分析5
　　1.3.1　算法描述5
　　1.3.2　算法分析6
　实验1　求解鸡兔同笼问题9
　习题19
第2章　类和类模板基础11
　2.1　使用类和对象11
　　2.1.1　使用对象和指针11
　　2.1.2　new和delete运算符13
　2.2　类模板14
　2.3　友元函数和友元类15
　2.4　使用组合18
　2.5　应用实例21
　　2.5.1　使用类求解一元二次方程21
　　2.5.2　使用类模板和头文件求解一元二次方程25
　2.6　使用模板描述算法的优点和注意事项27
　实验2　多文件编程28
　习题228
第3章　线性表30
　3.1　线性表的类型定义30
　　3.1.1　线性表的逻辑定义30
　　3.1.2　线性表的抽象数据类型30
　3.2　线性表的顺序存储及基本运算31
　　3.2.1　线性表的顺序存储31
　　3.2.2　顺序表上基本运算的实现32
　　3.2.3　顺序表运算应用实例36
　　3.2.4　线性顺序表元素为结构的实例37
　3.3　线性表的链式存储结构39
　　3.3.1　线性链表39
　　3.3.2　单链表上的基本运算40
　　3.3.3　单链表上的其他典型运算46
　　3.3.4　双向链表49
　3.4　顺序表和链表的比较53
　实验3　实现一元多项式的加法运算54
　习题354
第4章　栈和队列57
　4.1　栈57
　　4.1.1　栈的定义及抽象数据类型57
　　4.1.2　栈的存储表示和实现58
　4.2　栈应用实例63
　　4.2.1　圆括号匹配的检验63
　　4.2.2　字符串回文的判断63
　　4.2.3　数制转换64
　　4.2.4　栈与递归65
　4.3　队列67
　　4.3.1　抽象数据类型68
　　4.3.2　顺序循环队列68
　　4.3.3　链队列73
　4.4　栈和队列应用实例——表达式求值77
　　4.4.1　中缀表达式到后缀表达式的转换78
　　4.4.2　后缀表达式的计算80
　实验4　八皇后问题82
　习题482
第5章　字符串86
　5.1　串定义及其运算86
　　5.1.1　串的基本概念86
　　5.1.2　串的抽象数据类型86
　　5.1.3　串的存储结构87
　5.2　串的顺序存储结构87
　　5.2.1　顺序串的类型定义和常用算法87
　　5.2.2　串基本运算的实现88
　　5.2.3　串定位（模式匹配）运算89
　　5.2.4　取子串运算（求子串）90
　　5.2.5　连接字符串运算90
　　5.2.6　演示字符串操作的实例91
　5.3　串的链式存储91
　5.4　串运算应用实例92
　实验5　串模式匹配算法94
　习题594
第6章　多维数组和广义表96
　6.1　多维数组和运算96
　　6.1.1　数组的抽象数据类型96
　　6.1.2　数组的顺序存储97
　　6.1.3　矩阵类的定义和运算97
　6.2　矩阵的压缩存储102
　　6.2.1　特殊矩阵103
　　6.2.2　稀疏矩阵107
　6.3　广义表110
　　6.3.1　广义表的定义111
　　6.3.2　广义表的运算111
　6.4　运算符重载112
　　6.4.1　重载对象的赋值运算符112
　　6.4.2　运算符重载的实质115
　实验6　稀疏矩阵的加法运算116
　习题6116
第7章　树和二叉树118
　7.1　树的基本概念和术语118
　7.2　二叉树119
　　7.2.1　二叉树的定义和性质119
　　7.2.2　二叉树的抽象数据类型121
　　7.2.3　二叉树的存储结构121
　7.3　二叉树的运算123
　　7.3.1　二叉树的生成123
　　7.3.2　二叉树的递归遍历及其算法124
　　7.3.3　二叉树递归遍历应用实例127
　　7.3.4　非递归的按层遍历二叉链表130
　　7.3.5　二叉树的非递归遍历算法131
　7.4　线索二叉树133
　　7.4.1　二叉树的线索化134
　　7.4.2　线索二叉链表上的运算135
　7.5　树和森林137
　　7.5.1　树的存储结构137
　　7.5.2　树、森林与二叉树的转换139
　　7.5.3　树和森林的遍历140
　7.6　哈夫曼树及其应用141
　　7.6.1　最优二叉树(哈夫曼树)141
　　7.6.2　哈夫曼算法143
　　7.6.3　哈夫曼算法的实现143
　　7.6.4　哈夫曼编码146
　实验7　二叉树的遍历与查找算法148
　习题7149
第8章　图151
　8.1　图的定义和基本术语151
　8.2　图的存储结构153
　　8.2.1　邻接矩阵表示法153
　　8.2.2　邻接表表示法156
　8.3　图的遍历160
　　8.3.1　深度优先搜索160
　　8.3.2　广度优先搜索162
　8.4　图的生成树和最小生成树165
　　8.4.1　图的生成树165
　　8.4.2　最小生成树166
　8.5　最短路径172
　8.6　拓扑排序177
　实验8　实现无向网络的最小生成树的普里姆算法182
　习题8182
第9章　排序184
　9.1　基本概念184
　9.2　插入排序185
　　9.2.1　直接插入排序185
　　9.2.2　希尔排序186
　9.3　交换排序187
　　9.3.1　冒泡排序188
　　9.3.2　快速排序189
　9.4　选择排序192
　　9.4.1　使用顺序表结构实现直接选择排序193
　　9.4.2　使用链式存储结构实现直接选择排序194
　　9.4.3　堆排序196
　9.5　归并排序199
　9.6　分配排序：基数排序201
　9.7　内部排序方法的分析比较203
　实验9　堆排序204
　习题9204
第10章　查找207
　10.1　基本概念207
　10.2　顺序表的查找207
　　10.2.1　顺序查找208
　　10.2.2　二分查找209
　　10.2.3　分块查找212
　　10.2.4　三种查找方法的比较213
　10.3　树表的查找213
　　10.3.1　二叉排序树213
　　10.3.2　B树217
　　10.3.3　B+树221
　10.4　散列表的查找222
　　10.4.1　散列表的概念222
　　10.4.2　散列函数的构造方法223
　　10.4.3　处理冲突的方法224
　　10.4.4　散列表查找226
　实验10　二叉排序树231
　习题10231
第11章　文件234
　11.1　基本概念234
　11.2　顺序文件235
　11.3　索引文件235
　11.4　索引顺序文件236
　　11.4.1　ISAM文件236
　　11.4.2　VSAM文件237
　　11.4.3　散列文件237
　11.5　多关键字文件237
　　11.5.1　多重表文件237
　　11.5.2　倒排文件238
　实验11　使用文件239
　习题11240
附录A　考研指导242
　A.1　考纲要求242
　　A.1.1　绪论242
　　A.1.2　线性表242
　　A.1.3　栈、队列和数组243
　　A.1.4　树和二叉树243
　　A.1.5　图244
　　A.1.6　查找244
　　A.1.7　排序245
　A.2　知识点、重难点解析246
　A.3　复习方法247
　A.4　考试技巧248
　　A.4.1　单项选择题248
　　A.4.2　算法设计题249
　A.5　实战真题练习250
　　A.5.1　真题练习1250
　　A.5.2　真题练习2252
　　A.5.3　真题练习3255
　　A.5.4　真题练习4257
　　A.5.5　真题练习5259
　A.6　真题练习参考答案261
　　A.6.1　真题1参考答案261
　　A.6.2　真题2参考答案263
　　A.6.3　真题3参考答案264
　　A.6.4　真题4参考答案267
　　A.6.5　真题5参考答案269
附录B　七位ASCII代码表271
参考文献272