数据结构学习（考研408）

数据结构学习笔记，若有任何问题欢迎大家评论指出

1.存取包括存和取 2.第i个元素指下标为i-1的位置 3.注意题干，注意题干中的陷阱

有关概念：一个数据元素由若干个数据项组成，数据对象是具有相同性质的的数据元素的集合。 抽象数据元素可以理解为抽象成员，他是没有实际含义的数据元素，当实际使用时才确定他的数据类型 数据结构是相互存在一种或多种特定关系的数据元素的集合（数据之间的关系） 数据结构三要素： 存储结构（顺序，链式，索引，散列） 数据运算（与或非加减乘除等等） 逻辑结构：集合，线性，树形，图或网（主要分为线性和树状，图形） 线性是除了首尾外唯一前驱后继，树是除了根外唯一前驱不限后继数。图不限前驱后继数 逻辑结构+存储结构=物理结构，例：线索二叉树是物理结构 抽象数据类型包含逻辑结构和数据运算，可以定义一个完整的数据结构（实现则要用到存储结构） 是从基本数据类型中抽象出来的，即几种类型混合使用的类型，例如表，队列，堆等等 算法具有的特性：确定性：即运算结果是唯一的，每一步是确定的不是模棱两可的 有穷性，至少一个输出，有效性 最坏情况下某语句的频度指某一语句出现的频率（执行次数最大的时候） 时间和空间复杂度 时间复杂度：T（n） 一般表示程序执行次数T和传入的参数n的关系 一般只关注n的最高阶数，即如果T（n）=6n3+10n2+100000000，一般我们都假设T（n）=O（n3） o(1)next = p; //将新结点插入到头节点后面 p = r; //令p等于下一个结点继续循环 } return l;} 栈和队列

（操作受限的线性表）

栈（stack）：只能在栈头进行操作，先进后出，”堆“ 实现栈（顺序存储结构）：定义一个结构，包含一个存储栈中元素的静态数组(data)和表示栈顶的指针(top)（栈顶元素存储在数组中的下标，操作数据是从数组的尾部操作的） 初始化：设置top=-1 表示栈空 栈长为栈顶下标+1 链式存储结构：和单链表基本一样，只能在链表头操作结点 共享栈：顺序存储方式实现的栈，结构体包含两个指向栈顶的指针，一个从数组头开始，一个从尾开始，即从数组头定义一个栈，从数组尾也定义一个栈，增加空间的利用率， —在栈中，给你n个数，有多少种出栈的顺序？ 1/n+1 * Cn(上)2n（下）

