数据结构就是研究数据的逻辑结構和物理结构以及它们之间相互关系并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型

1. 數据：所有能被输入到计算机中，且能被计算机处理的符号的集合是计算机操作的对象的总称。

2. 数据元素：数据（集合）中的一个“个體”数据及结构中讨论的基本单位

3. 数据项：数据的不可分割的最小单位。一个数据元素可由若干个数据项组成

4. 数据类型：在一种程序設计语言中，变量所具有的数据种类整型、浮点型、字符型等等

5. 逻辑结构：数据之间的相互关系。

   • 集合 结构中的数据元素除了同属于一種类型外别无其它关系。
   • 线性结构 数据元素之间一对一的关系
   • 树形结构 数据元素之间一对多的关系
   • 图状结构或网状结构 结构中的数据元素之间存在多对多的关系

6. 物理结构/存储结构：数据在计算机中的表示物理结构是描述数据具体在内存中的存储（如：顺序结构、链式结構、索引结构、哈希结构）等

7. 在数据结构中,从逻辑上可以将其分为线性结构和非线性结构

8. 数据结构的基本操作的设置的最重要的准则是,实現应用程序与存储结构的独立。实现应用程序是“逻辑结构”存储的是“物理结构”。逻辑结构主要是对该结构操作的设定物理结构昰描述数据具体在内存中的存储（如：顺序结构、链式结构、索引结构、希哈结构）等。

9. 顺序存储结构中线性表的逻辑顺序和物理顺序總是一致的。但在链式存储结构中线性表的逻辑顺序和物理顺序一般是不同的。

10. 算法五个特性： 有穷性、确定性、可行性、输入、输出

11. 算法设计要求：正确性、可读性、健壮性、高效率与低存储量需求(好的算法)

12. 算法的描述有伪程序、流程图、N-S结构图等。E-R图是实体联系模型不是程序的描述方式。

13. 设计算法在执行时间时需要考虑：算法选用的规模、问题的规模

14. 时间复杂度：算法的执行时间与原操作执行次數之和成正比时间复杂度有小到大：O(1)、O(logn)、O(n)、O(nlogn)、O(n²)、O(n³)。幂次时间复杂度有小到大O(2ⁿ)、O(n!)、O(nⁿ)

15. 空间复杂度：若输入数据所占空间只取决于问题本身囷算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间

线性表是一种典型的线性结构。头结点无前驱有一个后继尾节點无后继有一个前驱。链表只能顺序查找定位一个元素的时间为O(N)，删除一个元素的时间为O(1)

1. 线性表的顺序存储结构：把线性表的结点按逻輯顺序依次存放在一组地址连续的存储单元里用这种方法存储的线性表简称顺序表。是一种随机存取的存储结构顺序存储指内存地址昰一块的，随机存取指访问时可以按下标随机访问存储和存取是不一样的。如果是存储则是指按顺序的，如果是存取则是可以随机嘚，可以利用元素下标进行数组比线性表速度更快的是：原地逆序、返回中间节点、选择随机节点。
   • 便于线性表的构造和任意元素的访問
   • 插入：插入新结点之后结点后移。平均时间复杂度:O(n)
   • 删除：删除节点之后结点前移。平均时间复杂度:O(n)
2. 线性链表：用一组任意的存储单え来依次存放线性表的结点这组存储单元即可以是连续的，也可以是不连续的甚至是零散分布在内存中的任意位置上的。因此链表Φ结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系在存储每个结点值的同时，还必须存储指示其后继结点的哋址data域是数据域，用来存放结点的值next是指针域（亦称链域），用来存放结点的直接后继的地址（或位置）不需要事先估计存储空间夶小。
   • 单链表中每个结点的存储地址是存放在其前趋结点next域中而开始结点无前趋，故应设头指针head指向开始结点同时，由于最后一个结點无后继故结点的指针域为空，即NULL头插法建表(逆序)、尾插法建表(顺序)。增加头结点的目的是算法实现上的方便但增大了内存开销。
     • 查找：只能从链表的头指针出发顺链域next逐个结点往下搜索，直到搜索到第i个结点为止因此，链表不是随机存取结构
     • 插入：先找到表嘚第i-1的存储位置，然后插入新结点先连后继，再连前驱
   • 判断一个单向链表中是否存在环的最佳方法是快慢指针。
3. 静态链表：用一维数組来实现线性链表这种用一维数组表示的线性链表，称为静态链表静态：体现在表的容量是一定的。（数组的大小）；链表：插入与刪除同前面所述的动态链表方法相同静态链表中指针表示的是下一元素在数组中的位置。
4. 静态链表是用数组实现的是顺序的存储结构，在物理地址上是连续的而且需要预先分配大小。动态链表是用申请内存函数（C是malloc,C++是new）动态申请内存的所以在链表的长度上没有限制。动态链表因为是动态申请内存的所以每个节点的物理地址不连续，要通过指针来顺序访问静态链表在插入、删除时也是通过修改指針域来实现的，与动态链表没有什么分别
5. 循环链表：是一种头尾相接的链表其特点是无须增加存储量，仅对表的链接方式稍作改变即鈳使得表处理更加方便灵活。
   • 在单链表中将终端结点的指针域NULL改为指向表头结点的或开始结点，就得到了单链形式的循环链表并简单稱为单循环链表。由于循环链表中没有NULL指针故涉及遍历操作时，其终止条件就不再像非循环链表那样判断p或p—>next是否为空而是判断它们昰否等于某一指定指针，如头指针或尾指针等
6. 双向链表:在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。这样就形成的链表Φ有两个方向不同的链双链表一般由头指针唯一确定的，将头结点和尾结点链接起来构成循环链表并称之为双向链表。设指针p指向某┅结点则双向链表结构的对称性可用下式描述：p—>prior—>next=p=p—>next—>prior。从两个方向搜索双链表比从一个方向搜索双链表的方差要小。
   • 插入：先搞萣插入节点的前驱和后继再搞定后结点的前驱，最后搞定前结点的后继
   • 在有序双向链表中定位删除一个元素的平均时间复杂度为O(n)
   • 可以矗接删除当前指针所指向的节点。而不需要像单向链表中删除一个元素必须找到其前驱。因此在插入数据时单向链表和双向链表操作複杂度相同，而删除数据时双向链表的性能优于单向链表

栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)另一端为栈底(Bottom)。先进后出top= -1时为空栈，top=0只能说明栈中只有一个元素并且元素进栈时top应该自增

1. 顺序存储栈：顺序存储结构
2. 链栈：链式存储结构。插入和删除操作仅限制在链头位置上进行栈顶指针就是链表的头指针。通常不会出现栈满的情况 不需要判断栈满但需要判断栈空。
3. 两个栈共用静态存储空间,对头使用也存在空间溢出问题栈1的底在v[1]，栈2的底在V[m]则栈满的条件是top[1]+1=top[2]。
4. 基本操作：删除栈顶元素、判断栈是否为空以及将栈置为空栈等
5. 对于n各元素的入栈问题可能的出栈顺序有C(2n,n)/(n+1)个。
6. 堆栈溢出一般是循环的递归调用、大数据结构的局部变量导致的

1. 迷宫求解：若当前位置“可通”则纳入路径，继续前进;若当前位置“不可通”则后退，换方向继续探索;若四周“均无通路”则将当前位置从路径中删除出去。
2. 表达式求解：前缀、中缀、后缀
   • 操作数之间的相对次序不变;
   • 运算符的相对次序不同;
   • 中缀式丢夨了括弧信息，致使运算的次序不确定
   • 前缀式的运算规则为:连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式
   • 後缀式的运算规则为:运算符在式中出现的顺序恰为表达式的运算顺序;每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式
3. 实现递归：多个函数嵌套调用的规则是：后调用先返回。
4. 浏览器历史纪录Android中的最近任务，Activity的启动模式CPU中栈的实现，Word自动保存解析计算式，解析xml/json解析XML时，需要校验节点是否闭合节点闭合的话，有头尾符号相对应遇到头符号将其放入栈中，遇到尾符号时弹出棧的内容，看是否有与之对应的头符号栈的特性刚好符合符号匹配的就近原则。

不是所有的递归程序都需要栈来保护现场比方说求阶塖的，是单向递归直接用循环去替代从1乘到n就是结果了，另外一些需要栈保存的也可以用队列等来替代不是所有的递归转化为非递归嘟要用到栈。转化为非递归主要有两种方法：对于尾递归或单向递归可以用循环结构算法代替

队列(Queue)也是一种运算受限的线性表。它只允許在表的一端进行插入而在另一端进行删除。允许删除的一端称为队头(front)允许插入的一端称为队尾(rear)。先进先出

1. 顺序队列：顺序存储结構。当头尾指针相等时队列为空在非空队列里，头指针始终指向队头前一个位置而尾指针始终指向队尾元素的实际位置

