数据结构与应用算法

序

前言

教学建议

第一部分 概论

第1章 数据结构

1.1 什么是数据

1.2 什么是数据结构

1.2.1 数据的逻辑结构

1.2.2 数据的存储结构

1.2.3 数据的运算

1.3 什么是数据类型

1.4 知识点小结

习题

第2章 算法

2.1 什么是算法

2.2 算法的描述

2.3 算法分析

2.3.1 时间复杂度

2.3.2 渐近符号

2.3.3 空间复杂度

2.3.4 复杂度分析举例

2.4 知识点小结

习题

第二部分 预备知识

第3章 C语言、递归及存储分配方式

3.1 C语言的相关内容

3.1.1 函数的参数传递与结果返回

3.1.2 结构体类型

3.1.3 指针

3.2 递归

3.3 存储分配方式

3.4 知识点小结

习题

第三部分 线性结构

第4章 线性表

4.1 线性表的类型定义

4.1.1 线性表的逻辑结构

4.1.2 线性表的基本运算

4.2 线性表的顺序存储表示

4.2.1 顺序表

4.2.2 顺序表中基本运算的实现

4.3 线性表的链式存储表示

4.3.1 单链表

4.3.2 单链表中基本运算的实现

4.4 线性表的其他链式存储表示

4.4.1 静态单链表

4.4.2 双(向)链表

4.4.3 循环单(向)链表

4.4.4 循环双(向)链表

4.5 线性表的应用举例

4.6 顺序表和链表的比较

4.7 知识点小结

习题

第5章 栈

5.1 栈的类型定义

5.1.1 栈的逻辑结构

5.1.2 栈的基本运算

5.2 栈的顺序存储表示

5.2.1 顺序栈

5.2.2 顺序栈中基本运算的实现

5.3 栈的链式存储表示

5.3.1 链栈

5.3.2 链栈中基本运算的实现

5.4 两个方向生长的栈

5.5 栈的应用举例

5.6 知识点小结

习题

第6章 队列

6.1 队列的类型定义

6.1.1 队列的逻辑结构

6.1.2 队列的基本运算

6.2 队列的链式存储表示

6.2.1 链队列

6.2.2 链队列中基本运算的实现

6.3 队列的顺序存储表示

6.3.1 顺序队列

6.3.2 循环队列

6.3.3 循环队列中基本运算的实现

6.4 双端队列

6.5 队列的应用举例

6.6 知识点小结

习题

第7章 串

7.1 串的类型定义

7.1.1 串的逻辑结构

7.1.2 串的基本运算

7.2 串的顺序存储表示

7.3 串的堆分配存储表示

7.4 串的块链存储表示

7.5 串的模式匹配

7.6 知识点小结

习题

第8章 数组及广义表

8.1 数组的类型定义

8.1.1 数组的定义

8.1.2 数组的性质

8.1.3 数组的基本运算

8.2 数组的顺序存储表示

8.3 特殊矩阵的压缩存储

8.3.1 特殊形状矩阵的压缩存储

8.3.2 随机稀疏矩阵的压缩存储及其运算

8.4 广义表

8.4.1 广义表的基本概念

8.4.2 广义表的基本运算

8.4.3 广义表的存储结构

8.5 知识点小结

习题

第四部分 非线性结构

第9章 树

9.1 概述

9.1.1 树的定义及基本术语

9.1.2 树的存储结构

9.2 二叉树

9.2.1 二叉树的定义

9.2.2 二叉树的性质

9.2.3 二叉树的存储结构

9.3 二叉树的遍历

9.3.1 遍历操作

9.3.2 先序遍历

9.3.3 中序遍历

9.3.4 后序遍历

9.3.5 层次遍历

9.3.6 二叉树遍历的应用举例

9.4 线索二叉树

9.4.1 二叉树的线索化

9.4.2 线索二叉树上的运算

9.5 二叉树的应用

9.5.1 哈夫曼树及其应用

9.5.2 二叉排序树

9.5.3 平衡二叉树

9.6 树、森林与二叉树的相互转换

9.6.1 树与二叉树的相互转换

9.6.2 森林与二叉树的相互转换

9.7 树、森林的遍历

9.7.1 树的遍历

9.7.2 森林的遍历

9.8 树的应用举例

9.9 知识点小结

习题

第10章 图

10.1 概述

10.1.1 图的定义及基本术语

10.1.2 图的存储结构

10.1.3 图的创建

10.2 图的遍历

10.2.1 深度优先搜索遍历

