数据结构要点精析

出版时间：2009-3  出版社：北京航空航天大学出版社  作者：侯风巍 著  页数：361  
Tag标签：无  

前言

　　自从本书于2007年出版发行以来，受到了广大读者的关心和推崇。在本书的伴随下，很多读者也已磨刀霍霍向牛羊，真正体验到了学习数据结构的从容与快乐。这的确是一件值得弹冠相庆的事情，这也正是编写本书的初衷之所在，故而编者感到莫大的光荣和欣慰。　　事情总是在发展的，本书也不能停留在同一个位置上。随着学科发展及应用范围的进一步拓宽和加深，对数据结构知识点的应用和考查也有所变化。这就要求本书的内容必须适应和反映其中的变化，并与时代的发展保持同步；同时本书力求做到保持“解牛之道”不变，以不变应万变。　　本着对数据结构之道不懈追求的态度，编者在第1版的基础上对本书内容进行了修订、调整和扩充。　　一方面，在保持第1版整体结构不变的情况下，对各章节内容进行了全面扩充和修正，增加了各大高校和科研院所近几年硕士研究生入学考试中的经典题目，并进行了详细而全面的解析。大家都知道，剖析、理解经典题目是掌握相应知识点的捷径，这也正是本书一直坚持使用考研真题作为解析知识点的原因所在。同时增加了链表、栈、树、图、排序中的一些必要知识点，并以联想网络的方式与原有知识网有机结合起来。无论是对题目的解析还是对知识点的诠释，本版都试图做到尽可能细致而全面。天下难事必做于易，天下大事必做于细。如果对每个知识点、每道题目都能钻研到细致入微处，那么掌握数据结构这门学科并游刃有余地应用数据结构知识解决实际问题，自然也就变得容易实现多了。　　另一方面，在改正第1版中发现的错误的基础上竭尽全力避免在新增加的内容中再引入新的错误。然而，由于编者水平有限，本版中某些欠缺和不妥之处仍会在所难免，敬请广大读者继续提出宝贵意见和建议。　　本书不是读完一遍就可以束之高阁的快餐读物，也不是能够立刻解决任何问题的万能题库，而是需要各位读者反复阅读体会，把“解牛之道”极力融入自己思想之中，这样才能真正达到“恢恢乎其于游刃必有余地”的境界。希望这本书能够帮助各位读者跨越数据结构的重重障碍，在高处领略“提刀而立，为之四顾，为之踌躇满志”的壮美。

内容概要

　　《数据结构要点精析：C语言版（第2版）》介绍数据结构线性表、栈和队列、串、数组和广义表、树和二叉树、图、查找、内排序等的基本概念、基本知识点、相关结论和各种数据类型的不同存储结构以及主要操作的实现算法；系统而全面地对读者在学习过程中可能遇到的问题，在相应的知识点处提出并加以解决；精选各大知名院校和研究所的硕士研究生入学试题及国内外教材中有代表性的习题，结合各相关知识点进行深入细致的分析、完整的解答和点评扩展。　　《数据结构要点精析：C语言版（第2版）》可作为计算机专业本、专科学生的教学参考书，也可作为报考计算机专业硕士研究生的学习参考书，还适于计算机等级考试者及广大工程技术人员和自学者参考。

书籍目录