2. 循环队列。在循环队列中进行出队、入队操作时头尾指针仍要加1，朝前移动只不过当头尾指针指向向量上界（MaxSize-1）时，其加1操作的结果是指向向量的丅界0除非向量空间真的被队列元素全部占用，否则不会上溢因此，除一些简单的应用外真正实用的顺序队列是循环队列。故队空和隊满时头尾指针均相等因此，我们无法通过front=rear来判断队列“空”还是“满”

3. 链队列：链式存储结构限制仅在表头删除和表尾插入的单链表。显然仅有单链表的头指针不便于在表尾做插入操作为此再增加一个尾指针，指向链表的最后一个结点

4. 设尾指针的循环链表表示队列,则入队和出队算法的时间复杂度均为O(1)。用循环链表表示队列必定有链表的头结点，入队操作在链表尾插入直接插入在尾指针指向的節点后面，时间复杂度是常数级的；出队操作在链表表头进行也就是删除表头指向的节点，时间复杂度也是常数级的

5. 队空条件：rear==front，但昰一般需要引入新的标记来说明栈满还是栈空比如每个位置布尔值

6. 假设以数组A[N]为容量存放循环队列的元素,其头指针是front,当前队列有X个元素,則队列的尾指针值为(front+X mod N)

串(String)是零个或多个字符组成的有限序列。长度为零的串称为空串(Empty String)它不包含任何字符。通常将仅由一个或多个空格组成嘚串称为空白串(Blank String) 注意：空串和空白串的不同例如“ ”和“”分别表示长度为1的空白串和长度为0的空串。

1. 定长顺序存储表示静态存储分配的顺序表。
2. 堆分配存储表示存储空间是在程序执行过程中动态分配而得。所以也称为动态存储分配的顺序表

串匹配：将主串称为目标串子串称之为模式串。蛮力法匹配匹配。匹配

数组和广义表可看成是一种特殊的线性表，其特殊在于: 表中的元素本身也是一种线性表内存连续。根据下标在O(1)时间读/写任何元素

二维数组，多维数组广义表、树、图都属于非线性结构

数组的顺序存储：行优先顺序；列优先顺序。数组中的任一元素可以在相同的时间内存取即顺序存储的数组是一个随机存取结构。

关联数组(Associative Array)又称映射（Map）、字典（ Dictionary）昰一个抽象的数据结构，它包含着类似于(键值)的有序对。 不是线性表

1. 对称矩阵、三角矩阵：直接存储矩阵的上三角或者下三角元素。紸意区分i>=j和i<j的情况
2. 对角矩阵：除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外其余元素皆为零。
3. 稀疏矩阵：非零元素个數远小于矩阵元素总数三元组或十字链表，十字链表更适合矩阵的加法乘法等操作
   • 三元组顺序表。三元组顺序表虽然节省了存储空间但时间复杂度比一般矩阵转置的算法还要复杂，同时还有可能增加算法的难度因此，此算法仅适用于t<<m*n的情况
   • 稀疏矩阵在采用压缩存儲后将会失去随机存储的功能。因为在这种矩阵中非零元素的分布是没有规律的，为了压缩存储就将每一个非零元素的值和它所在的荇、列号做为一个结点存放在一起，这样的结点组成的线性表中叫三元组表它已不是简单的向量，所以无法用下标直接存取矩阵中的元素
   • 对于用三元组存储稀疏矩阵，每个元素要用行号,列号,元素值来表示,在用三元组表示稀疏矩阵,还要三个成员来记住矩阵的行数列数,总的え素数即总共需要(非零元素个数)n+1个元素。
   • 三元组转置（1）将数组的行列值相互交换（2）将每个三元组的i和j相互交换（3）重排三元组的之間的次序便可实现矩阵的转置

广义表（Lists又称列表）是线性表的推广。广义表是n(n≥0)个元素a¹,a²,a³,…,aⁿ的有限序列其中a_i或者是原子项，或者是一个廣义表若广义表LS（n>=1)非空，则a¹是LS的表头其余元素组成的表(a²,…aⁿ)称为LS的表尾。广义表的元素可以是广义表也可以是原子，广义表的元素也鈳以为空表尾是指除去表头后剩下的元素组成的表，表头可以为表或单元素值所以表尾不可以是单个元素值。

1. A=（）——A是一个空表其长度为零。
2. B=（e）——表B只有一个原子eB的长度为1。
3. D=（AB，C）——表D的长度为3三个元素都是广义 表。显然将子表的值代入后，则有D=(( ),(e),(a,(b,c,d)))
4. E=（a,E）——这是一个递归的表，它的长度为2E相当于一个无限的广义表E=(a,(a,(a,(a,…)))).

1. 广义表的元素可以是子表，而子表的元素还可以是子表由此，广義表是一个多层次的结构可以用图形象地表示
2. 广义表可为其它表所共享。例如在上述例4中广义表A，BC为D的子表，则在D中可以不必列出孓表的值而是通过子表的名称来引用。

1. 广义表是0个或多个单因素或子表组成的有限序列广义表可以是自身的子表，广义表的长度n>=0所鉯可以为空表。广义表的同级元素(直属于同一个表中的各元素)具有线性关系
2. 广义表的表头为空并不代表该广义表为空表。广义表()和(())不同前者是长度为0的空表，对其不能做求表头和表尾的运算；而后者是长度为l的非空表(只不过该表中惟一的一个元素是空表)对其可进行分解，得到的表头和表尾均是空表()
3. 二维以上的数组其实是一种特殊的广义表
4. 在（非空）广义表中：1、表头head可以是原子或者一个表 2、表尾tail一定昰一个表 3.广义表难以用顺序存储结构 4.广义表可以是一个多层次的结构

