基本信息出版社：机械工业出版社
页码：263 页
出版日期：2009年08月
ISBN：9787111277941
条形码：9787111277941
版本：第1版
装帧：平装
开本：16
正文语种：中文
丛书名：高等院校规划教材计算机科学与技术系列

内容简介 《数据结构 (C++版)》共分11章。第1章介绍数据结构和算法的概念及相关术语。第2～5章介绍线性结构。第6～8章介绍非线性结构。第9章和第10章分别介绍了查找和排序。第11章介绍了一些常用文件。各章内容都有相对独立的部分，以便针对不同专业或不同层次的需要组织教学。《数据结构 (C++版)》可作为高等院校计算机类专业和相关专业数据结构课程的教材，也可以供从事计算机应用工作的工程技术人员参考。”
编辑推荐 《数据结构 (C++版)》是由机械工业出版社出版。
目录
出版说明
前言
第1章 绪论
1.1 数据结构的研究内容
1.2 数据结构的基本概念和相关术语
1.3 算法和算法分析
1.3.1 算法的概念
1.3.2 算法效率和存储量的估算方法
1.4 习题

第2章 线性表
2.1 线性表的基本概念
2.2 线性表的顺序存储结构
2.3 线性表的链式存储结构
2.3.1 线性链表
2.3.2 循环链表
2.3.3 双向链表
2.3.4 静态链表
2.4 一元多项式的表示和相加运算
2.5 习题

第3章 栈和队列
3.1 栈
3.1.1 栈的概念和抽象数据类型
3.1.2 栈的顺序存储结构
3.1.3 栈的链式存储结构
3.1.4 表达式求值
3.2 队列
3.2.1 队列的概念和抽象数据类型
3.2.2 队列的链式存储结构
3.2.3 队列的顺序存储结构——循环队列
3.3 栈和队列的应用实例
3.3.1 停车场管理
3.3.2 银行业务模拟
3.4 递归
3.4.1 递归的基本概念
3.4.2 递归算法设计
3.4.3 递归过程和递归工作栈
3.5 习题

第4章 数组和矩阵压缩存储
4.1 数组的逻辑特点
4.2 数组的存储结构
4.3 矩阵的压缩存储
4.3.1 特殊矩阵的压缩存储方法
4.3.2 稀疏矩阵的概念
4.3.3 稀疏矩阵的三元组表表示
4.3.4 稀疏矩阵的十字链表表示
4.4 习题

第5章 串
5.1 串的基本概念
5.2 串的存储结构
5.2.1 串的顺序存储结构
5.2.2 串的链式存储结构
5.3 串操作的实现
5.4 串的模式匹配
5.4.1 简单的模式匹配算法
5.4.2 KMP算法
5.5 建立词索引表
5.6 习题

第6章 广义表
6.1 广义表的基本概念
6.2 广义表的存储结构
6.3 广义表的基本运算
6.4 多元多项式的表示
6.5 习题

第7章 树
7.1 树的基本概念
7.1.1 树的定义
7.1.2 树的基本术语
7.1.3 树的抽象数据类型
7.2 二叉树的概念和存储结构
7.2.1 二叉树的定义
7.2.2 二叉树的性质
7.2.3 二叉树的存储结构
7.3 二叉树的数据类型
7.4 二叉树的遍历
7.4.1 先序遍历二又树
7.4.2 中序遍历二叉树
7.4.3 后序遍历二叉树
7.4.4 按层次遍历二又树
7.4.5 二叉树遍历的应用例子
7.5 线索二叉树
7.5.1 线索二又树的概念
7.5.2 中序线索二叉树和中序线索链表
7.6 树和森林
7.6.1 树的存储结构
7.6.2 树、森林与二叉树的转换
7.6.3 树和森林的遍历
7.7 哈夫曼树及其应用
7.7.1 哈夫曼树
7.7.2 哈夫曼编码
7.8 习题

第8章 图
8.1 图的基本概念
8.2 图的存储结构
8.2.1 数组表示
8.2.2 邻接表
8.2.3 十字链表
8.2.4 邻接多重表
8.3 图的遍历
8.3.1 深度优先遍历
8.3.2 广度优先遍历
8.4 有向无环图及其应用
8.4.1 拓扑排序
8.4.2 关键路径
8.5 最小生成树
8.5.1 普里姆算法
8.5.2 克鲁斯卡尔算法
8.6 最短路径
8.6.1 求从一个源点到其他各顶点的最短路径
8.6.2 求任意两个顶点之间的最短路径
8.7 习题

第9章 查找
9.1 概述
9.2 线性表的查找
9.2.1 顺序查找
9.2.2 折半查找
9.2.3 斐波那契查找
9.3 线性索引结构
9.3.1 线性稠密索引
9.3.2 分块索引
9.4 二叉排序树
9.4.1 二叉排序树的概念
9.4.2 二叉排序树的查找
9.4.3 二叉排序树的插入
9.4.4 二叉排序树的删除
9.4.5 二叉排序树的查找性能分析
9.5 平衡二叉树
9.5.1 平衡二叉树的概念和基本旋转操作
9.5.2 平衡二叉树的平衡旋转
9.5.3 在平衡二叉树上插入元素
9.6 B树
9.6.1 B树的基本概念和查找操作
9.6.2 B树的插入操作
9.6.3 B树的删除操作
9.6.4 B+树的基本概念
9.7 键树
9.8 散列表
9.8.1 散列表的基本概念
9.8.2 散列函数的构造方法
9.8.3 处理冲突的方法
9.8.4 散列表的查找方法
9.9 习题

