数据结构：C++语言描述

图书标准信息

• 作者 陈慧南 著
• 出版社 电子工业出版社
• 出版时间 2020-01
• ISBN 9787121366321
• 定价 59.80元
• 装帧 其他

【内容简介】

  作者依据ACM/IEEE的《计算机科学课程体系规范2013》，参考了近年来国内外很多优秀教材，对《数据结构：C++语言描述》一书从教材结构和内容方面都做了很大调整，编写了《数据结构：C++语言描述》。本次编写保留了经典数据结构和算法知识，引入更多高级数据结构的内容。《数据结构：C++语言描述》重视问题求解，反映抽象、封装和信息隐蔽等现代软件设计理念，重视算法的时间和空间分析，包括查找和排序时间的下界分析。数据结构和算法使用C++语言描述。《数据结构：C++语言描述》重视实践性和程序设计。书中算法都有完整的C++程序，构思精巧、结构清晰、注释详细，并且所有程序都已在VC++环境下编译通过并能正确运行。它们既是很好的学习数据结构和算法的示例，也是很好的C++程序设计示例。《数据结构：C++语言描述》配有大量的实例和图示，并有丰富的习题和实习题，易教易学。《数据结构：C++语言描述》涵盖计算机学科专业考研大纲数据结构部分的考查内容。

【作者简介】

陈慧南，教授，南京邮电大学计算机学院，主持了多项信息产业部基金项目的研究工作，并负责了多项企业办公自动化和信息管理网络系统的研制开发。出版多本教材。曾获江苏省普通高校教学成果三等奖，其主持的《数据结构》课程获江苏省高校一类优秀课程。

【目录】