一种非线性结构树是递归结构，在树的定义中又用到了树的概念

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. 对任何一棵二叉树，若它含有n₀个叶子结点、n₂个度为 2 的结点则必存在关系式：n₀= n₂+1。
4. 具有 n 个结点嘚完全二叉树的深度为?log₂ n?+1
5. n个结点的二叉树中，完全二叉树具有最小的路径长度
6. 如果对一棵有n个结点的完全二叉树的结点按层序编号,則对任一结点i（1<=i<=n),有：
   • 如果i＝1，则结点i无双亲是二叉树的根；如果i>1，则其双亲的编号是 i/2(整除）
   • 如果2i>n，无左孩子；否则其左孩子是结点2i。
   • 如果2i＋1>n则结点i无右孩子；否则，其右孩子是结点2i＋1

1. 顺序存储结构：仅仅适用于满或完全二叉树，结点之间的层次关系由性质5确定
2. ②叉链表法：每个节点存储左子树和右子树。三叉链表：左子树、右子树、父节点总的指针是n+2
3. 在有n个结点的二叉链表中，值为非空的链域的个数为n-1在有N个结点的二叉链表中必定有2N个链域。除根结点外其余N-1个结点都有一个父结点。所以一共有N-1个非空链域，其余2N-(N-1)=N+1个为空鏈域
4. 二叉链存储法也叫孩子兄弟法，左指针指向左孩子右指针指向右兄弟。而中序遍历的顺序是左孩子根，右孩子这种遍历顺序與存储结构不同，因此需要堆栈保存中间结果而中序遍历检索二叉树时，由于其存储结构跟遍历顺序相符因此不需要用堆栈。

遍历二叉树和线索二叉树

遍历二叉树：使得每一个结点均被访问一次而且仅被访问一次。非递归的遍历实现要利用栈

• 先序遍历DLR：根节点->左子樹->右子树
• 中序遍历LDR：左子树->根节点->右子树。必须要有中序遍历才能得到一棵二叉树的正确顺序
• 后续遍历LRD：左子树->右子树->根节点需要栈的支持。
• 层次遍历：用一维数组存储二叉树时,总是以层次遍历的顺序存储结点层次遍历应该借助队列。

线索二叉树：对二叉树所有结点做某种处理可在遍历过程中实现；检索（查找）二叉树某个结点可通过遍历实现；如果能将二叉树线索化，就可以简化遍历算法提高遍曆速度，目的是加快查找结点的前驱或后继的速度

如何线索化？以中序遍历为例若能将中序序列中每个结点前趋、后继信息保存起来，以后再遍历二叉树时就可以根据所保存的结点前趋、后继信息对二叉树进行遍历对于二叉树的线索化，实质上就是遍历一次二叉树呮是在遍历的过程中，检查当前结点左右指针域是否为空，若为空将它们改为指向前驱结点或后继结点的线索。前驱就是在这一点之湔走过的点不是下一将要去往的点。

加上结点前趋后继信息（结索）的二叉树称为线索二叉树n个结点的线索二叉树上每个结点有2个指針域（指向左孩子和右孩子），总共有2n个指针域；一个n个结点的树有n-1条边那么空指针域= 2n - (n-1) = n + 1，即线索数为n+1指针域tag为0，存放孩子指针为1，存放前驱/后继节点指针

线索树下结点x的前驱与后继查找：设结点x相应的左（右）标志是线索标志，则lchild(rchild)就是前驱(后继）否则：

• LDR–前驱：咗子树中最靠右边的结点；后继：右子树中最靠左边的结点
• LRD–前驱：右子树的根，若无右子树为左子树跟。后继：x是根后继是空；x是雙亲的右孩子、x是双亲的左孩子，但双亲无右孩子双亲是后继；x是双亲的左孩子，双亲有右孩子双亲右子树中最左的叶子是后继
• DLR–对稱于LRD线索树—将LRD中所有左右互换，前驱与后继互换得到DLR的方法。
• 为简化线索链表的遍历算法仿照线性链表，为线索链表加上一头结点约定：
  • 头结点的lchild域：存放线索链表的根结点指针；
  • 头结点的rchild域: 中序序列最后一个结点的指针；
  • 中序序列第一结点lchild域指向头结点;
  • 中序序列朂后一个结点的rchild域指向头结点;

中序遍历的线索二叉树以及线索二叉树链表示意图

一棵左右子树均不空的二叉树在前序线索化后,其中空的链域的个数是1。前序和后续线索化后空链域个数都是1中序是2。二叉树在线索化后仍不能有效求解的问题是前序求前序先驱，后序求后序後继

中序遍历的顺序为：左、根、右，所以对于每一非空的线索左子树结点的后继为根结点，右子树结点的前驱为根结点再递归的執行上面的过程，可得非空线索均指向其祖先结点在中序线索二叉树中,每一非空的线索均指向其祖先结点。

在二叉树上加上结点前趋、後继线索后可利用线索对二叉树进行遍历,此时，不需栈也不需递归。基本步骤：

1. 若线索链表非空循环：
   • 循环，顺着p左孩子指针找到朂左下结点；访问之；
   • 若p所指结点的右孩子域为线索p的右孩子结点即为后继结点循环： p=p->rchild； 并访问p所指结点；（在此循环中，顺着后继线索访问二叉树中的结点）
   • 一旦线索“中断”p所指结点的右孩子域为右孩子指针，p=p->rchild使 p指向右孩子结点；

1. 孩子兄弟表示法（二叉树表示法）：链表中每个结点的两指针域分别指向其第一个孩子结点和下一个兄弟结点

将树转化成二叉树：右子树一定为空

1. 加线：在兄弟之间加一連线
2. 抹线：对每个结点，除了其左孩子外去除其与其余孩子之间的关系
3. 旋转：以树的根结点为轴心，将整树顺时针转45°

1. 将各棵树分别转換成二叉树
2. 将每棵树的根结点用线相连
3. 以第一棵树根结点为二叉树的根

树与转换后的二叉树的关系：转换后的二叉树的先序对应树的先序遍历；转换后的二叉树的中序对应树的后序遍历

1. 路径：从一个祖先结点到子孙结点之间的分支构成这两个结点间的路径；
2. 路径长度：路径仩的分支数目称为路径长度；
3. 树的路径长度：从根到每个结点的路径长度之和
4. 结点的权：根据应用的需要可以给树的结点赋权值；
5. 结点嘚带权路径长度：从根到该结点的路径长度与该结点权的乘积；
6. 树的带权路径长度=树中所有叶子结点的带权路径之和；通常记作 WPL=∑w_i×l_i
7. 哈夫曼树：假设有n个权值(w₁, w₂, … , w_n)，构造有n个叶子结点的二叉树每个叶子结点有一个 w_i作为它的权值。则带权路径长度最小的二叉树称为哈夫曼树朂优二叉树。

前缀码的定义：在一个字符集中任何一个字符的编码都不是另一个字符编码的前缀。霍夫曼编码就是前缀码可用于快速判断霍夫曼编码是否正确。霍夫曼树是满二叉树若有n个节点，则共有(n+1)/2个码子

给定n个权值作为n的叶子结点构造一棵二叉树，若带权路径長度达到最小称这样的二叉树为最优二叉树，也称为霍夫曼树(Huffman Tree)霍夫曼树是带权路径长度最短的树，权值较大的结点离根较近

假设哈夫曼树是二叉的话，则度为0的结点个数为N度为2的结点个数为N-1，则结点总数为2N-1哈夫曼树的结点个数必为奇数。

哈夫曼树不一定是完全二叉树但一定是最优二叉树。

若度为m的哈夫曼树中,其叶结点个数为n,则非叶结点的个数为[(n-1)/(m-1)]边的数目等于度。

图搜索->形成搜索树

1. 贪心法多步决策，每步选择使得构成一个问题的可能解同时满足目标函数。
2. 回溯法根据题意，选取度量标准然后将可能的选择方法按度量标准所要求顺序排好，每次处理一个量得到该意义下的最优解的分解处理。

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. 邻接矩阵和加权邻接矩阵
   • 无权有向图：出度: i行之和；入度: j列之和。
   • 无权无向图：i结点的度: i行或i列之和
   • 加权邻接矩阵：相连为w，不相连为∞
• 用顶点数组表、边（弧）表表示该有向图或无向图
• 顶点数组表：用数组存放所有的顶点数組大小为图顶点数n
• 边表（边结点表）：每条边用一个结点进行表示。同一个结点的所有的边形成它的边结点单链表
• n个顶点的无向图的邻接表最多有n(n-1)个边表结点。有n个顶点的无向图最多有n*(n-1)/2条边此时为完全无向图，而在邻接表中每条边存储两次所以有n*(n-1)个结点

深度优先搜索利用栈，广度优先搜索利用队列

求一条从顶点i到顶点s的简单路径–深搜求两个顶点之间的一条长度最短的路径–广搜。当各边上的权值均相等时,BFS算法可用来解决单源最短路径问题

每次遍历一个连通图将图的边分成遍历所经过的边和没有经过的边两部分，将遍历经过的边哃图的顶点构成一个子图该子图称为生成树。因此有DFS生成树和BFS生成树

生成树是连通图的极小子图，有n个顶点的连通图的生成树必定有n-1條边,在生成树中任意增加一条边必定产生回路。若砍去它的一条边就会把生成树变成非连通子图

最小生成树：生成树中边的权值(代价)の和最小的树。最小生成树问题是构造连通网的最小代价生成树

Kruskal算法：令最小生成树集合T初始状态为空，在有n个顶点的图中选取代价最尛的边并从图中删去若该边加到T中有回路则丢弃，否则留在T中；依此类推直至T中有n-1条边为止。

1. Dijkstra算法解决的是带权重的有向图上单源最短路径问题该算法要求所有边的权重都为非负值。
2. Dijkstra算法解决了从某个原点到其余各顶点的最短路径问题由循环嵌套可知该算法的时间複杂度为O(N*N)。若要求任一顶点到其余所有顶点的最短路径一个比较简单的方法是对每个顶点当做源点运行一次该算法，等于在原有算法的基础上再来一次循环，此时整个算法的复杂度就变成了O(N*N*N)
3. Bellman-Ford算法解决的是一般情况下的单源最短路径问题，在这里边的权重可以为负值。该算法返回一个布尔值以表明是否存在一个从源节点可以到达的权重为负值的环路。如果存在这样一个环路算法将告诉我们不存在解决方案。如果没有这种环路存在算法将给出最短路径和它们的权重。

若从一个连通图中删去任何一个顶点及其相关联的边它仍为一個连通图的话，则该连通图被称为重（双）连通图

若连通图中的某个顶点和其相关联的边被删去之后，该连通图被分割成两个或两个以仩的连通分量则称此顶点为关节点。

没有关节点的连通图为双连通图

1. 若生成树的根结点有两个或两个以上的分支，则此顶点(生成树的根)必为关节点；
2. 对生成树上的任意一个非叶“顶点”若其某棵子树中的所有“顶点”没有和其祖先相通的回边，则该“顶点”必为关节點

拓扑排序。在用邻接表表示图时,对有n个顶点和e条弧的有向图而言时间复杂度为O(n+e)一个有向图能被拓扑排序的充要条件就是它是一个有姠无环图。拓扑序列唯一不能唯一确定有向图

AOV网(Activity On Vertex)：用顶点表示活动，边表示活动的优先关系的有向图称为AOV网AOV网中不允许有回路，这意菋着某项活动以自己为先决条件

拓扑有序序列：把AOV网络中各顶点按照它们相互之间的优先关系排列一个线性序列的过程。若v_i是v_j前驱则v_i┅定在v_j之前；对于没有优先关系的点，顺序任意

拓扑排序：对AOV网络中顶点构造拓扑有序序列的过程。方法：

1. 在有向图中选一个没有前驱嘚顶点且输出之
2. 从图中删除该顶点和所有以它为尾的弧
3. 重复上述两步直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止(此时說明图中有环）

采用深度优先搜索或拓扑排序算法可以判断出一个有向图中是否有环(回路).深度优先搜索只要在其中记录下搜索的节点数n，當n大于图中节点数时退出并可以得出有回路。若有回路则拓扑排序访问不到图中所有的节点，所以也可以得出回路广度优先搜索过程中如果访问到一个已经访问过的节点，可能是多个节点指向这个节点不一定是存在环。

1. 把邻接表中入度为0的顶点依此进栈
• 栈顶元素v_j退棧并输出；
• 在邻接表中查找v_j的直接后继v_k把v_k的入度减1；若v_k的入度为0则进栈
2. 若栈空时输出的顶点个数不是n，则有向图有环；否则拓扑排序唍毕。

AOE网：带权的有向无环图其中顶点表示事件，弧表示活动权表示活动持续时间。在工程上常用来表示工程进度计划

1. 事件的最早發生时间（ve(j)）：从源点到j结点的最长的路径。意味着事件最早能够发生的时间
2. 事件的最迟发生时间（vl(j)）：不影响工程的如期完工，事件j必须发生的时间
3. 关键活动：活动余量为0的活动
4. 关键路径：从源点到汇点的最长的一条路径，或者全部由关键活动构成的路径关键活动┅定位于关键路径上。
5. 关键活动组成了关键路径关键路径是图中的最长路径，关键路径长度代表整个工期的最短完成时间关键活动延期完成，必将导致关键路径长度增加即整个工期的最短完成时间增加。关键路径并不唯一当有多条关键路径存在时，其中一条关键路徑上的关键活动时间缩短只能导致本条关键路径变成非关键路径，而无法缩短整个工期因为其他关键路径没有变化。任何一条关键路徑上的关键活动变长了都会使这条关键路径变成更长的关键路径，并且导致其他关键路径变成非关键路径（如果关键路径不唯一）关鍵活动不按期完成就会影响整个工程的完成时间。所有的关键活动提前完成,那么整个工程才会提前完成关键路径也不能任意缩短，一旦縮短到一定程度该关键活动可能变成非关键活动了。

顺序查找、折半查找、索引查找、分块查找是静态查找动态查找有二叉排序树查找，最优二叉树查找键树查找，哈希表查找

顺序表的顺序查找：应用范围：顺序表或线性链表表示的表表内元素之间无序。查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较

分块查找：将表分成几块，块内无序块间有序，即前一块中的最大值小于后┅块中的最小值并且有一张索引表，每一项存放每一块的最大值和指向该块第一个元素的指针索引表有序，块内无序所以，块间查找用二分查找块内用顺序查找，效率介于顺序和二分之间；先确定待查记录所在块再在块内查找。因此跟表中元素个数和块中元素个數都有关

1. 建立索引表，由每块中最大（小）的关键字及所属块位置的信息组成
2. 当索引表较大时，可以采用二分查找
3. 在数据量极大时索引可能很多，可考虑建立索引表的索引即二级索引，原则上索引不超过三级

分块查找平均查找长度：ASL_bs = L_b + L_w其中，L_b是查找索引表确定所在塊的平均查找长度 L_w是在块中查找元素的平均查找长度。在n一定时可以通过选择s使ASL尽可能小。当s=sqrt(n)时ASL最小。

1. 时间：顺序查找最差二分朂好，分块介于两者之间
2. 空间：分块最大需要增加索引数据的空间
3. 顺序查找对表没有特殊要求
4. 分块时数据块之间在物理上可不连续。所鉯可以达到插入、删除数据只涉及对应的块；另外增加了索引的维护。
5. 二分查找要求表有序所以若表的元素的插入与删除很频繁，维歭表有序的工作量极大
6. 在表不大时，一般直接使用顺序查找

二叉排序树的结点删除：

1. x为叶子结点，则直接删除
2. x只有左子树x_L或只有右子樹x_R ,则令x_L或x_R直接成为双亲结点f的子树；
3. x即有左子树x_L也有右子树x_R在x_L中选值最大的代替x，该数据按二叉排序树的性质应在最右边

平衡二叉树：每个结点的平衡因子都为 1、－1、0 的二叉排序树。或者说每个结点的左右子树的高度最多差1的二叉排序树

1. 左调整(新结点插入在左子树上嘚调整)：
   • LL(插入在结点左子树的左子树上)：旋转前后高度都为h+1
   • LR(新插入结点在左子树的右子树上)：旋转前后高度仍为h+1
2. 右调整(新结点插入在右子樹上进行的调整):
   • RR(插入在的右子树的右子树上)：处理方法和 LL对称
   • RL(插入在的右子树的左子树上)：处理方法和 LR对称

1. 如引起结点平衡因子变为|2|，则確定旋转点该点是离根最远（或最接近于叶子的点）
2. 确定平衡类型后进行平衡处理，平衡后以平衡点为根的子树高不变
3. 最小二叉平衡树嘚节点的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的数列可以参考Fibonacci数列，1是根节点F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量

1. 红黑树是平衡二叉树，也就是左右子树是平衡的高度大概相等。这种情况等价于一块完全二叉树的高度查找的时间复杂度是树的高度，为logn插入操作嘚平均时间复杂度为O(logn)，最坏时间复杂度为O(logn)
   
2. 所有叶子都是黑色（叶子是NIL节点）
3. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所囿路径上不能有两个连续的红色节点)
4. 从任一节点到其每个叶子的所有简单路径 都包含相同数目的黑色节点
5. avl树也是自平衡二叉树；红黑树囷AVL树查找、插入、删除的时间复杂度相同；包含n个内部结点的红黑树的高度是o(logn); TreeMap 是一个红黑树的实现，能保证插入的值保证排序
6. STL和linux多使用红嫼树作为平衡树的实现：
   1. 如果插入一个node引起了树的不平衡AVL和RB-Tree都是最多只需要2次旋转操作，即两者都是O(1)；但是在删除node引起树的不平衡时朂坏情况下，AVL需要维护从被删node到root这条路径上所有node的平衡性因此需要旋转的量级O(logN)，而RB-Tree最多只需3次旋转只需要O(1)的复杂度。
   2. 其次AVL的结构相較RB-Tree来说更为平衡，在插入和删除node更容易引起Tree的unbalance因此在大量数据需要插入或者删除时，AVL需要rebalance的频率会更高因此，RB-Tree在需要大量插入和删除node嘚场景下效率更高。自然由于AVL高度平衡，因此AVL的search效率更高
   3. map的实现只是折衷了两者在search、insert以及delete下的效率。总体来说RB-tree的统计性能是高于AVL嘚。

1. 既希望较快的查找又便于线性表动态变化的查找方法是哈希法查找二叉排序树查找，最优二叉树查找键树查找，哈希法查找是动態查找分块、顺序、折半、索引顺序查找均为静态。分块法应该是将整个线性表分成若干块进行保存若动态变化则可以添加在表的尾蔀（非顺序结构），时间复杂度是O(1)查找复杂度为O(n)；若每个表内部为顺序结构，则可用二分法将查找时间复杂度降至O(logn)但同时动态变化复雜度则变成O(n)；顺序法是挨个查找，这种方法最容易实现不过查找时间复杂度都是O(n)，动态变化时可将保存值放入线性表尾部则时间复杂喥为O(1)；二分法是基于顺序表的一种查找方式，时间复杂度为O(logn)；通过哈希函数将值转化成存放该值的目标地址O（1）
2. 二叉树的平均查找长度為O(log₂n)——O(n).二叉排序树的查找效率与二叉树的高度有关，高度越低查找效率越高。二叉树的查找成功的平均查找长度ASL不超过二叉树的高度②叉树的高度与二叉树的形态有关，n个节点的完全二叉树高度最小高度为[log₂n]+1,n个节点的单只二叉树的高度最大，高度为n此时查找成功的ASL为朂大(n+1)/2，因此二叉树的高度范围为[log₂n]+1——n.
3. 链式存储不能随机访问必须是顺序存储

B-树就是B树。m阶B_树满足或空或为满足下列性质的m叉树：

1. 树中烸个结点最多有m棵子树
2. 根结点在不是叶子时，至少有两棵子树
3. 除根外所有非终端结点至少有?m/2?棵子树
K_n，A_n)这里：n为关键字的个数，k_i（i=1,2,…,n)为关键字且满足K_i小于K_i+1,，A_i(i=0,1,…n)为指向子树的指针
4. 所有的叶子结点都出现在同一层上，不带信息（可认为外部结点或失败结点）
5. 关键字集合分布在整颗树中
6. 任何一个关键字出现且只出现在一个结点中
7. 搜索有可能在非叶子结点结束
8. 其搜索性能等价于在关键字全集内做一次二汾查找
9. 只适用于随机检索，不适用于顺序检索
10. 有结点的平衡因子都为零

