本书围绕简明、易学、易用的原则来编写,在系统地介绍各种数据类型的数据结构的基础上,进行应用实例分析与c语言描述实现,示例程序很容易地利用Visual C++或TC等开发环境实现,较全面地把数据结构的理论与实践结合起来。全书共9章,包括绪论、线性表、栈和队列、串、数组和广义表、树、图、查找、排序等内容。教材中除详细的应用实例外,各章又配备了适量的习题,以便于读者理解和掌握数据结构的基本理论和方法。
本书可作为各类大专院校的计算机科学与技术和信息类相关专业的教材或学习参考书。本书要求读者熟悉C或C++语言。
“数据结构”是计算机科学与技术、通信和信息工程等专业的一门重要的专业技术基础课程。本教程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法;介绍了常用的多种查找和排序技术,并对其进行了性能分析和比较,内容非常丰富。在计算机科学中,数据结构不仅是一般程序设计(特别是非数值计算的程序设计)的基础,而且是设计和实现编译程序、操作系统、数据系统及其他系统程序和大型应用程序的重要基础,本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。因此,数据结构课程是计算机专业的一门核心的关键性课程。
第1章 绪论
1.1 数据结构的研究内容和作用
1.2 数据结构相关的基本概念
1.2.1 基本概念
1.2.2 数据结构
1.3 算法及其描述和分析
1.3.1 算法及其设计原则
1.3.2 算法的描述
1.3.3 算法效率的衡量方法
1.3.4 算法的存储空间需求
习题1
第2章 线性表
2.1 线性表的逻辑结构
2.1.1 线性表的定义
2.1.2 线性表的基本操作
2.2 线性表的顺序表示及其实现
2.2.1 顺序表
2.2.2 顺序表上的基本操作实现
2.2.3 顺序表应用举例
2.3 线性表的链式表示及其实现
2.3.1 单链表
2.3.2 单链表基本运算及其实现
2.3.3 循环链表
2.3.4 双向链表
2.3.5 静态链表
2.4 一元多项式的表示
2.5 线性表的应用举例
习题2
第3章 栈和队列
3.1 栈
3.1.1 栈的定义及基本运算
3.1.2 栈的存储与操作实现
3.1.3 栈的应用举例
3.2 队列
3.2.1 队列的定义及基本运算
3.2.2 队列的存储表示和操作的实现
3.2.3 队列应用举例
习题3
第4章 串
4.1 串的定义、表示和实现
4.1.1 串的基本概念
4.1.2 串的基本操作
4.2 串的存储和基本运算实现
4.2.1 串的定长顺序存储与基本运算实现
4.2.2串的堆存储与基本运算实现
4.2.3 串的块链存储与基本运算实现
4.3 串的模式匹配
4.3.1 简单模式匹配算法
4.3.2 改进的模式匹配算法
4.4 串的应用举例
习题4
第5章 数组和广义表
5.1 数组
5.1.1 数组的定义
5.1.2 数组的顺序存储结构
5.2 特殊矩阵的压缩存储
5.2.1 对称矩阵
5.2.2 下(上)三角矩阵
5.2.3 对角矩阵
5.3 稀疏矩阵的压缩存储
5.3.1 稀疏矩阵定义
5.3.2 稀疏矩阵的压缩存储方法——三元组表
5.3.3 稀疏矩阵的压缩存储方法——十字链存储法
5.4 广义表
5.4.1 广义表的概念和基本操作
5.4.2 广义表的存储结构
5.4.3 广义表基本操作的实现
习题5
第6章 树和二叉树
6.1 树的类型定义
6.2 二叉树
6.2.1 二叉树的类型定义
6.2.2 二叉树的几个特性
6.2.3 二叉树的基本操作
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.5.3 线索链表的生成
6.6 树和森林
6.6.1 树的存储结构
6.6.2 树、森林与二叉树的相互转换
6.6.3 树、森林的遍历
6.6.4 应用举例
6.7 哈夫曼树及其应用
6.7.1 最优二叉树的定义
6.7.2 最优二叉树的构造方法
6.7.3 最优前缀编码
6.7.4 哈夫曼编码算法的实现
习题6
第7章 图
7.1 图的基本概念
7.1.1 图的定义和术语
7.1.2 图的基本操作
7.2 图的存储结构
7.2.1 邻接矩阵
7.2.2 邻接表
7.3 图的遍历
7.3.1 深度优先遍历
7.3.2 广度优先遍历
7.4 图的连通性
7.4.1 图的连通性及其判定
7.4.2 生成树与最小生成树
7.5 有向无环图及其应用
7.5.1 有向无环图的概念
7.5.2 AOV网与拓扑排序
7.5.3 AOE网与关键路径
7.6 最短路径
7.6.1 求某一顶点到其余各顶点的最短路径
7.6.2 求任意一对顶点之间的最短路径
7.7 应用举例
习题7
第8章 查找
8.1 静态查找表
8.1.1 顺序查找
8.1.2 有序表的折半查找
8.1.3 分块查找
8.2 动态查找表
8.2.1 二叉排序树
8.2.2 平衡二叉树
8.2.3 B-树和B+树
8.3 哈希表
8.3.1 哈希表与哈希方法
8.3.2 常用的哈希函数
8.3.3 处理冲突的方法
8.3.4 哈希表的查找分析
习题8
第9章 排序
9.1 内排序算法
9.1.1 插入排序
9.1.2 交换排序
9.1.3 选择排序
9.1.4 二路归并排序
9.1.5 基数排序
9.2 外排序算法
习题9
参考文献