数据结构复习重点归纳二（适于清华严版教材)

考研网

　　第八章　内部排序
        　　内排是DS课程中最后一个重要的章节，建立在此章之上的考题可以有多种类型：填空，选择，判断乃至大型算法题。但是，归结到一点，就是考查你对书本上的各种排序算法及其思想以及其优缺点和性能指标(时间复杂度)能否了如指掌。
        　　这一章，我们对重点的规纳将跟以上各章不同。我们将从以下几个侧面来对排序一章进行不同的规纳，以期能更全面的理解排序一章的总体结构及各种算法。
        　　从排序算法的种类来分，本章主要阐述了以下几种排序方法：插入、选择、交换、归并、计数等五种排序方法。
        　　其中，在插入排序中又可分为：直接插入、折半插入、2路插入、希尔排序。这几种插入排序算法的最根本的不同点，说到底就是根据什么规则寻找新元素的插入点。直接插入是依次寻找，折半插入是折半寻找。希尔排序，是通过控制每次参与排序的数的总范围“由小到大”的增量来实现排序效率提高的目的。
        　　交换排序，又称冒泡排序，在交换排序的基础上改进又可以得到快速排序。快速排序的思想，一语以敝之：用中间数将待排数据组一分为二。快速排序，在处理的“问题规模”这个概念上，与希尔有点相反，快速排序，是先处理一个较大规模，然后逐渐把处理的规模降低，最终达到排序的目的。
        　　选择排序，相对于前面几种排序算法来说，难度大一点。具体来说，它可以分为：简单选择、树选择、堆排。这三种方法的不同点是，根据什么规则选取最小的数。简单选择，是通过简单的数组遍历方案确定最小数;树选择，是通过“锦标赛”类似的思想，让两数相比，不断淘汰较大(小)者，最终选出最小(大)数;而堆排序，是利用堆这种数据结构的性质，通过堆元素的删除、调整等一系列操作将最小数选出放在堆顶。堆排序中的堆建立、堆调整是重要考点。树选择排序，也曾经在一些学校中的大型算法题中出现，请大家注意。
        　　归并排序，故名思义，是通过“归并”这种操作完成排序的目的，既然是归并就必须是两者以上的数据集合才可能实现归并。所以，在归并排序中，关注最多的就是2路归并。算法思想比较简单，有一点，要铭记在心：归并排序是稳定排序。
        　　基数排序，是一种很特别的排序方法，也正是由于它的特殊，所以，基数排序就比较适合于一些特别的场合，比如扑克牌排序问题等。基数排序，又分为两种：多关键字的排序(扑克牌排序)，链式排序(整数排序)。基数排序的核心思想也是利用“基数空间”这个概念将问题规模规范、变小，并且，在排序的过程中，只要按照基排的思想，是不用进行关键字比较的，这样得出的最终序列就是一个有序序列。
        　　本章各种排序算法的思想以及伪代码实现，及其时间复杂度都是必须掌握的，学习时要多注意规纳、总结、对比。此外，对于教材中的10.7节，要求必须熟记，在理解的基础上记忆，这一节几乎成为很多学校每年的必考点。
        　　数据结构大学教程
        　　The Complete Data Structure Training Course
        　　第一章 数据结构及其基本概念
        　　Chapter 1 Data Structure and It’s Basic Concepts
        　　1.1什么是数据结构(What is Data Structure)
        　　如果你问一个木匠学徒：你工作的工具要用什么，他可能会回答你：“我只要一把锤子和一个锯”。但是如果你去问一个老木工或者是大师级的建筑师，他会告诉你“我需要一些精确的工具”。由于计算机所解决的问题都是从生活中抽象出来的问题，其复杂性不言而喻，所以我们需要这样精确有效的工具去解决现实生活中的复杂问题。算法、数据结构、程序设计语言都是这样的工具。数据结构是信息的组织方式。对于相同的算法，用不同的数据结构表示其中的抽象数据类型会造成不同的执行效率。这就有必要研究各种抽象数据类型用不同的数据结构表示的效率差异，以及其适用场合。
        　　何谓数据结构(What is Data Structure)
        　　数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成，即一个数据由哪些成分数据构成，以什么方式构成，呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系，而物理上的数据结构反映成分数据在计算机内部的存储安排。数据结构是信息的一种组织方式，好的数据结构可以提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。从学科角度来讲，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。
        　　数据结构学科的研究对象 (The Object of Data Structure Research)
        　　数据结构作为一门学科，主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。因此，主要有三个方面的内容：数据的逻辑结构;数据的物理存储结构;对数据的操作(即算法)。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。数据结构的研究不仅涉及到计算机硬件的研究，比如存储装置和存取方法，而且解决编译原理、操作系统、数据库系统的数据元素在存储器中的分配问题的重要基础。
        　　1.2 基本概念与学科术语(Basic Concepts and Terminologies)
        　　数据(Data):是一个集合的概念，是对客观事物的符号表示，在计算机科学中是指所有能被输入到计算机中，并被计算机处理的符号的总称。是计算机处理的信息的某种特定的符号表示形式。
        　　数据元素(Data Element):是数据的基本单位，数据中的一个“个体”。又称为“记录”或者“表目”。
        　　数据项(Data Item)：数据的不可分割的最小单位。数据元素是数据项的集合。
        　　数据对象(Data Object)：是性质相同的数据元素的集合，是数据的一个子集。
        　　数据项组成数据元素，数据元素组成数据对象，数据对象组成数据
        　　数据结构(Data Structure)：是相互之间存在一种或多种特定关系的数据元素的集合。它包括三个方面：数据元素的逻辑结构、存储结构和相适应的运算(操作)。

