数据结构：C++实现（第二版）

图书标准信息

• 作者 缪淮扣、沈俊、顾训穰 著
• 出版社 科学出版社
• 出版时间 2014-06
• 版次 1
• ISBN 9787030407399
• 定价 44.00元
• 装帧 平装
• 开本 16开
• 纸张 胶版纸
• 页数 341页

【内容简介】

数据结构是计算机专业教学计划中的一门核心课程，也是信息管理、通信电子、自动控制等与计算机技术关系密切的专业的一门基础课程。从事与计算机科学与技术相关的工作，尤其是计算机应用领域的开发和研制工作，必须具备坚实的数据结构的基础。本书对C++语言作了简单介绍，介绍了线性表、栈、队列、数组、广义表、树、图等数据结构，并介绍了查找和排序的方法。全书用C++语言描述并实现了所有数据结构的类和程序，并附有习题，便于教学。本书是为高等院校开设数据结构课程编著的教材，可作为计算机专业本科生教材使用，也可供从事计算机开发和应用的工程技术人员阅读、参考。

【目录】

第一章绪论1
1.1（算法+数据结构=程序1
1.2数据结构的基本概念2
1.2.1两个简单的数据结构实例2
1.2.2数据结构的定义3
1.3算法性能与复杂度5
1.3.1算法的定义5
1.3.2算法的性能标准6
1.3.3算法复杂度7
习题一10
第二章C++程序设计语言简介13
2.1C++语言基础13
2.1.1程序结构13
2.1.2数据声明和作用域14
2.1.3输入/输出16
2.1.4函数17
2.1.5参数传递18
2.1.6函数名重载19
2.1.7动态内存分配19
2.1.8结构与联合20
2.2类与对象的基本概念24
2.2.1类与对象24
2.2.2消息与合作26
2.2.3多态性26
2.3面向对象的程序设计方法26
2.4C++类与对象27
2.5构造函数和析构函数29
2.6工具函数31
2.7继承33
2.8this指针的使用36
2.9虚函数、多态性以及动态联编37
2.9.1虚函数和多态性37
2.9.2动态联编39
2.10类模板40
习题二42
第三章线性表46
3.1线性表的定义46
3.2线性表的顺序表示47
3.2.1顺序表的类模板定义47
3.2.2顺序表相关算法的复杂度分析53
3.3线性表的链表表示53
3.3.1单链表54
3.3.2双向循环链表63
3.3.3静态链表70
3.4线性表的应用71
3.4.1集合的表示和相关运算的实现71
3.4.2一元多项式表示和相关运算的实现72
习题三75
第四章栈、队列和递归79
4.1栈79
4.1.1顺序栈80
4.1.2链式栈83
4.1.3栈的应用——表达式求值86
4.2队列94
4.2.1循环队列95
4.2.2链式队列99
4.2.3队列的应用——车厢调度103
4.3递归105
4.3.1递归的概念105
4.3.2递归过程与递归工作栈106
4.3.3消除递归107
习题四112
第五章串、数组和广义表115
5.1字符串115
5.1.1字符串的基本概念115
5.1.2常用的C++字符串函数117
5.1.3串类的定义及其实现118
5.1.4模式匹配125
5.2数组130
5.2.1数组的基本概念130
5.2.2数组的顺序存储结构130
5.3稀疏矩阵132
5.3.1非零元素的三元组定义133
5.3.2三元组顺序表133
5.3.3十字链表137
5.4广义表143
5.4.1广义表的定义143
5.4.2广义表的存储结构143
5.4.3n元多项式的表示149
习题五151
第六章树和森林154
6.1树的概念154
6.1.1树的定义154
6.1.2树的术语155
6.1.3树的表示形式156
6.1.4树的基本操作156
6.2二叉树157
6.2.1二叉树的定义158
6.2.2二叉树的性质158
6.2.3二叉树的基本操作160
6.3二叉树的存储结构161
6.3.1顺序二叉树161
6.3.2二叉树的链表表示法162
6.3.3二叉树的二叉链表类模板声明163
6.4遍历二叉树167
6.4.1先序遍历168
6.4.2中序遍历169
6.4.3后序遍历169
6.4.4层序遍历170
6.5线索二叉树171
6.5.1线索二叉树的定义171
6.5.2线索二叉树的类模板定义173
6.6二叉树的应用180
6.6.1堆180
6.6.2哈夫曼树187
6.7树和森林的实现193
6.7.1树的存储结构193
6.7.2树、森林和二叉树的转换196
6.7.3树的遍历198
6.7.4森林的遍历199
6.8等价类及其表示200
6.8.1等价关系与等价类200
6.8.2并查集201
习题六206
第七章图210
7.1图的基本概念210
7.1.1图的定义210
7.1.2图的术语211
7.1.3图的基本操作213
7.2图的存储结构214
7.2.1邻接矩阵214
7.2.2邻接表221
7.2.3邻接多重表230
7.2.4十字链表230
7.3图的遍历与连通性232
7.3.1深度优先遍历232
7.3.2广度优先遍历233
7.3.3连通分量235
7.4最小生成树236
7.4.1克鲁斯卡尔算法237
7.4.2普里姆算法240
7.5最短路径243
7.5.1弧上权值为非负情形的单源点最短路径问题243
7.5.2弧上权值为任意值的单源点最短路径问题246
7.5.3所有顶点之间的最短路径249
7.6活动网络251
7.6.1用顶点表示活动的网络251
7.6.2用边表示活动的网络255
习题七259
第八章查找263
8.1基本概念263
8.2顺序表264
8.2.1顺序表的查找264
8.2.2有序表的折半查找265
8.3索引顺序表和倒排表269
8.3.1索引顺序表269
8.3.2倒排表271
8.4二叉排序树273
8.4.1二叉排序树定义273
8.4.2二叉排序树上的查找275
8.4.3二叉排序树的插入操作276
8.4.4二叉排序树的删除278
8.4.5二叉排序树查找的性能分析280
8.5平衡二叉树280
8.5.1平衡二叉树的定义281
8.5.2平衡旋转281
8.5.3平衡二叉树中插入结点283
8.5.4平衡二叉树中删除结点286
8.6B-树288
8.6.1动态的m路查找树288
8.6.2B-树的定义289
8.6.3B-树的插入290
8.6.4B-树的删除291
8.6.5B+树294
8.7散列表295
8.7.1散列表的基本概念295
8.7.2散列函数296
8.7.3处理冲突的闭散列方法——开地址方法298
8.7.4闭散列方法的实现302
8.7.5处理冲突的开散列方法——链地址法305
8.7.6散列表分析306
习题八307
第九章排序311
9.1基础知识311
9.2交换排序312
9.2.1冒泡排序312
9.2.2快速排序314
9.3插入排序316
9.3.1直接插入排序316
9.3.2折半插入排序320
9.3.3希尔排序320
9.4选择排序322
9.4.1简单选择排序322
9.4.2锦标赛排序325
9.4.3堆排序326
9.5归并排序329
9.5.1归并329
9.5.2两路归并排序330
9.5.3递归的归并排序332
9.6基数排序334
9.6.1多关键字排序334
9.6.2链式基数排序335
9.7各种排序方法的选择和使用338
习题九338
参考文献342