数据结构

章节摘录

插图：在本章中介绍了线性表的逻辑结构及其两种存储结构：顺序表和链表。通过讨论可知它们各有优缺点，顺序存储有三个优点：（1）方法简单，各种高级语言中都有数组，容易实现。（2）不用为表示结点间的逻辑关系而增加额外的存储开销。（3）顺序表具有按元素序号随机访问的特点。但它也有两个缺点：（1）在顺序表中作插入删除操作时，平均移动表中一半的元素，因此对较大的顺序表效率低。（2）需要预先分配足够大的存储空间，若分配的空间过大，可能会导致顺序表后部大量闲置；若预先分配过小，又会造成溢出。链表的优缺点恰好与顺序表相反。在实际选取存储结构时通常要考虑以下几点：（1）基于存储的考虑。顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模，也就是说，事先对“MAXSIZE”要有合适的设定，过大造成浪费，过小造成溢出。可见对线性表的长度或存储规模难以估计时，不宜采用顺序表；链表不用事先估计存储规模，但链表的存储密度较低，存储密度是指一个结点中数据元素所占的存储单元和整个结点所占的存储单元之比。显然链式存储结构的存储密度是小于l的。（2）基于运算的考虑。在顺序表中按序号访问的时间性能是O（1），而链表中按序号访问的时间性能是O（n），所以如果经常作的运算是按序号访问数据元素，显然顺序表优于链表；而在顺序表中作插入、删除时，需平均移动表中一半的元素，在链表中作插入、删除，虽然也要找插入位置，但操作主要是比较操作，从这个角度考虑显然后者优于前者。（3）基于环境的考虑。顺序表容易实现，任何高级语言中都有数组类型，链表的操作是基于指针的，相对来讲前者简单些，这也是用户考虑的一个因素。总之，两种存储结构各有长短，选择哪一种由实际问题中的主要因素决定。通常“较稳定”的线性表选择顺序存储，而频繁作插入、删除的即动态性较强的线性表宜选择链式存储。

前言

“数据结构”是计算机专业非常重要的一门主课，是计算机程序设计的理论基础。学好“数据结构”课，将为后续的“数据库原理”、“操作系统”、“编译原理”等专业课程打下良好的专业知识基础，为程序设计人员提供良好的技能训练。  本书共分8章。我们根据多年从事高职高专“数据结构”课程教学工作的经验，我们在教材内容的组织上力求做到“以应用为主体”，对相对较为抽象的概念和一部分难度较大又不常用的数据结构相关知识进行了删减，强调基础理论知识的理解和应用，突出对高职高专类学生应用能力和实际动手能力的培养。本教材有以下几个特点：1.本教材内容丰富，条理清晰，算法简洁，便于学生理解和掌握。2.每章起始均有本章要点和本章难点，使学生在每章学习的起始阶段对该章内容有个基本认识。3.理论知识的介绍由浅入深，通俗易懂，内容组织以应用为教学目标，略去了一部分理论推导和数学证明，对算法的设计分析和时空分析没有提出过高的要求。4.书中所有的算法实现均用c语言编写，并可直接调试运行，使学生便于上机验证各个算法的实现。本书由宋宏图任主编，卢敏和吴林华担任副主编，陈千、陈树祥、刘鲁楣、范渊、张定俊、董淑华、潘修强参加了编写工作。由于作者水平有限，书中不足与错误之处在所难免，敬请读者和专家批评指正。

书籍目录

第1章 绪论1.1 数据结构的基本概念和术语1.1.1 引言1.1.2 数据结构的有关概念和术语1.1.3 数据结构的分类1.1.4 数据结构和抽象数据类型1.2 算法分析1.2.1 算法的定义和要求1.2.2 算法分析技术基础知识习题第2章 线性表2.1 线性表的定义2.2 线性表的基本操作2.3 线性表的顺序存储结构2.3.1 线性表的顺序存储结构2.3.2 顺序表上基本运算的实现2.4 线性表的链式存储结构2.4.1 单链表上的基本运算2.4.2 循环链表2.4.3 双向链表2.5 顺序表和链表的比较2.6 应用举例习题第3章 栈和队列3.1 栈3.1.1 栈的定义和基本操作3.1.2 栈的顺序存储结构3.1.3 栈的链式存储结构3.2 队列3.2.1 队列的定义和基本操作3.2.2 队列的顺序存储结构3.2.3 队列的链式存储结构3.3 应用举例习题第4章 其他线性数据结构4.1 串4.1.1 串的定义和基本操作4.1.2 串的存储结构4.1.3 串的操作实现4.1.4 串的应用——文本编辑基本原理4.2 数组4.2.1 数组的概念4.2.2 数组的顺序表示4.2.3 特殊矩阵的压缩存储4.3 稀疏矩阵4.3.1 稀疏矩阵的压缩存储4.3.2 稀疏矩阵的运算4.3.3 应用举例——稀疏矩阵运算器习题第5章 树5.1 树的定义和基本操作5.1.1 树的定义5.1.2 树的表示方法5.1.3 树的基本操作5.2 二叉树5.2.1 二叉树的定义和基本操作5.2.2 二叉树的性质5.2.3 二叉树的存储结构5.2.4 遍历二叉树5.3 树和森林5.3.1 树的存储结构5.3.2 树、森林与二叉树的转换5.3.3 树和森林的遍历5.4 树的应用5.4.1 二叉排序树5.4.2 哈夫曼树及其应用习题第6章 图6.1 图的基本概念和术语6.2 图的存储结构6.2.1 邻接矩阵表示法6.2.2 邻接链表表示法6.3 图的遍历和求图的连通分量6.3.1 深度优先搜索遍历6.3.2 广度优先搜索遍历6.3.3 求图的连通分量6.4 图的应用6.4.1 生成树和最小生成树6.4.2 拓扑排序6.4.3 最短路径习题第7章 查找7.1 基本概念7.2 静态查找表7.2.1 顺序表上顺序查找7.2.2 有序表查找7.2.3 索引顺序表查找7.3 动态查找表7.3.1 二叉树排序树的生成和插入7.3.2 二叉排序树上的查找7.3.3 二叉排序树的删除7.4 散列表7.4.1 散列表与散列函数7.4.2 散列函数的构造7.4.3 解决冲突的主要方法7.4.4 散列表的查找及分析7.5 应用举例及分析习题第8章 内部排序8.1 基本概念8.2 插入排序8.2.1 直接插入排序8.2.2 折半插入排序8.2.3 希尔排序8.3 交换排序8.3.1 冒泡排序8.3.2 快速排序8.4 选择排序8.5 归并排序8.6 基数排序8.7 各种内部排序方法的比较习题主要参考文献

编辑推荐

《数据结构》由宋宏图任主编，卢敏和吴林华担任副主编，陈千、陈树祥、刘鲁楣、范渊、张定俊、董淑华、潘修强参加了编写工作。

作者简介

《数据结构》可作为高职高专计算机专业学生学习“数据结构”课程的选用教材，也可以作为大学非计算机类专业学生的选修课教材和计算机应用技术从业人员的参考书。“数据结构”是计算机专业的核心课程，《数据结构》对数据结构的有关知识作了系统全面的介绍，在内容组织上力求概念清晰，注重数据结构的实际应用。主要内容包括：数据结构基本概念、线性表、栈和队列、树、图、排序和查找。各章节给出的算法均用C语言编写，并可顺利地在计算机上调试运行，以便于读者理解。

---

 数据结构下载

---