数据结构

第1章 绪论

1.1 数据结构的概念

1.1.1 引言

1.1.2 数据结构有关概念与术语

1.2 抽象数据类型

1.3 算法描述与分析

1.3.1 什么是算法

1.3.2 算法分析技术

1.4 小结

讨论小课堂

习题

第2章 线性表

2.1 线性表的定义及其运算

2.1.1 线性表的定义

2.1.2 线性表的基本操作

2.2 线性表的顺序存储结构及实现

2.2.1 顺序存储结构

2.2.2 线性表在向量中基本运算的实现

2.3 线性表的链表存储结构

2.3.1 单链表

2.3.2 线性链表基本运算的实现

2.4 循环链表和双向链表

2.4.1 循环链表

2.4.2 双向链表

2.4.3 顺序存储结构与链表存储结构的综合分析与比较

2.5 单链表的应用

2.5.1 多项式相加的链表存储结构

2.5.2 多项式相加的算法实现

2.6 小结

讨论小课堂

习题

第3章 栈和队列

3.1 栈

3.1.1 栈的定义

3.1.2 栈的基本操作

3.2 栈的顺序存储结构及实现

3.2.1 栈的顺序存储结构

3.2.2 顺序栈的类定义

3.3 栈的链表存储结构及实现

3.4 栈的应用

3.4.1 表达式的计算

3.4.2 子程序的嵌套调用

3.4.3 递归调用

3.4.4 n阶Hanoi塔问题

3.5 队列

3.5.1 队列的定义及运算

3.5.2 队列的抽象数据类型描述

3.6 队列的顺序存储结构及实现

3.7 队列的链表存储结构及实现

3.8 队列的应用

3.9 小结

讨论小课堂

习题

第4章 串

4.1 串的基本概念

4.1.1 串的定义

4.1.2 串的基本操作

4.2 串的存储与基本操作的实现

4.2.1 定长顺序串

4.2.2 堆串

4.2.3 块链串

4.2.4 串操作的实现

4.3 串的模式匹配

4.3.1 朴素模式匹配算法

4.3.2 模式匹配的KMP算法

4.4 串的应用举例：文本编辑

4.5 小结

讨论小课堂

习题

第5章 数组和广义表

5.1 数组的定义及运算

5.1.1 数组的定义

5.1.2 数组的基本操作

5.2 数组的存储结构

5.3 特殊矩阵的压缩存储

5.3.1 对称矩阵

5.3.2 三角矩阵

5.3.3 对角矩阵

5.4 稀疏矩阵的压缩存储

5.4.1 稀疏矩阵的顺序存储结构——三元组顺序表

5.4.2 稀疏矩阵的链式存储结构

5.5 广义表

5.5.1 广义表的定义和基本运算

5.5.2 广义表的存储

5.6 小结

讨论小课堂

习题

第6章 树与二叉树

6.1 树的概念及术语

6.1.1 树的定义

6.1.2 树的基本操作

6.1.3 树的表示方式

6.2 二叉树

6.2.1 二叉树的定义

6.2.2 二叉树的重要性质

6.2.3 二叉树的存储结构

6.3 二叉树的遍历

6.3.1 先序遍历

6.3.2 中序遍历

6.3.3 后根遍历

6.3.4 按层遍历

6.3.5 非递归遍历算法

6.3.6 二叉树的建立

6.3.7 二叉树遍历的应用举例

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.7 二叉树的应用

6.7.1 哈夫曼树

6.7.2 哈夫曼树的构造

6.7.3 哈夫曼树的实现算法

6.7.4 哈夫曼编码

6.8 小结

讨论小课堂

习题

第7章 图

7.1 图的基本概念

7.1.1 图的定义

7.1.2 图的术语

7.1.3 图的基本操作

7.2 图的存储结构

7.2.1 图的邻接矩阵

7.2.2 邻接矩阵表示法的C语言类型描述

7.2.3 邻接矩阵表示法的基本操作的实现

7.2.4 图的邻接链表

7.2.5 图的邻接表表示法的c语言类型描述

7.2.6 建立图的邻接表函数和输出图的信息函数

7.3 图的遍历与图的连通性

7.3.1 图的深度优先遍历

7.3.2 图的广度优先遍历

7.3.3 非连通图和连通分量

7.4 图的最小生成树

7.4.1 最小生成树的基本概念

7.4.2 普里姆算法

7.4.3 克鲁斯卡尔算法

7.5 最短路径

7.5.1 从某顶点到其余各顶点的最短路径

7.5.2 每对顶点之间的最短路径

……

第8章 查找

第9章 排序

第10章 索引结构与散列

附录 上机实验指导

参考文献

本书系统地介绍了各种数据结构的特点、存储结构及相关算法。书中采用C语言描述算法。主要内容包括：数据结构的基本概念、算法描述和算法分析；线性表、堆栈、队列、串、数组、树、图等结构；查找、排序等。每章后面配有小结、习题和讨论题。最后一章附有完整的实验指导书，每节给出了完整的C语言源程序示例。本书叙述清晰、深入浅出、注重实践环节，便于教学与实践。本书可作为高等院校计算机专业的教材，也可供从事计算机应用与工程工作的科技工作者作为自学参考图书。