数据结构及应用

章节摘录

插图：有用就会有需求，有了需求就会有动力，因此在开始本课程学习之前，我们必须弄清楚一个问题：我们为什么需要学习数据结构？计算机领域分两个大的方向：一个是硬件方向，另一个是软件方向。硬件方向又包括两个大的方面：一个是硬件技术的发展，另一个是如何在现有硬件条件下设计出高性能的计算机系统。软件是程序、数据以及文件的集合，它大致可分为系统软件和应用软件两大类。系统软件追求的是如何在方便用户使用的前提下将计算机系统的性能发挥到极致；应用软件则是直接面对终端用户，它寻求的是更高的服务质量和更好的用户服务体验。我们将从应用软件开发者的视角来探寻数据结构的重要性。实际问题往往很复杂，当我们求解实际问题的时候，往往是对实际问题的模型进行求解。所谓模型就是对实际问题的简化，是反映问题本质的数据集合以及数据之间关系的集合。对模型的求解则是找到对给定的输入数据的一系列处理步骤，使得能够得到预期的输出。为了让计算机实现我们对模型的求解思路，则必须将模型映射到存储器中，这样计算机才能根据人的意图对操作对象（即数据）进行处理。通过上面的分析可知，计算机的各种应用实际上都是对数据的处理，因此对数据以及它们之间的关系进行分析、表示是必不可少的。

前言

在计算机科学中，数据结构是一种在计算机中组织和存储数据，以便高效利用这些数据的有效方式。几乎所有的程序或软件系统都用到了数据结构。数据结构是许多高效算法的基本要素，同时它也使得管理大规模数据成为可能。数据结构课程是计算机科学的一门非常重要的专业基础课，也是IT类各专业的核心基础课。数据结构中的数据和结构是两个紧密联系而又相互关联的概念，数据是数据结构的主要组成部分，它不涉及数据之间的关系；结构才涉及而且只涉及数据之间的关系。从中文构词上来看，数据结构更强调的是结构，即数据之间的关联方式。我们需要将适用于计算机的问题求解策略用计算机能理解的形式输入到计算机中，告诉计算机如何一步一步地处理数据并最终得到问题的解，这就是算法。因此，从抽象层面上讲，数据结构是为算法服务的。不同的应用需求需要不同的算法，不同的算法需要不同的数据结构来支持。从实现层面上讲，数据结构是为算法实现服务的。本书作者具有多年的教学和科研经验，对各种数据结构及应用算法有深入的了解。本书对什么是数据结构，什么是算法，算法和数据结构之间的关系进行了生动的阐述，并对各种线性数据结构、非线性数据结构、查找算法和排序算法等作了详尽的描述和分析。本书基本概念清晰，重点和难点问题讨论深入，而且循序渐进，为读者深入理解和应用数据结构给出了启示。本书既注重对数据结构经典内容的论述，又强调数据结构的应用，对相关内容进行了启发式讨论，是一本值得阅读和选用的教科书。

书籍目录

序前言教学建议第一部分 概论第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语言描述》内容丰富、概念清楚、逻辑推理严谨、通俗易懂，可以作为计算机科学与技术及相关专业本科生的教材，也可以作为高等院校计算机专业硕士研究生入学考试的复习用书，同时还可以作为广大工程技术人员的参考资料。

图书封面

---

 数据结构及应用下载 更多精彩书评

---