数据结构

出版时间：2012-2  出版社：清华大学出版社  作者：陈宝平 编  

前言

　　数据结构是计算机专业和信息管理专业一门重要的专业基础课，只要涉及程序的地方，均要用到数据结构的知识，许多课程（如操作系统、编译原理、数据库和人工智能等）也要用到数据结构的知识。其主要内容是研究和解决非数值计算的问题，讨论如何合理地组织、存储和处理数据的方法与技术； 其主要任务是使读者掌握数据组织、存储和处理的常用方法和常用的算法思想及在实际中的应用技巧，为今后学习后续专业课和进行软件开发打下良好的基础。　　本书的编写者长期从事数据结构的教学，对课程的难点和重点有比较深切的体会。在总结讲授数据结构课程的基础上，对多年传授的数据结构教学内容进行合理的重组，既强调数据结构的原理和方法，又注重其实践性与实用性。本书希望能够引起读者对数据结构课程的兴趣，提高对数据结构课程的重要性、必要性的认识，特别希望能够提高数据结构课程的教学实效，让读者满意并有收获。　　本书详细介绍了各种基本的数据结构，包括线性结构、数组和广义表、树（层次）结构和图结构； 基本的存储结构，包括顺序（数组）结构、链接结构、索引结构和散列结构，以及其中的一种或多种结构的组合及应用。本书具有以下特色：　　（1） 采用C++版，注重面向对象的编程，强调算法的逻辑性、严谨性、技巧性以及时间复杂度等，弱化C++语言中的继承、派生等机制。　　（2） 本着“加强基础，注重算法，因材施教，案例驱动”的教育理念，在算法的设计上做了大胆改革，为了更好地理解理论知识，每章之后都配有应用实例，提倡从实用性和实践性的角度学习数据结构。　　（3） 完全包含2011年计算机统考大纲中数据结构指定的相关知识点。　　（4） 通俗易懂、图文并茂，详略得当，便于从事计算机工作的人员自学。　　本书第1，5，10章及所有的课后习题由阿雅娜编写，第2，3，4章由张巨萍编写，第6，8章由陈宝平编写，第7，9章由孙宝军编写。陈宝平对全书的文字风格、内容、算法实现等方面进行了细致的修改和统稿。作者在此对赵俊岚教授、乔晓华教授和王彪教授表示衷心的感谢，他们对此书提出的建议和意见都弥足可贵。同时感谢王景龙、魏娜、李泽申等同学，仔细阅读本书的预印版，验证了书稿的部分算法并调试了代码。　　本书力求以通俗的语言和实例描述数据结构课程的内容。实例丰富，图表清晰，深入浅出，易于读者融会贯通。根据C++的特点设计与实现了各种数据结构的存储结构和算法，有助于读者进一步掌握C++的编程思想、方法和技术内涵。　　由于编者水平有限，书中错误和不妥之处在所难免，恳请读者与同行批评指正。　　陈宝平

内容概要

　　数据结构是计算机专业教学计划中的核心课程，也是计算机及相关专业考研和水平等级考试的必考科目。要从事和计算机科学与技术相关的工作，尤其是计算机应用领域的开发和研制工作，必须具备坚实的数据结构基础。《21世纪高等学校规划教材·计算机科学与技术：数据结构（C++版）》介绍了学习数据结构所用到的预备知识，叙述了数据结构、算法以及抽象数据类型的概念，介绍了线性表、栈、队列和串、数组和广义表、树和二叉树、图等常用数据结构，讨论了常用的查找、排序和索引技术。　　《21世纪高等学校规划教材·计算机科学与技术：数据结构（C++版）》内容丰富，层次清晰，讲解深入浅出，可作为计算机及相关专业本专科数据结构课程的教材，也可供从事计算机软件开发和应用的工程技术人员阅读、参考。

书籍目录

第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 算法效率的量度1.3.4 算法的设计方式习题第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.4 一元多项式求和2.4.1 一元多项式的表示2.4.2 一元多项式的求和习题第3章 栈和队列3.1 栈3.1.1 栈的抽象数据类型定义3.1.2 栈的实现3.2 栈的应用举例3.3 栈与递归3.4 队列3.4.1 队列的抽象数据类型定义3.4.2 队列的实现3.4.3 队列的应用习题第4章 串4.1 串类型的定义4.2 串的存储结构4.2.1 串的顺序存储结构4.2.2 堆分配存储表示4.2.3 串的块链存储表示4.3 串的模式匹配算法4.3.1 求子串的定位函数4.3.2 模式匹配的一种改进算法4.4 串的应用习题第5章 数组和广义表5.1 数组5.1.1 数组的定义5.1.2 数组的存储5.1.3 特殊矩阵5.1.4 稀疏矩阵5.2 广义表5.2.1 广义表的定义5.2.2 广义表的存储结构5.2.3 广义表的递归算法5.2.4 广义表的应用习题第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.5 树与森林6.5.1 树的存储表示6.5.2 森林与二叉树的转换6.5.3 树的遍历6.5.4 森林的遍历6.6 树的应用6.6.1 堆6.6.2 哈夫曼树与编码习题第7章 集合与搜索7.1 集合及其表示7.1.1 集合的定义7.1.2 集合的抽象数据类型7.1.3 用位向量实现集合7.2 静态搜索结构7.2.1 搜索的定义7.2.2 静态搜索结构7.2.3 顺序搜索7.2.4 基于有序顺序表的折半搜索7.2.5 分块搜索7.3 二叉搜索树7.3.1 二叉搜索树的定义7.3.2 二叉搜索树的搜索7.3.3 二叉搜索树的插入7.3.4 二叉搜索树的建立7.3.5 二叉搜索树的删除7.4 AVL树7.4.1 AVL树的定义7.4.2 最小不平衡二叉树7.4.3 不平衡二叉树的调整方法7.4.4 建立平衡二叉树举例7.5 应用举例计算机登录验证习题第8章 图8.1 图的定义8.1.1 图的定义与相关术语8.1.2 图的抽象数据类型8.2 图的存储结构8.2.1 数组表示法8.2.2 邻接表表示法8.2.3 邻接多重表表示法8.2.4 十字链表法8.3 图的遍历8.3.1 深度优先遍历8.3.2 广度优先遍历8.4 图的最小生成树8.4.1 Prim算法8.4.2 Kruskal算法8.5 最短路径8.5.1 单源最短路径8.5.2 每对顶点的最短路径8.6 拓扑排序8.7 关键路径8.8 应用实例习题第9章 排序9.1 概述9.2 插入排序9.2.1 直接插入排序9.2.2 折半插入排序9.2.3 希尔排序9.3 交换排序9.3.1 冒泡排序9.3.2 快速排序9.4 选择排序9.4.1 直接选择排序9.4.2 堆排序9.5 归并排序9.5.1 归并排序概述9.5.2 递归的归并排序算法9.6 基数排序9.6.1 多关键码排序9.6.2 链式基数排序9.7 各种排序方法的比较讨论9.8 外部排序的方法习题第10章 索引结构和散列10.1 静态索引结构10.1.1 线性索引10.1.2 倒排表10.1.3 m路静态索引树10.2 动态索引结构10.2.1 动态的m路静态索引树10.2.2 B_树10.2.3 B_树的插入10.2.4 B_树的删除10.2.5 B+树10.3 散列10.3.1 散列函数10.3.2 开散列方法10.3.3 闭散列方法10.3.4 散列表的实现10.3.5 散列表分析习题参考文献