数据结构

章节摘录

插图：

前言

我们生活在一个物质世界中，同时又时刻面对着一个数字的世界。如果将物质世界中的事与物数字化，那么它们在计算机中均表现为数据。这些数据来源于现实，具有具体的含义，而且在计算机中有着统一的表示方法，因而成为计算机程序处理的符号集合。研究数据在计算机中的表示方法、关联方法、存储方法以及典型处理方法，正是数据结构课程的主要内容。早在20ff纪80年代初，“数据结构”就已成为国内高校计算机专业教学计划中的核心课程。目前，ACM／IEEE计算学科课程计划（CC．2001）已将算法与数据结构类课程列为核心课程之首，数据结构愈益显现出其在信息学科理论中的重要地位。在软件系统的开发过程中，数据结构的思维方法在本质上不同于常规数学训练的公理系统思维方法，而是一种算法构造性思维方法。所谓构造性思维方法就是要让学生理解、习惯并掌握算法的一种思维方法，也是本门课程教学的重要内容和主要难点。要成为专业的软件开发人员，仅仅知道开发工具的语言规则和简单使用过程是远远不够的，只有培养自身的数据抽象能力、算法设计能力，掌握创造性思维方法，举一反三，触类旁通，才能够具备应用知识解决复杂问题的能力。本书是作者根据多年的教学经验，结合当前计算机科学技术的发展，并参考了众多的数据结构教材编著而成的。书中采用了能够自然体现抽象数据类型概念的c++语言作为算法描述语言，内容覆盖了数据结构课程的教学大纲，从数据类型角度系统地介绍了各种数据结构的逻辑特性、存储表示方法及基本操作算法，并针对常用的数据结构进一步讨论了各种应用算法及其实现方法。本书旨在培养学生分析计算机加工数据对象特征的能力，以便在实际操作中选择合适的数据结构和存储结构以及相应的算法，同时帮助学生掌握估算算法时间复杂度和空间复杂度的基本技巧。本书将数据结构的原理和算法分析技术有机地结合在一起，使用了参数化的模板，提高了算法中数据类型的通用性，支持高效的代码重用。书中介绍和分析重点设计思想时，结合了大量图解和具体示例，使读者能够联系实际，掌握数据结构的实质内容。此外，本书还介绍了一些比较高级的数据结构及相关的算法分析技术。

内容概要

余腊生，中南大学副教授。主讲计算机专业本科“数据结构”和“计算机系统结构”课程以及研究生“软件构件技术”课程多年，其中“数据结构”课程被评为“中南大学精品课程”。主持和参加了包括国家863应用示范工程和湖南省自然科学基金项目在内的10多个科研项目，在国内外专业核心刊物发表论文30多篇，EI检索多篇。主要研究方向为Agent理论及其计算技术、结构与算法、网络数据库技术等。

书籍目录