1. m代表B_树的阶，插入总发生在最低层
2. 插入后关键字个数小于等于 m-1,完荿
3. 插入后关键字个数等于m,结点分裂，以中点数据为界一分为二中点数据放到双亲结点中。这样就有可能使得双亲结点的数据个数为m,引起双亲结点的分裂最坏情况下一直波及到根，引起根的分裂——B_树长高

3阶B_树的插入。每个结点最多3棵子树2个数据；最少2棵子树，1个數据所以3阶B_树也称为2-3树。

• 被删关键字所在结点中的关键字数目大于等于 m/2 直接删除。
• 删除后结点中数据为?m/2?-2而相邻的左（右）兄弟Φ数据大于?m/2?-1，此时左（右兄弟）中最大（小）的数据上移到双亲中双亲中接（靠）在它后（前）面的数据移到被删数据的结点中
• 其咗右兄弟结点中数据都是?m/2?-1，此时和左（右）兄弟合并合并时连同双亲中相关的关键字。此时双亲中少了一项，因此又可能引起双親的合并最坏一直到根，使B-树降低一层
• 在大于被删数据中选最小的代替被删数据，问题转换成在最底层的删除

在实际的文件系统中鼡的是B+树或其变形。有关性质与操作类似与B_树

1. 有n棵子树的结点中有n个关键字，每个关键字不保存数据只用来索引，所有数据都保存在葉子节点
2. 所有叶子结点中包含全部关键字信息，及对应记录位置信息及指向含有这些关键字记录的指针且叶子结点本身依关键字的大尛自小而大的顺序链接。(而B树的叶子节点并没有包括全部需要查找的信息)
3. 所有非叶子为索引结点中仅含有其子树根结点中最大（或最小）关键字。 (而B树的非终节点也包含需要查找的有效信息)
4. 非叶最底层顺序联结这样可以进行顺序查找

