编辑推荐

　　数据结构毫无疑问是计算机科学既经典又核心的课程之一，不管是从事计算机软件还是硬件的开发工作，如果没有系统地学习过数据结构或者没有专心自学过，很容易被人打上“非专业”的标签。对于任何在信息技术行业工作的专业人员或者想进入此行业的人来说，什么时候开始学数据结构都不会晚，更不会过时。
　　从“数据结构”的名字看，它不仅仅只是讲授数据的结构以及在计算机内如何存储和组织数据的方式，这些只是它的表面现象。数据结构背后真正蕴含的是与之息息相关的算法，精心选择的数据结构配合恰如其分的算法就意味着数据或者信息在计算机内被高效率的存储和高效率的处理。算法其实就是数据结构的灵魂，它既神秘又神奇“好玩”，当然对初学者也比较难，算法可以说是“聪明人在计算机上的游戏”。
　　《图解数据结构：使用C++》是一本综合而且全面讲述数据结构及其算法分析的教科书，为了便于高校的教学或者读者自学，作者在描述数据结构原理和算法时文字清晰且严谨，为每个算法及其数据结构提供了演算的详细图解。另外，为了适合教学中让学生上机实践或者自学者上机“操练”，《图解数据结构：使用C++》为每个经典的算法都提供了C++语言编写的完整范例程序实例（包含完整的源代码），每个范例程序都不需要经过修改，直接通过编译就可以运行，目的就是让《图解数据结构：使用C++》的学习者以这些范例程序作为参照迅速掌握数据结构和算法的要点。
　　《图解数据结构：使用C++》的所有范例程序都可以在标准的C++语言编程环境中编译通过并顺利运行，我们在改编《图解数据结构：使用C++》的过程中选用了免费的DevC++5.11集成开发环境，对原书的所有范例程序进行编译、修改、调试和测试，并确保它们都可以准确无误地运行。附录A包含了“C/C++编译程序的介绍与安装”，其中重点就介绍了DevC++。附录B则包含了“C++程序设计语言简介”。

内容简介

　　《图解数据结构：使用C++》主要讲解如何将数据结构概念用C++程序语言进行实作。《图解数据结构：使用C++》将复杂的理论结合图文并茂的解说方式，并搭配丰富的图表及范例介绍，将数据结构中重要的观念及演算方法加以诠释，集中学习焦点。
　　《图解数据结构：使用C++》适合数据结构的初学者使用，也可以作为计算机相关专业的教科书。

作者简介

　　胡昭民，现任荣钦科技股份有限公司董事长，美国RochesterInstituteofTechnology计算机科学研究所毕业，长期从事信息教育及计算机图书写作的工作，并监制过多套游戏及教学软件的研发。

目录

