C/C++与数据结构(第3版)(下册)(普通高等教育“十一五”国家级规划教材，教育部:微软精品课程建设立项项目)
点此进入淘宝搜索页搜索分類: 图书,教材教辅与参考书,大学,计算机专业,
品牌: 王立柱
基本信息·出版社：清华大学出版社
·页码：151 页
·出版日期：2009年09月
·ISBN：730220067X/9787302200673
·条形码：9787302200673
·包装版本：第3版
·装帧：平装
·开本：16
·正文语种：中文
·丛书名：普通高等教育“十一五”国家级规划教材，教育部:微软精品课程建设立项项目
产品信息有问题吗？请帮我们更新产品信息。
内容简介《C/C++与数据结构(第3版)》（下册）共9章，从第26~第34章，涵盖了二叉树、堆、树、图、二叉搜索树、平衡二叉搜索树、B树、散列和排序等主要内容。基于上册已经包含了C++基础，模拟的C++新标准中的Vector、List、String等数据结构线性部分，通用算法和迭代器等内容，《C/C++与数据结构(第3版)》集中讨论了数据结构的非线性部分，并利用C++实现了全部算法。
《C/C++与数据结构(第3版)(下册)》可以作为C语言和C++语言的本科或专科教材，也可以作为计算机爱好者和程序员的自学教材或参考书。
作者简介王立柱，天津师范大学教授。1982年毕业于南开大学数学系，毕业后在南开大学分校数学系任教，后转入天津师范大学管理学院执教至今。主要从事计算机基础教育和计算机应用研究。讲授过的课程有：离散数学、数学分析、数据结构等。
编辑推荐《C/C++与数据结构(第3版)(下册)》多媒体教学软件独具特色：具有二级菜单．与教材章节一一对应。配有任务栏．相当于三级菜单，与教材每节中更具体的内容对应。算法、程序代码、抽象结构、存储结果、运行过程和结果同时展现。蓝色光条用于跟踪演示程序执行过程。黑色光条用于算法分析。显示器上的数据输入按钮用于输入用户要处理的数据。黄色字体是热区，单击可显示相关的具体内容。《C/C++与数据结构(第3版)(下册)》多媒体教学软件可在作者的教学网站下载。
目录
第26章 二叉树 /1
26.1 二叉树的基本概念 /1
26.2 二叉树的性质 /2
26.3 二叉树的存储结构 /3
26.3.1 二叉树顺序存储 /3
26.3.2 二叉树链式存储 /3
26.4 二叉树层次遍历 /5
26.4.1 层次遍历 /6
26.4.2 把二叉树的顺序存储转为链式存储 /7
26.4.3 垂直输出二叉树 /7
26.5 二叉树前序遍历 /11
26.5.1 前序遍历递归算法 /11
26.5.2 前序遍历非递归算法 /12
26.5.3 快速排序 /12
26.5.4 集合的幂集 /14
26.6 二叉树中序遍历 /16
26.6.1 中序遍历递归算法 /16
26.6.2 中序遍历非递归算法 /17
26.6.3 汉诺塔递归算法 /18
26.7 二叉树后序遍历 /19
26.7.1 后序遍历递归算法 /19
26.7.2 后序遍历非递归算法 /20
26.7.3 求二叉树深度、二叉链表的复制和删除 /20
26.7.4 把二叉树的顺序存储转为链式存储的递归算法 /22
26.7.5 由前序和中序序列建立二叉链表 /22
习题26 /24
第27章 堆 /25
27.1 小根堆Heap类 /25
27.2 堆排序 /29
27.3 哈夫曼树 /32
27.3.1 哈夫曼树的定义 /32
27.3.2 建立哈夫曼树 /32
27.3.3 哈夫曼编码 /35
习题27 /35
第28章 树 /36
28.1 树的基本概念和存储 /36
28.2 Tree类 /39
28.3 树的遍历 /43
28.4 八皇后 /45
习题28 /49
第29章 图 /50
29.1 图的基本概念 /50
29.2 Graph类 /52
29.3 图的遍历 /59
29.3.1 广度优先遍历 /59
29.3.2 深度优先遍历 /61
29.4 最小生成树 /63
29.4.1 普里姆算法 /64
29.4.2 克鲁斯卡尔算法 /70
29.5 最短路径 /73
29.5.1 单源最短路径迪克斯特拉算法 /73
29.5.2 所有顶点对之间的最短带权路径 /79
29.5.3 一顶点对之间的最短带权路径 /84
29.6 拓扑序列 /86
29.7 关键路径 /90
29.8 迷宫求解 /93
习题29 /97
第30章 二叉搜索树 /98
30.1 类型声明与实现 /98
30.2 中序迭代器 /104
30.3 频率统计 /106
30.4 中序线索二叉树 /108
习题30 /109
第31章 平衡二叉搜索树 /110
31.1 动态平衡方法 /110
31.2 二叉平衡搜索树类型 /113
习题31 /116
第32章 B树 /117
32.1 线性索引 /117
32.2 静态m路搜索树 /118
32.3 B-树 /119
32.4 B+树 /122
第33章 散列 /124
33.1 散列表 /124
33.2 散列函数 /125
33.2.1 平方取中法 /125
33.2.2 除留余数法 /125
33.2.3 折叠法 /126
33.2.4 数字分析法 /126
33.3 分离链接法 /126
33.4 开放定址法 /129
33.4.1 线性探查法 /129
33.4.2 平方探查法 /130
33.4.3 双散列函数探查法 /130
习题33 /130
第34章 排序 /131
34.1 性能分析 /131
34.1.1 时间复杂性分析 /131
34.1.2 空间复杂性分析 /132
34.2 插入排序 /133
34.2.1 直接插入排序 /133
34.2.2 折半插入排序 /134
34.2.3 希尔排序 /135
34.3 交换排序 /136
34.3.1 起泡排序 /136
34.3.2 快速排序 /137
34.4 选择排序 /138
34.4.1 直接选择排序 /138
34.4.2 堆排序 /139
34.4.3 锦标赛排序 /140
34.5 归并排序 /144
34.5.1 归并 /144
34.5.2 迭代的归并排序 /145
34.6 基数排序 /146
34.7 外排序 /148
34.7.1 外排序基本过程 /148
34.7.2 k 路归并 /149
习题34 /151
参考文献 /152
……[看更多目录]
序言本书（下册）内容是在上册已经包含了C++基础，模拟的C++新标准中的Vector、List、String等数据结构线性部分，通用算法和迭代器内容的基础上组织的，主要讨论数据结构非线性部分，共9章，从第26~第34章，涵盖了二叉树、堆、树、图、二叉搜索树、平衡二叉搜索树、B树、散列和排序，并利用C++实现了全部算法。这是与第2版教材的主要区别。
本书将一些经典的算法纳入相应的经典结构中进行描述。例如，快速排序和幂集归入二叉树前序遍历，汉诺塔问题并入二叉树中序遍历，哈夫曼树是堆类的直接应用，八皇后和迷宫分别在树和图的深度优先遍历中解决。本书中的算法描述清晰紧凑，代码简洁流畅，既保留了第2版的特点，又因为改用C++语言描述而有所不同。
图1 多媒体软件示例算法性能分析历来是学习数据结构的难点之一，本书将它放在了最后一章，和排序算法一起讨论，使读者可以首先集中精力熟悉和理解各种算法设计和代码实现，然后在充分的感性认识基础上，以综合提高的姿态，以排序为典型内容，学习和掌握算法的时间和空间复杂度分析技术。这是第2版教材没有的内容。
本书的图类综合了Vector、List、适配器、堆方法和C++文件读写方法等多项内容，增强了教材内容的连贯性和整体性。
和上册一样，本书配备了多媒体课件（如图1所示），既可助教又可助学，使复杂和抽象的算法变得直观而简单，尤其对平衡二叉树、图的最短路径、单元最短路径等难度很大的算法，效果更加明显，对初学者更是意义非凡。
本书的源代码和课件可以从精品课网站上直接下载，网址：http://59.67.71.237:8080/dsc.
读者如有问题或发现错误，欢迎直接与作者联系，作者将不胜感激。
文摘插图：
如何在二叉链表上实现层次遍历呢？为此有必要把线性链表和二叉链表作一次比较：线性链表存储的是线性结构，结点结构中存放着其后继的指针，遍历又是按照前驱——后继的顺序进行。访问一个结点之后，从当前结点的指针域可以直接读取其后继结点的地址。而二叉链表存储的是非线性结构，结点结构中虽然寄存着其后继的指针，但是遍历是一层一层进行的，不是按前驱一一后继的顺序，从访问的当前结点的结构中不能直接得到下一个要访问的结点地址。这表明，算法设计的关键是如何按照层次遍历的顺序寄存并提取结点指针，为此，引用队列用来存储二叉链表的结点指针。对结点的访问可以在结点指针出队时进行，也可以在人队前进行，由此分成两种层次遍历方法。
方法1的步骤（过程演示见表26．2中的方法1，代码见表26．3中层次遍历方法1）：
（1）建队列，根结点指针入队。
（2）如果队列不空，从队列删除一个结点指针，访问该指针指向的结点，并把该结点的左右孩子指针（如果存在）依次插入队列。
（3）重复步骤（2），直至队列为空。
方法2的步骤（过程演示见表26．2中的方法2，代码见表26．3中层次遍历方法2）：
（1）建队列，访问根结点，根结点指针入队。
（2）若队列不空，则从队列读取一个结点指针。如果该结点有左孩子，访问左孩子，然后把左孩子指针插入队中；如果该结点有右孩子，访问右孩子，然后把右孩子指针插入队中。
（3）重复步骤（2），直至队列为空。