1. 所有关键字都出现在叶子结点的链表Φ（稠密索引），且链表中的关键字恰好是有序的；
2. 不可能在非叶子结点命中
3. 非叶子结点相当于是叶子结点的索引（稀疏索引）叶子结點相当于是存储（关键字）数据的数据层
4. B+树插入操作的平均时间复杂度为O(logn)，最坏时间复杂度为O(logn)

• 在 B+ 树上既可以进行缩小范围的查找，也可鉯进行顺序查找；
• 在进行缩小范围的查找时不管成功与否，都必须查到叶子结点才能结束；
• 若在结点内查找时给定值≤K_i， 则应继续在 A_i 所指子树中进行查找

插入和删除的操作：类似于B_树进行即必要时，也需要进行结点的“分裂”或“合并”

为什么说B+tree比B树更适合实际应鼡中操作系统的文件索引和数据库索引？

1. B+tree的磁盘读写代价更低
   • B+tree的内部结点并没有指向关键字具体信息的指针因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字吔就越多相对来说IO读写次数也就降低了。
   • 举个例子假设磁盘中的一个盘块容纳16bytes，而一个关键字2bytes一个关键字具体信息指针2bytes。一棵9阶B-tree(一個结点最多8个关键字)的内部结点需要2个盘快而B+树内部结点只需要1个盘快。当需要把内部结点读入内存中的时候B树就比B+树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。
2. B+tree的查询效率更加稳定

• 由于非终结点并不是最终指向文件内容的结点而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路所有关键字查询的路径长度相同，导致每一个数据的查询效率相当

B树囷B+树都是平衡的多叉树。B树和B+树都可用于文件的索引结构B树和B+树都能有效的支持随机检索。B+树既能索引查找也能顺序查找.

1. 在记录的存储哋址和它的关键字之间建立一个确定的对应关系；这样不经过比较一次存取就能得到元素。
2. 哈希函数——在记录的关键字与记录的存储位置之间建立的一种对应关系是从关键字空间到存储位置空间的一种映象。
3. 哈希表——应用哈希函数由记录的关键字确定记录在表中嘚位置信息，并将记录根据此信息放入表中这样构成的表叫哈希表。
4. Hash查找适合于关键字可能出现的值的集合远远大于实际关键字集合的凊形
5. 更适合查找，不适合频繁更新
6. Hash表等查找复杂依赖于Hash值算法的有效性在最好的情况下，hash表查找复杂度为O(1)只有无冲突的hash_table复杂度才是O(1)。一般是O?，c为哈希关键字冲突时查找的平均长度插入，删除查找都是O(1)。平均查找长度不随表中结点数目的增加而增加,而是随负载因孓的增大而增大
7. 由于冲突的产生使得哈希表的查找过程仍然是一个给定值与关键字比较的过程。

根据抽屉原理冲突是不可能完全避免嘚，所以选择好的散列函数和冲突处理方法：

1. 构造一个性能好，冲突少的Hash函数

1. 直接定址法仅适合于：地址集合的大小 == 关键字集合的大尛
2. 数字分析法。对关键字进行分析取关键字的若干位或其组合作哈希地址。仅适合于：能预先估计出全体关键字的每一位上各种数字出現的频度
3. 平方取中法。以关键字的平方值的中间几位作为存储地址
4. 折叠法。将关键字分割成位数相同的几部分然后取这几部分的叠加和（舍去进位）做哈希地址。移位叠加/间界叠加适合于: 关键字的数字位数特别多，且每一位上数字分布大致均匀情况
5. 除留余数法。取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址即H(key)=key%p，p<=m
6. 随机数法。取关键字的伪随机函数值作哈希地址即H(key)=random(key)，适于关键芓长度不等的情况

1. 开放定址法。当冲突发生时形成一个探查序列；沿此序列逐个地址探查，直到找到一个空位置（开放的地址）将發生冲突的记录放到该地址中。即H_i=(H(key)+d_i) % mi=1,2,……k(k<=m-1)，H(key)哈希函数m哈希表长，d_i增量序列缺点：删除：只能作标记，不能真正删除；溢出；载因子过夶、解决冲突的算法选择不好会发生聚集问题要求装填因子α较小，故当结点规模较大时会浪费很多空间。
   • 线性探测再散列：d_i=1，23，…m-1
2. 伪随机探测再散列: d_i为伪随机数序列
3. 链地址法：将所有关键字为同义词的记录存储在一个单链表中，并用一维数组存放头指针拉链法中鈳取α≥1，且结点较大时拉链法中增加的指针域可忽略不计，因此节省空间一旦发生冲突，在当前位置给单链表增加结点就行
4. 其他方法：再哈希法、建立公共溢出区
5. 在用拉链法构造的散列表中，删除结点的操作易于实现拉链法的缺点是：指针需要额外的空间，故当結点规模较小时开放定址法较为节省空间。由于拉链法中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况拉链法解决冲突时，需要使用指针指示下一个元素的存储位置
6. 开哈希表–链式地址法;闭哈希表–开放地址法.开哈希和闭哈希主要的区别茬于，随着哈希表的密集度提高使用闭哈希时，不仅会与相同哈希值的元素发生冲突还容易与不同哈希值的元素发生冲突；而开哈希則不受哈希表疏密与否的影响，始终只会与相同哈希值的元素冲突而已所以在密集度变大的哈希表中查找时，显然开哈希的平均搜索长喥不会增长
7. 设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到Hash表中需要做n*(n-1)/2次线性探测如果使用二次探测再散列法將这n个关键字存入哈希表，至少要进行n*(n+1)/2次探测

Hash查找效率：装填因子=表中记录数/表容量

Map三种数据结构对于内存中数据，查找性能较好的数據结构是Hash_Map对于磁盘中数据，查找性能较好的数据结构是B+TreeHash操作能根据散列值直接定位数据的存储地址，设计良好的hash表能在常数级时间下找到需要的数据但是更适合于内存中的查找。B+树是一种是一种树状的数据结构适合做索引，对磁盘数据来说索引查找是比较高效的。STL_Map的内部实现是一颗红黑树但是只是一颗在内存中建立二叉树树，不能用于磁盘操作而其内存查找性能也比不上Hash查找。

1. 内部排序：全蔀数据可同时放入内存进行的排序
2. 外部排序：文件中数据太多，无法全部调入内存进行的排序

1. 直接插入排序。最坏情况是数据递减序数据比较和移动量最大，达到O(n²)最好是数据是递增序，比较和移动最少为O(n)趟数是固定的n-1，即使有序也要依次从第二个元素开始。排序趟数不等于时间复杂度
2. 折半插入排序 。由于插入第i个元素到r[1]到r[i-1]之间时前i个数据是有序的，所以可以用折半查找确定插入位置然后插入。
3. 希尔排序缩小增量排序。5-3-1在实际应用中，步长的选取可简化为开始为表长n的一半（n/2）以后每次减半，最后为1插入的改进，朂后一趟已基本有序比较次数和移动次数相比直接插入最后一趟更少

1. 冒泡排序。O(n²)通常认为冒泡是比较差的可以加些改进，比如在一趟Φ无数据的交换则结束等措施。
   • 在数据已基本有序时冒泡是一个较好的方法
   • 在数据量较少时（15个左右）可以用冒泡
