数据结构
2009-9
水利水电出版社
陆勤
269
455000
数据结构是一门讨论“描述现实世界实体的数学模型（非数值计算）及其上的操作在计算机中如何表示和实现”的学科。随着计算机硬件、软件技术的飞速发展和计算机系统在各行业的广泛应用，有关数据结构的理论和技术也成为了计算机应用技术教育的重要部分。 数据结构是计算机技术应用方面的主要基础课程之一，它引导学生学会从实际应用问题入手，分析研究计算机加工的数据结构的特性，以便为应用所涉及的数据选择适当的逻辑结构、存储结构及其相应的操作算法，并初步掌握算法的时间和空间分析技术。另一方面，本课程的学习过程也是进行复杂程序设计、调试并排除错误的训练过程，要求学生编写的程序代码结构清晰、正确易读，具有良好的可维护性。 本书按照非计算机专业计算机课程基本要求中所规定的数据结构课程的教学内容，并参考教育部制定的计算机基础教学主要课程教学大纲编写。全书共分9章。第1章介绍数据结构的基本概念和算法描述及分析。第2章至第7章分别介绍线性表、栈和队列、字符串、数组与特殊矩阵、树、图的多种存储结构和典型算法应用示例。第8章介绍了线性表的查找、查找树、哈希表查找（杂凑法）方法。第9章介绍了插入排序、交换排序、选择排序、二路归并排序、基数排序等多种排序算法。 本书可用作高等学校非计算机专业本科学生数据结构课程的教材，旨在培养学生运用数据结构的基本概念和方法解决实际问题的能力。一般情况下，课堂讲授学时数应安排为40～60学时，集体卜机实践时间应安排为30学时，可根据具体条件适当增减教学内容和学时数。多上机实践是学好本书内容的捷径，希望读者通过学习本书尽快掌握数据结构的基本应用技能。 本书由陆勤主编，特别感谢国防科学技术大学邹逢兴教授对本书的出版所给予的巨大帮助。此外，作者参阅了国内外一些有关数据结构的教材、书籍，受益匪浅。在此，谨向这些教材、书籍的作者表示感谢。 由于时问仓促及作者水平有限，书中难免存在错误或不当之处，敬请广大读者批评指正。
本书系统地阐述了基本数据结构的多种存储结构和典型算法，以及应用数据结构理论解决实际问题的基本方法和技巧，努力使读者牢固掌握数据结构的理论，培养灵活运用并巧妙解决具体问题的能力，为读者今后进一步地深入学习实践打下坚实基础。 全书内容严谨、编排合理、文字流畅、示例典型、实用性强，书中的程序均已在MicrosoftVisual c++6.0系统下编译运行。全书共分9章。第l章介绍数据结构的基本概念和算法描述及分析。第2章至第7章分别介绍线性表、栈和队列、字符串、数组与特殊矩阵、树、图的多种存储结构和典型算法应用示例。第8章介绍了线性表的查找、查找树、哈希表查找（杂凑法）方法。第9章介绍了插入排序、交换排序、选择排序、二路归并排序、基数排序等多种排序算法。 本书可用作高等学校非计算机专业本科学生数据结构课程的教材。
总序前言第1章 绪论 1.1 数据结构讨论的范畴 1.2 数据结构的基本概念 1.2.1 基本术语 1.2.2 数据结构 1.2.3 数据类型和抽象数据类型 1.3 算法及其描述和分析 1.3.1 算法的特性及其设计原则 1.3.2 算法的描述 1.3.3 算法分析 思考题与习题第2章 线性表 2.1 线性表的定义和基本运算 2.2 线性表的顺序存储结构 2.2.1 顺序存储结构 2.2.2 顺序表的基本操作及其时间效率分析 2.3 线性表的链式存储结构 2.3.1 单链表及其基本操作 2.3.2 特殊链表 2.4 线性表的应用示例——多项式的代数运算 思考题与习题第3章 栈和队列 3.1 栈 3.1.1 栈的定义及其运算 3.1.2 顺序栈 3.1.3 多栈共享邻接空间 3.1.4 链栈 3.1.5 栈的应用举例 3.2 队列(queue) 3.2.1 队列的定义及其运算 3.2.2 队列的顺序存储结构 3.2.3 队列的链式存储结构 3.2.4 循环队列 3.2.5 队列的应用举例 思考题与习题第4章 字符串 4.1 串的概念 4.1.1 串的定义 4.1.2 主串和子串 4.2 串的存储结构 4.2.1 串的静态存储结构 4.2.2 串的动态存储结构 4.3 求子串运算 4.4 串的模式匹配 4.4.1 串的模式匹配的简单算法 4.4.2 模式匹配的改进算法——KMP算法 思考题与习题第5章 数组与特殊矩阵 5.1 数组的概念 5.2 静态数组与动态数组 5.3 特殊矩阵及其压缩存储 5.3.1 特殊矩阵 5.3.2 特殊矩阵的压缩存储 5.4 稀疏矩阵 5.4.1 三元组顺序表 5.4.2 行逻辑链接的顺序表 5.4.3 十字链表 思考题与习题第6章 树 6.1 基本概念 6.1.1 树的定义和有关术语 6.1.2 二叉树 6.2 二叉树的存储 6.2.1 顺序存储结构 6.2.2 链式存储结构 6.3 二叉树的抽象数据类型 6.4 二叉树的遍历 6.4.1 二叉树的遍历方法 6.4.2 二又树的遍历算法 6.4.3 树、森林和二又树的转换 6.5 二叉树的构造 6.5.1 用中序序列和先序序列构造二叉树 6.5.2 用扩充先序序列构造二义树 6.6 线索二叉树 6.6.1 线索二叉树的定义及结构 6.6.2 线索二叉树的操作 6.7 树的存储结构 6.8 树和森林的遍历 6.8.1 树的遍历 6.8.2 森林的遍历 6.9 哈夫曼树 6.9.1 哈夫曼树算法 6.9.2 哈夫曼树在编码问题中的应用 思考题与习题第7章 图 7.1 基本概念 7.1.1 图的定义 7.1.2 有关术语 7.2 图的存储方法 7.2.1 邻接矩阵及其顺序存储 7.2.2 邻接表 7.2.3 十字链表 7.2.4 邻接多重表 7.3 图的遍历 7.3.1 深度优先搜索 7.3.2 广度优先搜索 7.4 最小生成树 7.4.1 最小生成树的基本概念 7.4.2 构造最小生成树的普里姆(Prim)方法 7.4.3 构造最小生成树的克鲁斯卡尔(Kruskal)算法 7.5 最短路径 7.5.1 单源点最短路径 7.5.2 每一对顶点之间的最短路径 7.6 有向无环图及其应用 7.6.1 AOV网与拓扑排序 7.6.2 AOE网与关键路径 思考题与习题第8章 查找 8.1 基本概念与术语 8.2 线性表的查找 8.2.1 顺序查找 8.2.2 顺序表的折半查找 8.2.3 分块查找 8.3 查找树 8.3.1 二叉查找树 8.3.2 平衡二叉树(AVL树) 8.3.3 B-树和B+树 8.4 哈希表查找(杂凑法) 8.4.1 哈希表与哈希方法 8.4.2 哈希函数的构造方法 8.4.3 处理冲突方法 8.4.4 哈希表中查找和插入算法的实现 8.4.5 哈希表的查找算法分析 思考题与习题第9章 排序 9.1 基本概念 9.2 插入排序 9.2.1 直接插入排序 9.2.2 二分法插入排序 9.2.3 表插入排序 9.2.4 希尔排序(Shell's Sort) 9.3 交换排序 9.3.1 冒泡排序(Bubble Sott) 9.3.2 快速排序 9.4 选择排序 9.4.1 简单选择排序 9.4.2 树形选择排序 9.4.3 堆排序(Heap Sort) 9.5 二路归并排序 9.6 基数排序 9.6.1 多关键字排序 9.6.2 链式基数排序 思考题与习题参考文献
2.结点 用于描述一个独立事物的名称、数量、特征、性质的一组相关信息组成一个数据结点，简称结点（node）。结点也称数据元素（data element），是组成数据的基本单位。在程序中通常把结点作为一个整体进行考虑和处理。例如，在表1.1所示的学生数据中，为了便于处理，把其中的每一行（代表一名学生的信息）作为一个基本单位来考虑，故该数据由10个结点构成。 一般情况下，一个结点中含有若干个字段（也叫数据项）。例如，在表1.1 所示的表格数据中，每个结点都由学号、姓名、课程、成绩4个字段构成。字段是构成数据的最小单位。 3. 关键字 每个数据项叫做结点的一个域（field），唯一标识结点的一组域称为关键字（key）。例如，在设计处理上述学生成绩的程序时，每个学生的数据结点均包括学生的学号、姓名、课程、成绩等，学号和课程可以作为结点的关键字，用以唯一标识学生信息。 4. 逻辑结构 类型相同、内容相关的众多结点构成一个结点集合。结点集合中结点和结点之间的逻辑关系称为数据的逻辑结构。在表1-1所示的表格数据中，各结点之间在逻辑上有一种线性关系，它指出了10个结点在表中的排列顺序。根据这种线性关系，可以处理表中第1位学生的信息、第2位学生的信息……等等。 5. 存储结构 数据在计算机中的存储表示和实现称为数据的存储结构或物理结构，也称存储表示。在存储结点集合时，除了存储数据结点外，还必须体现出结点之间的关系。表1-l所示的表格数据在计算机中可以有多种存储表示，例如，可以表示成数组，存放在内存中；也可以表示成文件，存放在磁盘上。 用来存储一个数据结点，以及该结点与其他结点之间关系的存储单元称为存储结点。因为一个数据结点对应一个存储结点，所以，在不致混淆时，存储结点也简称为结点。尚未存储数据的存储结点称为空白结点（或空结点、自由结点）。6.数据处理数据处理是指利用程序对数据进行查找、插入、删除、合并、排序、统计以及计算等操作。数据结构重点研究各种数据通常需要进行哪些操作，如何设计完成相应的算法，从而提高程序运行效率。
新世纪电子信息与自动化系列课程改革教材。 名师策划，名师主理，教改结晶，教材精品。
