2014计算机考研数据结构复习重点归纳(三)
数据的逻辑结构可归结为以下四类:(1)集合结构
结构中的数据元素之间除了同属于一个集合的关系外别无其他关系
(2)线性结构
结构中的数据元素之间存在一个对一个的前趋后继关系
在此种结构下：
有且仅有一个元素无前趋元素
有且仅有一个元素无后继元素
其余任何一个元素均有且仅有一个前趋有且仅有一个后继元素。
(3)树形结构
结构中的数据元素之间存在一个对多个的关系
任何一个节点最多有一个前趋，可以有多个后继，是一种典型的非线性结构
(4)图状结构(网状结构)
结构中的数据元素之间存在多个对多个的关系
这种结构的特征是任何一个元素可以有多个前趋，也可以有多个后继，是一种多对多的前趋后继关系
表和树是最常用的两种高效数据结构，许多高效的算法可以用这两种数据结构来设计实现。表是线性结构的(全序关系)，树(偏序或层次关系)和图(局部有序(weak/local orders))是非线性结构。
数据结构在计算机中的表示(又称为映像)称为数据的存储结构(物理结构)
数据结构的物理结构是指逻辑结构的存储映像(image)。数据结构 DS 的物理结构 P 对应于从 DS 的数据元素到存储区M(维护着逻辑结构S)的一个映射：
PD,S) -- > M
存储器模型：一个存储器 M 是一系列固定大小的存储单元，每个单元 U 有一个唯一的地址 A(U)，该地址被连续地编码。每个单元 U 有一个唯一的后继单元 U'=succ(U)。
P 的四种基本映射模型：顺序(sequential)、链接(linked)、索引(indexed)和散列(hashing)映射。因此，我们至少可以得到4×4种可能的物理数据结构：
sequential (sets) linked lists indexed trees hashing graphs
需要指出的是：并不是所有的可能组合都合理。
第七章 内部排序
内排是DS课程中最后一个重要的章节，建立在此章之上的考题可以有多种类型：填空，选择，判断乃至大型算法题。但是，归结到一点，就是考查你对书本上的各种排序算法及其思想以及其优缺点和性能指标(时间复杂度)能否了如指掌。 这一章，我们对重点的规纳将跟以上各章不同。我们将从以下几个侧面来对排序一章进行不同的规纳，以期能更全面的理解排序一章的总体结构及各种算法。
从排序算法的种类来分，本章主要阐述了以下几种排序方法：插入、选择、交换、归并、计数等五种排序方法。
其中，在插入排序中又可分为：直接插入、折半插入、2路插入、希尔排序。这几种插入排序算法的最根本的不同点，说到底就是根据什么规则寻找新元素的插入点。直接插入是依次寻找，折半插入是折半寻找。希尔排序，是通过控制每次参与排序的数的总范围“由小到大”的增量来实现排序效率提高的目的。
交换排序，又称冒泡排序，在交换排序的基础上改进又可以得到快速排序。快速排序的思想，一语以敝之：用中间数将待排数据组一分为二。快速排序，在处理的“问题规模”这个概念上，与希尔有点相反，快速排序，是先处理一个较大规模，然后逐渐把处理的规模降低，最终达到排序的目的。
选择排序，相对于前面几种排序算法来说，难度大一点。具体来说，它可以分为：简单选择、树选择、堆排。这三种方法的不同点是，根据什么规则选取最小的数。简单选择，是通过简单的数组遍历方案确定最小数;树选择，是通过“锦标赛”类似的思想，让两数相比，不断淘汰较大(小)者，最终选出最小(大)数;而堆排序，是利用堆这种数据结构的性质，通过堆元素的删除、调整等一系列操作将最小数选出放在堆顶。堆排序中的堆建立、堆调整是重要考点。树选择排序，也曾经在一些学校中的大型算法题中出现，请大家注意。
归并排序，故名思义，是通过“归并”这种操作完成排序的目的，既然是归并就必须是两者以上的数据集合才可能实现归并。所以，在归并排序中，关注最多的就是2路归并。算法思想比较简单，有一点，要铭记在心：归并排序是稳定排序。
基数排序，是一种很特别的排序方法，也正是由于它的特殊，所以，基数排序就比较适合于一些特别的场合，比如扑克牌排序问题等。基数排序，又分为两种：多关键字的排序(扑克牌排序)，链式排序(整数排序)。基数排序的核心思想也是利用“基数空间”这个概念将问题规模规范、变小，并且，在排序的过程中，只要按照基排的思想，是不用进行关键字比较的，这样得出的最终序列就是一个有序序列。
本章各种排序算法的思想以及伪代码实现，及其时间复杂度都是必须掌握的，学习时要多注意规纳、总结、对比。此外，对于教材中的10.7节，要求必须熟记，在理解的基础上记忆，这一节几乎成为很多学校每年的必考点。
页:
[1]