第10章 排序
10.1 排序的基本概念
10.2 插入排序
10.2.1 直接插入排序
10.2.2 折半插入排序
10.2.3 表插入排序
10.2.4 希尔排序
10.3 交换排序
10.3.1 冒泡排序
10.3.2 快速排序
10.4 选择排序
10.4.1 简单选择排序
10.4.2 树形选择排序
10.4.3 堆排序
10.5 归并排序
10.6 基数排序
10.6.1 多关键字排序
10.6.2 链式基数排序
10.7 各种内部排序方法的性能比较
10.8 外部排序
10.8.1 外部排序过程
10.8.2 多路平衡归并
10.8.3 使用置换－选择排序生成初始归并段
10.8.4 最佳归并树
10.9 习题

第11章 文件
11.1 文件概述
11.2 顺序文件
11.3 索引文件
11.4 散列文件
11.5 多关键字文件
11.6 习题
参考文献
……
序言 “数据结构”是计算机及相关专业的一门重要的专业基础课，也是部分理工科专业的选修课程。数据结构课程的主要任务是，研究现实世界中各种数据对象的逻辑结构在计算机中的存储表示以及在不同存储结构上的相应算法，初步掌握算法的时间分析技术和空间分析技术，并通过实际编程训练为开发复杂程序打下良好基础。
数据结构广泛应用于计算机的各个领域。在计算机操作系统、计算机图形学、软件工程、多媒体技术、计算机网络、编译原理、数据库原理和技术、计算机辅助设计、人工智能等课程中普遍使用数据结构的理论和方法来描述和解决问题。因此，学好数据结构课程是学好其他后续计算机课程，特别是计算机软件方面课程的基础，同时也为今后走上工作岗位从事大型计算机软件开发奠定了基础。
本书共分11章。第1章主要介绍数据结构的基本概念和相关术语，并简单介绍了进行算法描述和算法分析的基本方法；第2～5章介绍线性结构（线性表、栈、队列、数组、串）的逻辑特征，存储表示方法和基本操作的实现算法，以及一些应用实例；第6～8章介绍非线性结构（广义表、树、图）的逻辑特征，存储表示方法和基本操作的实现算法，以及应用实例；第9章和第10章分别介绍非数值计算领域中的两种非常重要的操作，即查找和排序；’第11章介绍一些常用文件的逻辑结构和物理结构特征。各章内容都有相对独立的部分，以便针对不同专业或不同层次的需要组织教学。
本书采用简化的c++程序设计语言作为算法的描述语言，与目前多数学校采用c++语言作为教学语言相衔接。但考虑到本书的学习对象主要是低年级学生，因此除了使用类模板描述数据类型以外，只使用了c++相对简单的内容来描述算法，以便于学生理解和接受。
本书的所有算法都已在VC++6.0环境下上机调试通过，但为了节省篇幅，所有算法都以函数形式给出。若读者要运行这些算法，除了需要编写主函数来调用它们以外，还必须包含头文件和添加必要的变量说明。本书选用的例题都针对特定的数据结构，便于学生学习使用数据结构原理解决实际问题的方法。
本书建议理论讲授50～60个学时，上机实践20～30个学时。在实际教学过程中，授课教师可以根据学生的专业特点和不同层次进行适当增删。
由于作者水平有限，书中难免有不妥之处，敬请读者批评指正。
文摘 插图：


第1章 绪论
随着计算机产业的发展，特别是计算机技术的高速发展和微型计算机的日益普及，计算机系统无论在硬件方面，还是在软件方面都远远超过了人们对它的预料，它已广泛渗透到人类社会的各个领域。现在的计算机已不再局限于处理纯数值计算问题，而更多地用于控制、管理以及数据处理等领域。与此相对应，计算机处理的对象也由纯粹的数值发展到诸如字符、表格、声音、图像、视频等复杂且具有结构的非数值数据。因此，在相应程序的设计过程中，必须研究数据的特性和数据之间存在的内在关系，才能设计出优良的程序，这正是学习本课程的基本目的。“数据结构”是一门综合性的计算机专业基础课，是介于数学、计算机硬件和计算机软件之问的一门核心课程，其内容不仅是一般程序设计（特别是非数值计算程序设计）的基础，而且是设计编译程序、操作系统、数据库系统以及其他复杂程序的重要基础。
1.1 数据结构的研究内容
一般来说，使用计算机解决问题大致需要以下几个步骤：首先从具体问题中抽象出一个适当的数学模型，然后设计一个解此数学模型的算法，最后编写出程序，进行测试和修改，直至得到最终解答。在解决问题的过程中，寻求数学模型的实质是通过分析，从问题中提取操作的对象，并找到这些对象之间的关系，然后用数学语言加以描述。然而，对非数值计算问题，往往很难用一个或几个数学方程来描述对象之间的关系，只能采用数据结构方法进行描述。