网站开发综合实训,产品介绍网站如何做seo,网站搭建要多少钱,wordpress rss小工具前言#xff1a; Hello大家好#xff0c;我是Dream。今年保研上岸山东大学人工智能专业 #xff08;经验贴#xff09;#xff0c;现在将我自己的专业课备考知识点整理出来#xff0c;分享给大家#xff0c;希望可以帮助到大家#xff01;这是重点知识总结#xff0c;… 前言 Hello大家好我是Dream。今年保研上岸山东大学人工智能专业 经验贴现在将我自己的专业课备考知识点整理出来分享给大家希望可以帮助到大家这是重点知识总结如果你想看全部的内容的话这里我给大家都已经打包好了需要自取 保研复试全套材料408专业课知识总结及思维导图点击即可内容速看 1.保研复试全套材料含有夏令营准备材料包括联系老师模板、面试自我介绍、提交材料和推荐信模板以及预推免准备材料 2.408专业课复习材料、思维导图 3.高等数学、线性代数、概率、离散复习材料及思维导图 4.机器学习常见常问算法总结 5.算法总结以及机试得分训练秘籍 6.面试前必看知识408常问内容总结及面试常见问题。 数据结构面试常问问题目录 第一章、绪论知识框架1 .时间复杂度2.空间复杂度3.数的逻辑结构4.数的存储结构5.用循环比递归的效率高吗6.贪心算法和动态规划以及分治法的区别 第二章、线性表知识框架7.顺序表和链表的比较1.存取读写方式2.逻辑结构与物理结构3.查找、插入和删除操作4.空间分配 8.头指针和头结点的区别 第三章、栈和队列知识框架9.栈和队列的区别10.共享栈11.如何区分循环队列是队空还是队满12.栈在括号匹配中的算法思想13.栈在通过后缀表达式求值的算法思想14.栈在递归中的应用15.队列在层次遍历中的作用16.队列在计算机系统中的应用17.矩阵的压缩存储 第四章、串知识框架18.串的模式匹配 第五章、树与二叉树知识框架19.树与二叉树的相关概念20.如何由遍历序列构造一棵二叉树21.线索二叉树的概念22.树的存储结构1.双亲表示法2.孩子表示法3.孩子兄弟表示法 23.二叉排序树1.二叉排序树的定义2.二叉排序树的查找 24.平衡二叉树25.哈夫曼树和哈夫曼编码 第六章、图知识框架26.图的一些相关定义27.图的存储结构:1.邻接矩阵法2.邻接表法3.十字链表法4.邻接多重表 28.图的遍历1.广度优先搜索(Breadth-First-Search, BFS)2.深度优先搜索Depth-First-Search, DFS): 29.最小生成树和最短路径30.关键路径 第七章、查找知识框架31.对各种查找方法的概括32.B树和B树 第八章、排序知识框架:33.对各种内部排序的概括与总结34.快速排序基本原理 第一章、绪论
知识框架 1 .时间复杂度
一个语句的频度是指该语句在算法中被重复执行的次数。算法中所有语句的频度之和记为T(n), 它 是该算法问题规模n 的函数时间复杂度主要分析T(n) 的数量级。算法中基本运算的频度与T(n) 同数量级因此通常采用算法中基本运算的频度f(n)来分析算法的时间复杂度。因此算法的时间复杂度记为T(n) O(f(n)) 上式中 O 的含义是T(n) 的数量级其严格的数学定义是若T(n)和f(n)是定义在正整数集合上的 两个函数则存在正常数C 和n0使得当n n0时都满足0 T(n) Cf(n) 。
2.空间复杂度
算法的空间复杂度S(n)定义为该算法所耗费的存储空间它是问题规模n 的函数。记为S(n) O(g(n)) 一个程序在执行时除需要存储空间来存放本身所用的指令、常数、变量和输入数据外还需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。若输入数据所占空间只取决于问题本身和算法无关则只需分析除输入和程序之外的额外空间。 算法原地工作是指算法所需的辅助空间为常量即O(1)。
3.数的逻辑结构
指的是数据元素之间逻辑关系与数的存储结构无关是独立于计算机
4.数的存储结构
存储结构是指数据结构在计算机中的表示也称物理结构主要有以下4种 1) 顺序存储。 把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中元素之间的关系由存储单元的邻接关系来体现。其优点是可以实现随机存取每个元素占用最少的存储空间缺点是只能使用相邻的一整块存储单元因此可能产生较多的外部碎片。 2) 链式存储。 不要求逻辑上相邻的元素在物理位置上也相邻借助指示元素存储地址的指针来表示元素之间的逻辑关系。其优点是不会出现碎片现象能充分利用所有存储单元缺点是每个元素因存储指针而占用额外的存储空间且只能实现顺序存取。 3) 索引存储。 在存储元素信息的同时还建立附加的索引表。索引表中的每项称为索引项索引项的一般形式是关键字地址。其优点是检索速度快缺点是附加的索引表额外占用存储空间。另外增加和删除数据时也要修改索引表因而会花费较多的时间。 4) 散列存储。 根据元素的关键字直接计算出该元素的存储地址又称哈希存储。其优点是检索、增加和删除结点的操作都很快缺点是若散列函数不好则可能出现元素存储单元的冲突而解决冲突会增加时间和空间开销。
5.用循环比递归的效率高吗
循环和递归两者是可以互换的不能决定性的说循环的效率比递归高。 递归的优点是代码简洁清晰容易检查正确性缺点是当递归调用的次数较多时要增加额外的堆栈处理有可能产生堆栈溢出的情况对执行效率有一定的影响。 循环的优点是结构简单速度快缺点是它并不能解决全部问题有的问题适合于用递归来解决不适合用循环。
6.贪心算法和动态规划以及分治法的区别
贪心算法顾名思义就是做出在当前看来是最好的结果它不从整体上加以考虑也就是局部最优解。 贪心算法从上往下从顶部一步一步最优得到最后的结果它不能保证全局最优解与贪心策略的选择有关。 动态规划是把问题分解成子问题这些子问题可能有重复可以记录下前面子问题的结果防止重复计算。动态规划解决子问题前一个子问题的解对后一个子问题产生一定的影响。在求解子问题的过程中保留哪些有可能得到最优的局部解丢弃其他局部解直到解决最后一个问题时也就是初始问题的解。动态规划是从下到上一步一步找到全局最优解。各子问题重叠 分治法divide-and-conquer 将原问题划分成n个规模较小而结构与原问题相似的子问题递归地解决这些子问题然后再合并其结果 就得到原问题的解。各子问题独立 分治模式在每一层递归上都有三个步骤 分解Divide 将原问题分解成一系列子问题 解决conquer 递归地解各个子问题。若子问题足够小则直接求解 合并Combine 将子问题的结果合并成原问题的解。 例如归并排序
第二章、线性表
知识框架 7.顺序表和链表的比较
1.存取读写方式
顺序表可以顺序存取也可以随机存取链表只能从表头顺序存取元素。例如在第i个位置上执行存或取的操作顺序表仅需一次访问而链表则需从表头开始依次访问i次。
2.逻辑结构与物理结构
采用顺序存储时逻辑上相邻的元素对应的物理存储位置也相邻。而采用链式存储时逻辑上相邻的元素物理存储位置则不一定相邻对应的逻辑关系是通过指针链接来表示的。
3.查找、插入和删除操作
对于按值查找顺序表无序时两者的时间复杂度均为O(n); 顺序表有序时可采用折半查找此时的时间复杂度为O(log2n) 。 对于按序号查找顺序表支持随机访问时间复杂度仅为0(1), 而链表的平均时间复杂度为O(n) 。顺序表的插入、删除操作平均需要移动半个表长的元素。链表的插入、删除操作只需修改相关结点的指针域即可。 由于链表的每个结点都带有指针域故而存储密度不够大。
4.空间分配
顺序存储在静态存储分配情形下一旦存储空间装满就不能扩充若再加入新元素则会出现内存溢出因此需要预先分配足够大的存储空间。链式存储的结点空间只在需要时申请分配只要内存有空间就可以分配操作灵活、高效。
8.头指针和头结点的区别
头指针 是指向第一个节点存储位置的指针具有标识作用头指针是链表的必要元素无论链表是否为空头指针都存在。 头结点 是放在第一个元素节点之前便于在第一个元素节点之前进行插入和删除的操作头结点不是链表的必须元素可有可无头结点的数据域也可以不存储任何信息。
第三章、栈和队列
知识框架 9.栈和队列的区别
队列是允许在一段进行插入另一端进行删除的线性表。队列顾名思义就像排队一样对于进入队列的元素按“先进先出”的规则处理在表头进行删除在表尾进行插入。由于队列要进行频繁的插入和删除一般为了高效选择用定长数组来存储队列元素在对队列进行操作之前要判断队列是否为空或是否已满。如果想要动态长度也可以用链表来存储队列这时要记住队头和对位指针的地址。 栈是只能在表尾进行插入和删除操作的线性表。对于插入到栈的元素按“后进先出”的规则处理插入和删除操作都在栈顶进行与队列类似一般用定长数组存储栈元素。由于进栈和出栈都是在栈顶进行因此要有一个size变量来记录当前栈的大小当进栈时size不能超过数组长度size1出栈时栈不为空size-1。
10.共享栈
利用栈底位置相对不变的特性可以让两个顺序栈共享一个一维数组空间将两个栈的栈底分别设置在共享空间的两端两个栈顶向共享空间的中间延伸。这样能够更有效的利用存储空间两个栈的空间相互调节只有在整个存储空间被占满时才发生上溢。
11.如何区分循环队列是队空还是队满
普通情况下循环队列队空和队满的判定条件是一样的都是Q.front Q.rear。 ps:队头指针指向第一个数队尾指针指向最后一个数的下一个位置即将要入队的位置。 方法一牺牲一个单元来区分队空和队满这个时候(Q.rear1)%MaxSize Q.front才是队满标 志 。 方法二类型中增设表示元素个数的数据成员。这样队空的条件为Q.size 0;队满的条件为 Q.size MaxSize。
12.栈在括号匹配中的算法思想
括号匹配算法思想 1出现的凡是“左括号”则进栈 2出现的是“右括号” 首先检查栈是否空若栈空则表明该“右括号”多余 否则和栈顶元素比较若相匹配则栈顶“左括号出栈”否则表明不匹配 3表达式检验结束时 若栈空则表明表达式中匹配正确否则表明“左括号”有余。
13.栈在通过后缀表达式求值的算法思想
顺序扫描表达式的每一项然后根据它的类型做如下相应操作若该项是操作数则将其压入栈 中若该项是操作符,则连续从栈中退出两个操作数y 和x, 形成运算指令XY, 并将计算结果重新压入栈中。当表达式的所有项都扫描并处理完后栈顶存放的就是最后的计算结果。
14.栈在递归中的应用
递归是一种重要的程序设计方法。若在一个函数、过程或数据结构的定义中又应用了它自身则这个函数、过程或数据结构称为是递归定义的简称递归。 它通常把一个大型的复杂问题层层转化为一个与原问题相似的规模较小的问题来求解递归策略只需少量的代码就可以描述出解题过程所需要的多次重复计算大大减少了程序的代码量。但在通常情况下它的效率并不是太高。 将递归算法转换为非递归算法通常需要借助栈来实现这种转换。
15.队列在层次遍历中的作用
在信息处理中有一大类问题需要逐层或逐行处理。这类问题的解决方法往往是在处理当前层或当前行时就对下一层或下一行做预处理把处理顺序安排好待当前层或当前行处理完毕就可以处理下一层或下一行。使用队列是为了保存下一步的处理顺序。下面用二叉树层次遍历的例子说明队列的应用。
16.队列在计算机系统中的应用
队列在计算机系统中的应用非常广泛以下仅从两个方面来简述队列在计算机系统中的作用第一个方面是解决主机与外部设备之间速度不匹配的问题第二个方面是解决由多用户引起的资源竞争问题。 对于第一个方面仅以主机和打印机之间速度不匹配的问题为例做简要说明。主机输出数据给打印机打印输出数据的速度比打印数据的速度要快得多由于速度不匹配若直接把输出的数据送给打印机打印显然是不行的。解决的方法是设置一个打印数据缓冲区主机把要打印输出的数据依次写入这个缓冲区写满后就暂停输出转去做其他的事情。打印机就从缓冲区中按照先进先出的原则依次取出数据并打印打印完后再向主机发出请求。主机接到请求后再向缓冲区写入打印数据。这样做既保证了打印数据的正确又使主机提高了效率。由此可见打印数据缓冲区中所存储的数据就是一个队列。 对于第二个方面 CPU (即中央处理器它包括运算器和控制器资源的竞争就是一个典型的例子。在一个带有多终端的计算机系统上有多个用户需要CPU 各自运行自己的程序它们分别通过各自的终端向操作系统提出占用CPU 的请求。操作系统通常按照每个请求在时间上的先后顺序把它们排成一个队列每次把CPU 分配给队首请求的用户使用。当相应的程序运行结束或用完规定的时间间隔后令其出队再把CPU 分配给新的队首请求的用户使用。这样既能满足每个用户的请求又使CPU 能够正常运行。
17.矩阵的压缩存储
数据结构中提供针对某些特殊矩阵的压缩存储结构。这里所说的特殊矩阵主要分为以下两类 含有大量相同数据元素的矩阵比如对称矩阵 含有大量 0 元素的矩阵比如稀疏矩阵、上下三角矩阵 针对以上两类矩阵数据结构的压缩存储思想是矩阵中的相同数据元素包括元素 0只存储一个。
第四章、串
知识框架 18.串的模式匹配
子串的定位操作通常称为串的模式匹配他求的是子串常称模式串在主串中的位置。 暴力模式匹配算法的思想是从主串的第一个字符起与子串的第一个字符比较相等则继续比较不等则从主串的下一个位置起继续和子串开始比较直到最后看是否匹配成功。 以下的子串为‘abcac’: 改进的模式匹配算法-----KMP算法 从分析模式本身的结构着手如果已匹配相等的前缀序列中有某个后缀正好是模式的前缀那么就可以将模式向后滑动到与这些相等字符对齐的位置主串i指针无须回溯并继续从该位置开始进行比较。而模式向后滑动位数的计算仅与模式本身的结构有关与主串无关。
第五章、树与二叉树
知识框架 19.树与二叉树的相关概念
树是非线性结构其元素之间有明显的层次关系。在树的结构中每个节点都只有一个前件称为父节点没有前件的节点为树的根节点简称为树的根每个节点可以有多个后件成为节点的子节点没有后件的节点称为叶子节点。 在树的结构中一个节点所拥有的子节点个数称为该节点的度树中最大的节点的度为树的度树的最大的层次称为树的深度 二叉树二叉树是另一种树形结构其特点是每个结点至多只有两棵子树并且二叉树的子树有左右之分其次序不能任意颠倒。与树相似二叉树也以递归的形式定义。二叉树是n (n 0) 个结点的有限集合 1)或者为空二叉树即n0 。 2)或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。 二叉树是有序树若将其左、右子树颠倒则成为另一棵不同的二叉树。即使树中结点只有一棵子树也要区分它是左子树还是右子树 满二叉树满二叉树是指除了最后一层外其他节点均有两颗子树。 完全二叉树完全二叉树是指除了最后一层外其他任何一层的节点数均达到最大值且最后一层也只是在最右侧缺少节点 二叉树的存储二叉树可以用链式存储结构来存储满二叉树和完全二叉树可以用顺序存储结构来存储 二叉树的遍历二叉树有先序遍历根左右中序遍历左根右和后续遍历左右根还有层次遍历需要借助一个队列。 三种遍历算法中递归遍历左、右子树的顺序都是固定的只是访问根结点的顺序不同。不管采用哪种遍历算法每个结点都访问一次且仅访问一次故时间复杂度都是O(n) 。在递归遍历中递归工作栈的栈深恰好为树的深度所以在最坏情况下二叉树是有n 个结点且深度为n 的单支树遍历算法的空间复杂度为O(n) 。
20.如何由遍历序列构造一棵二叉树
1)由二叉树的先序序列和中序序列可以唯一地确定一棵二叉树。 在先序遍历序列中第一个结点一定是二叉树的根结点而在中序遍历中根结点必然将中序序列分割成两个子序列前一个子序列是根结点的左子树的中序序列后一个子序列是根结点的右子树的中序序列。根据这两个子序列在先序序列中找到对应的左子序列和右子序列。在先序序列中左子序列的第一个结点是左子树的根结点右子序列的第一个结点是右子树的根结点。如此递归地进行下去便能唯一地确定这棵二叉树。 2)由二叉树的后序序列和中序序列也可以唯一地确定一棵二叉树。 因为后序序列的最后一个结点就如同先序序列的第一个结点可以将中序序列分割成两个子序列然后采用类似的方法递归地进行划分进而得到一棵二叉树。 3由二叉树的层序序列和中序序列也可以唯一地确定一棵二叉树。需要注意的是若只知道二叉树的先序序列和后序序列则无法唯一确定一棵二叉树。
21.线索二叉树的概念
对于n个结点的二叉树在二叉链存储结构中有n1个空链域利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针这些指针称为线索加上线索的二叉树称为线索二叉树。 这种加上了线索的二叉链表称为线索链表相应的二叉树称为线索二叉树(ThreadedBinaryTree)。根据线索性质的不同线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。 注意线索链表解决了无法直接找到该结点在某种遍历序列中的前驱和后继结点的问题解决了二叉链表找左、右孩子困难的问题。 二叉树的遍历本质上是将一个复杂的非线性结构转换为线性结构使每个结点都有了唯一前驱和后继第一个结点无前驱最后一个结点无后继。对于二叉树的一个结点查找其左右子女是方便的其前驱后继只有在遍历中得到。为了容易找到前驱和后继有两种方法。一是在结点结构中增加向前和向后的指针这种方法增加了存储开销不可取二是利用二叉树的空链指针。
22.树的存储结构
1.双亲表示法
这种存储方式采用一组连续空间来存储每个结点同时在每个结点中增设一个伪指针指示其双亲结点在数组中的位置。 该存储结构利用了每个结点根结点除外只有唯一双亲的性质可以很快得到每个结点的双亲结点但求结点的孩子时需要遍历整个结构。
2.孩子表示法
孩子表示法是将每个结点的孩子结点都用单链表链接起来形成一个线性结构此时n 个结点就有n 个孩子链表叶子结点的孩子链表为空表这种存储方式寻找子女的操作非常直接而寻找双亲的操作需要遍历n个结点中孩子链表指针域所指向的n个孩子链表。
3.孩子兄弟表示法
孩子兄弟表示法又称二叉树表示法即以二叉链表作为树的存储结构。孩子兄弟表示法使每个结点包括三部分内容结点值、指向结点第一个孩子结点的指针及指向结点下一个兄弟结点的指针沿此域可以找到结点的所有兄弟结点 这种存储表示法比较灵活其最大的优点是可以方便地实现树转换为二叉树的操作易于查找结点的孩子等但缺点是从当前结点查找其双亲结点比较麻烦。若为每个结点增设一个parent域指向其父结点则查找结点的父结点也很方便。
23.二叉排序树
1.二叉排序树的定义
二叉排序树也称二叉查找树或者是一棵空树或者是具有下列特性的二叉树
若左子树非空则左子树上所有结点的值均小于根结点的值。若右子树非空则右子树上所有结点的值均大于根结点的值。左、右子树也分别是一棵二叉排序树。 根据二叉排序树的定义左子树结点值根结点值右子树结点值所以对二叉排序树进行中序遍历可以得到一个递增的有序序列。
2.二叉排序树的查找
二叉排序树的查找是从根节点开始的延某个分支逐层向下比较的过程。若二叉树非空先将给定值与根结点的关键字比较若相等则查找成功若不等如果小于根结点的关键字则在根结点的左子树上查找否则在根的右子树上查找。这显然是一个递归的过程。
24.平衡二叉树
为避免树的高度增长过快降低二叉排序树的性能规定在插入和删除二叉树结点时要保证任意结点的左、右子树高度差的绝对值不超过1, 将这样的二叉树称为平衡二叉树, 简称平衡树。定义结点左子树与右子树的高度差为该结点的平衡因子则平衡二叉树结点的平衡因子的值只可能是-1 、0 或1 。因此平衡二叉树可定义为或者是一棵空树或者是具有下列性质的二叉树它的左子树和右子树都是平衡二叉树且左子树和右子树的高度差的绝对值不超过1 。
25.哈夫曼树和哈夫曼编码 2.哈夫曼树的构造 给定n 个权值分别为W1,W2… Wn 的结点构造哈夫曼树的算法描述如下
将这n 个结点分别作为n 棵仅含一个结点的二叉树构成森林F 。构造一个新结点从F 中选取两棵根结点权值最小的树作为新结点的左、右子树并且将新结 点的权值置为左、右子树上根结点的权值之和。从F 中删除刚才选出的两棵树同时将新得到的树加入F 中。重复步骤2) 和3)直至F 中只剩下一棵树为止。 从上述构造过程中可以看出哈夫曼树具有如下特点每个初始结点最终都成为叶结点且权值越小的结点到根结点的路径长度越大。构造过程中共新建了n — 1 个结点双分支结点因此哈夫曼树的结点总数为2n -1 。每次构造都选择2 棵树作为新结点的孩子因此哈夫曼树中不存在度为1 的结点。 3.哈夫曼编码 在数据通信中若对每个字符用相等长度的二进制位表示称这种编码方式为固定长度编码。若允许对不同字符用不等长的二进制位表示则这种编码方式称为可变长度编码。可变长度编码比固定长度编码要好得多其特点是对频率高的字符赋以短编码而对频率较低的字符则赋以较长一些的编码从而可以使字符的平均编码长度减短起到压缩数据的效果。哈夫曼编码是一种被广泛应用而且非常有效的数据压缩编码。若没有一个编码是另一个编码的前缀则称这样的编码为前缀编码。 由哈夫曼树得到哈夫曼编码是很自然的过程。首先将每个出现的字符当作一个独立的结点其权值为它出现的频度或次数构造出对应的哈夫曼树。显然所有字符结点都出现在叶结点中。我们可将字符的编码解释为从根至该字符的路径上边标记的序列其中边标记为0 表示“转向左孩子”标记为1 表示“转向右孩子“。
第六章、图
知识框架 26.图的一些相关定义
无向图Undirected Graph每条边没有方向可以双向遍历。有向图Directed Graph每条边有方向只能按指定方向遍历。加权图Weighted Graph每条边带有一个权重Weight或成本用于表示边的关联强度或成本。有向无环图Directed Acyclic Graph简称DAG有向图中不存在环路的图。连通图Connected Graph在无向图中任意两个顶点之间都存在路径。强连通图Strongly Connected Graph在有向图中任意两个顶点之间都存在双向路径。子图Subgraph由原图中的一部分顶点和边组成的图。完全图Complete Graph任意两个顶点之间都有边相连的图。正则图Regular Graph所有顶点的度数相等的图。最小生成树Minimum Spanning Tree连接图上所有顶点的边的总权重最小的树。欧拉图Eulerian Graph可以沿着边遍历每个顶点一次且仅一次的图。哈密顿图Hamiltonian Graph含有一条包含所有顶点的哈密顿路径的图。
27.图的存储结构:
1.邻接矩阵法
所谓邻接矩阵存储是指用一个一维数组存储图中顶点的信息用一个二维数组存储图中边的信息即各顶点之间的邻接关系存储顶点之间邻接关系的二维数组称为邻接矩阵。有向图、无向图和网对应的邻接矩阵实例图如下 适合稠密图。
2.邻接表法
**当一个图为稀疏图时使用邻接矩阵法显然要浪费大量的存储空间而图的邻接表法结合了顺序存储和链式存储方法大大减少了这种不必要的浪费。**所谓邻接表是指对图G 中的每个顶点V建立一个单链表第i个单链表中的结点表示依附于顶点v, 的边对于有向图则是以顶点v, 为尾的弧这个单链表就称为顶点vi 的边表对于有向图则称为出边表。边表的头指针和顶点 的数据信息采用顺序存储称为顶点表所以在邻接表中存在两种结点顶点表结点和边表结点。
3.十字链表法
十字链表法是有向图的一种链式存储结构。在十字链表中对应于有向图中的每条弧有一个结点对应于每个顶点也有一个结点。
4.邻接多重表
邻接多重表是无向图的另一种链式存储结构。 在邻接表中容易求得顶点和边的各种信息但在邻接表中求两个顶点之间是否存在边而对边执行删除等操作时需要分别在两个顶点的边表中遍历效率较低。与十字链表类似在邻接多重表中每条边用一个结点表示每个顶点也用一个结点表示。
28.图的遍历
图的遍历是指从图中的某一顶点出发按照某种搜索方法沿着图中的边对图中的所有顶点访问一次且仅访问一次。注意到树是一种特殊的图所以树的遍历实际上也可视为一种特殊的图的遍历。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。图的遍历比树的遍历要复杂得多因为图的任一顶点都可能和其余的顶点相邻接所以在访问某个顶点后可能沿着某条路径搜索又回到该顶点上。为避免同一顶点被访问多次在遍历图的过程中必须记下每个已访问过的顶点为此可以设一个辅助数组visited[ ] 来标记顶点是否被访问过。图的遍历算法主要有两种广度优先搜索和深度优先搜索。
1.广度优先搜索(Breadth-First-Search, BFS)
类似于二叉树的层序遍历算法。基本思想是首先访问起始顶点V, 接着由V出发依次访问V 的各个未访问过的邻接顶点W1, W2,… Wn, 然后依次访问W1, W2,…, Wn 的所有未被访问过的邻接顶点再从这些访问过的顶点出发访问它们所有未被访问过的邻接顶点直至图中所有顶点都被访问过为止。若此时图中尚有顶点未被访问则另选图中一个未曾被访问的顶点作为初始点重复上述过程。Dijkstra源最短路径算法和Prim 最小生成树算法也应用了类似的思想。
2.深度优先搜索Depth-First-Search, DFS):
它的基本思想如下首先访问图中某一起始顶点V, 然后由v 出发访问与v 邻接且未被访问的任一顶点W1, 再访问与W1邻接且未被访问的任一顶点W2……重复上述过程。当不能再继续向下访问时依次退回到最近被访问的顶点若它还有邻接顶点未被访问过则从该点开始继续上述搜索过程直至图中所有顶点均被访问过为止。
29.最小生成树和最短路径
最小生成树是指在一个加权连通图中找到一个子图使得这个子图包含了原图中的所有顶点并且所有边的权重之和最小。换句话说最小生成树是一棵包含了原图全部顶点的树且这棵树中的边权重之和最小。最小生成树可以用来解决一些问题比如网络规划、电路布线等。
最短路径则是指在一个加权图中找到连接两个顶点的最短路径即路径上边的权重之和最小。最短路径算法常用于解决网络路由、导航、资源分配等问题。最短路径算法的经典示例是Dijkstra算法和Floyd-Warshall算法。
最小生成树和最短路径不一定是唯一的。对于最小生成树来说可能存在多个不同的最小生成树对于最短路径来说两个顶点之间可能存在多条长度相等的最短路径。在选择最小生成树或最短路径时需要根据具体情况做出合理的选择。
30.关键路径
关键路径Critical Path是项目管理中的一个概念用于确定整个项目中最长的路径以及该路径上的关键任务。关键路径包含了项目中不能延误的任务因为延误这些任务将会延误整个项目的完成时间。
第七章、查找
知识框架 31.对各种查找方法的概括
查找分为静态查找表和动态查找表静态查找表包括顺序查找、折半查找、分块查找动态查 找包括二叉排序树和平衡二叉树。 1顺序查找把待查关键字key放入哨兵位置i0再从后往前依次把表中元素和key比 较如果返回值为0则查找失败表中没有这个key值如果返回值为元素的位置ii!0则查找 成功设置哨兵的位置是为了加快执行速度。他的时间效率为On其特点是结构简单对 顺序结构和连式结构都适用但是查找效率太低。 2折半查找要求查找表为顺序存储结构并且有序若关键字在表中则返回关键字的位置若 关键字不在表中时停止查找的典型标志是查找范围的上界查找范围的下界。 3分块查找先把查找表分为若干子表要求每个子表的元素都要比他后面的子表的元素小 也就是保证块间是有序的但是子表内不一定有序把各子表中的最大关键字构成一张索引 表表中还包含各子表的起始地址。他的特点是块间有序块内无序查找时块间进行索引查 找块内进行顺序查找。 4二叉排序树二叉排序树的定义为或者是一棵空树或者是一棵具有如下特点的树如果 该树有左子树则其左子树的所有节点值小于根的值若该树有右子树则其右子树的所有节点 值均大于根的值其左右子树也分别为二叉排序树。在查找时可以进行动态的插入插入节点要 符合二叉排序树的定义这也是动态查找和静态查找的区别静态查找不能进行动态插入。 5平衡二叉树平衡二叉树又称为AVL树它或者是一棵空树或者具有如下特点他的左子树 和右子树的高度差的绝对值不能大于1且他的左右子树也都是平衡二叉树。 平衡因子是指左子树的高度减去右子树的高度它的值只能为1,0-1 如果再一个平衡二叉树中插入一个节点可能造成失衡这时就要进行树结构的调整即平衡旋 转。包括4中情况在左子树的左子树上插入节点时向右进行单向旋转在右子树的右子树上插入 节点时向左进行单向旋转在左子树的右子树插入节点时先向左旋转再向右旋转在右子树的左 子树插入节点时先向右旋转再向左旋转。
32.B树和B树
1.B 树又称多路平衡查找树 B 树中所有结点的孩子个数的最大值称为B 树的阶通常用m表示。一棵m 阶B 树或为空树或为满足如下特性的m 叉树
树中每个结点至多有m 棵子树即至多含有m-1 个关键字。若根结点不是终端结点则至少有两棵子树。除根结点外的所有非叶结点至少有「m/2] 棵子树即至少含有「m/2]- 1 个关键字。所有的叶结点都出现在同一层次上并且不带信息可以视为外部结点或类似千折半查找判定树的查找失败结点实际上这些结点不存在指向这些结点的指针为空。
B 树是所有结点的平衡因子均等于0 的多路平衡查找树。 2.B树是应数据库所需而出现的一种B 树的变形树。 一棵m 阶的B树需满足下列条件
每个分支结点最多有m 棵子树孩子结点。非叶根结点至少有两棵子树其他每个分支结点至少有「m/2]棵子树。结点的子树个数与关键字个数相等。所有叶结点包含全部关键字及指向相应记录的指针叶结点中将关键字按大小顺序排列 并且相邻叶结点按大小顺序相互链接起来。所有分支结点可视为索引的索引中仅包含它的各个子结点即下一级的索引块中 关键字的最大值及指向其子结点的指针 m 阶的B树与m 阶的B 树的主要差异如下在B树中具有n 个关键字的结点只含有n 棵子树即每个关键字对应一棵子树而在 B 树中具有n 个关键字的结点含有n1棵子树。在B树中每个结点非根内部结点的关键字个数n 的范围是「m/2]n m (根结点 1nm); 在B 树中每个结点非根内部结点的关键字个数n 的范围是「m/2]-1n m-1 。在B树中叶结点包含信息所有非叶结点仅起索引作用非叶结点中的每个索引项只 含有对应子树的最大关键字和指向该子树的指针不含有该关键字对应记录的存储地址。在B树中叶结点包含了全部关键字即在非叶结点中出现的关键字也会出现在叶结点 中而在B 树中叶结点包含的关键字和其他结点包含的关键字是不重复的
第八章、排序
知识框架: 33.对各种内部排序的概括与总结
排序是指把一个任意元素的序列排列成一个按关键字key有序的序列。内部排序包括插入排序、选择排序、交换排序、归并排序、基数排序。其中插入排序包括直接插入排序、折半插入排序、希尔排序选择排序包括简单选择排序堆排序交换排序包括冒泡排序、快速排序。 1直接插入排序稳定基本思想为将序列分为有序部分和无序部分从无序部分依次选择元素与有序部分比较找到合适的位置将原来的元素往后移将元素插入到相应位置上。时间复杂度为On^2,空间复杂度为O1 2折半插入排序稳定基本思想为设置三个变量low high mid令mid(lowhigh)/2,若a[mid]key,则令highmid-1,否则令lowmid1,直到lowhigh时停止循环对序列中的每个元素做以上处理找到合适位置将其他元素后移进行插入。他的比较次数为O(nlog2n),但是因为要后移因此时间复杂度为O(n^2),空间复杂度为O(1)。 优点是比较次数大大减少。 3希尔排序不稳定基本思想为先将序列分为若干个子序列对各子序列进行直接插入排序等到序列基本有序时再对整个序列进行一次直接插入排序。优点是让关键字值小的元素能够很快移动到前面且序列基本有序时进行直接插入排序时间效率会提升很多空间复杂度为O1。 4简单选择排序不稳定基本思想为将序列分为2部分每经过一趟就在无序部分找到一个最小值然后与无序部分的第一个元素交换位置。优点是实现起来特别简单缺点是每一趟只能确定一个元素的位置时间效率低。时间复杂度为On^2空间复杂度为O1。 5堆排序不稳定设有一个任意序列k1,k2,…,kn当满足下面特点时称之为堆让此序列排列成完全二叉树该树具有以下特点该树中任意节点均大于或小于其左右孩子此树的根节点为最大值或者最小值。优点是对大文件效率明显提高但对小文件效率不明显。时间复杂度为O(nlog2n),空间复杂度为O(1)。 6冒泡排序稳定基本思路为每一趟都将元素进行两两比较并且按照“前小后大”的规则进行交换。优点是每一趟不仅能找到一个最大的元素放到序列后面而且还把其他元素理顺如果下一趟排序没有发生交换则可以提前结束排序。时间复杂度为On^2,空间复杂度为O1。 7快速排序不稳定基本思路为在序列中任意选择一个元素作为中心比它大的元素一律向后移动比它小的元素一律向前移动形成左右两个子序列再把子序列按上述操作进行调整直到所有的子序列中都只有一个元素时序列即为有序。优点是每一趟不仅能确定一个元素时间效率较高。时间复杂度为O(nlog2n),空间复杂度为Olog2n. 8归并排序稳定基本思想为把两个或者两个以上的有序表合并成一个新的有序表。时间复杂度为Onlogn,空间复杂度和待排序的元素个数相同。 9基数排序时间复杂度为对于n个记录进行链式基数排序的时间复杂度为Od(nrd),其中每一趟分配的时间复杂度为O(n),回收的时间复杂度为Ord。 各种排序的总结表格如下 直接插入排序、冒泡排序和简单选择排序是基本的排序方法它们主要用于元素个数n不是很大(n 10000) 的情形。 对于中等规模的元素序列(n 1000), 希尔排序是一种很好的选择。 对于元素个数n 很大的情况可以采用快排、堆排序、归并排序或基数排序其中快排和堆排序都是不稳定的而归并排序和基数排序是稳定的排序算法。
34.快速排序基本原理
快速排序Quick Sort是常用的排序算法之一。其基本原理如下
1. 选择一个元素作为枢纽pivot常规选择数组的第一个元素或者随机选择一个元素作为枢纽。 2. 将数组分割成两个子数组使得左子数组中的元素都小于等于枢纽右子数组中的元素都大于等于枢纽。 3. 对左子数组和右子数组递归地进行快速排序。 4. 合并排序后的左子数组、枢纽元素和右子数组得到最终有序的数组。
快速排序是一种高效的排序算法平均时间复杂度为O(nlogn)但它的最坏时间复杂度为O(n^2)即在最差情况下可能出现时间复杂度退化的情况。为了避免最坏情况的发生可以采取一些优化策略如随机选择枢纽元素或者使用三数取中法来选择枢纽元素等。
本期推荐 硅基物语 AI写作高手从零开始用ChatGPT学会写作 看清AI写作逻辑 讲透AI写作之道购买通道
