基本信息出版社：电子工业出版社
页码：305 页
出版日期：2009年05月
ISBN：9787121083013
条形码：9787121083013
版本：第1版
装帧：平装
开本：16
正文语种：中文
丛书名：普通高等教育“十一五”国家级规划教材，高等学校计算机基础及应用教材
内容简介 《数据结构与算法(C++语言版)》为普通高等教育“十一五”国家级规划教材。全书共分15章，主要内容包括：绪论、线性表、栈和队列、串、多维数组和广义表、树和二叉树、图、查找、内部排序、文件组织和外排序、贪婪算法、分而治之算法、动态规划、回溯、分枝定界法。在前10章中，对相应的数据结构的ADT描述、存储结构、基本操作、综合算法做了全面深入的阐述，每章的最后都对该章的基本内容、学习要点、具体要求、重点和难点进行了归纳和总结。在第11～15章中，列举了几个应用多种数据结构进行综合性算法设计的典型例子。另外，作者在参考了近年来许多的国内外教材之后，选编了大量精心设计的习题。《数据结构与算法(C++语言版)》每章的学习内容翔实，算法和例题典型，而且给出了对应的VC++6.0源程序。《数据结构与算法(C++语言版)》免费提供电子课件。《数据结构与算法(C++语言版)》不仅可作为计算机学科各专业学生的教材，也适合作为广大工程技术人员和自学考试人员的参考书。
作者简介 肖南峰博士，男，1962年11月生，华南理工大学计算机科学与工程学院教授，博士生导师。1982年7月毕业于华中工学院（现为华中科技大学）自动控制与计算机工程系，获工学学士学位；1989年1月毕业于东北工学院（现为东北大学），获工学硕士学位：2001年6月毕业于日本横浜国立大学，获工学博士学位。2001年9月至2002年9月在澳大利亚Deakin大学从事科学研究。他作为主持人先后完成了2项国家自然科学基金项目、2项广东省自然科学基金重点项目，1项教育部留学回国人员科研启动基金项目，以及由广东省教育厅和华南理工大学等资助的20多项教学与科研课题，在国内外发表学术论文120多篇，其中被三大索引收录近50篇，出版专著和教材5部，申请或获得发明及实用新型专利5项，软件版权10项。他一直在教学一线从事“数据结构”等课程的教学，已先后为近20届计算机专业、计算机辅修专业、电类联合班、继续教育学院和网络学院的本科生讲授过“数据结构”、“高级程序设计语言”等课程，积累了丰富的教学经验。
编辑推荐 《数据结构与算法(C++语言版)》为普通高等教育“十一五”国家级规划教材，高等学校计算机基础及应用教材之一。
目录
第1章 绪论
1.1 什么是数据结构
1.1.1 基本概念
1.1.2 数据结构的内涵
1.1.3 数据类型和抽象数据类型
1.2 算法和算法分析
1.2.1 算法的描述
1.2.2 算法设计的要求
1.2.3 算法分析
本章总结
习题1
第2章 线性表
2.1 线性表的类型定义
2.1.1 基本概念
2.1.2 抽象数据类型描述
2.1.3 线性表抽象类
2.1.4 异常类NoMem和OutOfBounds
2.2 线性表的顺序存储结构
2.2.1 基本概念
2.2.2 基本操作
2.3 线性表的链式存储结构
2.3.1 线性链表
2.3.2 循环链表
2.3.3 双向链表
2.3.4 顺序表和链表的比较
2.4 线性表的应用——多项式相加与Josephus问题
2.4.1 多项式表示
2.4.2 多项式相加
本章总结
习题2
第3章 栈与队列
3.1 栈
3.1.1 栈的定义
3.1.2 栈的抽象类
3.1.3 栈的顺序存储结构
3.1.4 栈的链式存储结构
3.2 栈的应用举例
3.3 栈与递归
3.4 队列
3.4.1 队列的定义
3.4.2 队列的顺序存储结构
3.4.3 队列的链式存储结构
本章总结
习题3
第4章 串
4.1 串的逻辑结构
4.1.1 基本概念
4.1.2 串的大小比较
4.2 串的存储结构
4.3 串函数与串的类定义
4.3.1 常用的C++串函数
4.3.2 串的类定义
4.4 串模式匹配
4.4.1 简单串模式匹配算法
4.4.2 无回溯的匹配算法
4.5 串的应用——文本编辑
本章总结
习题4
第5章 多维数组与广义表
5.1 数组
5.1.1 数组的定义
5.1.2 C++的数组
5.1.3 数组的存储结构与寻址问题
5.2 类Array1D
5.3 矩阵的压缩存储
5.3.1 特殊矩阵
5.3.2 稀疏矩阵
5.4 十字链表
5.4.1 存储方式
5.4.2 十字链表对象
5.4.3 基本操作的实现
5.4.4 十字链表相加法
5.5 广义表
5.5.1 广义表的定义
5.5.2 广义表的抽象数据类型定义
5.5.3 广义表的存储结构
本章总结
习题5
第6章 树与二叉树
6.1 树的相关概念
6.1.1 树的递归定义和逻辑表示法
6.1.2 树的基本术语
6.1.3 树的抽象类型定义
6.2 树的存储结构与遍历
6.2.1 树的存储结构
6.2.2 树与森林的遍历
6.3 二叉树
6.3.1 二叉树的定义
6.3.2 二叉树的性质
6.4 二叉树的存储结构
6.4.1 顺序存储结构
6.4.2 链式存储结构
6.5 二叉树对象模型
6.5.1 二叉树结点对象
6.5.2 二叉树对象
6.6 二叉树的遍历与线索化
6.6.1 二叉树的遍历
6.6.2 二叉树的线索化
6.6.3 二叉树与森林的转换
6.7 哈夫曼树及其应用
6.7.1 哈夫曼树
6.7.2 哈夫曼编码
本章总结
习题6
第7章 图
7.1 图的定义和术语
7.2 图的对象抽象模型
7.2.1 图结点对象抽象模型
7.2.2 图的边对象抽象模型
7.2.3 图对象抽象模型
7.3 图的存储结构
7.3.1 邻接矩阵
7.3.2 邻接表
7.3.3 十字链表（有向图）
7.3.4 邻接多重表（无向图）
7.4 图的遍历
7.4.1 深度优先遍历
7.4.2 广度优先遍历
7.5 图的连通性问题
7.5.1 图的连通分量
7.5.2 生成树及生成森林
7.6 有向无环图及其应用
7.6.1 有向无环图
7.6.2 AOV网与拓扑排序
7.6.3 AOE网与关键路径
本章总结
习题7
第8章 查找
8.1 查找表的相关概念
8.1.1 基本概念
8.1.2 类型说明
8.2 静态查找表
8.2.1 概述
8.2.2 顺序表的查找
8.2.3 有序表的查找
8.2.4 索引顺序表的查找
8.3 动态查找表
8.3.1 概述
8.3.2 二叉排序树
8.3.3 平衡二叉树
8.3.4 B树和B+树
8.4 哈希表
8.4.1 哈希表的定义
8.4.2 哈希函数的构造
8.4.3 处理冲突的方法
8.4.4 哈希表的查找及其分析
本章总结
习题8
第9章 内部排序
9.1 排序的基本概念
9.2 插入排序
9.2.1 直接插入排序
9.2.2 折半插入排序
9.2.3 2路插入排序
9.2.4 表插入排序
9.2.5 希尔排序
9.3 交换排序
9.3.1 冒泡排序
9.3.2 快速排序
9.4 选择排序
9.4.1 简单选择排序
9.4.2 堆排序
9.5 归并排序
9.6 基数排序
9.6.1 多关键码的排序
9.6.2 链式基数排序
9.7 内排序方法的比较和讨论
本章总结
习题9
第10章 文件组织和外排序
10.1 外存储器概述
10.1.1 磁带及其信息的存取
10.1.2 磁盘及其信息的存取
10.1.3 U盘
10.2 文件的基本概念
10.2.1 文件
10.2.2 文件的操作（运算）与存取
10.2.3 文件的物理结构
10.3 顺序文件
10.4 索引文件
10.5 ISAM文件和VSAM文件
10.5.1 ISAM文件
10.5.2 VSAM文件
10.6 散列文件
10.7 多关键字文件
10.7.1 多重表文件
10.7.2 倒排文件
10.8 外部排序
本章总结
习题10
第11章 贪婪算法
11.1 最优化问题
11.2 算法思想
11.3 应用
11.3.1 货箱装船
11.3.2 0-1背包问题
11.3.3 拓扑排序
11.3.4 二分覆盖
11.3.5 单源最短路径
11.3.6 最小代价生成树
习题11
第12章 分而治之算法
12.1 算法思想
12.2 应用
12.2.1 最大最小问题
12.2.2 归并排序
12.2.3 快速排序
12.2.4 选择问题
12.2.5 距离最近的点对问题
习题12
第13章 动态规划
13.1 算法思想
13.2 应用
13.2.1 0-1背包问题
13.2.2 图像压缩
13.2.3 矩阵连乘法
习题13
第14章 回溯
14.1 算法思想
14.2 应用
14.2.1 货箱装船
14.2.2 0-1背包问题
14.2.3 最大完备子图
习题14
第15章 分枝定界法
15.1 算法思想
15.2 应用
15.2.1 货箱装船
15.2.2 0-1背包问题
15.2.3 最大完备子图
习题15
参考文献
……
序言 “数据结构”是计算机学科各个专业的一门重要的专业基础课程。本课程主要讲授数据的逻辑结构、存储结构、基本运算、运算实现、算法设计、算法分析、算法评价等方面的内容，使学生对线性表、栈、队列、串、数组、树及二叉树、无向图和有向图、静态及动态查找表、文件等各种数据结构有深刻的理解，对各种常见的排序方法与算法有深入的了解。在此基础上，还要求学生系统地掌握在不同的存储结构上利用上述数据结构进行综合性算法设计的方法和技巧。因此，它是一门理论性和实践性都很强的课程。
根据作者多年的教学实践发现，学生对于数据结构的应用，特别是在做算法设计习题和编程上机实习这两个环节上都不同程度地存在着一定的困难。为了帮助学生更好地掌握该课程的知识，提高算法设计和动手编程的能力，急需为计算机学科各专业开设的“数据结构”课程编写一本基础扎实、知识面广、适应性强的教材。为此，在华南理工大学精品课程建设基金的资助下，我们编写了这本《数据结构与算法（C++语言版）》教材，主要目的就是加强基础、拓宽知识面、增强适应性，以便使学生能够更深入地理解教材内容，开拓思想，培养并掌握良好的算法设计与程序实现的技能，以及解决实际问题的能力。
本书为普通高等教育“十一五”国家级规划教材。
本书共分15章，主要内容包括：绪论、线性表、栈和队列、串、多维数组和广义表、树和二叉树、图、查找、内部排序、文件组织和外排序、贪婪算法、分而治之算法、动态规划、回溯、分枝定界法。在前10章中，对相应的数据结构的ADT描述、存储结构、基本操作、综合算法做了全面深入的阐述，每章的最后都对该章的基本内容、学习要点、具体要求、重点难点进行归纳和总结。在第11~15章中，列举了几个应用多种数据结构进行综合性算法设计的典型例子。另外，作者在参考了近年来许多的国内外教材之后，选编了大量精心设计的习题。本书每章的学习内容翔实，算法和例题典型，而且给出了对应的VC++ 6.0源程序。本书提供免费电子课件。
本书不仅可作为计算机学科各专业学生的教材，也适合作为广大工程技术人员和自学考试人员的参考书。
文摘 插图：
第1章绪论
从世界上第一台计算机诞生至今，已有60多年的历史。在这期间，计算机的发展和应用已经渗透到了人类社会的各个领域，计算机加工和处理的对象也从纯粹的数值发展到了字符、图像、声音等各种具有一定结构的数据。为了更好地设计程序，以提高计算机在解决复杂问题时的处理效率，研究数据的特性和数据之间存在的关系至关重要。“数据结构”作为计算机科学与技术领域中的一门专业基础课，它专门研究数据的特性和数据之间存在的关系，以及如何在计算机中有效地存取数据和处理数据。因此，“数据结构”是设计和实现编译程序、操作系统、数据库系统和大型应用程序的重要基础，它也是介于数学、计算机硬件和计算机软件之间的一门核心课程，并将随着人类社会的各个领域中计算问题的不断深入研究而继续发展。
1.1什么是数据结构
1.1.1基本概念
（1）数据：信息的载体，是客观事物的符号表示。数据能够被计算机识别、存取和处理，数据也是计算机程序加工和处理的“原料”。例如，实数、字符串、图像和声音等。
（2）数据项：具有独立含义的最小标识单位。例如，字段、域、属性等。
（3）数据元素：数据的基本单位。一个数据元素可由若干个数据项组成。
（4）数据对象：性质相同的数据元素的集合，是数据的一个子集。例如，26个英文字母构成的字符集合，一个学校全体学生或教师构成的学生集合或教师集合等。