kythree

        　　数据元素之间的逻辑关系被称为数据元素的逻辑结构，可以用一个二元组表示：
        　　Data_Structure = (D, S) // Data_Structure= (Data-part, Logic-Structure-Part)
        　　这里D是数据元素的集合，S是定义在D(或其他集合)上的关系的集合，
        　　S = { R │ R : D×D×...}。
        　　数据的逻辑结构可归结为以下四类:
        　　(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
        　　需要指出的是：并不是所有的可能组合都合理。

kyone

        　　数据结构DS上的操作：所有的定义在DS上的操作在改变数据元素(节点)或节点的域时必须保持DS的逻辑和物理结构。
        　　DS上的基本操作：任何其他对DS的高级操作都可以用这些基本操作来实现。最好将DS和他的所有基本操作看作一个整体——称之为模块(model)。我们可以进一步将该模块抽象为数据类型(其中DS的存储结构被表示为私有成员，基本操作被表示为公共方法)，称之为ADT(即是抽象数据类型Abstract Data Type，指一个数学模型以及定义在该模型上的一组操作)。
        　　ADT按照其值的不同特性分为下列三种类型：
        　　原子类型(Atomic Data Type)：变量是不带结构的，不可分解的。
        　　固定聚合类型(Fixed-aggregate Data Type)：其值由确定数目的成分按照某种结构组成
        　　可变聚合类型(Variable-Aggregate Data Type)：值的成分的数目不确定
        　　抽象数据类型的描述方法
        　　抽象数据类型可用(D，S，P)三元组表示
        　　其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。
        　　ADT 抽象数据类型名 {
        　　数据对象：〈数据对象的定义〉
        　　数据关系：〈数据关系的定义〉
        　　基本操作：〈基本操作的定义〉
        　　} ADT 抽象数据类型名
        　　其中，数据对象和数据关系的定义用伪码描述，基本操作的定义格式为
        　　基本操作名(参数表)
        　　初始条件：〈初始条件描述〉
        　　操作结果：〈操作结果描述〉
        　　基本操作有两种参数：赋值参数只为操作提供输入值;引用参数以&打头， 除可提供输入值外，还将返回操作结果。“初始条件”描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。“操作结果”说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则将其省略。需要注意的是：抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。
        　　顺便提一句，多形数据类型(Polymorphic Data Type)是指值的成分不确定的数据类型，不过这个不太多见，或者是可以用ADT表示，所以我们在今后的章节再论述。
        　　好的和坏的DS：如果一个DS可以通过某种“线性规则”被转化为线性的DS(例如线性表)，则称它为好的DS。好的DS通常对应于好的(高效的)算法。这是由计算机的计算能力决定的，因为计算机本质上只能存取逻辑连续的内存单元，因此如何没有线性化的结构逻辑上是不可计算的。比如对一个图进行操作，要访问图的所有结点，则必须按照某种顺序来依次访问所有节点(要形成一个偏序)，必须通过某种方式将图固有的非线性结构转化为线性结构才能对图进行操作。
        　　树是好的DS——它有非常简单而高效的线性化规则，因此可以利用树设计出许多非常高效的算法。树的实现和使用都很简单，但可以解决大量特殊的复杂问题，因此树是实际编程中最重要和最有用的一种数据结构。树的结构本质上有递归的性质——每一个叶节点可以被一棵子树所替代，反之亦然。实际上，每一种递归的结构都可以被转化为(或等价于)树形结构。说到递归在北京大学的数据结构课程里面有个老师经常说“不懂递归就不算北大计算机系的学生”，这样看来足以从侧面说明书的结构的重要性。
        　　1.3 算法和算法分析
        　　Algorithms and Algorithm Analysis

kythree

        　　1.3.1算法
        　　所谓算法(Algorithm)是对问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。在CLRS中是这样给出算法的定义的：Informally, an algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. An algorithm is thus a sequence of computational steps that transform the input into the output.
        　　一个算法必须满足以下五个重要特性：
        　　1.有穷性 对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成;
        　　2.确定性 对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径;
        　　3.可行性 算法中描述的操作都可以通过已经实现的基本操作运算有限次实现之;
        　　4.有输入 作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中;
        　　5.有输出 它是一组与输入有确定关系的量值，是算法进行信息加工后得到的结果。
        　　1.3.2算法设计的原则
        　　设计算法时我们应当严格考虑：
        　　1.正确性(Correctness)
        　　首先，算法应当满足以特定的“规格说明”方式给出的需求。对算法是否“正确”的理解可以有以下四个层次：
        　　a.程序中不含语法错误;
        　　b.程序对于几组输入数据能够得出满足要求的输出结果;
        　　c.程序对于精心选择的、典型、苛刻的几组输入数据能够得出满足要求的结果;
        　　d.程序对于一切合法的输入数据都能得出满足要求的结果;
        　　通常以第c层意义的正确性作为衡量一个算法是否合格的标准。因为作为输入，我们有时候不可能提前做出所有的预期。
        　　2. 可读性(Readability)
        　　算法主要是为了人的阅读与交流，其次才是为计算机执行。因此算法应该易于人的理解;另一方面，晦涩难读的程序易于隐藏较多错误而难以调试;有些程序设计者总是把自己设计的算法写的只有自己才能看懂，这样的算法反而没有太大的价值。
        　　3.健壮性(Rubustness)
        　　当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。这就需要我们一定要充分的考虑异常情况(Unexpected Exceptions)并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。
        　　4.高效率与低存储量需求
        　　通常，效率指的是算法执行时间;存储量指的是算法执行过程中所需的最大存储空间。两者都与问题的规模有关。
        　　1.3.3算法效率的衡量方法与准则
        　　通常有两种衡量算法效率的方法:
        　　1.事后统计法
        　　缺点：
        　　(1)必须执行程序才能进行判断
        　　(2)其它因素(如硬件、软件环境)掩盖算法本质
        　　2.事前分析估算法
        　　主要是看消耗的时间。和算法执行时间相关的因素：
        　　1.算法选用的策略
        　　2.问题的规模
        　　3.编写程序的语言
        　　4.编译程序产生的机器代码的质量
        　　5.计算机执行指令的速度

kyfour

        　　一个特定算法的“运行工作量”的大小，只依赖于问题的规模(通常用整数量n表示)，或者说，它是问题规模的函数。假如，随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作：
        　　T (n) = O(f(n))
        　　称T (n) 为算法的渐近时间复杂度(Asymptotic Time Complexity),简称时间复杂度。O是数量级的符号。
        　　下面我们探讨一下如何估算算法的时间复杂度
        　　算法 = 控制结构 + 原操作(固有数据类型的操作)
        　　算法的执行时间=原操作(i)的执行次数×原操作(i)的执行时间
        　　算法的执行时间与原操作执行次数之和成正比
        　　我们先介绍一个概念：
        　　for(j=1;j
        　　for(k=1;k
        　　语句重复执行的次数被称为语句的频度(Frequency Count)上程序段中++x的语句频度就是n2。
        　　我们经常采用：从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。这个原操作多数情况下是最深层次循环内的语句中的原操作。
        　　例如：
        　　for (i=1; i
        　　for (j=1; j
        　　c = 0;
        　　for (k=1; k
        　　c += a*b;
        　　}
        　　该算法的基本操作是乘法操作。时间复杂度为 O(n3)
        　　1.3.4算法的存储空间(Memory Space for Algorithms)
        　　算法的空间复杂度S(n) = O(g(n))
        　　表示随着问题规模n的增大，算法运行所需存储量的增长率与g(n)的增长率相同。
        　　算法的存储量包括:
        　　1.输入数据所占空间;
        　　2.程序本身所占空间;
        　　3.辅助变量所占空间。
        　　若输入数据所占空间只取决与问题本身，和算法无关，则只需要分析除输入和程序之外的额外空间。若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作。