第1章数据结构导论1
1.1数据结构简介2
1.1.1数据结构的应用2
1.1.2算法4
1.1.3算法的描述工具5
1.2认识程序设计7
1.2.1高级程序设计语言7
1.2.2程序设计要领8
1.3程序设计的风格8
1.3.1自顶向下与模块化设计8
1.3.2可读性设计8
1.3.3控制结构设计9
1.3.4面向对象设计10
1.4面向对象设计与C++12
1.4.1C++的面向对象功能12
1.4.2类的基本概念13
1.4.3访问权限关键词14
1.4.4继承关系15
1.4.5多态16
1.5递归算法17
1.5.1递归的定义17
1.5.2斐波拉契数列19
1.5.3汉诺塔问题20
1.6程序效率的分析25
1.6.1Big-oh27
1.6.2Ω(omega)28
1.6.3θ(theta)28
本章习题29
第2章线性表33
2.1线性表的定义34
2.1.1线性表的用途34
2.2数组35
2.2.1一维数组35
2.2.2二维数组37
2.2.3多维数组41
2.2.4结构数组45
2.2.5C++的字符串48
2.2.6字符串数组50
2.2.7String类51
2.2.8指针数组52
2.3矩阵54
2.3.1矩阵的运算54
2.3.2稀疏矩阵57
2.3.3上三角形矩阵60
2.3.4下三角形矩阵62
2.3.5带状矩阵66
本章习题66
第3章链表70
3.1动态分配内存71
3.1.1C++的动态分配变量72
3.1.2动态配置数组73
3.2单向链表74
3.2.1单向链表的创建与遍历74
3.2.2单向链表插入新节点76
3.2.3单向链表删除节点78
3.2.4单向链表的反转80
3.3环形链表82
3.3.1环形链表中插入新节点83
3.3.2环形链表节点的删除84
3.3.3环形链表的连接功能86
3.4双向链表87
3.4.1双向链表的建立与遍历87
3.4.2双向链表中加入新节点88
3.4.3双向链表节点的删除90
3.5链表相关应用简介91
3.5.1多项式表式法92
3.5.2稀疏矩阵表示法95
本章习题97
第4章堆栈与队列103
4.1堆栈简介104
4.1.1堆栈的基本操作105
4.1.2用数组实现堆栈105
4.1.3用链表实现堆栈107
4.1.4堆栈类样板的实现108
4.1.5老鼠走迷宫109
4.1.6八皇后问题112
4.2算术表达式的表示法114
4.2.1中序转为前序与后序115
4.2.2前序与后序转为中序120
4.2.3中序表示法求值122
4.2.4前序法的求值运算124
4.2.5后序法的求值运算125
4.3队列125
4.3.1队列的基本操作126
4.3.2用数组实现队列126
4.4队列的相关应用129
4.4.1环形队列129
4.4.2双向队列133
4.4.3优先队列134
本章习题135
第5章树状结构147
5.1树的基本概念148
5.1.1专有名词介绍149
5.2二叉树150
5.2.1二叉树的特性150
5.2.2特殊二叉树简介152
5.3二叉树的存储方式153
5.3.1一维数组表示法153
5.3.2链表表示法155
5.4二叉树的遍历156
5.4.1中序遍历157
5.4.2后序遍历158
5.4.3前序遍历158
5.4.4二叉树节点的插入与删除160
5.4.5二叉运算树165
5.5线索二叉树167
5.5.1二叉树转为线索二叉树167
5.6树的二叉树表示法171
5.6.1树转化为二叉树171
5.6.2二叉树转换成树173
5.6.3森林化为二叉树174
5.6.4二叉树转换成森林175
5.6.5树与森林的遍历176
5.6.6确定唯一二叉树180
5.7优化二叉查找树182
5.7.1扩充二叉树182
5.7.2霍夫曼树184
5.8平衡树185
5.8.1平衡树的定义185
5.9高级树状结构的研究187
5.9.1决策树187
5.9.2B树189
5.9.3二叉空间分割树190
5.9.4四叉树与八叉树191
本章习题192
第6章图形结构202
6.1图形简介203
6.1.1图的定义204
6.1.2无向图204
6.1.3有向图206
6.2图的数据表示法207
6.2.1邻接矩阵法207
6.2.2邻接表法210
6.2.3邻接复合链表法212
6.2.4索引表格法214
6.3图的遍历217
6.3.1深度优先遍历法217
6.3.2广度优先遍历法219
6.4生成树221
6.4.1DFS生成树和BFS生成树222
6.4.2最小生成树223
6.4.3Kruskal算法224
6.4.4Prim算法227
6.5图的最短路径228
6.5.1单点对全部顶点229
6.5.2两两顶点间的最短路径232
6.6AOV网络与拓朴排序235
6.6.1拓朴排列简介236
6.7AOE网络237
6.7.1关键路径238
本章习题239
第7章排序248
7.1排序简介249
7.1.1排序的分类250
7.2内部排序法251
7.2.1冒泡排序法251
7.2.2选择排序法254
7.2.3插入排序法256
7.2.4希尔排序法258
7.2.5合并排序法260
7.2.6快速排序法260
7.2.7堆积排序法263
7.2.8基数排序法269
7.3外部排序法272
7.3.1直接合并排序法272
7.3.2k路合并法275
7.3.3多相合并法276
本章习题276
第8章查找286
8.1常见的查找方法287
8.1.1顺序查找法287
8.1.2二分查找法288
8.1.3插值查找法290
8.1.4斐波那契查找法292
8.2哈希查找法295
8.2.1哈希法简介296
8.3常见的哈希函数297
8.3.1除留余数法297
8.3.2平方取中法297
8.3.3折叠法298
8.3.4数字分析法299
8.4碰撞与溢出问题的处理300
8.4.1线性探测法300
8.4.2平方探测301
8.4.3再哈希301
8.4.4链表301
本章习题303
附录AC/C++编译程序的介绍与安装309
A.1C/C++编译程序简介310
A.2DevC++的安装与介绍313
附录BC++程序设计语言简介319
B.1C++语言的基本概念320
B.2C++语言的运算符与表达式323
B.3C++语言的流程控制327
B.4　C++语言的高级语法332
B.5C++语言与面向对象概念341
附录C数据结构专有名词索引349

精彩书摘