目    录 
第1章  概论1
1．1  问题求解方法1
1．1．1  问题和问题求解1
1．1．2  问题求解过程1
1．1．3  计算机求解问题的过程2
1．2  什么是数据结构2
1．2．1  算法与数据结构2
1．2．2  数据结构基本概念3
1．2．3  数据的逻辑结构4
1．2．4  数据的存储表示5
1．2．5  数据结构的操作6
1．3  数据抽象和抽象数据类型7
1．3．1  数据抽象和过程抽象7
1．3．2  模块化、封装与信息隐蔽7
1．3．3  数据类型和抽象数据类型8
1．4  面向对象方法10
1．4．1  面向对象方法的由来10
1．4．2  面向对象方法的基本思想10
1．4．3  面向对象方法的基本要素11
1．4．4  抽象数据类型和面向对象方法12
1．4．5  C++语言对抽象数据类型的支持13
1．5  描述数据结构和算法13
1．5．1  数据结构的规范13
1．5．2  实现数据结构14
1．6  算法分析的基本方法15
1．6．1  算法及其性能标准15
1．6．2  算法的时间复杂度16
1．6．3  渐近时间复杂度18
1．6．4  最好、最坏和平均情况时间复杂度19
1．6．5  算法按时间复杂度分类19
1．6．6  算法的空间复杂度19
本章小结20
习题120
第2章  数组和链表22
2．1  两种基本的存储表示方式22
2．2  结构和类22
2．2．1  结构22
2．2．2  结构表示元素23
2．3  指针和动态存储分配24
2．3．1  指针24
2．3．2  动态存储分配25
2．3．3  静态变量和动态变量26
2．4  数组26
2．4．1  一维数组26
2．4．2  二维数组27
2．4．3  多维数组28
2．4．4  数组和指针28
2．4．5  固定长度数组和可变长度数组28
2．5  链表29
2．5．1  指向结构的指针30
2．5．2  单链表30
2．5．3  带表头结点的单链表33
2．5．4  单循环链表33
2．5．5  双向链表33
2．6  采用模拟指针的链表35
2．6．1  结点结构35
2．6．2  可用空间表35
2．7  异常处理37
本章小结38
习题238
第3章  栈和队列40
3．1  栈40
3．1．1  栈ADT40
3．1．2  栈的顺序表示41
3．1．3  栈的链接表示44
3．2  队列47
3．2．1  队列ADT47
3．2．2  队列的顺序表示48
3．2．3  队列的链接表示51
3．3  表达式计算51
3．3．1  表达式51
3．3．2  中缀表达式转换为后缀表达式52
3．3．3  计算后缀表达式的值55
3．4  演示与测试58
本章小结61
习题361
第4章  递归63
4．1  递归和递归算法63
4．1．1  递归的概念63
4．1．2  递归算法示例64
4．2  归纳证明66
4．3  递推关系67
4．4  实现递归67
4．4．1  函数调用和系统栈68
4．4．2  递归函数的性能69
4．4．3  尾递归69
4．4．4  消去递归70
本章小结70
习题470
第5章  线性表和串72
5．1  线性表72
5．1．1  线性表ADT72
5．1．2  线性表的顺序表示73
5．1．3  线性表的链接表示76
5．1．4  两种存储表示的比较79
5．2  一元多项式算术运算80
5．2．1  多项式ADT80
5．2．2  多项式的链接表示80
5．2．3  项结点类81
5．2．4  多项式类82
5．2．5  多项式的输入和输出83
5．2．6  多项式相加84
5．2．7  多项式相乘85
5．2．8  重载运算符86
5．3  串86
5．3．1  串ADT86
5．3．2  串的存储表示87
5．3．3  串运算的实现88
5．3．4  简单模式匹配算法89
5．3．5  KMP算法91
本章小结95
习题595
第6章  数组和广义表97
6．1  数组作为抽象数据类型97
6．1．1  数组ADT97
6．1．2  一维数组的C++类98
6．2  矩阵99
6．2．1  矩阵的概念99
6．2．2  矩阵ADT99
6．2．3  矩阵的二维数组表示100
6．3  特殊矩阵101
6．3．1  对称矩阵101
6．3．2  带状矩阵102
6．4  稀疏矩阵103
6．4．1  稀疏矩阵的三元组表103
6．4．2  稀疏矩阵转置105
6．4．3  稀疏矩阵相加107
6．4．4  稀疏矩阵相乘108
6．5  稀疏矩阵的正交链表109
6．5．1  正交链表结构109
6．5．2  正交链表结点类110
6．5．3  正交链表类111
6．5．4  建立正交链表111
6．5．5  输出正交链表113
6．6  广义表113
6．6．1  广义表的概念113
6．6．2  广义表ADT114
6．6．3  广义表的存储表示115
6．6．4  广义表算法116
本章小结116
习题6117
第7章  树118
7．1  树的基本概念118
7．1．1  树的定义118
7．1．2  基本术语119
7．2  二叉树120
7．2．1  二叉树的定义120
7．2．2  二叉树的性质121
7．2．3  二叉树ADT122
7．2．4  二叉树的存储表示123
7．2．5  二叉树类123
7．2．6  实现二叉树的基本操作124
7．3  二叉树的遍历126
7．3．1  二叉树遍历算法126
7．3．2  二叉树遍历的递归算法128
7．3．3  二叉树遍历的应用实例129
7．4  二叉树遍历的非递归算法131
7．4．1  遍历器类131
7．4．2  中序遍历器类132
7．4．3  后序遍历器类134
7．5  二叉线索树136
7．5．1  二叉线索树的定义136
7．5．2  构造中序线索树137
7．5．3  遍历中序线索树138
7．6  树和森林139
7．6．1  森林与二叉树的转换139
7．6．2  树和森林的存储表示141
7．6．3  树和森林的遍历142
本章小结143
习题7143
第8章  树的应用145
8．1  堆145
8．1．1  堆的定义145
8．1．2  堆的顺序表示145
8．1．3  向下调整和建堆操作145
8．2  优先权队列147
8．2．1  优先权队列ADT147
8．2．2  优先权队列类148
8．2．3  实现优先权队列148
8．3  哈夫曼树和哈夫曼编码150
8．3．1  树的路径长度151
8．3．2  哈夫曼算法152
8．3．3  哈夫曼树类152
8．3．4  构造哈夫曼树153
8．3．5  哈夫曼编码155
8．3．6  哈夫曼编码算法156
8．4  并查集和等价关系156
8．4．1  并查集ADT157
8．4．2  并查集的存储表示157
8．4．3  并查集类158
8．4．4  Union和Find函数159
8．4．5  改进的Union和Find函数159
8．4．6  按等价关系分组160
本章小结161
习题8161
第9章  字典和查找162
9．1  字典及其表示162
9．1．1  字典162
9．1．2  字典查找163
9．1．3  字典ADT163
9．1．4  字典的存储表示164
9．2  顺序查找165
9．2．1  无序表的顺序查找165
9．2．2  有序表的顺序查找165
9．2．3  平均查找长度166
9．2．4  自组织表166
9．3  二分查找167
9．3．1  二分查找算法167
9．3．2  对半查找算法168
9．3．3  二叉判定树169
9．3．4  斐波那契查找算法170
9．3．5  插值查找172
9．4  分块查找172
9．5  查找算法的时间复杂度下界173
本章小结174
习题9174
第10章  二叉查找树175
10．1  二叉查找树表示字典175
10．1．1  二叉查找树的定义175
10．1．2  二叉查找树的查找操作176
10．1．3  二叉查找树的插入操作177
10．1．4  二叉查找树的删除操作178
10．1．5  二叉查找树的高度179
10．2  二叉平衡树179
10．2．1  二叉平衡树的定义179
10．2．2  二叉平衡树类180
10．2．3  二叉平衡树的平衡旋转181
10．2．4  二叉平衡树的插入操作185
10．2．5  二叉平衡树的删除操作187
10．2．6  二叉平衡树的高度189
10．3  伸展树190
10．3．1  自调节树和伸展树190
10．3．2  伸展树的伸展操作191
10．3．3  伸展树类193
10．3．4  旋转的实现193
10．3．5  伸展树的插入操作194
10．3．6  分摊时间分析195
10．4  红黑树195
10．4．1  红黑树的定义195
10．4．2  红黑树的查找操作196
10．4．3  红黑树的插入操作196
10．4．4  红黑树的删除操作198
10．4．5  红黑树的高度199
本章小结199
习题10199
第11章  多叉查找树201
11．1  m叉查找树201
11．2  B?树202
11．2．1  B?树的定义203
11．2．2  B?树的高度203
11．2．3  B?树的查找操作203
11．2．4  B?树的插入操作204
11．2．5  B?树的删除操作206
11．2．6  B?树类207
11．2．7  B?树的查找操作208
11．2．8  B?树的插入函数209
11．2．9  B?树的删除函数210
11．3  键树212
11．3．1  键树的定义212
11．3．2  双链树213
11．3．3  Trie树214
11．3．4  Trie树的查找操作216
11．3．5  Trie树的插入操作216
11．3．6  Trie树的删除操作217
11．3．7  Trie树性能分析217
本章小结218
习题11218
第12章  跳表和散列表219
12．1  跳表219
12．1．1  跳表的概念219
12．1．2  跳表类221
12．1．3  跳表的查找函数222
12．1．4  跳表的插入函数223
12．1．5  跳表的删除函数224
12．1．6  性能分析224
12．2  散列表224
12．2．1  散列技术225
12．2．2  散列函数226
12．2．3  拉链法227
12．2．4  开地址法228
12．2．5  线性探查法228
12．2．6  其他开地址法231
12．2．7  性能分析233
本章小结233
习题12234
第13章  图235
13．1  图的基本概念235
13．1．1  图的定义与术语235
13．1．2  图的抽象数据类型237
13．2  图的存储结构238
13．2．1  图的矩阵表示238
13．2．2  图的邻接矩阵实现239
13．2．3  图的邻接表表示241
13．2．4  图的邻接表实现242
13．2．5  有向图的正交链表表示245
13．2．6  无向图的邻接多重表表示245
13．3  图的遍历246
13．3．1  扩充的图类246
13．3．2  深度优先遍历247
13．3．3  广度优先遍历248
13．3．4  基本遍历方法249
13．4  拓扑排序250
13．4．1  AOV网络250
13．4．2  拓扑排序算法252
13．4．3  拓扑排序算法实现252
13．5  关键路径254
13．5．1  AOE网254
13．5．2  关键路径算法255
13．5．3  关键路径算法实现257
13．6  最小代价生成树258
13．6．1  基本概念258
13．6．2  普里姆算法258
13．6．3  克鲁斯卡尔算法260
13．6．4  算法正确性262
13．7  单源最短路径262
13．7．1  最短路径问题262
13．7．2  迪杰斯特拉算法263
13．7．3  数据结构选择263
13．7．4  迪杰斯特拉算法实现264
13．8  所有顶点之间的最短路径266
13．8．1  弗洛伊德算法266
13．8．2  弗洛伊德算法实现267
本章小结268
习题13268
第14章  内排序270
14．1  基本概念270
14．2  插入排序271
14．2．1  直接插入排序271
14．2．2  顺序表的直接插入排序272
14．2．3  单链表的直接插入排序273
14．2．4  希尔排序274
14．2．5  对半插入排序276
14．3  选择排序276
14．3．1  简单选择排序276
14．3．2  堆排序277
14．4  交换排序278
14．4．1  冒泡排序278
14．4．2  快速排序280
14．4．3  快速排序性能分析281
14．5  两路合并排序283
14．5．1  合并两个有序序列284
14．5．2  两路合并排序迭代算法284
14．5．3  两路合并排序递归算法285
14．5．4  单链表两路合并排序285
14．6  排序算法的时间复杂度下界287
14．7  基数排序288
14．7．1  分配排序289
14．7．2  基数排序算法289
14．7．3  基数排序实现290
本章小结292
习题14292
第15章  文件和外排序294
15．1  辅助存储器简介294
15．1．1  主存储器和辅助存储器294
15．1．2  磁盘存储器294
15．2  文件295
15．2．1  文件的基本概念295
15．2．2  文件的组织方式296
15．3  文件的索引结构298
15．3．1  静态索引结构298
15．3．2  动态索引结构299
15．4  外排序300
15．4．1  外排序的基本过程300
15．4．2  初始游程的生成300
15．4．3  多路合并302
15．4．4  最佳合并树304
本章小结304
习题15305
第16章  实习指导和实习题306
16．1  实习目的、要求和步骤306
16．2  面向对象表示法307
16．3  实习报告和范例308
16．3．1  实习报告308
16．3．2  实习题范例309
16．3．3  实习报告范例309
16．4  实习题312
实习1  C++语言的类及模板的使用312
实习2  数组和链表操作313
实习3  栈、队列及表达式计算313
实习4  线性表的操作及应用314
实习5  一元多项式的相加和相乘314
实习6  对称矩阵和稀疏矩阵的 压缩存储315
实习7  字符串操作和文本 处理315
实习8  二叉树操作和哈夫曼编码315
实习9  有序表查找316
实习10  B?树检索317
实习11  散列表查找317
实习12  图的操作及应用318
实习13  内排序算法及其性能比较318
实习14  置换选择和K路合并的 外排序算法318
附录A  程序测试和调试319
A．1  面向对象程序测试319
A．2  程序测试步骤319
A．3  测试方法320
A．4  程序调试321
附录B  2019年计算机考研大纲与教材内容对照323
B．1  2019年计算机考研大纲323
B．2  教材内容对2019年计算机考研大纲的适应性324
参考文献326