10.2.2 广度优先搜索遍历

10.2.3 图遍历的应用举例

10.3 生成树

10.3.1 连通图的生成树

10.3.2 连通网的最小生成树

10.4 最短路径

10.4.1 单源最短路径

10.4.2 每对顶点间的最短路径

10.5 有向无环图及其应用

10.5.1 AOV网与拓扑排序

10.5.2 AOE网与关键路径

10.6 知识点小结

习题

第五部分 两种重要运算

第11章 查找

11.1 查找的基本概念

11.2 主要查找方法简介

11.3 静态查找

11.3.1 顺序查找

11.3.2 二分查找

11.3.3 分块查找

11.4 动态查找

11.5 散列查找

11.5.1 散列表的概念

11.5.2 散列函数的构造方法

11.5.3 处理冲突的方法

11.5.4 散列表的查找

11.6 知识点小结

习题

第12章 内排序

12.1 排序的基本概念

12.2 插入排序

12.2.1 直接插入排序

12.2.2 希尔排序

12.3 交换排序

12.3.1 冒泡排序

12.3.2 快速排序

12.4 选择排序

12.4.1 直接选择排序

12.4.2 树形选择排序

12.4.3 堆排序

12.5 归并排序

12.6 分配排序

12.6.1 箱排序

12.6.2 基数排序

12.7 各种内排序法的比较

12.8 知识点小结

习题

第六部分 文件的组织结构及排序

第13章 文件

13.1 文件的基本概念

13.2 顺序文件

13.3 索引文件

13.4 索引顺序文件

13.5 散列文件

13.6 多关键字文件

13.7 知识点小结

习题

第14章 外排序

14.1 多路平衡归并

14.2 置换选择排序

14.3 归并树及最佳归并树

14.4 知识点小结

习题

参考文献

《数据结构及应用：C语言描述》系统地介绍各种常用的数据结构以及排序、查找的各种算法，阐述各种数据结构的逻辑关系、存储表示及运算，涵盖研究生入学考试大纲的所有内容。全书采用c语言作为数据结构和算法的描述语言，并对C语言描述的算法作了详细的注解和简要的性能分析。全书共分为六个部分：第一部分主要介绍什么是数据结构，什么是算法，它们之间有着怎样的联系，如何进行算法分析；第二部分针对后续学习的需要帮助读者温习一些相关知识；第三部分和第四部分分别重点介绍几种常见的线性结构和非线性结构；第五部分介绍在实际应用中最常遇到的两个运算——查找（即搜索）和排序，以及实现这两种运算的各种算法；第六部分则简要介绍文件和外排序的相关内容。 为了帮助读者直观、正确地理解各种数据结构和算法的要旨，《数据结构及应用：C语言描述》利用大量的图表进行诠释，并通过典型的思考题、例题和习题来加深读者对相关知识的理解。 《数据结构及应用：C语言描述》内容丰富、概念清楚、逻辑推理严谨、通俗易懂，可以作为计算机科学与技术及相关专业本科生的教材，也可以作为高等院校计算机专业硕士研究生入学考试的复习用书，同时还可以作为广大工程技术人员的参考资料。

《数据结构及应用：C语言描述》系统地介绍了各种常用的数据结构以及排序、查找的各种算法，阐述了各种数据结构的逻辑关系、存储表示及运算操作，基本涵盖了研究生入学考试大纲的所有内容。基础与应用并重。《数据结构及应用：C语言描述》不仅对什么是数据结构，什么是算法，它们之间有着怎样的联系，如何鉴定一个算法的好坏，数据结构有哪些常用的线性结构和非线性结构，它们各有什么特点和应用，有哪些经典的查找和排序算法等问题进行清晰、全面的阐述，而且关注应用，利用众多实例帮助读者加深对基本知识的理解并灵活运用。图文并茂，生动有趣。《数据结构及应用：C语言描述》为了帮助读者直观、正确地理解各种数据结构和算法的要旨，利用大量的图表进行诠释，以通俗易懂的方式介绍复杂的概念。积极引导，活跃思维。《数据结构及应用：C语言描述》在介绍完重要知识点后会设置一些思考题，引导读者对数据结构的应用进行深入思考和理解，训练读者的发散性思维。读者对象广泛。《数据结构及应用：C语言描述》内容丰富、概念清楚、逻辑推理严谨、通俗易懂，既便于教学，又适合自学，可作为计算机及相关专业本科生的教材，也可作为计算机专业硕士研究生入学考试的复习用书，还可作为广大工程技术人员的参考资料。