　　第7章排序
　　随着信息科技的逐渐普及与全球国际化的影响，企业所拥有的数据量成倍数的增长。无论是庞大的商业应用软件，还是小至个人的文字处理软件，每项工作的核心都与数据库有着莫大的关系，而数据库中最常见且重要的功能就是排序与查找，如图7.1所示。
　　图7.1现在每项工作的核心都与数据库关系密切
　　“排序”（sorting）是指将一组数据，按特定规则调换位置，使数据具有某种顺序关系（递增或递减）。例如数据库内可针对某一字段进行排序，而此字段称为“键（key）”，字段里面的值我们称之为“键值（keyvalue）”。
　　7.1排序简介
　　在排序的过程中，数据的移动方式可分为“直接移动”和“逻辑移动”两种。“直接移动”是直接交换存储数据的位置，而“逻辑移动”并不会移动数据存储的位置，仅改变指向这些数据的辅助指针的值。如图7.2和图7.3所示。
　　图7.2直接移动排序
　　图7.3逻辑移动排序
　　两者间的优劣在于直接移动会浪费许多时间进行数据的移动，而逻辑移动只要改变辅助指针指向的位置就能轻易达到排序的目的。例如在数据库中，可在报表中可显示多项记录，也可以针对这些字段的特性来分组并进行排序与汇总，这就是属于逻辑移动，而不是去实际移动改变数据在数据文件中的位置，如图7.4所示。
　　图7.4数据库使用的是逻辑移动排序
　　7.1.1排序的分类
　　排序通常按照数据量的多寡和所使用的内存可分为“内部排序”（internalsort）和“外部排序”（externalsort），数据量小则可以全部加载到内存（如RAM）来进行的排序就称为内部排序，大部分排序属于此类。数据量大无法全部一次性加载到内存，必须借助磁带、磁盘等辅助存储器进行排序则称为外部排序。
　　以上只是粗略的区分，其实随着数据结构科学的进步，陆续提出了如冒泡排序法、选择排序法、插入排序法、合并排序法、快速排序法、堆积排序法、希尔排序法、基数排序法、直接合并排序法等等，各有其特色与应用场合。
　　就排序法的选择来说，当数据量相当大时，排序算法所花费的时间就显得相当重要；一个排序法是否为一种有效率（efficiency）的排序法，取决于其时间复杂度，而时间复杂度的决定因素则是排序过程中数据的交换次数及其比较次数的多少。
　　排序前：213445567781
　　排序后：817756453421
　　【这种排序的时间复杂度就是最坏情况】
　　时间复杂度可分为最好情况（bestcase）、最坏情况（worstcase）及平均情况（averagecase）。最好情况就是数据已完成排序，例如原本数据已经完成升序了，如果再进行一次升序所使用的时间复杂度就是最好情况。最坏情况是指每一个键值均须重新排列，简单的例子就如原本为升序现在要重新排序成为降序，就是最坏情况。而空间复杂度就是指算法在执行过程所需占用的额外内存空间，排序法所使用到的额外空间越少，它的空间复杂度就越佳，例如冒泡法在排序过程中仅会用到一个额外的空间，在所有的排序算法中，这样的空间复杂度就算是最好的。
　　7.2内部排序法
　　在正式讨论排序法之前，还要来讨论排序的稳定度，因为并非所有排序法都是稳定排序法。所谓稳定的排序是指数据在经过排序后，两个相同键值的记录仍然保持原来的顺序，如下例中30左的原始位置在30右的左边（所谓30左和30右是指相同键值一个在左而一个在右），稳定的排序（StableSort）后30左仍应在30右的左边，不稳定排序则有可能30左会跑到30右的右边去：
　　原始数据顺序：30左106530右21
　　稳定的排序：102130左30右65
　　不稳定的排序：102130右30左65
　　事实上，每一种排序方法都有其适用的情况与数据种类。建议大家要充分了解排序算法的过程及其所花费的时间与空间复杂度。
　　7.2.1冒泡排序法
　　冒泡排序法又称为交换排序法，是从观察水中气泡变化构思而成，原理是从第一个元素开始，比较相邻元素的大小，若大小顺序有误，则对调后再进行下一个元素的比较，就仿佛气泡逐渐从水底逐渐冒升到水面上一样。如此扫描过一次之后就可确保最后一个元素是位于正确的顺序。接着再逐步进行第二次扫描，直到完成所有元素的排序关系为止。
　　以下使用55、23、87、62、16数列的演示排序过程，这样大家可以清楚地知道冒泡排序法的具体流程。图7.5为原始顺序，图7.6到7.9为排序的具体过程。
　　从小到大排序：
　　图7.5排序前的原始位置
　　图7.6冒泡排序的第一次扫描
　　第一次扫描会先拿第一个元素55和第二个元素23进行比较，如果第二个元素小于第一个元素，则进行互换。接着拿55和87进行比较，就这样一直比较并互换，到第4次比较完后即可确定最大值在数组的最后面。
　　图7.7冒泡排序的第二次扫描
　　第二次扫描也是从头比较，但因为最后一个元素在第一次扫描就已确定是数组中的最大值，故只需比较3次即可把剩余数组元素的最大值排到剩余数组的最后面。
　　第三次扫描完，完成3个值的排序，如图7.8所示。
　　图7.8冒泡排序的第三次扫描
　　第四次扫描完，即可完成所有排序，如图7.9所示。
　　图7.9冒泡排序的第四次扫描
　　由此可知5个元素的冒泡排序法必须执行5-1次扫描，第一次扫描需比较5-1次，共比较4+3+2+1=10次
　　7.2.1
　　数列(43,35,12,9,3,99)用冒泡排序法（BubbleSort）进行从小到大排序，在执行时前3次（Swap，互换）的结果各是什么？
　　第一次互换的结果为(35,43,12,9,3,99)
　　第二次互换的结果为(35,12,43,9,3,99)
　　第三次交换的结果为(35,12,9,43,3,99)
　　冒泡排序法的C++算法：
　　for(inti=5;i>0;i--)//扫描次数
　　{
　　for(intj=0;jdata[j+1])//比较相邻两数，如第一个数较大则互换
　　{
　　inttmp;
　　tmp=data[j];
　　data[j]=data[j+1];
　　data[j+1]=tmp;
　　}
　　}
　　cout

其他推荐