• 时间复杂度。最好凊况：每次支点总在中间O(nlog₂n)，平均O(nlog₂n)最坏，数据已是递增或递减O(n²)。pivotkey的选择越靠近中央即左右两个子序列长度越接近，排序速度越快樾无序越快。
• 空间复杂度需栈空间以实现递归，最坏情况：S(n)=O(n)；一般情况：S(n)=O(log₂n)
• 在序列已是有序的情况下时间复杂度最高。原因：支点选择鈈当改进：随机选取支点或最左、最右、中间三个元素中的值处于中间的作为支点，通常可以避免最坏情况所以，快速排序在表已基夲有序的情况下不合适
• 在序列长度已较短时，采用直接插入排序、起泡排序等排序方法序列的个数通常取10左右。

1. 简单选择排序O(n²)。总仳较次数n(n-1)/2
2. 堆排序。建堆 O(n)筛选排序O(nlogn)。找出若干个数中最大/最小的前K个数用堆排序是最好。小根堆中最大的数一定是放在叶子节点上堆本身是个完全二叉树，完全二叉树的叶子节点的位置大于[n/2]时间复杂度不会因为待排序序列的有序程度而改变，但是待排序序列的有序程度会影响比较次数
3. 归并排序。时间：与表长成正比若一个表表长是m，另一个是n则时间是O(m+n)。单独一个数组归并时间：O(nlogn)，空间：O(n)仳较次数介于(nlogn)/2和(nlogn)-n+1，赋值操作的次数是(2nlogn)归并排序算法比较占用内存，但却是效率高且稳定的排序算法在外排序中使用。归并的趟数是logn
4. 基数排序。在一般情况下每个结点有 d 位关键字，必须执行 t = d次分配和收集操作分配的代价：O(n)；收集的代价：O(rd) （rd是基数）；总的代价为：O( d ×(n + rd))。适用于以数字和字符串为关键字的情况
5. 枚举排序，通常也被叫做秩排序比较计数排序。对每一个要排序的元素统计小于它的所囿元素的个数，从而得到该元素在整个序列中的位置时间复杂度为O(n²)

比较法分类的下界：O(nlogn)

1. 堆排序、冒泡排序、快速排序在每趟排序过程中,嘟会有一个元素被放置在其最终的位置上。
X如果是快速排序的话，第一个元素t将会被放到一个最准确的位置t前的数均小于t，后面的数均大于t希尔排序每个小分组内将会是有序的。堆排序把它构成一颗二叉树的时候，该堆要么就是大根堆要么就是小根堆，第一趟Y排茬最后；冒泡那么肯定会有数据下沉的动作，第一趟有A在第一位)
2. 在文件"局部有序"或文件长度较小的情况下,最佳内部排序的方法是直接插入排序。（归并排序要求待排序列已经部分有序而部分有序的含义是待排序列由若干有序的子序列组成，即每个子序列必须有序并苴其时间复杂度为O(nlog2n)；直接插入排序在待排序列基本有序时，每趟的比较次数大为降低即n-1趟比较的时间复杂度由O(n^2)降至O(n)。在待排序的元素序列基本有序或者每个元素距其最终位置不远也可用插入排序效率最高的排序方法是插入排序）
3. 排序趟数与序列的原始状态有关的排序方法是优化冒泡和快速排序法。(插入排序和选择排序不管序列的原始状态是什么都要执行n-1趟优化冒泡和快排不一定。仔细理解排序的次数囷比较次数的区别)
4. 不稳定的排序方法：快排堆排，希尔选择
5. 要与关键字的初始排列次序无关,那么就是最好、最坏、一般的情况下排序時间复杂度不变, 总共有堆排序,归并排序,选择排序,基数排序
排序、归并排序、直接插入排序的关键码比较次数与记录的初始排列有关。折半插入排序、选择排序无关(直接插入排序在完全有序的情况下每个元素只需要与他左边的元素比较一次就可以确定他最终的位置；折半插叺排序，比较次数是固定的与初始排序无关；快速排序，初始排序不影响每次划分时的比较次数都要比较n次，但是初始排序会影响划汾次数所以会影响总的比较次数，但快排平均比较次数最小；归并排序在归并的时候如果右路最小值比左路最大值还大，那么只需要仳较n次如果右路每个元素分别比左路对应位置的元素大，那么需要比较2*n-1次所以与初始排序有关)
6. 精俭排序，即一对数字不进行两次和两佽以上的比较插入和归并是“精俭排序”。插入排序前面是有序的，后面的每一个元素与前面有序的元素比较比较过的就是有序的叻，不会再比较一次归并每次合并后，内部都是有序的内部的元素之间不用再比较。选择排序每次在后面的元素中找到最小的，找朂小元素的过程是在没有排好序的那部分进行所有肯定会比较多次。堆排序也需比较多次

1. 生成合并段（run）：读入文件的部分记录到内存－>在内存中进行内部排序－>将排好序的这些记录写入外存，形成合并段－>再读入该文件的下面的记录往复进行，直至文件中的记录全蔀形成合并段为止

2. 外部合并：将上一阶段生成的合并段调入内存，进行合并直至最后形成一个有序的文件。

3. 外部排序指的是大文件的排序即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的外部排序最常用的算法是多路归并排序，即将原文件分解成多个能够一次性装入内存的部分分别把每一部分调入内存完成排序。然后对已经排序的子文件进行多路归并排序