第1章　绪论   　1.1　数据结构的概念   　　1.1.1　为什么要学习数据结构   　　1.1.2　相关概念和术语   　1.2　抽象数据类型   　　1.2.1　数据类型   　　1.2.2　抽象数据类型   　1.3　算法和算法分析  　　1.3.1　问题求解概述  　　1.3.2　算法特性  　　1.3.3　常见的算法类型  　　1.3.4　算法描述  　　1.3.5　算法性能分析与度量  　习题  　实习题  第2章　线性表  　2.1　线性表的逻辑结构  　　2.1.1　线性表的定义  　　2.1.2　线性表的基本操作  　2.2　线性表的顺序存储及操作实现  　　2.2.1　顺序表  　　2.2.2　顺序表上基本操作的实现  　　2.2.3　顺序表应用举例  　　2.2.4　小结  　2.3　线性表的链式存储及操作实现  　　2.3.1　单向链表  　　2.3.2　单向链表上基本操作的实现  　　2.3.3　循环链表  　　2.3.4　双向链表  　　2.3.5　静态链表  　　2.3.6　单向链表应用举例  　2.4　顺序表和链表的选取  　习题  　实习题  第3章　栈和队列  　3.1　栈  　　3.1.1　栈的定义及基本操作  　　3.1.2　栈的存储及操作实现  　　3.1.3　栈应用举例  　3.2　队列  　　3.2.1　队列的定义及基本操作  　　3.2.2　队列的存储及操作实现  　　3.2.3　优先队列  　　3.2.4　双端队列  　　3.2.5　队列应用举例  　习题  　实习题  第4章　递归和广义表  　4.1　何谓递归  　4.2　递归的执行过程  　4.3　尾部递归函数  　4.4　递归的应用  　　4.4.1　汉诺塔问题  　　4.4.2　迷宫问题  　　4.4.3　n皇后问题  　4.5　递归程序到非递归程序的转换  　　4.5.1　简单转换  　　4.5.2　复杂转换  　　4.5.3　转化的形式化步骤  　4.6　广义表 　　4.6.1　广义表的定义及基本操作 　　4.6.2　广义表的存储 　　4.6.3　广义表有关操作的实现 　习题 　实习题 第5章　字符串 　5.1　字符串及其基本操作 　　5.1.1　字符串的基本概念 　　5.1.2　字符串的基本操作 　5.2　字符串的定长顺序存储及基本操作 　　5.2.1　字符串的定长顺序存储 　　5.2.2　定长顺序串的基本操作 　　5.2.3　模式匹配 　5.3　字符串的堆存储 　　5.3.1　字符串名的存储映像 　　5.3.2　堆存储结构 　　5.3.3　基于堆存储结构的基本操作 　5.4　字符串的链式存储 　5.5　字符串的应用 　　5.5.1　中文分词 　　5.5.2　遗传算法 　习题 　实习题 第6章　数组与矩阵 　6.1　数组 　　6.1.1　数组的逻辑结构 　　6.1.2　数组的内存映像 　6.2　特殊矩阵的压缩存储 　　6.2.1　对角矩阵 　　6.2.2　三对角矩阵 　　6.2.3　三角矩阵 　　6.2.4　对称矩阵 　6.3　稀疏矩阵 　　6.3.1　稀疏矩阵的三元组表存储 　　6.3.2　稀疏矩阵的链式存储 　　6.3.3　稀疏矩阵的十字链表存储 　习题 　实习题 第7章　树与二叉树 　7.1　树的定义及表示 　　7.1.1　树的定义 　　7.1.2　树的表示 　　7.1.3　树的特点 　　7.1.4　与树相关的基本术语 　　7.1.5　树形结构的逻辑特征 　　7.1.6　树的存储 　7.2　二叉树 　　7.2.1　二叉树的定义及相关概念 　　7.2.2　二叉树的主要性质 　　7.2.3　二叉树的存储 　　7.2.4　二叉树的基本操作及实现 　7.3　二叉树的遍历 　　7.3.1　二叉树的遍历方法及递归实现 　　7.3.2　二叉树遍历的非递归实现 　　7.3.3　遍历算法应用举例 　　7.3.4　由遍历序列恢复二叉树 　　7.3.5　不用栈的二叉树遍历非递归方法 　7.4　线索二叉树 　　7.4.1　线索二叉树的定义及结构 　　7.4.2　线索二叉树的基本操作及实现 　7.5　最优二叉树——赫夫曼树 　　7.5.1　赫夫曼树的基本概念 　　7.5.2　赫夫曼树的构造算法 　　7.5.3　赫夫曼树的应用 　7.6　树、森林与二叉树的转换 　　7.6.1　树、森林到二叉树的转换 　　7.6.2　二叉树到树和森林的转换 　7.7　树和森林的遍历 　　7.7.1　树的遍历 　　7.7.2　森林的遍历 　　7.7.3　树和森林的层次次序遍历 　7.8　树的应用 　　7.8.1　判定树 　　7.8.2　集合的表示 　习题 　实习题 第8章　图 　8.1　基本概念 　　8.1.1　图的定义和术语 　　8.1.2　图的抽象数据类型 　8.2　图的存储结构 　　8.2.1　邻接矩阵 　　8.2.2　邻接表 　　8.2.3　邻接矩阵和邻接表的比较 　　8.2.4　十字链表 　　8.2.5　邻接多重表 　　8.2.6　索引表 　8.3　图的遍历 　　8.3.1　深度优先搜索 　　8.3.2　广度优先搜索 　8.4　图的连通性 　　8.4.1　无向图的连通性 　　8.4.2　有向图的连通性 　　8.4.3　生成树和生成森林 　　8.4.4　关节点和双连通分量 　8.5　最小生成树 　　8.5.1　最小生成树的基本概念 　　8.5.2　Prim算法 　　8.5.3　Kruskal算法 　8.6　最短路径 　　8.6.1　无权最短路径问题 　　8.6.2　从一个源点到其他各顶点的最短路径 　　8.6.3　边上权值为任意值的单源最短路径问题 　　8.6.4　负权最短路径问题 　　8.6.5　每对顶点之间的最短路径 　8.7　DAG及其应用 　　8.7.1　DAG的概念 　　8.7.2　AOV网与拓扑排序 　　8.7.3　AOE图与关键路径 　习题 　实习题 第9章　查找 　9.1　基本概念 　9.2　静态查找表 　　9.2.1　静态查找表结构 　　9.2.2　顺序查找 　　9.2.3　有序表的二分查找 　　9.2.4　有序表的斐波那契查找和插值查找 　　9.2.5　分块查找 　9.3　动态查找表 　　9.3.1　二叉排序树 　　9.3.2　平衡二叉树 　　9.3.3　红黑树 　　9.3.4　B树 　　9.3.5　B+树   9.4　散列表查找 　　9.4.1　散列表与散列方法 　　9.4.2　常用的散列函数 　　9.4.3　处理冲突的方法 　　9.4.4　散列表的查找分析 　　9.4.5　散列表的操作 　习题 　实习题 第10章　排序 　10.1　基本概念 　10.2　插入排序 　　10.2.1　直接插入排序 　　10.2.2　二分插入排序 　　10.2.3　表插入排序 　　10.2.4　谢尔排序 　10.3　交换排序  　　10.3.1　冒泡排序  　　10.3.2　快速排序 　10.4　选择排序 　　10.4.1　线性选择排序 　　10.4.2　交换线性选择排序 　　10.4.3　树形选择排序 　　10.4.4　堆排序 　　10.4.5　用堆实现的优先队列 　10.5　两路归并排序 　10.6　分配排序 　　10.6.1　多键排序 　　10.6.2　桶排序 　　10.6.3　链式基数排序 　10.7　其他排序方法 　　10.7.1　二叉树排序法 　　10.7.2　计数排序法 　10.8　各种内排序方法的比较 　10.9　外排序 　　10.9.1　外排序的方法 　　10.9.2　自然归并排序法 　　10.9.3　k路归并法 　　10.9.4　多段归并法 　习题 　实习题 参考文献 附录　实验指导（图灵网站下载）

