数据结构与算法总结
❶ 什么是算法与数据结构
算法（Algorithm）是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决一类问题。
一个算法应该具有以下五个重要的特征：
1、有穷性： 一个算法必须保证执行有限步之后结束；
2、确切性： 算法的每一步骤必须有确切的定义；
3、输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件；
4、输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；
5、可行性： 算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。
计算机科学家尼克劳斯-沃思曾着过一本着名的书《数据结构十算法= 程序》，可见算法在计算机科学界与计算机应用界的地位。
数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。
一般认为，一个数据结构是由数据元素依据某种逻辑联系组织起来的。对数据元素间逻辑关系的描述称为数据的逻辑结构；数据必须在计算机内存储，数据的存储结构是数据结构的实现形式，是其在计算机内的表示；此外讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义。
在许多类型的程序的设计中，数据结构的选择是一个基本的设计考虑因素。许多大型系统的构造经验表明，系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。许多时候，确定了数据结构后，算法就容易得到了。有些时候事情也会反过来，我们根据特定算法来选择数据结构与之适应。不论哪种情况，选择合适的数据结构都是非常重要的。
选择了数据结构，算法也随之确定，是数据而不是算法是系统构造的关键因素。这种洞见导致了许多种软件设计方法和程序设计语言的出现，面向对象的程序设计语言就是其中之一。
在计算机科学中，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象（数据元素）以及它们之间的关系和运算等的学科，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。
“数据结构”作为一门独立的课程在国外是从1968年才开始设立的。 1968年美国唐·欧·克努特教授开创了数据结构的最初体系，他所着的《计算机程序设计技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的着作。“数据结构”在计算机科学中是一门综合性的专业基础课。数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。数据结构这一门课的内容不仅是一般程序设计（特别是非数值性程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。
计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：
信息的表示
信息的处理
而信息的表示和组又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。众所周知，计算机的程序是对信息进行加工处理。在大多数情况下，这些信息并不是没有组织，信息（数据）之间往往具有重要的结构关系，这就是数据结构的内容。数据的结构，直接影响算法的选择和效率。
计算机解决一个具体问题时，大致需要经过下列几个步骤：首先要从具体问题中抽象出一个适当的数学模型，然后设计一个解此数学模型的算法（Algorithm），最后编出程序、进行测试、调整直至得到最终解答。寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。计算机算法与数据的结构密切相关，算法无不依附于具体的数据结构，数据结构直接关系到算法的选择和效率。运算是由计算机来完成，这就要设计相应的插入、删除和修改的算法 。也就是说，数据结构还需要给出每种结构类型所定义的各种运算的算法。
数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并由计算机程序处理的符号的总称。
数据元素是数据的基本单位，在计算机程序中通常作为一个整体考虑。一个数据元素由若干个数据项组成。数据项是数据的不可分割的最小单位。有两类数据元素：一类是不可分割的原子型数据元素，如：整数"5"，字符 "N" 等；另一类是由多个款项构成的数据元素，其中每个款项被称为一个数据项。例如描述一个学生的信息的数据元素可由下列6个数据项组成。其中的出身日期又可以由三个数据项："年"、"月"和"日"组成，则称"出身日期"为组合项，而其它不可分割的数据项为原子项。
关键字指的是能识别一个或多个数据元素的数据项。若能起唯一识别作用，则称之为 "主" 关键字，否则称之为 "次" 关键字。
数据对象是性质相同的数据元素的集合，是数据的一个子集。数据对象可以是有限的，也可以是无限的。
数据处理是指对数据进行查找、插入、删除、合并、排序、统计以及简单计算等的操作过程。在早期，计算机主要用于科学和工程计算，进入八十年代以后，计算机主要用于数据处理。据有关统计资料表明，现在计算机用于数据处理的时间比例达到80%以上，随着时间的推移和计算机应用的进一步普及，计算机用于数据处理的时间比例必将进一步增大。
数据结构是指同一数据元素类中各数据元素之间存在的关系。数据结构分别为逻辑结构、存储结构（物理结构）和数据的运算。数据的逻辑结构是对数据之间关系的描述，有时就把逻辑结构简称为数据结构。逻辑结构形式地定义为（K，R）（或（D，S）），其中，K是数据元素的有限集，R是K上的关系的有限集。
数据元素相互之间的关系称为结构。有四类基本结构：集合、线性结构、树形结构、图状结构（网状结构）。树形结构和图形结构全称为非线性结构。集合结构中的数据元素除了同属于一种类型外，别无其它关系。线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。在图形结构中每个结点的前驱结点数和后续结点数可以任意多个。
数据结构在计算机中的表示（映像）称为数据的物理（存储）结构。它包括数据元素的表示和关系的表示。数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现，由此得到的存储表示称为顺序存储结构。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构，链式存储结构通常借助于程序设计语言中的指针类型来实现。索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。
数据结构中，逻辑上（逻辑结构：数据元素之间的逻辑关系）可以把数据结构分成线性结构和非线性结构。线性结构的顺序存储结构是一种随机存取的存储结构，线性表的链式存储结构是一种顺序存取的存储结构。线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。逻辑结构与数据元素本身的形式、内容、相对位置、所含结点个数都无关。
算法的设计取决于数据（逻辑）结构，而算法的实现依赖于采用的存储结构。数据的运算是在数据的逻辑结构上定义的操作算法，如检索、插入、删除、更新的排序等。
❷ 什么是数据结构和算法分析在编程里起到什么作用
编程是为了解决问题，这些问题并表都是数值计算，其所处理的数据并不都是数值，但计算机所能处理的最终是0和1的二进制串，所以需要把问题中的数据用计算机能处理的方式来表示，这就需要数据结构。
简单的说，数据结构是数据在计算机中的表示方式，有逻辑结构和物理结构之分，如逻辑上同样的队列，物理上可以是顺序存储，也可以是链式存储。
通俗的讲，算法就是解决问题的方法，比如同样的排序，可以用冒泡排序、插入排序等，不同的算法可以达到相同的目标，但是效率可能有所不同。
❸ 19年3月二级C--数据结构与算法
1.假设线性表的长度为n，则最坏情况下:
冒泡排序: 需要经过n/2遍的从前往后扫描和n/2遍从后往前扫描，需要比较的次数为n(n-1)/2。总的时间复杂度为O(n的平方)。
快速排序: 比较次数也是n(n-1)/2。总的时间复杂度为O(n的平方)。
直接插入排序: 所需要比较的次数为n(n-1)/2。总的时间复杂度为O(n的平方)。
希尔排序所需要比较的次数为O(n的1.5次方)。(时间复杂度小于以上三种)
堆排序: 最坏情况下，其时间复杂度为O(nlogn)。(小于O(n的平方))。
2.根据数据结构中各元素之间前后关系的复杂程度，一般数据结构分为两大类: 线性结构和非线性结构。
如果一个非空的数据结构满足下列两个条件，①有且只有一个根结点 ②每个结点最多有一个前件，也最多有一个后件。则称该数据结构为线性结构，又称线性表。
3.算法时间复杂度与空间复杂度没有关系。
4.所谓算法的时间复杂度，是指执行算法所需要的计算工作量。
为了能够比较客观的反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所用的计算机程序设计语言，以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。
5.同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。
算法分析的目的在于选择合适算法和改进算法。
6.堆排序在平均情况下的时间复杂度与最坏情况下的时间复杂度都是O(nlogn)。
7.二叉链表: 以二叉链表作为树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和第一个孩子下的一个兄弟结点。
循环链表是链式存储结构，循环队列是线性存储结构。( 【×】循环链表是循环队列的链式存储结构)
双向链表也叫双链表，是链表的一种，它的每个数据结点都有两个指针，分别指向直接后继和直接前驱，所以从双链表中的任意一个结点开始都可以很方便地访问它的前驱结点和后继结点。
8.数据的逻辑结构由两个要素: 一是数据元素的集合，通常记为D。二是D上的关系，它反映了D中各元素之间的前后件关系，通常记为R。
即一个数据结构可以表示成B=(D,R)，其中B表示数据结构，为了反映D中各元素之间的前后件关系，一般用二元组来表示。例如，假如a与b是D中的两个数据，则二元组表示a是b的前件，b是a的后件。
线性结构用图形表示更加直观。例如: R=｛(5,1)，(7,9)，(1,7)，(9,3)｝，结构为: 5→1→7→9→3
9.快速排序法是一种互换类的排序方法，但由于比冒泡排序的速度快，因此称为快速排序。
其基本思想是从线性表中选择一个元素设为t，将线性表后面小于t的元素移到前面，而前面大于t的元素移到后面，结果就将线性表分成了两部分，t插入到分界线的位置处，这个过程称为线性表的分割。
简单插入排序法，是指将无序序列中的各元素依次插入到已经有序的线性表中。
冒泡排序法是一种最简单的交换类排序方法，它是通过相邻数据元素的交换，逐步将线性表变为有序。
后两种元素的移动过程中不会产生新的逆序。
10.程序可作为算法的一种描述。
11.为了降低算法的空间复杂度，要求算法尽量采用原地工作，所谓的原地工作是指执行算法时所使用的额外空间固定。
一个算法的空间复杂度一般是指执行这个算法所需要的内存空间，一个算法所占用的存储空间包括程序所占的空间，输入的初始数据所占的空间以及算法执行过程中所需要的额外空间。
12.能从任意一个结点开始没有重复的扫描到所有结点的数据结构是循环链表。
13.循环队列是队列的一种存储结构
14.算法的设计要求包括效率与低存储量，即要考虑算法的时间复杂度与空间复杂度。
算法的复杂度包括时间复杂度和空间复杂度。
时间复杂度: 是指执行算法所需要的计算工作量。
空间复杂度: 一般是指执行这个算法所需要的内存空间。
15.栈是一种特殊的线性表。链式结构把每一个存储结点分为数据域与指针域，带链的栈可以通过指针域的变化改变原有的栈的组织数据原则; 而顺序栈的栈底指针不变，栈顶指针改变。
16.堆排序在最坏的情况下需要比较nlogn次。
快速排序，在最坏情况下需要比较n(n-1)/2次。
顺序查找，在最坏情况下需要比较n次。
最坏情况下，二分查找需要log2n(小于n-1)
在长度为n的顺序表中寻找最大项/最小项时，比较次数最少为1，最多为n-1。
17.如果一个非空的数据结构满足下列两个条件，①有且只有一个根节点 ②每一个结点最多有一个前件，也最多有一个后件，则称该数据结构为线性结构。如果一个数据结构不是线性结构，则称为非线性结构。
18.带链栈空的条件是 top=bottom=NULL
19.满二叉树也是完全二叉树，完全二叉树不一定是满二叉树。对于满二叉树和完全二叉树来说，可以按照程序进行顺序存储，不仅节省了空间，又能方便地确定每一个结点的父结点等于左右子结点的位置，但顺序存储结构对于一般的二叉树不适用。
20.带链栈队头指针与队尾指针相同，且不为空时，队列元素个数为1; 若为空时，队列元素个数为0。
带链栈的栈底指针是随栈的操作而动态变化的。
21.二叉树的链式存储结构，也称为二叉链表。在二叉树中，由于每一个元素可以有两个后件，因此用于存储二叉树的存储结点的指针域有两个，所以二叉链表属于非线性结构。
22.线性表由一组元素数据元素构成，各元素的数据类型必须相同，矩阵是一个比较复杂的线性表，线性表除了插入和删除运算之外，还可以查找，排序，分解，合并等。数组是长度固定的线性表。
23.冒泡排序中，在互换两个相邻元素时，只能消除一个逆序; 快速排序及希尔排序中，一次交换可以消除多个逆序。
24.二分法检索的效率比较高，设线性表有n个元素，则最多的比较次数为log2n，最少检索次数为1。
25.循环链表的结构具有以下两个特点。一，在循环链表中，增加了一个表头结点，其数据域为任意或者根据需要来设置指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。二、循环链表中最后一个节点的指针域不是空，而是指向表头结点，即在循环链表中所有的结点指针构成一个环状链。
26.二叉树的存储结构是非线性结构，而完全二叉树是特殊形态的二叉树。采用顺序存储的完全二叉树属于非线性结构。
27.时间复杂度和计算机运行速度以及存储空间无关。
算法的空间复杂度和存储结构无关。
数据处理效率与数据的存储结构有关。
28.线性表，向量，栈，队列都属于线性结构的顺序存储。
29.循环队列是队列的存储结构。
循环链表是另一种形式的念式存储结构。
(✘循环链表是循环队列的链式存储结构。✘)
30.完全二叉树的总结点为奇数时，叶子结点是总结点加一再除以二。
31.在实际处理中，可以用一位数组来存储堆序列中的元素，也可以用完全二叉树来直观的表示堆的结构。在用完全二叉树表示堆时，树中所有非叶子结点值均不小于其左，右子树的根结点值，因为堆顶元素必须为序列的n个元素的最大项，因此其中序并不是有序序列。
多重链表指表中每个结点由两个或两个以上的指针域的链表。如果一个非空的数据结构满足下列两个条件，①有且只有一个根结点，②每个结点最多有一个前件，也最多有一个后件，则称该数据结构为线性结构，所以多重链表不一定是非线性结构。
在计算机中二叉树通常采用链式存储结构，对于满二叉树和完全二叉树来说，可以按层次进行顺序存储。
排序二叉树的中序遍历序列是有序序列。
32.对于一个固定的规模，算法所执行的基本运算次数还可能与特定的输入有关。
33.在线性表中寻找最大项时，平均情况下和最坏情况下比较次数都是n-1。
34.在长度为n的顺序表中查找一 个元素， 假没需要查找的元素有一半的机会在表中，并且如果元素在表中，则出现在表中每个位置上的可能性是相
同的。则在平均情况下需要比较的次数大约为_
A.3n/4 B.n C.n/2 D.n/4
本题的考查知识点是顺序表的存储结构。
因为需要查找的元素有一半机会在表中，所以二分之一的情况下平均比较次数为n/2，另二分之一的情况下平均比较次数为n。总的平均比较次数为(n/2+n) /2-3n/4。
故本题答案为A。
35.设数据结构B=(D, R)，其中
D={a,b,c,d，e，f}
R={(a，b)，(b，c)，(c，d)，(d，e)，(e，f)，(f,a)}该数据结构为
A.线性结构 B.循环队列
C.循环链表 D.非线性结构
本题的考查知识点是数据结构。
如果一个非控的数据结构满足下列两个条件: 1) 有且只有一个根节点; 2) 每一一个结点最多有一一个前件，也最多有一一个后件。则称该数据结构为线性结构。如果一个数据结构不是线性结构，则称之为非线性结构。
数据结构B=(D, R)中， 每一个结点均有一个前件，不符合“有且只有一个根节点”的条件，所以为非线性结构。故本题答案选D。
36.某带链的队列初始状态为front=rear=NULL。经过一系列正常的入队与退队操作后，front=rear=10。 该队列中的元素个数为_
A.1 B.0 C.1或0 D.不确定
本题的考查知识点是带链队列。
在初始状态为front=rear=NULL的带链队列入队时，如果插入的结点既是队首结点又是队尾结点，则rear和front同时指向这个结点;否则在循环队列的队尾加入一一个新元素，rear指向新增结点的数据域，rear+1, front不变。 退队时，在循环队列的排头位置退出一个元素并赋给指定的变量，front指向第二个结点的数据域，front+1, rear不变。当front=rear=10时， front和rear同时指向这个唯一 元素，所以该队列中的元素个数为1。
故本题答案为A。
37.若二叉树没有叶子结点，则为空二叉树。
38.某带链栈的初始状态为top=bottom=NULL, 经过一系列正 常的入栈与退栈操作后，top=10, bottom=20。 该栈中的元素个数为_____。
A.不确定 B. 10 C.1 D.0
本题考查的知识点是栈。
带链的栈是具有栈属性的链表，线性链表的存储单元是不连续的，为把存储空间中一-些离散的空闲存 储结点利用起来，把所有空闲的结点组织成一个带链的栈，称为可利用栈。
线性链表执行删除操作运算时， 被删除的结点可以”回收到可利用栈，对应于可利用栈的入栈运算;线性链表执行插入运算时，需要一个新的结点，可以在可利用栈中取栈顶结点，对应于可利用栈的退栈运算。
可利用栈的入栈运算和退栈运算只需要改动top指针即可。因为是不连续的存储空间，所以top指针将不会有规律地连续变化，因此无法据此判断栈中的元素个数。
所以本题答案为A。
❹ 数据结构复习总结第八章排序
第八章排序
基本概念
文件有一组记录组成 记录有若干数据项组成 唯一标识记录的数据项称关键字;
排序是将文件按关键字的递增(减)顺序排列;
排序文件中有相同的关键字时 若排序后相对次序保持不变的称稳定排序 否则称不稳定排序;
在排序过程中 文件放在内存中处理不涉及数据的内 外存交换的称内部排序 反之称外部排序;
排序算法的基本操作 )比较关键字的大小; )改变指向记录的指针或移动记录本身
评价排序方法的标准 )执行时间; )所需辅助空间 辅助空间为O( )称就地排序;另要注意算法的复杂程度
若关键字类型没有比较运算符 可事先定义宏或函数表示比较运算
插入排序
直接插入排序
实现过程
void insertsort(seqlist R)
{
int i j;
for(i= ;i<=n;i++)
if(R[i] key< R[i ] key{
R[ ]=R[i];j=i ;
do{R[j+ ]=R[j];j ;}
while(R[ ] key <r[j].key); p=""> </r[j].key);>
R[j+1]=R[0];
}
}
算法中引入监视哨R[0]的作用是：1)保存R[i]的副本;2)简化边界条件，防止循环下标越界。WiNgwit
关键字比较次数最大为(n+2)(n-1)/2;记录移动次数最大为(n+4)(n-1)/2;
算法的最好时间是O(n);最坏时间是O(n^2);平均时间是O(n^2);是一种就地的稳定的排序;
8.2.2希尔排序
实现过程：是将直接插入排序的间隔变为d。d的取值要注意：1)最后一次必为1;2)避免d值互为倍数;
关键字比较次数最大为n^1.25;记录移动次数最大为1.6n^1.25;
算法的平均时间是O(n^1.25);是一种就地的不稳定的排序;
8.3交换排序
8.3.1冒泡排序
实现过程：从下到上相邻两个比较，按小在上原则扫描一次，确定最小值，重复n-1次。
关键字比较次数最小为n-1、最大为n(n-1)/2;记录码含移动次数最小为0，最大为3n(n-1)/2;
算法的最好时间是O(n);最坏时间是O(n^2);平均时间是O(n^2);是一种就地的稳定的排序;
8.3.2快速排序
实现过程：将第一个值作为基准，设置i,j指针交替从两头与基准比较含轮，有交换后,交换j，i。i=j时确定基准，并以其为界限将序列分为两段。重复以上步骤。
关键字比较次数最好为nlog2n+nC(1)、最坏为n(n-1)/2;
算法的最好时间是O(nlog2n);最坏时间是O(n^2);平均时间是谈模信O(nlog2n);辅助空间为O(log2n);是一种不稳定排序;
8.4选择排序
8.4.1直接选择排序
实现过程：选择序列中最小的插入第一位，在剩余的序列中重复上一步，共重复n-1次。
关键字比较次数为n(n-1)/2;记录移动次数最小为0，最大为3(n-1);
算法的最好时间是O(n^2);最坏时间是O(n^2);平均时间是O(n^2);是一种就地的不稳定的排序;
8.4.2堆排序
实现过程：把序列按层次填入完全二叉树，调整位置使双亲大于或小于孩子，建立初始大根或小根堆，调整树根与最后一个叶子的位置，排除该叶子重新调整位置。
算法的最好时间是O(nlog2n);最坏时间是O(nlog2n);平均时间是O(nlog2n);是一种就地的不稳定排序;
8.5归并排序
实现过程：将初始序列分为2个一组，最后单数轮空，对每一组排序后作为一个单元，对2个单元排序，直到结束。
算法的最好时间是O(nlog2n);最坏时间是O(nlog2n);平均时间是O(nlog2n);辅助空间为O(n);是一种稳定排序;
8.6分配排序
8.6.1箱排序
实现过程：按关键字的取值范围确定箱子的个数，将序列按关键字放入箱中，输出非空箱的关键字。
在桶内分配和收集，及对各桶进行插入排序的时间为O(n),算法的期望时间是O(n),最坏时间是O(n^2)。
8.6.2基数排序
实现过程：按基数设置箱子，对关键字从低位到高位依次进行箱排序。
算法的最好时间是O(d*n+d*rd);最坏时间是O(d*n+d*rd);平均时间是O(d*n+d*rd);辅助空间O(n+rd);是一种稳定排序;
8.7各种内部排序方法的比较和选择
按平均时间复杂度分为：
1) 平方阶排序：直接插入、直接选择、冒泡排序;
2) 线性对数阶：快速排序、堆排序、归并排序;
3) 指数阶：希尔排序;
4) 线性阶：箱排序、基数排序。
选择合适排序方法的因素：1)待排序的记录数;2)记录的大小;3)关键字的结构和初始状态;4)对稳定性的要求;5)语言工具的条件;6)存储结构;7)时间和辅助空间复杂度。
结论：
1) 若规模较小可采用直接插入或直接选择排序;
2) 若文件初始状态基本有序可采用直接插入、冒泡或随机快速排序;
3) 若规模较大可采用快速排序、堆排序或归并排序;
4) 任何借助于比较的排序，至少需要O(nlog2n)的时间，箱排序和基数排序只适用于有明显结构特征的关键字;
5) 有的语言没有提供指针及递归，使归并、快速、基数排序算法复杂;
6) 记录规模较大时为避免大量移动记录可用链表作为存储结构，如插入、归并、基数排序，但快速、堆排序在链表上难以实现，可提取关键字建立索引表，然后对索引表排序。
附二:
第八章排序
*************************************************************************************
记录中可用某一项来标识一个记录，则称为关键字项，该数据项的值称为关键字。
排序是使文件中的记录按关键字递增(或递减)次序排列起来。·基本操作：比较关键字大小;改变指向记录的指针或移动记录。
·存储结构：顺序结构、链表结构、索引结构。
经过排序后这些具有相同关键字的记录之间的相对次序保持不变,则称这种排序方法是稳定的，否则排序算法是不稳定的。
排序过程中不涉及数据的内、外存交换则称之为"内部排序"(内排序)，反之，若存在数据的内外存交换，则称之为外排序。
内部排序方法可分五类：插入排序、选择排序、交换排序、归并排序和分配排序。
评价排序算法好坏的标准主要有两条：执行时间和所需的辅助空间，另外算法的复杂程序也是要考虑的一个因素。
*************************************************************************************
插入排序：·直接插入排序： ·逐个向前插入到合适位置。
·哨兵(监视哨)有两个作用： ·作为临变量存放R[i]
·是在查找循环中用来监视下标变量j是否越界。
·直接插入排序是就地的稳定排序。时间复杂度为O(n^2)，比较次数为(n+2)(n-1)/2;移动次数为(n+4)(n-1)/2;
·希尔排序： ·等间隔的数据比较并按要求顺序排列，最后间隔为1。
·希尔排序是就地的不稳定排序。时间复杂度为O(n^1.25)，比较次数为(n^1.25);移动次数为(1.6n^1.25);
交换排序：·冒泡排序：·自下向上确定最轻的一个。·自上向下确定最重的一个。·自下向上确定最轻的一个，后自上向下确定最重的一个。
·冒泡排序是就地的稳定排序。时间复杂度为O(n^2)，比较次数为n(n-1)/2;移动次数为3n(n-1)/2;
·快速排序：·以第一个元素为参考基准，设定、动两个指针，发生交换后指针交换位置，直到指针重合。重复直到排序完成。
·快速排序是非就地的不稳定排序。时间复杂度为O(nlog2n)，比较次数为n(n-1)/2;
选择排序：·直接选择排序： ·选择最小的放在比较区前。
·直接选择排序就地的不稳定排序。时间复杂度为O(n^2)。比较次数为n(n-1)/2;
·堆排序 ·建堆：按层次将数据填入完全二叉树，从int(n/2)处向前逐个调整位置。
·然后将树根与最后一个叶子交换值并断开与树的连接并重建堆，直到全断开。
·堆排序是就地不稳定的排序，时间复杂度为O(nlog2n)，不适宜于记录数较少的文件。。
归并排序： ·先两个一组排序，形成(n+1)/2组，再将两组并一组，直到剩下一组为止。
·归并排序是非就地稳定排序，时间复杂度是O(nlog2n),
分配排序：·箱排序： ·按关键字的取值范围确定箱子数，按关键字投入箱子，链接所有非空箱。
·箱排序的平均时间复杂度是线性的O(n).
·基数排序：·从低位到高位依次对关键字进行箱排序。
·基数排序是非就稳定的排序，时间复杂度是O(d*n+d*rd)。
各种排序方法的比较和选择： ·.待排序的记录数目n;n较大的要用时间复杂度为O(nlog2n)的排序方法;
·记录的大小(规模);记录大最好用链表作为存储结构，而快速排序和堆排序在链表上难于实现;
·关键字的结构及其初始状态;
·对稳定性的要求;
·语言工具的条件;
·存储结构;
·时间和辅助空间复杂度。
lishixin/Article/program/sjjg/201311/23750
❺ 数据结构课设总结
我正好在做课设，我把我的总结给你。
数据结构是计算机程序设计的重要理论技术基础，它不仅是计算机科学的核心课程，而且也已经成为其他理工专业的热门选修课。随着高级语言的发展，数据结构在计算机的研究和应用中已展现出强大的生命力，它兼顾了诸多高级语言的特点，是一种典型的结构化程序设计语言，它处理能力强，使用灵活方便握握，应用面广，具有良好的可移植性。
紧张的两周数据结构实训很快就过去了，通过这两周的实践学习，不仅使我们巩固了以前的知识并在此基础上还对数据结构的特点和算法有了更深的了解，使我们在这门课程的实际应用上也有了一个提高。
首先这两周的学习，使我们在巩固了原有的理论知识上，又培养了灵活运用和组合集成所学过知识及技能来分析、解决实际问题的能力，使我们体会到自身知识和能力在实际中的应用和发挥。其次，它激发了我们创新意识，开发创造的能力和培养沟通能力。另外，让我们进一步熟悉了数据结构的设计应用。每一处编码都是在反复的熟悉数据结构的结构特性，及其语法、函数和程序设计思想的过程，对我们数据结构的学习和提高很有益处，并且使我们明白了程序设计过程，如解决一些实际问题，从解决实际问题的角度，我们可以这样来看：第一要了解这个问题的基本要求，即输入、输出、完成从输入到输出的要求是什么；第二，从问题的要害入手，从前到后的解决问题的每个方面，即从输入开始入手，着重考虑如何从输入导出输出，在这个过程中，可确定所需的数据结构的基本类型——线性表、栈、队列、串、数组、广义表、树和二叉树以及图等，然后确定处理过程——算法，通过在编译环境中的编译与调试，可到最终的程序。最后，在这次的实训过程中，我们深刻的认识到了自己在学习方面的不足之处，我知道我还有太多的基本的思想没有真正的理解，当然我们不会灰心，我们会在以后的日子里努力弥补我们的不足。
在两周的实训中，我们也体会到了团队合作的重要性，从最初的查阅资料到最后的程序的成功运行，我们组有过山穷水尽的困惑；有过柳暗花明的惊喜；有过唇枪舌剑的辩论；有过相互鼓励的安慰。两个礼拜的时间我们经历了很多，也收获禅皮改了很多。与其说这次的实训是体贺判力与脑力的作业，不如说它是合作精神和毅力的考验。经过这次课程设计，我们不仅学到了很多知识和技能，更重要的是我们学会了如何运用所学知识去解决实际问题。
总之，两个礼拜的课程设计让我们受益匪浅。我们深深认识到，要学好一门学科，没有刻苦钻研的精神是不行的，只有在不断的尝试中，经历失败，从失败中总结经验，然后再不断的尝试，才能获得成功。
❻ 数据结构学的到底是什么,和算法的关系
本人乃一个数据痴迷者,在计算机的道路上,也是一个数据结构的痴迷者,现在大学里面和同学搞开发也痴迷于数据库,我就我个人的理解给你谈一谈: 首先,数据结构是一门计算机语言学的基础学科，它不属于任何一门语言，其体现的是几乎所有标准语言的算法的思想。 上面的概念有一些模糊，我们现在来指碰灶具体说一说，相信你门的数据结构使用的是一门具体的语言比如C/C++语言来说明，那是为了辅助的学习数据结构，而数据结构本身不属于任何语言（相信你把书上的程序敲到电脑里面是不能通过的吧，其只是描述了过程，要调试程序，还需要修改和增加一些东西）。你们的书上开始应该在讲究数据的物理存储结构/逻辑存储结构等概念，说明数据结构首先就是“数据的结构”，在内存上的存储方式，就是物理的存储结构，在程序使用人员的思想上它是逻辑的，比如： 你们在C/C++中学习到链表，那么链表是什么一个概念，你们使用指针制向下一个结点的首地址，让他们串联起来，形成一个接一个的结点，就像显示生活中的火车一样。而这只是对于程序员的概念，但是在内存中存储的方式是怎样的那？对于你程序员来说这是“透明”的，其内部分配空间在那里，都是随机的，而内存中也没有一个又一根的线将他们串联起来，所以，这是一个物理与逻辑的概念，对于我们程序员只需要知道这些就可以了，而我们主要要研究的是“逻辑结构”。 我可以给你一个我自己总结的一个概念：所有的算唯扮法必须基于数据结构生存。也就是说，我们对于任何算法的编写，必须依赖一个已经存在的数据结构来对它进行操作，数据结构成为算法的操作对象，这也是为什么算法和数据结构两门分类不分家的概念，算法在没有数据结构的情况下，没有任何存在的意义；而数据结构没有算法就等于是一个尸体而没有灵魂。估计这个对于算法的初学者可能有点晕，我们在具体的说一些东西吧： 我们在数据结构中最简单的是什么：我个人把书籍中线性表更加细化一层（这里是为了便于理解在这样说的）：单个元素，比如：int i;这个i就是一个数据结构，它是一个什么样的数据结构，就是一个类型为int的变量，我们可以对它进行加法/减法/乘法/除法/自加等等一系列操作，当然对于单个元素我们对它的数据结构和算法的研究没有什么意义，因为它本来就是原子的，某些具体运算上可能算法存在比较小的差异；而提升一个层次：就是我们的线性表（一般包含有：顺序表/链表）那么我们研究这样两种数据结构主要就是要研究它的什么东西那？一般我们主要研究他们以结构为单位（就是结点）的增加/删除/修改/检索（查询）四个操作（为什么有这样的操作，我在下面说到），我们一般把“增加/删除/修改”都把它称为更新，对于一个结点，若要进行更新一类的操作比如：删除，对于顺序表来说是使用下标访问方式吵渗，那么我们在删除了一个元素后需要将这个元素后的所有元素后的所有元素全部向前移动，这个时间是对于越长的顺序表，时间越长的，而对于链表，没有顺序的概念，其删除元素只需要将前一个结点的指针指向被删除点的下一个结点，将空间使用free()函数进行释放，还原给操作系统。当执行检索操作的时候，由于顺序表直接使用下标进行随机访问，而链表需要从头开始访问一一匹配才可以得到使用的元素，这个时间也是和链表的结点个数成正比的。所以我们每一种数据结构对于不同的算法会产生不同的效果，各自没有绝对的好，也没有绝对的不好，他们都有自己的应用价值和方式；这样我们就可以在实际的项目开发中，对于内部的算法时间和空间以及项目所能提供的硬件能力进行综合评估，以让自己的算法能够更加好。 （在这里只提到了基于数据结构的一个方面就是：速度，其实算法的要素还应该包括：稳定性、健壮性、正确性、有穷性、可理解性、有输入和输出等等） 为什么要以结点方式进行这些乱七八糟的操作那？首先明确一个概念就是：对于过程化程序设计语言所提供的都是一些基础第一信息，比如一些关键字/保留字/运算符/分界符。而我们需要用程序解决现实生活中的问题，比如我们要程序记录某公司人员的情况变化，那么人员这个数据类型，在程序设计语言中是没有的，那么我们需要对人员的内部信息定义（不可能完全，只是我们需要那些就定义那些），比如：年龄/性别/姓名/出生日期/民族/工作单位/职称/职务/工资状态等，那么就可以用一些C/C++语言描述了，如年龄我们就可以进行如下定义: int age;/*age变量，表示人员公司人员的年龄*/ 同理进行其他的定义，我们用结构体或类把他们封装成自定义数据类型或类的形式，这样用他们定义的就是一个人的对象的了，它内部包含了很多的模板数据了。 我就我个人的经历估计的代码量应该10000以内的（我个人的经理：只是建议，从你的第一行代码开始算，不论程序正确与否，不论那一门语言，作为一个标准程序员需要十万行的代码的功底（这个是我在大学二年级感觉有一定时候的大致数据，不一定适合其他人），而十万行代码功底一般需要四门基础远支撑，若老师没有教，可以自学一些语言）。
❼ 牛掰！阿里大佬刷了四年LeetCode才总结出来的数据结构和算法手册
前几天和一个粉丝首扒聊面试，他说去年同时拿到了阿里和网易的 offer，最后选择了阿里。
我了解了下他的面试过程，就一点，无论拍敏是网易还是阿里的面试，其中一个占比非常大的权重就是 数据结构与算法。
其实现在不管面试什么岗位，前端也好，后端也罢，都必须考察算法，这关过了，基本上就没太大问题了。他告诉我，那些大厂认为，你能把最基本、最核心的算法都能搞定，那么那些编程语言啊、不同的应用方向，开发框架啊对你来说一定不是难事。
那么，如何才能更好地啃下算法这块骨头呢？
无他，就是靠自己的毅力以及决心。一天不行，一个月；一个月不行，一年；有决心的人，啥学历、智商或者资历，那些都是借口。
不过除了毅力和决心之外， 其实学习还是有效率之差的。
互联网时代，其实网上有很多免费学习资料，只要你用点心，也总能找到学习资料，今天团长就在这里分享一份 阿里 大佬的leetcode上面刷了四年题总结的数据结构和算法面试解析手册！袭芹枝
❽ 【请教】关于数据结构
一楼说的不错。
从我参加工作角度和大学期间ACM经历而言，我想要强调两点。
第一，算法和数据结构不要分开来看。国外最着名的数据结构的教材《数据结构与算法分析——c语言描述》和最有名的算法类书籍《算法导论》都强调，数据结构和算法乃一脉相承之物。学好了数据结构，对后续专门的算法设计方法的学习是有巨大帮助的。比如，在ACM中我们经常用到各种搜索，诸如剪枝法，深度搜索，广度搜索等等，这里如果你没有对二叉树的理解，何谈这些算法的设计？所以，《算法设计》是建立在《数据结构》之上的更进一层的学习和研究，肯定比数据结构难（比如我认为动态规划就很复杂，主要是状态转移方程难找~），而且《算法设计》有些东西数据结构不一定讲授，内容肯定更多。因而，算法设计提供了更多复杂的高层的算法！这点不错带嫌~
第二点，想成为编程牛人，没错，算法设计类课程必学！无论ACM拿奖选手还是google 招聘的牛人都是算法高手！但是千万不要以为算法学好了，你就能靠编程吃饭了~
大学期间学算法主要是培养你的思维和相关意识。如果你真的进派高入iT这一行，你就会发现，算法其实也没“那么重要”~这也是我不太同意一楼的说法的地方~所谓“软件设计思想”绝非算法就可以概括，软件架构和开发综合考虑的因素太多太多~而且真正的软件项目，会更多的用到各种框架平台。如今开源资源丰富，几乎你碰到某个难题，到网上一搜，发现已经有更好的算法给你使用了~再花精力，自己写个算法，效率不一定高，而且容易出错~
所以说，在软件开发这一行，更多的是看你积木搭得好不好，而不在于你会不会自己做积木块~
如果楼主想以编程吃饭的话，有意识的参加实际项目也许更好！
但是一定要明确：上面说算法在工作中没有太大用处，是从很实际很现实的角度说的~但是，算法设计的思维对你今后蠢羡手的生涯会有这潜移默化的影响。一般而言，算法学得好的人，写起程序来逻辑性都会更强，效率更高！所以千万不要荒废对算法的学习！
最后总结一句，算法重要，必学！但不要神话算法的作用。
PS:算法这个词汇一般说来就是你所说的什么贪心法，动态规划，分治等等。但是精确的说，算法不仅仅如此，如果你学3D图形学，你就会知道在图形学中，算法=数学，算法=微分几何，计算方法等等。。。。大学期间学的算法只是通用意义上的离散性质较强的算法，等你到了计算机的具体的领域，算法就会千差万别~
❾ 计算机二级公共基础知识是什么啊
《计算机二级-公共基础》网络网盘资源免费下载
链接: https://pan..com/s/1juX-rK_zhvGXNXQrq-qvew
计算机二级-公共基础|第一章|第四章|第三章|第二章|第二章-程明升序设计基础（一）.mp4|第二章-程序设计基础（二）.mp4|第三章软件工程基础软件工明老程基础（七）.mp4|第三章软件工程基础（五）.mp4|第三章软件工程基础激槐升（四）.mp4|第三章-软件工程基础（一）.mp4|第三章-软件工程基础（三）.mp4|第三章-软件工程基础（六）.mp4|第三章-软件工程基础（二）.mp4|第四章数据库设计基础（二）.mp4
❿ 数据结构知识点总结
线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。是随机存取的顺序存储结构。顺序存储指内存地址是一块的，随机存取指访问时可以按下标随机访问，存储和存取是不一样的。
用一组任意的存储单元来依次存放线性表的结点，这组存储单元即可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。链表中结点的逻辑次序和物孙毕帆理次序不一定相同。
队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。先进先出。
串(String)是零个或多个字符组成的有限序列。长度为零的串称为空串(Empty String)，它不包含任何字符。通常将仅由一个或多个空格组成的串称为空白串(Blank String) 注意：空串和空白串的不同，例如“ ”和“”分别表示长度为1的空白串和长度为0的空串。
串的表示和实现
数组和广义表可看成是一种特殊的线性表，其特殊在于: 表中的元素本身也是一种线性表。内存连续。根据下标在O(1)时间读/写任何元素。
二维数组，多维数组，广义表，树，图都属于非线性结构
数组
数组的顺序存储：行优先顺序；列优先顺序。数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构。
关联数组(Associative Array)，又称映射（Map）、字典（ Dictionary）是一个抽象的数据结构，它包含着类似于(键，值)的有序对。 不是线性表。
广义表
广义表（Lists，又称列表）是线性表的推广。广义表是n(n≥0)个元素a1,a2,a3,…,an的有限序列，其中ai或者是原子项，或者是一个广义表。若广义表LS（n>=1)非空，则a1是LS的表头，其余元素组成的表(a2,…an)称为LS的表尾。广义表的元素可以是广义表，也可以是原子，广义表的元素也可以为空。表尾是指除去表头后剩下的元素组成的表，表头可以为表或单元素值。所以表尾不可以是单个元素值。
三个结论
考点
一种非线性结构。树是递归结构，在树的定义中又用到了树的概念。
基本术语
1.树结点：包含一个数据元素及若干指向子树的分支；
2.孩子结点：结点的子树的根称为该结点的孩子；
3.双亲结点：B结点是A结点的孩子，则A结点是B结点的双亲；
4.兄弟结点：同一双亲的孩子结点；
5.堂兄结点：同一层上结点；
6.结点层次：根结点的层定义为1；根的孩子为第二层结点，依此类推；
7.树的高（深）度：树中最大的结点层
8.结点的度：结点子树的个数，就是有几个孩子
9.树的度： 树中最大的结点度。
10.叶子结点：也叫终端结点，是度为0的结点；
11.分枝结点：度不为0的结点（非终端结点）；
12.森林：互不相交的树集合；
13.有序树：子树有序的树，如：家族树；
14.无序树：不考虑子树的顺序；
二叉树
二叉树可以为空。二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。
注意区分： 二叉树、二叉查找树/二叉排序数念树/二叉搜索树、二叉平衡(查找)树
二叉树遍历
先序遍历：根左右
中序遍历：左根右
后序遍历：左右根
层次遍历：一维数组存储二叉树，总是以层次遍历的顺序存储结点。层次遍历应该借助队列。
二叉树性质
1.在二叉树的第 i 层上至多有2的i次幂-1个结点
2.深度为 k 的二叉树上至多含 2的k次幂-1 个结点（k≥1）
3.树与转换后的二叉树的关系：转则雹换后的二叉树的先序对应树的先序遍历；转换后的二叉树的中序对应树的后序遍历
一些概念
1.路径：从一个祖先结点到子孙结点之间的分支构成这两个结点间的路径；
2.路径长度：路径上的分支数目称为路径长度；
3.树的路径长度：从根到每个结点的路径长度之和。
4.结点的权：根据应用的需要可以给树的结点赋权值；
5.结点的带权路径长度：从根到该结点的路径长度与该结点权的乘积；
6.树的带权路径长度=树中所有叶子结点的带权路径之和；通常记作 WPL=∑wi×li
7.哈夫曼树：假设有n个权值(w1, w2, … , wn)，构造有n个叶子结点的二叉树，每个叶子结点有一个 wi作为它的权值。则带权路径长度最小的二叉树称为哈夫曼树。最优二叉树。
图搜索->形成搜索树
1.穷举法
2.贪心法。多步决策，每步选择使得构成一个问题的可能解，同时满足目标函数
3.回溯法，根据题意，选取度量标准，然后将可能的选择方法按度量标准所要求顺序排好，每次处理一个量，得到该意义下的最优解的分解处理
无向图
1.回路或环：第一个顶点和最后一个顶点相同的路径。
2.简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路
3.连通：顶点v至v’ 之间有路径存在
4.连通图：无向图图 G 的任意两点之间都是连通的，则称G是连通图。
5.连通分量：极大连通子图，子图中包含的顶点个数极大
6.所有顶点度的和必须为偶数
有向图
1.回路或环：第一个顶点和最后一个顶点相同的路径。
2.简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。
3.连通：顶点v至v’之间有路径存在
4.强连通图：有向图G的任意两点之间都是连通的，则称G是强连通图。各个顶点间均可达。
5.强连通分量：极大连通子图
6.有向图顶点的度是顶点的入度与出度之和。邻接矩阵中第V行中的1的个数是V的出度
7.生成树：极小连通子图。包含图的所有n个结点，但只含图的n-1条边。在生成树中添加一条边之后，必定会形成回路或环。
8.完全图：有 n(n-1)/2 条边的无向图。其中n是结点个数。必定是连通图。
9.有向完全图：有n(n-1)条边的有向图。其中n是结点个数。每两个顶点之间都有两条方向相反的边连接的图。
10.一个无向图 G=(V,E) 是连通的，那么边的数目大于等于顶点的数目减一：|E|>=|V|-1，而反之不成立。如果 G=(V,E) 是有向图，那么它是强连通图的必要条件是边的数目大于等于顶点的数目：|E|>=|V|，而反之不成立。没有回路的无向图是连通的当且仅当它是树，即等价于：|E|=|V|-1。
图的邻接矩阵和邻接表
1.邻接矩阵和加权邻接矩阵
深度优先搜索利用栈
深度优先遍历类似于树的先序遍历，是树的先序遍历的推广
广度优先遍历
图的广度优先遍历就类似于树的层序遍历
每次遍历一个连通图将图的边分成遍历所经过的边和没有经过的边两部分，将遍历经过的边同图的顶点构成一个子图，该子图称为生成树。因此有DFS生成树和BFS生成树。
生成树是连通图的极小子图，有n个顶点的连通图的生成树必定有n-1条边,在生成树中任意增加一条边，必定产生回路。若砍去它的一条边，就会把生成树变成非连通子图
最小生成树：生成树中边的权值(代价)之和最小的树。最小生成树问题是构造连通网的最小代价生成树。
Kruskal算法 ：令最小生成树集合T初始状态为空，在有n个顶点的图中选取权值最小的边并从图中删去，若该边加到T中有回路则丢弃，否则留在T中；依次类推，知道T中有n-1条边为止
Prim算法： 它的基本思想是以顶点为主导地位，从起始顶点出发，通过选择当前可用的最小权值边把顶点加入到生成树当中来：
1.从连通网络N={V,E}中的某一顶点U0出发，选择与它关联的具有最小权值的边（U0,V）,将其顶点加入到生成树的顶点集合U中。
2.以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(U,V),把它的顶点加入到集合U中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合U中为止。
Prim算法，Kruskal算法和Dijkstra算法都属于贪心算法
Dijkstra算法适用于边权值为正的情况，如果边权值为负数就才用另一种最短路算法Bellman-Ford算法。该算法是指从单个源点到各个结点的最短路，该算法适用于有向图和无向图。复杂度O(n^2)
Dijkstra算法图文详解
若从一个连通图中删去任何一个顶点及其相关联的边，它仍为一个连通图的话，则该连通图被称为 重（双）连通图。
若连通图中的某个顶点和其相关联的边被删去之后，该连通图被分割成两个或两个以上的连通分量，则称此顶点为 关节点。
没有关节点的连通图称为双连通图
1.生成树的根结点，有两个或两个以上的分支，则此顶点(生成树的根)必为关节点；
2.对生成树上的任意一个非叶“顶点”，若其某棵子树中的所有“顶点”没有和其祖先相通的回边，则该“顶点”必为关节点
拓扑排序。在用邻接表表示图时,对有n个顶点和e条弧的有向图而言时间复杂度为O(n+e)。一个有向图能被拓扑排序的充要条件就是它是一个有向无环图。
AOV网(Activity On Vertex)：用顶点表示活动，边表示活动的优先关系的有向图称为AOV网。AOV网中不允许有回路，这意味着某项活动以自己为先决条件。
拓扑有序序列：把AOV网络中各顶点按照它们相互之间的优先关系排列一个线性序列的过程。若vi是vj前驱，则vi一定在vj之前；对于没有优先关系的点，顺序任意。
拓扑排序：对AOV网络中顶点构造拓扑有序序列的过程。方法：
采用 深度优先搜索 或者 拓扑排序 算法可以判断出一个有向图中是否有环（回路）。
深度优先搜索只要在其中记录下搜索的节点数n，当n大于图中节点数时退出，并可以得出有回路。若有回路，则拓扑排序访问不到图中所有的节点，所以也可以得出回路。广度优先搜索过程中如果访问到一个已经访问过的节点，可能是多个节点指向这个节点，不一定是存在环。
拓扑算法描述 ：
AOE网：带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续时间。在工程上常用来表示工程进度计划。
常用哈希函数
1.直接寻址法。
2.数字分析法。
3.平方取中法。
4.折叠法。
5.除留余数法。
6.随机数法。
冲突解决
1.开放寻址法：当发生冲突时，形成一个探查序列，沿此序列逐个地址探查，知道找到一个空位置，将发生冲突的记录放到该地址中。即Hi=(H(key)+di) % m，i=1,2,……k(k<=m-1)，H(key)哈希函数，m哈希表长，di增量序列。
2.链地址法：将所有关键字为同义词的记录存储在一个单链表中，并用一维数组存放头指针。
3.设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到Hash表中需要做n (n-1)/2次线性探测。如果使用二次探测再散列法将这n个关键字存入哈希表，至少要进行n (n+1)/2次探测
4.Hash查找效率：装填因子=表中记录数/表容量
5.开哈希表——链地址法；闭哈希表——开放地址法
B树的查找
时间复杂度O(logn)
B树的插入
例：用1，2，6，7，11，4，8，13，10，5，17，9，16，20，3，12，14，18，19，15构建5阶B树
因为构建5阶的B树，所以每个节点的关键字个数范围为[2,4]
插入11时，该节点的关键字个数超出范围，进行分裂
之后直接插入4，8，13
当插入10时，节点关键字个数再次超出范围
将子节点分裂
直接插入5，17，9，16，插入20
关键字个数超出范围，进行分裂
继续插入3
关键字个数超出范围，进行分裂
继续插入15
关键个数超出范围，进行分裂
这时候根节点关键字个数也超出范围，继续分裂
B+的优点
1.单一节点存储更多的元素，使得查询的IO次数更少。
2.所有查询都要查询叶到叶子节点，查询更加稳定
3.所有叶子节点形成有序链表，便于范围查询。