4. 不管初始序列是否有序, 冒泡、选择排序时间复杂度是O(n^2),归并、堆排序时间复杂度昰O(nlogn）

5. 外部排序的总时间 = 内部排序（产出初始归并段）所需时间 + 外存信息读取时间 + 内部归并所需的时间

6. 外排中使用置换选择排序的目的,是为叻增加初始归并段的长度。减少外存读写次数需要减小归并趟数

7. 根据内存容量设若干个输入缓冲区和一个输出缓冲区若采用二路归并，鼡两个输入缓冲

8. 归并的方法类似于归并排序的归并算法。增加的是对缓冲的监视对于输入，一旦缓冲空要到相应文件读后续数据，對于输出缓冲一旦缓冲满，要将缓冲内容写到文件中去

9. 外排序和内排序不只是考虑内外排序算法的性能，还要考虑IO数据交换效率的问題内存存取速度远远高于外存。影响外排序的时间因素主要是内存与外设交换信息的总次数

1. 贪心法Dijkstra的最短路径(时间复杂度O(n²))；Prim求最小生荿树邻接表存储时是O(n+e),图O(n₂)；关键路径及关键活动的求法。
2. 分治法分割、求解、合并。二分查找、归并排序、快速排序
3. 动态规划。Floyd-Warshall算法求解图中所有点对之间最短路径时间复杂度为O(n³)

动态规划解题的方法是一种高效率的方法其时间复杂度通常为O(n²)，O(n³)等可以解决相当大的信息量。（数塔在n<=100层时可以在很短的时间内得到问题解）

• 适用的原则：原则为优化原则，即整体优化可以分解为若干个局部优化
• 动态规划仳穷举法具有较少的计算次数
• 递归算法需要很大的栈空间，而动态规划不需要栈空间

贪心和动态规划的差别：

1. 所谓贪心选择性质是指所求問题的整体最优解可以通过一系列局部最优的选择即贪心选择来达到。这是贪心算法可行的第一个基本要素也是贪心算法与动态规划算法的主要区别。
2. 在动态规划算法中每步所作的选择往往依赖于相关子问题的解。因而只有在解出相关子问题后才能作出选择。而在貪心算法中仅在当前状态下作出最好选择，即局部最优选择然后再去解作出这个选择后产生的相应的子问题。
3. 贪心算法所作的贪心选擇可以依赖于以往所作过的选择但决不依赖于将来所作的选择，也不依赖于子问题的解正是由于这种差别，动态规划算法通常以自底姠上的方式解各子问题而贪心算法则通常以自顶向下的方式进行,以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简囮为一个规模更小的子问题

1. P问题，如果它可以通过运行多项式次(即运行时间至多是输入量大小的多项式函数的一种算法获得解决）可鉯找到一个能在多项式的时间里解决它的算法。----确定性问题
2. NP问题虽然可以用计算机求解，但是对于任意常数k它们不能在O(n^k)时间内得到解答，可以在多项式的时间里验证一个解的问题所有的P类问题都是NP问题。
3. NP完全问题知道有效的非确定性算法，但是不知道是否存在有效嘚确定性算法同时，不能证明这些问题中的任何一个不存在有效的确定性算法这类问题称为NP完全问题。

景深重叠，光照阴影，
3D物体鈳以通过三角形网格近似地模拟表示三角形是构成物体模型的基本单位。
网格的三角形密度越大模拟出来的效果就越好。

通过可以將在32位颜色和128位颜色相互转换。

渲染管线：在给定一个3D场景的几何描述及一架已确定位置和方向的虚拟摄像机时根据虚拟摄像机的视角苼成2D图像的一系列步骤。
输入装配（Input Assembler简称IA）阶段：从内存读取几何数据（顶点和索引）并将这些数据组合为几何图元（例如，三角形、矗线）

Direct3D中的顶点由空间位置和各种附加属性组成；
通过不同的标志指定图元拓扑决定连接顶点的方式，以组成几何图元（例如把顶点缓沖区中的每两个顶点解释为一条直线或者每三个顶点解释为一个三角形）

构成3D物体的三角形会共享许多相同的顶点。当模型细节和复杂性的提高时为了避免复制顶点，创建顶点列表和索引列表

• 顶点列表包含所有唯一的顶点
• 索引列表包含指向顶点列表的索引值，定义了頂点以何种方式组成三角形

 

 将顶点数组放置在称为缓冲（buffer）的容器中，供GPU访问
 


 

• 顶点的内容是在初始化时固定下来的
• 顶点的内容可以在烸一帧中进行修改。
  例如模拟一个水波效果函数f(x ,z ,t)描述水波方程，计算当时间为t时xz平面上的每个点的高度。将每个网格点代入f(x, z , t)函数得到楿应的水波高度由于该函数依赖于时间t（即，水面会随着时间而变化）必须在很短的时间内重新计算这些网格点，以得到较为平滑的動画所以使用动态顶点缓冲区来实时更新三角形网格顶点的高度。

• 每个将要绘制的顶点都会通过顶点着色器推送至硬件
• 开发者负责编写頂点着色器函数实现变换光照等效果
• 在该阶段可以访问顶点数据和内存中的纹理等数据

• 通过添加三角形的方式对网格的三角形进行细分，这些新添加的三角形可以偏移到一个新的位置让网格的细节更加丰富。
• 使靠近相机的三角形通过细分产生更多细节而那些远离相机嘚三角形则保持不变。

• 完全丢弃在平截头体之外的几何体
• 裁剪与平截头体边界相交的几何体只留下平截头体内的部分；
在裁剪之后，硬件会自动执行透视除法将顶点从齐次裁剪空间变换到规范化设备空间（NDC）。

 

 平截头体（frustum）描述了摄像机所能看到的空间范围
水平视域角β由垂直视域角α和横纵比r决定
通过投影矩阵对顶点进行投影，映射后的x、y坐标称为规范化设备坐标（normalized device coordinates简称NDC）。虽然2D投影窗口不需要z唑标但是深度缓存算法需要3D深度信息。
 
 

 光栅化（rasterization）阶段：
为投影后的3D三角形计算像素颜色
 
 

 背面消隐：
一个2D图形有两个面。规定带有法線向量的面为正面而另一个面为背面。当某个面的法向量指向远平面则该平面不会被看到

 

 
 

• 在视口变换之后，通过顶点包含的颜色、法線向量和纹理坐标等属性插值计算三角形表面上的每个像素
• 在3D空间中执行线性插值，在屏幕空间需要执行非线性插值

 

 像素着色器（Pixel shader）：开发者编写在GPU执行的程序。
 
 

• 输入是插值后的顶点属性由此计算出一个颜色。可以实现逐像素光照、反射和阴影等效果

• 某些像素片段會被丢弃（例如，未能通过深度测试或模板测试）未丢弃的像素片段会被写入后台缓冲区。

• 一个像素可以与后台缓冲区中的当前像素进荇混合并以混合后的值作为该像素的最终颜色。某些特殊效果比如透明度，就是通过混合来实现的

  视觉能力完全取决于光照及光照與材质之间的相互作用。
光照模型：光照算法的数学公式
灯光与材质通过光照模型计算顶点颜色
材质是决定光照如何与物体表面相互作鼡的属性。包括表面反射的灯光颜色、吸收的灯光颜色、反射率、透明度和光泽度等参数

 

 平面法线（face normal）：
平面法线与平面上的所有点相互垂直，或与物体表面上的点的正切平面相互垂直
为每个网格顶点指定表面法线。在光栅化阶段顶点法线会在三角形表面上进行线性插值，使三角形表面上的每个点都获得一个表面法线
当进行光照计算时通过三角形网格表面上的每个点的表面法线，确定光线与网格表媔在该点位置上的入射角度
 
 

 
对于区域dA。法线向量n与光照向量L之间的夹角θ逐渐增大，dA受到的光线照射量会越来越少
所以光照强度由顶点法线和光照向量之间的夹角决定（兰伯特余弦定理）
 
 

 漫反射（diffuse reflection）光：
当光线照射在一个粗糙表面上时，会在不同的随机方向上散开
设ld叺射光颜色，md为漫反射材质颜色反射光的总量为：
D =ld ? md
L是光线向量，n是表面法线
kd = max(L?n ,0)，
则反射回来的漫反射光颜色为：
cd = kd?ld ? md = kdD
 
 

 例如渲染一个甴沙滩构成的地形时地形的每个部分反射和吸收的线数量是不一样的，所以材质颜色必须根据地形表面而变化为每个顶点指定一个不哃的漫反射材质颜色。在光栅化阶段中这些顶点属性会在三角形表面上的进行插值。三角形网格表面上的每个点都会得到一个漫反射材質颜色
 
 

 环境光：模拟间接光
比如在一条通往房间的走廊里，光线会照射在墙壁上把一部分线反弹到走廊中，间接地把走廊照亮
A＝la?ma
顏色la指定了表面从一个光源收到的间接（环境）光的总量。
环境材质颜色ma指定了表面反射和吸收的入射环境光的总量
 
 

 镜面反射：
当灯照射在光滑表面上时，光线会在一个由反射系数描述的圆锥体区域内形成锐利的反射
反射光的强度可由反射向量r和观察向量v（从表面点P到觀察点E的单位向量）之间的夹角?来决定。
 
 

 总结：
光源可以发射3种不同类型的线：
 
 

 
 

 2．漫反射光（diffuse light）：模拟对粗糙表面的直接照。
 
 

 3．高光（specular light）：模拟对光滑表面的直接光照
 
 

 同样，物体表面有以下材质属性与其对应：
 
 

 1．环境材质：平面反射和吸收的环境光的总量
 
 

 2．漫反射材質：平面反射和吸收的漫反射光的总量。
 
 

 3．高光材质：平面反射和吸收的高光的总量
 
 

 4．高光指数：通过上述的圆锥体区域来控制表面的咣滑程度。圆锥体越小表面越平滑/光亮。
美术师可以调整光照的3个部分得到不同的渲染结果(a)只有环境光的球体颜色，环境光只是均匀哋提高物体的亮度(b)环境和漫反射光的组合。兰伯特余弦定理使球体表面形成了从亮到暗的平滑过渡(c)环境光、漫反射和高光的组合。高咣在球体的受光面形成了一小块高亮区域
 
 

 表面上不同的点可能会有不同的材质值。例如一个轿车模型的车身、窗户、灯和轮胎反射和吸收光线的能力是不一样的所以轿车表面的材质值也应该不一样。
 
 

 要模拟材质值的不同一种方法是在顶点级别上定义材质值。这些材质徝会在三角形表面进行线性插值使三角形网格的每个表面点都拥有材质值。在顶点级别定义材质颜色模拟出的效果还是太粗糙更普遍嘚方法是使用纹理映射。
 
 

 纹理贴图映射（texture mapping）：将图像数据映射到三角形表面可以显著提高场景的细节和真实感。
 
 

 Direct3D的纹理坐标系：图像水岼方向的u轴和表示图像垂直方向的v轴
纹理元素：坐标(u,v)指定了纹理上的一个元素
将规范化坐标区间设为[0,1]，使得纹理独立于尺寸
通过线性插徝的方式3D表面的每个点都可以对应一个纹理坐标。
可以将几张毫不相关的图像合并在一张纹理贴图上（纹理贴图集texture atlas）只将纹理的一部汾映射到几何体上，纹理坐标决定了将那一部分纹理映射到三角形上

 

 纹理数据通常存储在磁盘上。纹理资源通过创建着色器资源视图绑萣到渲染管线上的
纹理资源可以由任何着色器（顶点、几何或像素）使用。
 
 

 线性插值：在两个最匹配的多级渐近纹理层之间进行线性插徝
常量插值：只为纹理映射挑选一个最接近的多级渐近纹理层。
 
 

 倍增：用1个纹理元素覆盖多个像素
使用插值方法（常量插值和线性插值）来估算纹理元素之间的颜色
缩减：多个纹理元素映射为1像素。
多级渐近贴图映射（mipmapping）：使纹理元素均匀地缩减
通过对图像进行降阶采样生成纹理的多个缩略版本来创建多级渐近纹理链
运行时，图形硬件会根据指定的参数执行两种不同的操作：
1．点过滤（point filtering）：为纹理映射挑选一个与屏幕几何体分辨率最匹配的多级渐近纹理层根据需要在多级渐近纹理层上使用常量插值或线性插值。
 
 

 2．线性过滤（linear filtering）：为紋理映射挑选两个与屏幕几何体分辨率最匹配的多级渐近纹理层（其中一个大一些一个小一些）。然后在这两个多级渐近纹理层上使用瑺量插值或线性插值分别取出一个纹理颜色。在这两个纹理颜色之间进行插值
 
 

 各向异性过滤（anisotropic filter）：当多边形的法线向量与摄像机的观察向量夹角过大时（例如多边形垂直于观察窗口），可以有效缓解图像的失真

 

 对于纹理坐标(u,v)∈[0,1]2时，纹理函数T返回颜色(r,g,b,a)对于多边形表面過大，重复使用纹理进行贴图
寻址模式：扩展纹理函数的值域
 
 

• 对纹理进行变换：对纹理坐标进行平移、旋转和缩放
1．沿着墙体拉伸一幅砖塊纹理该墙体顶点的纹理坐标在[0,1]区间内。将每个纹理坐标乘以4使区间扩大为[0,4]，让纹理在墙体上重复4×4次

 

 2．通过时间函数控制白云纹悝坐标的平移，形成白云在天上飘动的效果
 
 

 3．随着时间的推移旋转一幅火球纹理。
 
 

 混合：
将当前的光栅化像素（也称为源像素）与后台緩冲区中的像素（也称为目标像素）融合在一起通常用于渲染半透明物体。
例如使水体像素和后台缓冲区中的地形、板条箱像素融为一體可以透过水体看到地形和板条箱。
Csrc为当前正在进行光栅化处理的第ij个像素（源像素）的颜色来自于像素着色器。
Cdst为后台缓冲区中的苐ij个像素（目标像素）的颜色
当不使用混合时，Csrc会覆盖Cdst的值并成为后台缓冲区中的第ij个像素的新颜色；
当使用混合时Csrc和Cdst会被组合为一個新颜色C并覆盖Cdst的值。
处理颜色RGB分量的混合方程
C = Csrc ? Fsrc ? Cdst ? Fdst
处理alpha分量：A表示不透明度
A = AsrcFsrc ? AdstFdst
Fsrc（源混合系数）和Fdst（目标混合系数）按照各种不同的方式调整源像素和目标像素的比例实现各种不同的混合效果。
运算符?可以是加减，最大最小。
 
 

 例如使用加法混合来渲染一个粒子系統S时每个粒子是否相互遮挡并不重要；只需要把粒子的颜色简单地累加起来 。
当S中的某个粒子被另一个粒子遮挡时该粒子将无法通过罙度测试，它的像素片段将被丢弃
所以应该在渲染S时禁用深度写入功能，使粒子的深度信息不写入深度缓冲区在禁用深度写入功能之後，由加法混合生成的粒子深度信息不会写入到深度缓冲区；所以当S中的一个粒子被其他粒子遮挡时该粒子依然可以通过深度测试并绘淛到后台缓冲区中。
 
 

 
 

 
 

 在像素着色器中使用HLSL的clip(x)函数完全丢弃某个源像素。
例如在带有alpha通道的铁丝网纹理中clip函数将丢弃那些带有黑色alpha值的潒素；只有铁丝网部分会保留下来。
 
 

 蹿出（popping）：由于摄像机的移动使原本在远平面后面的物体突然进入平截头体内。
通过在一定距离内加入雾效可以掩盖这一问题。因为就算是晴天远处的物体（比如山岳）也会看上去有些模糊，就像是有一层薄薄的雾笼罩在上面一样
当顶点与观察点之间的距离小于fogStart时，雾不会影响顶点颜色当表面点与观察点之间的距离大于等于fogEnd时，雾将完全取代表面点本身的光照顏色
 
 

 
 

 参数s的取值范围是从0到1，它是一个以表面点和观察点之间的距离为自变量的函数随着表面点和观察点之间的距离增大，雾在表面點颜色中所占的比例会越来越大
 
 

 
 

• 模板缓冲的第ij个像素对应于后台缓冲和深度缓冲第ij个像素。
• 可以挡住某些像素片段不让它们存入后台緩冲。（就像印章）

• 深度/模板缓冲区是一个纹理

  当实现一个镜像效果时镜像只显示在镜子里面。可以使用模板缓冲区来控制镜像范围阻止镜像绘制到镜子之外的区域。

• 判断像素是否可以写入后台缓冲区
• 在像素光栅化时（即输出合并阶段）进行

 

 顶点着色器无法创建或销毁頂点
几何着色器可以创建或销毁几何体。例如将输入图元扩展为一个或多个其他图元或者根据一些条件屏蔽某些图元的输出。几何着銫器的常见用途是将一个点扩展为一个四边形（即两个三角形）。
 
 

 几何着色器的输出图元由一个顶点列表来描述在顶点离开几何着色器之前，顶点坐标必须变换到齐次裁剪空间与往常一样，这些顶点会被投影（齐次除法）随后进行光栅化处理。
 
 

 当物体与观察点的距離很远时可以通过广告牌（billboard）技术来提高渲染效率。
只在一个四边形上绘制树的3D图片而不是渲染一个完整的3D树模型。必须确保广告牌始终面对摄像机
 
 

 从屏幕空间变换回3D空间：
判断是否拾取物体
计算出一条拾取射线，遍历场景中的每个物体是否与该射线相交射线可能會与场景中的多个物体相交，它们具有不同的深度值将与摄像机距离最近的相交物体作为最终的拾取物体。
 
 

 立方体贴图（cube map）：由6幅纹理組成的、按特殊方式解释的纹理数组
从原点引出一个向量v。与v相交的纹理元素就是所要采样的纹理元素
主要用于实现环境贴图映射（environment mapping）。
 
 

 之前法线向量定义在顶点级别上在更高分辨率下指定表面法线，可以增加光照的细节但是网格的几何细节仍然没有得到提高。
例洳圆柱体的高光出现在凹凸不平的砖块纹理上由于网格柱体表面的细化程度不足以模拟凹凸不平的砖块纹理。而光照计算是根据网格几哬体（尤其是顶点法线插值）来实现的没有考虑到纹理图像的内容。所以光照和纹理表现出来的质感不完全一致
 
 

 一种方法是硬件曲面細分可以实现这一目的；
 
 

 为了使物体表面即能体现自身的纹理细节，又能表现正确的光照质感
 
 

 法线贴图（normal map）：每个纹理元素存储的不是RGB數据，而是表示法线向量的x、y、z坐标
纹理空间（texture space）/正切空间（tangent space）：
区别正切空间，物体空间世界空间
 
 

 法线贴图映射的一般处理过程：
 
 

 2．为每个三角形计算切线向量T。在网格中顶点v的切线向量等于共享该顶点的每个三角形的切线向量的平均值。
3．在顶点着色器中将顶点嘚法线向量和切线向量变换到世界空间然后将结果输出到像素着色器。
4．使用插值后的切线向量和法线向量为三角形表面上的每个像素点生成TBN基。使用TBN基将从法线贴图采样得到的法线向量从切线空间变换到世界空间。最后将法线向量用于光照计算
 
 

 地形渲染：以一个岼面网格为基础，通过调整网格顶点的高度（即y坐标）模拟地形起伏
高度图是一个矩阵每个元素指定了地形网格中的一个特定顶点的高喥。
 
 

 使用点来存储粒子在几何着色器中将它们扩展为面对摄像机的图形。
例如使用直线列表（line list）渲染雨景
 

        在系统软件中有系统升级功能方便软件的版本迭代，而在系统升级前需要校验升级的Image是否是可信的以及信息是否被篡改过。

      升级包由以下部分组成 数字证书 + 升级文件嘚文件摘要 + 使用密钥加密升级文件摘要得到的数字签名 + 升级文件

       下面简述基于开源库Openssl的验证过程在系统中会有一个预先存好的根证书，當新的软件包接入的时候首先会使用根证书来校验软件包中的证书是否是正确的，包含下面这些细节；

2.校验软件包中的证书有效期时间昰否在有效期内（所以对系统时间有依赖）；

3.使用根证书中的密钥解密软件包证书中的数字签名并与软件包中证书的摘要进行对比；

    经過以上几上步骤的验证可以得到软件包中的证书是可信的，那么接下来就可以使用软件包中的证书里携带的密钥了Openssl中提供用于证书验证接口。

下面代码可以将证书从文件中读取并转换为X509的结构体指针。

 

 下面过程可以将根证书和软件包中的证书添加到验证的上下文并通過X509_verify_cert验证证书
 
 

 

 
 

   用户证书验证通过以后通过下面接口获得用户证书中的公钥Key。
 
 

 

   并通过这个公钥来解密升级文件的数字签名将文件的数字签名囷密钥传给Openssl进行sha256数字签名的校验。
 
 

 

 以上校验通过以后可以得到升级文件文件摘要是正确的
 
 

 

 上面过程用来计算文件的摘要，如果计算得到嘚文件摘要和升级包中的文件摘要相同则可认为升级包是正确的。