编辑推荐

《数据结构基于C++模板类的实现》是作者在多年教学实践的基础上编写而成的，写作中注意借鉴近年出版的多种数据结构领域优秀著作的长处。《数据结构基于C++模板类的实现》采用C++模板类描述算法，强调实践性，深入地阐述了数据结构的基本知识和各种数据结构的具体应用，并比较、分析了每一种数据结构的不同存储方法及其有关算法。内容包括线性表、栈和队列、递归与广义表、串、数组和矩阵、树和二叉树、图、排序和查找等。·大多数算法使用了参数化的模板，支持高效的代码重用。·大量的图解和具体的实例分析使抽象的内容变得具体而且浅显易懂。·对于重点算法给出了富于启发性的问题及讨论。·设计了许多有典型性的习题和实验指导，帮助读者能够学会正确地选择数据结构，编写符合程序规范的代码，为应用程序的开发打下基础。

作者简介

《数据结构基于C++模板类的实现》采用能够自然体现抽象数据类型概念的C++ 语言作为算法描述语言，把数据结构的原理和算法分析技术有机地结合在一起。全书内容包括线性表、栈、队列、递归、广义表、字符串、数组、树、图、查找以及各种排序算法，并给出了相关的实验指导。书中还引入了一些比较高级的数据结构和相关的算法分析技术。

《数据结构基于C++模板类的实现》可作为高等院校计算机或相关专业的教材，也可以作为其他程序类课程的辅导教材，同时也适用准备参加研究生入学考试、自学考试和各类程序设计竞赛的人员阅读。

图书封面

---

 数据结构下载

---