队列：只允许在队尾进行插入，在队头进行删除，先进先出（队尾进，队头出） 静态队列（顺序存储结构）：结构体包含一个数组和队头（top）及队尾指针(end) 初始化：将top,end设置为0(表头指针指向队头结点，表尾指针指向尾结点下一个位置） 循环队列：即将数组的线性空间当作环状空间使用。 //判断循环队列是否满有三种方式，常见第一种 1.数组中的一个位置不存储数据，以保证在队满时，队尾指针在队头指针的后面 (q->end + 1) % n = = q->top; 2.增加一个用于计算当前队列中数据个数的变量 3.增加一个布尔类型的变量（tag），当上一次操作是入队时，令tag=1， 则当tag=1且q->end == q->top时，队列满，（因为入队操作不会导致队空）

链式存储的队列：是一个有队头指针和队尾指针的单链表（一般是带头结点的）。定义一个结构表示单链表，再定义一个结构表示队列，结构中有两个指针，分别表示链表头和尾 所以一个链队的基本组成是头结点和队头及队尾指针 双端队列：允许在两端进行删除和添加操作（双端序列没有先进先出？） 输入受限的双端队列就是只能在一端输入，但可以两端输出

栈的应用： 栈与递归：递归的深度越大，越可能导致栈溢出（超出栈的容量）， 因为系统会开辟一个栈来存储每一层递归的返回点，局部变量，传入的实参等数据 递归就是递推式，例f(n)=f(n-1) 递归中，递归体内的变量(包括参数)每一层的值都会压入栈中，在返回时依次弹出 分析递归的时间复杂度按进出栈的次数和分析。循环的效率远高于递归 进栈n次出栈n次，时间复杂度为2n。。空间复杂度计算递归的深度？ 递归转为非递归1.用循环2.用栈 括号匹配判断一个括号序列是否合法，即每一个左括号都有一个右括号对应，用栈实现，每一个左括号入栈，出栈时匹配右括号 中缀表达式就是平时的写法 前缀表达式（波兰表达式）：a+b写成+ab ，a+b-c写成-+abc或+a-bc（从右边开始计算） 后缀表达式（重点）（逆波兰）：即把运算符放在操作数后面。对于一个计算，先提出操作数，再将操作符放后面即可 例a+b写成ab+ 则再以ab+为一个操作数进行运算，例：a+b-c写成ab+c- 也可以写成abc-+ （从右边开始计算） 在把中缀改为后缀时应该按左优先原则（使运算结果唯一），即左边的运算符优先执行，这样得出的结果中的运算符的顺序和你先定的计算顺序一致 例：a/b+cd 运算顺序应该定义为/ * + (不定义为 * /+)，则改为后缀为 ab/cd * + 实现将后缀转换为中缀（计算后缀表达式的值） 从左向右扫描字符，如果是操作数则存储在栈中，如果是运算符则移出栈中的两个元素进行运算，将运算结果放回栈中（其结果当作一个数）先出栈的是右操作数，例a-b写为ab- 则a先入栈，b先出栈 前缀表达式的计算只要改为从右扫描字符即可 -实现将中缀转换为后缀 A+B-C * D/E+F 写成 AB+CD E/-F+ 用两个栈来实现，一个栈存储结果，一个栈用于存储运算符 从左到右处理各个元素，直到末尾。可能遇到三种情况（左优先，先算左边）: ①遇到操作数。直接加入后缀表达式。 ②遇到界限符。遇到“(”直接将（入栈;遇到“)”则依次弹出栈内运算符并加入后缀表达式，直到弹出“(”为止。括号不需要加入后缀表达式中 ③遇到运算符。如果栈中已经有运算符，则依次弹出优先级比遇到的运算符高或相等的所有运算符（例：栈从上至下有 * - ，遇到+，则弹出 * -，遇到/则弹出*），（括号的优先级比所有运算符高 ） 然后把遇到的运算符入栈 按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达（即栈底元素是后缀表达式的第一个元素） 队列的应用： 树的层次遍历（图的广度优先搜索）。操作系统中的先来先服务策略（解决多用户竞争资源）。解决主机与外部设备速度不匹配的问题等等

c语言是按行主序 普通矩阵用二维数组存储即可，矩阵的压缩存储即将矩阵存储在一维数组中，考察存储和查找 对称矩阵，对称矩阵即中斜轴对称的矩阵,三角矩阵则多用一个位置存储那个常量即可 —存储：用一维数组按行或列存储轴和上下任一区的元素即可，A表示一维数组，a表示矩阵 若按行存储，则A[0]存储a[1] [1],A[1]存储a[2] [1],A[2]存储a[2] [2]… —查找：如果按行存储，则i>j区（即下区）第a[i][j]个元素对应数组中的下标为i(i-1)/2+j-1 a[i][j]在A[n]中对应的下标为这个元素前面有多少个元素，i(i-1)/2+j-1，i(i-1)/2是前i-1行元素的个数（等差数列求和），j-1是元素所在行在该元素前面的元素的个数 即 a[i][j]=A[i(i-1)/2+j-1] （下标从0开始） 访问上区的元素只要把ij互换即可 上三角矩阵的查询和按列存储的查询一样 a[i][j]=A[(i-1)(2n-i+2)/2+j-i] （下标从0开始） 带状矩阵（三对角矩阵）：中斜轴除对角两个元素外每个元素的上下左右都有一个非0元素，其他元素都是0（只有中间三条斜轴有数据） —存储：和对称矩阵一样，按行或列存储都可 —查找：a[i][j]=A[2i+j-3]（下标从0开始） 稀疏矩阵：即非0元素少于为0的元素， —存储方法1：用一个结构存储非0元素的值和其地址（行值和列值）(或者用二维数组存储) 方法2：十字链表法，即用两个数组，一个数组存储行的非0元素，一个数组存储列的非0元素。 十字链表是由一个横向和竖向的数组构成，数组中的每个元素都是一个单链表，单链表中的每一个结点包括三个数据和两个指针，三个数据指行值和列值和本身的值，两个指针分别为指向同行的下一个元素及同列的下一个元素，因为每个结点都可以有上下左右的指针，所以称为十字链表 （考研不考）广义表：扩展线性链表 广义表就是广义的线性表，即表中的每个元素都可以是一个广义表，广义表中的单个元素称为原子（非子表） 例：表a=（1,3（4,1）,(1,(4,6))）,表的深度指子表括号数+1，即a的深度为3 广义表的每个结构由三个元素组成（指向头和尾的指针，和一个标志位（是为原子还是子表））， 子表中的每个元素用含三个元素的结构构成（值和指向下一个元素的指针和（标志位？））（见222）

串也是线性结构，是特殊的线性表 子串：串中任意个连续的字符串组成的子序列（可以为0） 串的位置：第一个字符的位置（位序是从1开始） 每个英文占一个字节 串的链式存储：一个结点存储一个指针和一个字符数组（数组长度一般是4） 这样的做原因是提高存储密度，因为一个指针占4B而一个字符占1B，存储密度低 子串的定位操作称为串的模式匹配（KMP算法就是串的模式匹配）

目的：传入一个长度为n的子串，在主串中寻找是否有和子串相同的序列 brute-force算法(常规字符匹配算法):从第一个相等的字符开始匹配，若失败则从第二个相等的字符开始匹配 缺点:是当出现连续比较相等但最后一个值不相等时会浪费时间,且程序每一次比较失败会从头开始匹配 时间复杂度是O（mn） kmp算法有时比较次数也会多于上述算法，在模式串多次右滑，仍然比较不相等时发生 KMP算法的思路：当匹配不相等时，子串应该回到哪开始继续比较，先将这个算出来放入一个数组中，然后当比较不相等时直接回到应该回到的位置（能节约时间的位置） 以主串A为abcabcac子串B为abcabd为例：当指针a和b为6时比较失败（a是主串指针，b是子串指针，表示下一次是A[a-1]与B[b-1]比较）即A[a-1]不等于d时,则令b等于3继续匹配（所以next[5]=3） 时间复杂度是O（m+n）主串和子串的长度和

求next数组：next[j]=s s=前后缀相等且最长的子串的长度+1 其他情况s=1 (前后缀指从前往后从前面取两个数和从后面取两个数比较，然后从前面取三个数和从后面取三个数比较) 书上是第一个数的next值为-1 .其他情况为0（一个数匹配的和没有数匹配的都是0）) next[1]=0 next[2]=1(数组的第一位数恒等于0，第二位恒等于1)， 例：一，23325 next[1]=0 next[2]=1 next[3]=1 next[4]=1 next[5]=1 二， 23235 next[1]=0 next[2]=1 next[3]=1 next[4]=2 next[5]=3 在二中 next[4]=2取的是第一个数和第三个数（前后缀等于2），next[5]=3取23和23 优化版的KMP算法：就是对得到的next数组进行优化为nextval[]数组 如果第n个元素匹配失败，且前面有和这个数相等的数，则这个数的下标等于前个数的下标 从next获得nextval[]数组，从第一个数开始，若后面有和前面一样的数，且在next数组中的值等于前面那个数的下标，则将后面数的值定为前面那个数的值 例：23325优化为nextval[1]=0 nextval[2]=1 nextval[3]=1 nextval[4]=0 nextval[5]=1 二。 23235 nextval[1]=0 nextval[2]=1 nextval[3]=0 nextval[4]=1 nextval[5]=3 在二中，nextval[3]=0是因为子串B中，B[3]=B[1],且next[3]=1所以令nextval[3]=next[1] KMP算法的代码实现思路：问题1.主串指针a什么时候后移？答：当b==0 或A[a-1]==B[b-1] 时a++ （因为在next数组中第一个数始终为0，所以当b=0时，则说明需要重新开始匹配了，即a++,b=1） 其他情况令b=next[b]即可（next数组中位序从1开始，字符串的存储位序从0开始（普遍定义））

森林：大于等于0个树的集合 度：树中一个结点的子结点的个数称为该结点的度，树中最大的度为该树的度 叶子结点：度=0的结点，又称为终端结点。 分支结点：度大于0的结点 前驱结点：指按某种遍历方法，先遍历b再遍历a，则b为a的前驱结点，后继结点类推 边：父结点和子结点的连线（关系）称为边，n个结点的树有n-1条边 树的高度：高度=层数=深度 树的深度不包括根，即一个结点的树深度为0，两个结点的树深度为1 兄弟结点：同一层且有同一个父亲的结点互为兄弟结点， 路径长度：两个结点之间的路径上所经过的边的个数 结点的带权路径长度：=结点的权值 * 其深度 （根结点的深度为0） 树的带权路径长度(WPL)是所有叶结点的带权路径长度之和 树的性质： 树的所有结点数=所有结点的度数和+1（即n1+2n2+3n3…）（n2表示度为2的结点的个数）

二叉树不是一种特殊的树，度为2的有序树不是一颗二叉树 二叉树的定义：可以为空，度为2，有序树（左右结点是有序的） 二叉树的性质：1.非空二叉树的叶子结点数等于度为2的结点数+1 特殊的二叉树 -----满二叉树：除叶子结点外的结点的度数都为2 性质：1.结点数为2^n - 1 （n为树的深度） 2.编号为i的结点（左子树比右子树小），其父结点的编号为[i/2]向左取整，左孩子为2i，右孩子为2i+1 ----完全二叉树：只有当一颗树按满二叉树的编号方法编号时（从左一层一层的编号），则这个树为完全二叉树。即最后一层可能不能像二叉树一样放满 性质：1.若有度为1的结点，则只有可能有1个，且该结点只有左孩子结点 2.若结点数为m则树的高度为log2(n+1)或log2n +1 ----二叉排序树(二叉搜索树)：左孩子结点小于父结点，右孩子结点大于父结点 ---- 平衡二叉树：每一个结点下的左右子树的深度差不超过1 二叉树的存储结构 顺序存储结构： 适用于完全二叉树和满二叉树，存储其他二叉树会浪费很多空间 一个完全二叉树的左结点为2i,右结点为2i+1,(从上-下，左-右编号)，按编号存储在对应数组的下标中 而非完全二叉树只要将非完全二叉树补成完全二叉树即可，空位存储0 链式存储结构：一般用两个指针和一个数据域的结构体表示一个结点，指针分别表示左和右孩子结点。也可以增加一个指针指向父结点，这时称为三叉链表 二叉链表中非空指针的个数=边数=n-1 所以空指针的个数=2n-(n-1)=n+1

相关概念：中序后继：即按中序遍历方法，遍历A后应该再遍历B，则B是A的中序遍历后继 假设我们定义一个规则（先遍历左子树，再遍历右子树，即先把根的左边遍历完再遍历右边）则有三种递归遍历方法：1.左右根 2.根左右 3.左根右 （所谓先序遍历指的是先遍历根） 1.先序遍历（根左右）：从上至下，先遍历根，然后先序遍历左子树，再先序遍历右子树 对于下面图片中的例子，先序遍历的结果是A BDE CFG 先A再B，对于B，先B再DE，所以是ABDE 2.中序遍历（左根右）：从上至下，先中序遍历左子树，然后遍历根，再中序遍历右子树 下图中序遍历的结果是 DBE A FCG 2.后序遍历类推，下图后序遍历的结果是 DEB FGC A 非递归遍历则使用栈实现，先序按中序类推即可 用栈实现中序遍历：1.初始时将根结点及根的所有左侧结点放入栈中 2.然后出栈一次 3.若有右子结点，则将右子结点作为根结点重复1，2，3若没有右子结点，则重复2.3 以上图的树为例，依次入栈ABD，然后出D，B，入E，出E，A，入C,F，出F，C，入G，出G 后序：思路：第一步和中序一样，先找到第一个访问的结点，即最左端的结点，中途结点依次入栈 第二步：访问栈顶结点，若有右子树且从未被访问过，则重复第一步，若无右子树则出栈并访问，且该结点就是最近被访问的结点，然后继续访问栈顶元素，如此循环 以上图为例，依次入栈ABD，访D，出D，访B，入E，访E，出E，访B，出B。。。 层次遍历用队列实现即可：先入根，若队列不为空则一直循环，出队，入根左，入根右。（左到右 ）

层次遍历，即从上至下一层一层的遍历，使用队列实现 1.将根入队，然后出队，2.将根的左，右子结点入队（先左后右） 3.出队一个元素，4.将出队的结点的左右子结点入对 1重复操作至队空为止 由遍历方法构造二叉树 先（或后或层）序遍历加中序遍历即可构造确定的二叉树（即唯一的一颗树）（即先根后先左或先右） 线索二叉树：若无左子1树，则将左指针指向其前驱结点，若无右子树，则将右指针指向其后驱结点 并增加两个标识位用于区分其指针是指向的子结点还是前驱后继 二叉树的线索化：即遍历一次树，实现将二叉树变为线索二叉树 中序线索二叉树：空指针所指向的前驱后继是通过中序遍历得到的序列，该结点的前驱后继 线索二叉树上线索数为n+1 关于遍历的解题技巧：不需要把完整的树构出来，根据以下性质从排除选项的出答案即可 1.中序遍历序列中，根结点左边是左子树中序序列，右边是右子树中序序列， 第一个数是最左端的结点，最后一个数是最右端的结点 2.先序序列中，第二个数是根的左子结点（若存在），最后一个数是最右端的结点 3.后序序列中，倒数第二个数是根的右子结点（若存在），第一个数是最左端的结点 4.前序和后序遍历序列中，顺序相反的结点可以确定祖孙关系，例：eabc,ebca,则a是bc的祖先1 遍历的应用 1.树的高度的计算：用层次遍历，设置两个变量，一个指向当前层最右的结点（r），一个记录当前正在访问的结点的层数(b) 初始r=b=0，根入队，end=根，r=end,出队，入其左右子结点，end随着加 判断出队结点==r，若是，则b++，r=end，若不是，继续出队。循环这个过程即可 （在层序遍历中，出队的结点就是正在被访问的结点。出队后将其左右子结点入队，并判断正在访问的结点是不是最右结点，若是，则b++;且r=end(下一层最右结点)） (在层次遍历中的队列，一般队头指针top指向第一个结点前一个位置，队尾指针end指向最后一个结点) 2.求树的最大宽度：设置一个结构体，里面包含一个表示队列的数组及及指向队头队尾的指针，还包括一个数组A，表示队列中对应位置的结点所在的层数 在层次遍历中，将队列中每个结点对应的层数存储在A中，然后利用A遍历队列找出最大宽度（统计队列中第i层的结点数，统计到第j个值时，A[j]!=i,则统计第A[j]层的结点个数(I=A[j]),直到j指向队列的末尾） 先记录出队结点的层数k，则在入队时，入队结点的层数为k+1 3.判断一颗树是否为完全二叉树：将二叉树的所有结点层次遍历后加入数组中（空节点也遍历）。 在数组（链表也行）中，若空结点后有结点，则不是完全二叉树

森林中所有树都互为兄弟关系 树的存储方法 1.孩子存储法：对3做出一个修改,A中包含结点的值和一个单链表(单链表存储每个结点的孩子结点) 2.左孩子右兄弟存储法：（可用于树与二叉树的转换） 即用链表存储，每一个结点包含三个元素（数据，指向左子结点的左指针，指向右兄弟结点的右指针 3.双亲存储法：即用两个结构，一个结构A包含结点的值和其父节点的下标（根节点的下标用-1表示），另一个结构B包含一个A类型的数组和表示该数组中数据的个数的变量 树，二叉树和森林的互换 树–>二叉树：用左孩子右兄弟存储法即可（树转化成的二叉树右子树必为空） 森林–>二叉树：将每一棵树转为二叉树，然后每棵二叉树的根依次作为上一棵二叉树的右子树 二叉树–>森林：（从二叉树到森林逆推即可）二叉树右根断开，根的右节点为根的兄弟结点 森林和二叉树的遍历方法相同，遍历次序相同 树的先根遍历和二叉树的先序遍历相同，后根遍历和中序遍历相同

（考研不考）并查集：给一个集合或者多个集合，将其用双亲存储法存储 即每个集合表示一颗树，令集合中第一个元素为根，则其他元素就是它的子结点 如果为一个集合我们可以认为他是一个数组或者里面所有值都是没有子结点的树

二叉排序树：二叉查找树,树中所有左子树上所有的结点都小于根结点,右子树所有结点大于根结点 二叉排序树中所有结点的值不同 二叉排序树的中序遍历序列是递增有序的序列 创建二叉排序树：将结点按规则插入到末尾即可（即新加入的结点一定是叶子结点，且在查找新插入的结点时一定是在最后找到的） 二叉树的删除：若被删除的结点是叶子结点，直接删除即可，若该结点有一个子结点，让子结点替换其即可 ，若被删除的结点A有左右子树，则让其中序遍历的后继B代替A，则B的位置空了，继续按规则补充B的位置 查找成功的平均查找长度=每一层的结点数*层数的和/结点总数 查找失败的平均查找长度=每个结点的深度乘其空指针的数量的和/树的空指针的数量 平衡二叉树（AVL树）：左子树的高度-右子树的高度n-1,则此图一定有环 简单路径：顶点不重复出现 简单回路：除第一个顶点和最后一个顶点外，其余顶点不重复出现 有向树：一个顶点的入度为0，其余顶点的入度都为1的有向图称为有向树 弧：有向图中的边

1.邻接矩阵法：对于稀疏图会浪费许多空间 实现：定义一个一维数组存储所有结点。然后根据图生成一个邻接矩阵（二维数组），即从一维数组的第一个元素（结点）开始，到其他所有结点，有边则为1，无边则为0。 特点：1.对于无向图 ，矩阵为对称矩阵（左上，右下斜线对称）， 且第i行/列的非0元素的个数为顶点i的度数 2.对于有向图，第i行非无穷元素（非0元素）的个数为顶点i的出度，第i列则为入度 3.对于带权图来说，有边的存放权值，没有边的为正无穷 4.邻接矩阵A^2中第i行j列的元素表示从i到j的路径的条数 A^n中第i行j列的非0元素表示从i到j的长度为n的路径的条数 所谓以行主序表示为在矩阵中第i行第j列的数表示为（i,j），以列主序则为（j,i） 2.邻接表法：适用于稀疏图，同一个图建立的表是不唯一的 用一个数组存储每个结点（每个结点的头指针） 为每个结点创建一个链表（单链表）用于存储从这个结点出发的边 边结点存储弧头顶点的下标和指向下一个边的边结点指针 3.十字链表：专用于存储有向图的链式存储结构 定义一个数组，数组每个元素存储一个结构，结构中定义三个变量，一个是数据，一个是出边的头指针（从结点出发的边），一个是入边的头指针 (出边的头指针存储从结点出发的所有的边，然后其他的变量的作用都是用于区分的查找这些边是从这个结点出发还是以这个结点为终点) 对于每个头指针定义一个单链表，链表中每个结点存储5个变量(其中一个存储权值)，分别是边尾的结点和边头的结点（数组中的下标，边尾指从a指向b的边中的a）（int） 头边和尾边,头边指指向终点相同的下一条边 尾边是指指向起点相同的下一条边（即表示两条边都有共同的终点或起点） ,(当一个结点有三条边以他为终点时应该如何指？） 单链表中的每一个结点都是一条边（称为弧结点） 4.邻接多重表：专用于存储无向图的链式存储结构 定义一个数组，数组中每个元素存储两个变量，一个是数据，一个是该结点的边的头指针(任意一条？) 定义一个单链表，链表存储四个变量（还可以加标记（该边是否被访问）和该边的权值）四个变量分别是这条边的两个结点在数组中的下标（int）(a,b)，和指向连接a的下一边的指针和指向连接b的下一边的指针

广度优先遍历：BFS和树的层次遍历差不多，只是多了一个变量用于标记该结点是否已经被遍历过 从第一个顶点a开始，依次访问其各个邻接的未被访问的顶点a1,a2,a3,然后对a1,a2,a3,从a1开始依次访问其邻接的未被访问的顶点，若最后依然没有访问所有结点则任选一个未被访问的结点重新开始循环 （将图画成树的形式，然后进行层次遍历即可）（算法和层次遍历比多个判断该结点是否已被访问过） 广度优先遍历的应用：求无权图单源最短路径：从该结点出发，到达其他所有结点的最短路径（边数最少） 广度优先遍历1会生成一颗树或者森林，由于图的邻接表存储不唯一，所以其生成树不唯一 深度优先遍历：DFS与树的先序遍历差不多，只是多了一个变量用于标记该结点是否已经被遍历过 实现机制：从第一个顶点开始访问，然后访问与他邻接的未被访问过的顶点b，然后再访问与b邻接的未被访问过的顶点，直到没有未被访问过的邻接的顶点，则依次退回上一次被访问的顶点，访问他们邻接的顶点，直到访问玩图中所有顶点 （概括来就是沿着一条路径一直访问沿途的顶点，直到终点则后退一个顶点继续走另一条路…） 邻接矩阵法遍历的顺序唯一，邻接表不唯一 深度优先遍历会生成一颗树或者森林，邻接矩阵法的生成树唯一，邻接不唯一 对无向连通图做一次深度优先搜索可以访问到图的所有顶点 两种遍历对于邻接表存储的图，其时间复杂度都为边+顶点数,空间复杂度都顶点数 对于邻接矩阵则时间复杂度都为顶点数的平方，空间复杂度都顶点数 对于有向图，要按方向遍历 深度优先遍历生成的树高于广度优先，深度优先总往最深的遍历，广度反之

带权无向连通图包含全部顶点的一个最小连通子图（且权值和最小） 一个图的最小生成树不一定唯一（所有边的权值都不同则唯一或图的边数为结点数-1） 创建最小生成树一：prim算法 时间复杂度v^2 适用于边密集的图 1.创建一颗空树， 2.将图中任意一结点（a）加入树中， 3.从图中找一条包含结点a且权值最小的边（ae），将结点e加入树中并将边ae加入树中 4.再从图中找一个和树中已有结点邻接的，且（边值）权值最小的结点，将结点及其边加入树中 然后重复4.直到树中包含图中的所有结点 创建最小生成树二：kruskal算法，借助并查集，适用于稀疏图，时间复杂度eloge 1.创建一颗树，包含图中所有结点，但不包含边 2.将图中的边按权值从小到大依次加入树中，如果构成回路，则那条边舍弃。直到树中包含所有结点（树与图的区别在于图会构成回路，树不会，即有三个结点互相连通） 这两种算法构造的最小生成树可能相同，可能不同

带权有向图中一个结点到另一个结点所经过的边的权值和最小。最短路径一定是简单路径(出自严蔚敏) 找最短路径的算法无法判断一个图是否有环（最短路径算法允许有环图） 单源最短路径（Dijkstra算法）：最终会得到从第一个结点到其他所有结点的最短路径，包括序列 不适合有权值为负数的图，时间复杂度为V^2，(也适合求任意两个顶点间的路径) 求依次得到的各最短路径的目标结点，这个顺序=各顶点按路径长度排序 思想：dist[]用于存储到每个点的最短路径，初始时dist等于下图m的第一行 从m的第一行一直遍历到最后一行 对于第二行，第二行存在2个值表示通过结点2可以到达2个点，则计算到这三个点的路径，若小于dist存储的对应的值，则更新dist 对于通过2到3他的路线为1-2-3，时间为dist[2]+9=106 1，5。。3，2.。。8，4这三组，每组进行直接插入排序 按升序结果是1，2，4，5，3，8.然后对3/2取上界(增量)继续分组， 1,4,3。。2，5，8.两组，每组进行直接插入排序。然后继续取增量直到增量为1

归并排序：（两路归并）稳定 时间复杂度为nlog2n 空间复杂度为n(实现)(占空间最多的排序算法) 将一个待排序的序列（总长度为n）非为n个块，然后将每两个元素组成一个有序的块，然后继续使每两个块合为一个有序的块，直到只剩一个块 2路归并排序，指每次使两个块归并 将两个块合并的算法：创建一个数组存储两个块的数据，从两个块中第i ,j个数开始比较，若i 小，则将i 加入到结果序列中，并i++,若j小，则将j 加入结果序列中，并j++。直到一个块中的所有元素都加入了结果序列，则将另一个块中剩余的数全加入结果序列即可

基数排序：稳定，时间复杂度为O(r(n+q)) 空间复杂度为q 对于一组待排序序列，有n个值，序列中最大的值的长度为r(r=3,则最大值为百位数)，每一个数的取值范围为q（q=10,则取值范围可能为0~9） 排序过程一共循环r次，需要q个辅助队列，下面是最低位优先算法(LSD)(即先从最低位排序) 高位优先为(MSD) 1.定义q个队列 2.将每一个待排序的值按个位数的大小放入对应队列中，即个位数为0的放入第0个队列中， 3.从第0个队列开始依次从队列中取值，组成一个新的序列（新序列按个位数的大小排序） 4.将每一个待排序的值按十位数的大小放入对应队列中。。。（重复23） 排序算法的选择若n较小时可选直接插入排序或简单选择排序 若已基本有序选直接插入排序或冒泡排序为宜 若n较大时应采用时间复杂度在nlog2^n的算法。当关键字随机分布时快速排序平均时间最短 选择排序的比较次数和待排序序列的初始状态无关（初始关键字的顺序） 交换排序的趟数和初始状态无关

总时间=内部排序时间+外存信息读写时间+内部归并时间 在待排序序列的大小大于内部存储空间的大小时，应该使用外部排序，外部排序基于归并排序实现 因为外部磁盘的读写速度是远慢于内存的，所以与外存的i/o次数是主要影响因素 严格k叉树：只有度为k与度为0的结点的k叉树 外部排序一 1.假设内部空间大小为n，我们将待排序序列分为a个块，每一个块的大小为n，将每一个块用内部排序算法排序成有序序列，这些有序子文件称为归并段或顺串 2.将内部空间分为三个部分，前两个空间用于存放两个块中的前几个元素，后面一个块存放输出结果 3.比较前两个块中最小的值放入输出空间中，当输出空间满的时候输出结果，当前两个块中某个块中的所有元素都已存在与结果中时释放该空间，并将该块剩余的元素添加到块中继续比较 4.重复循环 外部排序二：败者树使内部归并不受归并路数k的增大的影响，每次输出一个最小(递减)或最大值 1.假设内部空间大小为n，将待排序序列分为a个块，每一个块的大小为n，将每一个块排序成有序序列 2.定义一个完全二叉树，使所有叶子结点存储待比较的值，每一个叶子结点分别存储一个块中的第一个值（即待比较的值）（有a个叶子结点） 3.叶子结点的父结点存储它的两个子结点中最大值的块的编号（即每个块都有编号）（在递增排序中，较小的值为胜利者，较大的为失败者） 每个结点存储左右子树中的失败者，而胜利者则会继续上传继续比较。（即每个结点会代表胜利者继续和它的兄弟结点做比较，将胜利者上传并记录失败者） 3.到根节点后会输出该树中最小的值，并传入最小的值所在的块的第二个值继续比较 k个记录(关键字)中选择最小关键字最多需要log2^k(取上界)次比较 所以总的比较次数为(n-1)log2^r(取上界) ,r为归并段的数量

外部排序三：置换-选择排序产生更长的初始归并段以减少归并趟数 设有待排序序列a，工作区b（内存，大小为3），输出文件c 1.从a中拿出三个值放入b中（从头开始拿）， 2.从b中取最小值（q）放入c中 3.然后从a中拿一个值放入b中（保持b中有三个值），取b中最小且比q大的值放入c中 4.循环2.3，直到b中所有值都小于c中的值,则输出c 5.继续循环2.3.4.直到a为空，这样的结果就是生成了n个有序的长度不等的块

外部排序三：最佳归并树对置换-选择排序所生成的归并段,组织归并顺序使得i /o次数最少 将哈夫曼树的思想推广到m叉树的情形 将每个归并段中关键字的个数看作一个结点构造生成哈夫曼树，严格k叉树 缺少的结点用0补 补充的0的结点称为虚段 1.先计算出需要补充的虚段的数量，已知归并段数为a,m叉树…则虚段数=(m-1)-(a-1)%(m-1) 2.先将虚段添加到结点森林中，然后开始构造哈夫曼树

一个缓冲区对应一个输入/输出文件 a路平衡归并排序中，并行处理需要2m个输入缓冲区和2个输出缓冲区， 进行串行操作需要m个输入缓冲区，1个输出缓冲区

算法分析 第一步，找可以作为循环条件结束的点(如果是找值问题，则思考如何能取到这个值，) 第二步：思考特殊情况下自己的算法是否依然成立（比如取临界值时，比如存在0或负数，比如比较中的相等的情况，还有其他情况视题目而定，比如找中值问题中的当一个数组中所有数都小于另一个数组时，比如取数组中的数的个数分为奇偶讨论）

要求在序列中处理重复数据的问题且对空间复杂度无要求的都可以用类似下面这个算法解决 1.在任给的一个全是整数的序列中，找出最小的，未出现的正整数，已知数组长度为n 思路：若序列为{5，-1，-3，1，3}，则最小的正整数应该为2，因为没有比1更小的正整数 考虑创建一个新的数组以解决问题，设置新数组的初始值为0，从给定序列的第一个数开始扫描，将扫描的正的数放入新建数组对应的下标中，直到扫描到序列的结尾，然后扫描一遍新建数组，则第一个值为0的下标就是所求的未出现的正整数 2定义D=|a-b|+|b-c|+|c-a|,a,b,c分别取自三个升序数组A,B,C，求D的最小的值

2：