第1章 绪论1.1 基本概念1.1.1 数据的逻辑结构1.1.2 数据的存储结构1.1.3 数据的逻辑结构与存储结构的关系1.2 抽象数据类型1.2.1 算法1.2.2 算法的分析第2章 线性表2.1 线性表的逻辑结构2.2 线性表的顺序存储结构2.3 线性表的链式存储结构2.3.1 单链表2.3.2 静态链表2.3.3 循环链表2.3.4 双向链表第3章 栈和队列3.1 栈3.1.1 顺序栈3.1.2 双栈3.1.3 链栈3.2 队列3.2.1 队列的顺序存储结构和循环队列3.2.2 循环队列3.2.3 链队列第4章 字符串4.1 串类型的相关概念4.2 字符串的存储表示和实现4.2.1 定长顺序存储表示4.2.2 堆分配存储表示和实现4.2.3 串的块链存储表示4.3 串的模式匹配算法4.3.1 朴素的模式匹配算法4.3.2 模式匹配算法的一种改进算法——KMP算法第5章 数组和广义表5.1 数组的定义5.2 数组的顺序表示和实现5.3 矩阵的压缩存储5.3.1 特殊矩阵的压缩存储5.3.2 稀疏矩阵的压缩存储5.4 广义表5.4.1 广义表的定义5.4.2 广义表的存储结构99目录第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 后序遍历6.3.4 按层次遍历6.4 表达式树及其构造6.4.1 由表达式构造表达式树6.4.2 由前缀表达式构造表达式树6.4.3 由后缀表达式构造表达式树6.4.4 由后缀表达式求值6.4.5 由（中缀）表达式直接求其前（后）缀表达式6.5 线索二叉树6.5.1 线索二叉树的定义6.5.2 二叉树的线索化6.5.3 线索二叉树上搜索指定结点的前驱、后继结点6.6 树和森林与二叉树6.6.1 树和森林与二叉树的转换6.6.2 树和森林的遍历6.7 哈夫曼树及其应用6.7.1 哈夫曼树6.7.2 哈夫曼编码6.8 树与等价问题第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 Prim（普里姆）算法7.4.2 Kruskal（克鲁斯卡尔）算法7.5 关节点7.6 有向无环图的应用7.6.1 表达式的有向无环图7.6.2 拓扑排序7.6.3 关键路径7.7 最短路径7.7.1 单源点的最短路径问题7.7.2 每一对顶点之间的最短路径问题第8章 查找8.1 基本概念和相关约定8.1.1 基本概念8.1.2 算法的平均查找长度8.1.3 判定树8.1.4 相关约定8.2 静态查找表的查找算法8.2.1 无序顺序表的查找——顺序查找法8.2.2 有序顺序表的查找——折半查找法8.2.3 次优查找树8.2.4 索引顺序表的查找——分块查找8.3 动态查找表8.3.1 二叉排序树8.3.2 平衡二叉树8.3.3 B-树8.3.4 B+树8.3.5键树8.4 哈希表8.4.1 哈希函数的构造方法8.4.2 处理冲突的方法8.4.3 哈希表的查找8.4.4 哈希表的插入和删除8.5 各种查找方法的比较第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.4.3 堆排序9.5 归并排序9.6 基于关键字比较的排序算法的时间下界9.7 基数排序9.7.1 多关键字排序9.7.2 链式基数排序9.8 各种内部排序方法的比较参考文献

章节摘录

　　第1章　绪论　　【学习要点】　　1.理解数据、数据对象、数据元素和数据结构等基本概念，尤其是数据的逻辑结构与物理（存储）结构间的关系以及在这种结构上所定义的操作。　　2.掌握算法的定义和特性、算法的时间复杂度和空间复杂度。　　3.掌握计算语句频度和估算算法的时间复杂度和空间复杂度的方法。　　【要点精讲】　　本章主要讨论数据结构学科的基本概念及其所研究的主要内容，包括算法的概念、特点、要求及其评价方法。　　要使用计算机解决现实世界中的问题，就需要利用一些数据结构来表达现实生活中的各种事物，进而对实际问题进行建模，并加以解决。大体上数据结构可分为逻辑结构和物理结构，而逻辑结构又可分为线性结构和非线性结构。算法和程序是不同的，程序是用某种计算机语言实现了的算法，而算法是更高层次上的抽象。　　在各种类型的考试中，比较侧重于对数据结构、数据类型、ADT和算法等重要基本概念的考察，对算法的描述方法以及评价标准与方法的考察，也请读者特别注意。　　1.1　基本概念　　1.数据（data）　　数据是信息的载体，是对客观事物的符号表示，是所有能输入到计算机并被计算机程序处理的符号总称。　　2.数据元素（data element）　　数据元素是数据的基本单位。　　3.数据项（data item）　　数据项是数据不可再分割的最小单位。　　注意：数据元素和数据项的区别　　数据元素一般在计算机程序里被看做一个整体来考虑和处理。一个数据元素可以是不可分割的原子，也可以由若干个数据项组成。数据项强调不可再分性。