专业教学资源库网站建设工作,咸阳市网站建设,培训班的ui设计,软件技术方案模板文章目录第一章 绪论考点 1#xff1a;时间复杂度与空间复杂度时间复杂度空间复杂度第二章 线性表考点 2#xff1a;顺序表考点 3#xff1a;单链表第三章 栈和队列考点 4#xff1a;栈和队列的基本性质考点5#xff1a;循环队列考点6#xff1a;双端队列输出受限的双端队…
文章目录第一章 绪论考点 1时间复杂度与空间复杂度时间复杂度空间复杂度第二章 线性表考点 2顺序表考点 3单链表第三章 栈和队列考点 4栈和队列的基本性质考点5循环队列考点6双端队列输出受限的双端队列输入受限的双端队列考点7栈与队列的应用考点 8特殊矩阵的存储第四章 串考点 9串的模式匹配算法第五章 树与二叉树考点 10树的基本性质考点 11特殊二叉树的定义与性质特殊二叉树完全二叉树的性质考点 12二叉树的遍历考点 13树、森林与二叉树的转换考点 14线索二叉树考点 15哈夫曼哈夫曼树哈夫曼编码第六章 图考点 16图的基本概念基本术语图的基本性质考点 17图的存储及基本操作邻接矩阵存储法邻接表存储法考点 18图的遍历广度优先搜索 BFS深度优先搜索 DFS考点 19最小代价生成树Prim 算法Kruskal 算法考点 20最短路径最短路径权值问题Dijkstra 算法Floyd 算法考点 21拓扑排序考点 22关键路径求关键路径算法第七章 查找考点 23查找的基本术语考点 24顺序查找第一章 绪论
考点 1时间复杂度与空间复杂度
时间复杂度
定义将算法中基本运算的执行次数的数量级作为时间复杂度记为O(n)O(n)O(n)。
计算原则
加法法则T(n)T1(n)T2(n)O(f(n))O(g(n))O(max(f(n),g(n)))T(n)T_{1}(n)T_{2}(n)O(f(n))O(g(n))O(\max (f(n), g(n)))T(n)T1(n)T2(n)O(f(n))O(g(n))O(max(f(n),g(n)))乘法法则T(n)T1(n)T2(n)O(f(n))O(g(n))O(f(n)g(n))T(n)T_{1}(n) T_{2}(n)O(f(n)) O(g(n))O(f(n) g(n))T(n)T1(n)T2(n)O(f(n))O(g(n))O(f(n)g(n))
计算方法
列方程法用于递推实现的算法中设基本运算运行xxx次找出与问题规模nnn之间的方程关系式解出xf(n)xf\left ( n \right )xf(n)f(n)f\left ( n \right )f(n)的最高次数为kkk则算法的时间复杂度为O(nk)O\left ( n^{k} \right )O(nk)。递推公式法用于递归实现的算法中设T(n)T\left ( n \right )T(n)是问题规模为nnn的算法的时间复杂度T(n−1)T(n-1)T(n−1)是问题规模为n−1n-1n−1的算法的时间复杂度建立T(n)T(n)T(n)与T(n−1)T(n-1)T(n−1)[或T(n−2)T(n-2)T(n−2)等]的递推关系式根据关系式解出T(n)T(n)T(n)。
空间复杂度
定义指算法运行过程中所使用的辅助空间的大小记为S(n)S(n)S(n)。算法原地工作是指算法所需辅助空间是常量即O(1)O(1)O(1)。 递归算法特性 一个算法直接或间接调用自身称为递归调用。必须有一个明确的递归结束条件称为递归出口。实现递归的关键是建立递归调用工作栈。栈的大小也就是递归深度和递归算法空间复杂度的。 第二章 线性表
考点 2顺序表
定义指用一组连续的存储单元依次存储线性表中的各个元素从而使得逻辑上相邻的元素在物理位置上也相邻因此可以随机存取根据首元素地址和元素序号表中任何一个元素。
基本操作 结构 插入 若表长为nnn,下标从0开始则在第iii位置插入元素eee则从ana_nan到aia_iai都要向后移动一个位置共需移动n−i1n-i1n−i1个元素平均时间复杂度为O(n)O(n)O(n)。 //判断1的范围是否有效否则非法
//判断当前存储空间是否已满否则不能插入
for(int jL.length;ji;--) //将第1个位置及之后的元素后移L.data[j]L.data[j-1];
L.data[i-1]e; //在位置i处放入e,数组从0开始存储
L.length; //线性表长度加1删除 若表长为nnn,下标从000开始当删除第i个元素时则从i个元素时则从i个元素时则从ai1a_{i1}ai1 到ana_nan都要向前移动一个位置共需移动n−in-in−i个元素平均时间复杂度为O(n)O(n)O(n)。 //判断1的范围是否有效
for(int ji;jL.length;j) //将第i个位置及之后的元素前移L.data[j-1]L.data[j];
L.length--; //线性表长度减1查找 按序号下标查找顺序表具有随机存取根据首元地址和序号的特点时间复杂度为O(1)O(1)O(1)。按值查找主要运算是比较操作比较的次数与值在表中的位置和表长有关平均比较次数为(n1)/2(n1)/2(n1)/2时间复杂度为O(n)O(n)O(n)。
考点 3单链表
定义为了建立元素之间的线性关系对每个链表结点除了存放元素自身的信息还需要存放一个指向其后继的指针。
基本操作 查找 只能从表中第一个结点出发顺序查找顺着指针nextnextnext域逐个往下搜索直到找到满足条件的结点为止。时间复杂度为O(n)O(n)O(n)。 创建 头插法从一个空表开始然后将新结点插入到当前链表的表头即头结点之后。 s-nextL-next; //①新结点的指针指向原链表的第一个结点
L-nexts; //②头结点的指针指向新结点L为头指针尾插法将新结点插入到当前链表的表尾上为此必须增加一个尾指针 rrr使其始终指向当前链表的尾结点。 r-nexts; //原链表中的尾结点r所指的指针指向新结点
rs; //r指向新的表尾结点插入 将值为xxx的新结点插入到单链表的第iii个位置。先检查插入位置的合法性然后找到待插入位置的前驱结点即第i−1i-1i−1 个结点再在其后插入新结点。 pGetElem(L,i-1); //查找插入位置的前驱结点
s-nextp-next; //①s的指针指向p的下一结点
p-next-s; //②p的指针指向s删除 将单链表的第iii个结点删除。先检查删除位置的合法性然后查找表中第i−1i-1i−1 个结点即被删结点的前驱结点再将其删除。 pGetElem(L,i-1); //查找删除位置的前驱结点
qp-next; //令q指向被删除结点
p-nextq-next; //将*q结点从链中断开
delete q; //释放待删结点所占空间求表长 不含头结点从首结点开始依次顺序访问表中的每个结点为此需要设置一个计数器变量每访问一个结点计数器加111直到访问到NULLNULLNULL为止。不带头结点的单链表的表长时对空结点需要单独处理。 len0; //1en表示单链表长度初值设为0
LNode *pL-next; //令p指向单链表的第一个结点
while(p) {len;pp-next;} //跳出循环时len的值即为单链表的长度第三章 栈和队列
考点 4栈和队列的基本性质
术语定义栈只允许在表的一端栈顶进行插入或删除的线性表。栈的操作特性为先进后出。队列只允许在表尾队尾插入表头队头删除的线性表。队列的操作特性为先进先出。nnn个不同的元素进栈则不同出栈序列个数为1n1C2nn\frac{1}{n1} C_{2 n}^{n}n11C2nn。 考点5循环队列
定义把顺序存储的队列从逻辑上视为一个环称为循环队列。通常利用除模取余运算(%)(\%)(%)来实现循环。 基本操作 元素出队Q.front(Q.front1)%MaxSize 元素入队Q.rear(Q.rearl)%MaxSize 队列长度(Q.rear-Q.front-MaxSize)%MaxSizefrontfrontfront指向第一个元素、rearrearrear指向最后一个元素的下一位置) 为了区分是队空还是队满通常采用牺牲一个存储单元的方法约定以“队头指针在队尾指针的下一位置作为队满的标志”。 队满条件(Q.rear1)%MaxSizeQ.front 队空条件Q.frontQ.rear 考点6双端队列
定义允许两端都可以进行入队和出队操作的队列即每个元素仅有一个前驱结点和一个后继结点首位元素除外。将队列的两端分别称为前端和后端。 基本操作 进队前端进的元素排在后端进的元素的前面后端进的元素排在前端进的元素的后面。 出队无论是前端出队还是后端出队先出的元素排列在后出的元素的前面。
输出受限的双端队列
定义允许在一端进行插入和删除但在另一端只允许插入的双端队列。 输入受限的双端队列
定义允许在一端进行插入和删除但在另一端只允许删除的双端队列。 考点7栈与队列的应用
栈的应用队列的应用数制转换层序遍历二叉树括号匹配缓冲区表达式求值进程的就绪队列给定进栈和出栈顺序确定该栈的最小容量最大深度广度优先遍历BFSBFSBFS
考点 8特殊矩阵的存储
存储方式
按行优先存储按列优先存储
特殊矩阵 对称矩阵 存储方式只存放主对角线和下三角区的元素。 三角矩阵 下三角矩阵上三角区的所有元素均为同一常量存储完下三角区和主对角线上的元素之后紧接着存储对角线上方的常量一次。 上三角矩阵下三角区的所有元素均为同一常量存储完上三角区和主对角线上的元素之后紧接着存储对角线下方的常量一次。
第四章 串
考点 9串的模式匹配算法 简单模式匹配算法 算法思想从主串SSS的第一个字符起与模式TTT的第一个字符比较若相等则继续逐个比较后续字符否则从主串的下一个字符起重新和模式的字符比较以此类推直至模式TTT中的每个字符依次和主串SSS 中一个连续的字符序列相等则称匹配成功否则称匹配不成功。简单模式匹配算法的最坏时间复杂度为O(mn)O(mn)O(mn)。 算法代码 int Index(SString S,SString T){int i1,j1;while(iS.length jT.length){ if(S.ch[i]T.ch[j]){ 1j;//继续比较后继字符 }else{ ii-j2;j1;//指针后退重新开始匹配 }}if(jT.length) return i-T.length;else return 0;
}KMPKMPKMP 算法 前缀指除最后一个字符以外字符串的所有头部子串。 后缀指除第一个字符外字符串的所有尾部字串。 部分匹配值字符串的前缀和后缀的最长相等前后缀长度。 匹配失败时子串需要向后移动的位数移动位数已匹配的字符数-最后一位匹配字符对应的部分匹配值。 Next 数组计算 计算模式串中每个位置所对应的字串的最长前缀长度最后一个位置所对应的字串无须计算)记为next1next1next1。next1next1next1右移111位第111位补−1-1−1得nextnextnext数组。
第五章 树与二叉树
考点 10树的基本性质
树的基本术语
术语定义结点的度树中一个结点的子结点个数树的度树中结点的最大度数分支结点度大于 0 的结点称为分支结点叶子结点度等于 0 的结点称为叶子结点结点的深度从根结点到该结点的路径上结点的个数之和根结点深度为 1树的高度树中结点的最大层数根结点为第一层路径树中两个结点之间所经过的结点序列路径长度路径上所经过的边的条数树可以是空树结点数0。森林可以是空森林树个数0。 树的基本性质
树中的结点总数等于总度数加 1结点总数边总数 1。度为mmm的树中第hhh层最多有mh−1m^{h-1}mh−1个结点。高度为hhh的mmm叉树最多有(mk−1)/(m−1)(m^k-1)/(m-1)(mk−1)/(m−1)个结点。具有nnn个结点的mmm叉树的最小高度为⌈logm(n(m−1)1)⌉\left\lceil\log_{m}{\left(n\left(m-1\right)1\right)}\right\rceil⌈logm(n(m−1)1)⌉。
考点 11特殊二叉树的定义与性质
特殊二叉树
术语定义满二叉树一棵高度为hhh并且含有2h−12^h-12h−1个结点的二叉树称为满二叉树。满结点。完全二叉树一棵高度为hhh有nnn个结点的二叉树仅当其每个结点都与高度为hhh个结点的二叉树仅当其每个结点都与高度为hhh的满二叉树中编号为1∼n1\sim n1∼n 的结点一一对应称为完全二叉树。
完全二叉树的性质
最后一个分支结点非叶结点的编号⌊n/2⌋\left \lfloor n/2 \right \rfloor⌊n/2⌋。叶子结点只可能在层次最大的两层上出现。如果有度为111 的结点只可能有一个且该结点只有左孩子。若nnn为奇数则每个分支结点都有左子女和右子女若nnn 为偶数则编号最大的分支结点只有左子女。结点iii所在层次深度为⌊log2i⌋1\left\lfloor\log _{2} i\right\rfloor1⌊log2i⌋1。具有nnn个(n0)(n0)(n0)结点的完全二叉树的高度为⌊log2(n1)⌋\left\lfloor\log _{2} (n1)\right\rfloor⌊log2(n1)⌋或⌊log2n⌋1\left\lfloor\log _{2} n\right\rfloor1⌊log2n⌋1。编号为iii的结点的双亲结点的编号为⌊i/2⌋\left \lfloor i/2 \right \rfloor⌊i/2⌋左孩子编号为2i2i2i右孩子编号为2i12i12i1。
考点 12二叉树的遍历
遍历方式
先序遍历先访问根结点再访问左子树最后访问右子树。中序遍历先访问左子树再访问根结点最后访问右子树。后序遍历先访问左子树再访问右子树最后访问根结点。层序遍历按自顶向下、自左向右的顺序来逐层访问树中结点。
构造二叉树
中序序列与前序序列。中序序列与后序序列。中序序列与层序序列。 唯一确定一棵二叉树的序列组合都需要中序序列 考点 13树、森林与二叉树的转换
规则左结点指向孩子结点右结点指向兄弟结点左孩子右兄弟。
考点 14线索二叉树
结点结构 线索利用空链域存放指向直接前驱或直接后继的指针。
线索化对二叉树遍历使其变为线索二叉树。线索化时若无左子树则令IchildIchildIchild指向其前驱结点若无右子树则令rchildrchildrchild指向其后继结点。两个tagtagtag标志域表明当前指针域所指对象是指向左右子结点还是直接前驱后继。 ltag {0,lchild域指示结点的左孩子 1,lchild域指示结点的前驱 rtag{0,rchild域指示结点的右孩子 1,rchild域指示结点的后继 \text { ltag }\left\{\begin{array}{ll} 0, \text { lchild域指示结点的左孩子 } \\ 1, \text { lchild域指示结点的前驱 } \end{array}\right.\operatorname{rtag}\left\{\begin{array}{ll} 0, \text { rchild域指示结点的右孩子 } \\ 1, \text { rchild域指示结点的后继 } \end{array}\right. ltag {0,1, lchild域指示结点的左孩子 lchild域指示结点的前驱 rtag{0,1, rchild域指示结点的右孩子 rchild域指示结点的后继 在有 N 个结点的二叉树中有 N1 个空指针域。 考点 15哈夫曼
哈夫曼树
树的带权路径长度树中所有叶结点的带权路径长度之和。wiw_iwi是第iii个叶结点所带的权值lil_ili是该叶结点到根结点的路径长度。 WPL∑i1nwili\mathrm{WPL}\sum_{i1}^{n} w_{i} l_{i} WPLi1∑nwili
哈夫曼树带权路径长度最小的二叉树。
构造哈夫曼树
构造一个新结点选取两个权值最小的结点作为新结点的左、右子树新结点的权值置为左、右子树上根结点的权值之和。从序列中删除刚才选出的两个结点同时将新结点加入序列。
哈夫曼树特点
每个初始结点最终都成为叶结点并且权值越小的结点到根结点的路径长度越大。哈夫曼树中结点总数为2N−12N-12N−1。哈夫曼树中不存在度为111的结点。同一序列构造的哈夫曼树不唯一但带权路径长度唯一且最优。
哈夫曼编码
前缀编码没有一个编码是另一个编码的前缀。
哈夫曼编码构造 根据待编码元素构造对应的哈夫曼树。 从根至该字符的路径上进行标记“左孩子”的边标记为000“右孩子”的边标记为111。 从根结点到待编码元素结点的路径形成的000、111序列就是哈夫曼编码。
第六章 图
考点 16图的基本概念
基本术语 无向图有向图边顶点的无序对记为(v,w)(v,w)(v,w)或(w,v)(w,v)(w,v)弧顶点的有序对记为v,wv,wv,wvvv称为弧尾www 称为弧头无向图若EEE是无向边简称边的有限集合时则图GGG为无向图有向图若EEE是有向边也称弧的有限集合时则图GGG为有向图顶点的度指依附于该顶点的边的数量记为TD(v)TD(v)TD(v)顶点的度入度和出度之和入度是以vvv为终点的有向边的数目出度是以vvv为起点的有向边的数目连通从顶点vvv到顶点www有路径存在则称vvv和www 是连通的强连通从顶点vvv到顶点www和从顶点www到顶点vvv之间都有路径则称vvv和www 是强连通的连通图图中任意两个顶点都是连通的则称图GGG为连通图否则为非连通图强连通图图中任意一对项点都是强连通的则称此图为强连通图连通分量图的极大连通子图称为连通分量强连通分量图的极大强连通子图称为有向图的强连通分量无向完全图任意两个顶点之间都存在边共有(n−1)/2(n-1)/2(n−1)/2条边有向完全图任意两个顶点之间都存在方向相反的两条弧共有n(n−1)n(n-1)n(n−1)条有向边
术语定义生成树连通图的生成树是包含图中全部顶点的一个极小连通子图生成森林非连通图的连通分量的生成树构成了非连通图的生成森林回路环第一个顶点和最后一个顶点相同的路径称为回路或环极大连通子图包含了图中尽可能多的顶点以及尽可能多的边极小连通子图包含图中全部顶点且包含边最少 图的基本性质
无向图中任意顶点的入度等于出度。无向图中无论是否连通所有顶点的度数之和等于边数的两倍。在有向图中全部顶点的“入度之和”“出度之和”边数。图的邻接矩阵表示中各顶点的度等于矩阵中该结点对应的行对应出度和列对应入度的非零元素数量之和。
考点 17图的存储及基本操作
邻接矩阵存储法 方式用一个一维数组存储图中顶点的信息用一个二维数组存储图中边的信息
特点 无向图的邻接矩阵一定是一个对称矩阵可采用压缩存储。有向图的邻接矩阵不一定是对称矩阵有向完全图的邻接矩阵是对称矩阵。 对于无向图邻接矩阵的第iii行或第iii列非零元素或非∞∞∞元素的个数正好是第 iii个顶点的度。 对于有向图邻接矩阵的第iii行或第iii列非零元素或非∞∞∞元素的个数正好是第iii个顶点的出度或入度。 对于无权图的邻接矩阵AAA矩阵中各位置的值为000或111An[i][j]\left.A^{n}[i][j\right]An[i][j]的值表示由顶点iii到顶点jjj的路径长度为nnn的路径的数量。 稠密图适合使用邻接矩阵的存储表示。
邻接表存储法 方式
将图中所有邻接于顶点vvv的顶点链成一个单链表这个单链表就称为顶点vvv 的邻接表。将所有顶点的邻接表的表头放到数组中就构成了图的邻接表。
特点 若无向图有nnn个顶点、eee条边则其邻接表仅需nnn个头结点和2e2e2e个表结点。 对于无向图顶点viv_ivi的度等于第iii个链表中的结点数对于有向图第iii 个链表中的结点数只是顶点viv_ivi的出度求入度必须遍历整个邻接表。 在邻接表上容易找到任一顶点连接的所有边。但要判定任意两个顶点viv_ivi和vjv_jvj之间是否有边或弧相连则需搜索第iii个或第jjj 个链表在这方面不及邻接矩阵方便。 图的邻接表不唯一取决于建立邻接表的算法以及边的输入次序。
考点 18图的遍历
广度优先搜索 BFS 遍历过程
访问起始顶点vvv。依次访问顶点vvv未访问过的邻接顶点v2v_2v2v3v_3v3。直到图中所有和vvv连通的顶点都被访问过为止。另选一个未被访问过的顶点作为起始顶点 vvv重新开始直至所有顶点都被访问。
性能分析
BFSBFSBFS算法需要借助一个辅助队列空间复杂度为O(∣V∣)O(|V|)O(∣V∣)。邻接矩阵表示时算法总的时间复杂度为O(∣V∣2)O(|V|^2)O(∣V∣2)。邻接表表示时算法总的时间复杂度为O(∣V∣∣E∣)O(|V||E|)O(∣V∣∣E∣)。
深度优先搜索 DFS 遍历过程
访问起始顶点vvv。访问与顶点vvv邻接且未被访问过的任一邻接顶点v2v_2v2。再访问与v2v_2v2邻接且未被访问的任一顶点v3v_3v3。当不能再继续向下访问时依次退回到最近被访问的顶点若它还有邻接顶点未被访问则从该顶点重新开始直到图中所有顶点均被访问过为止。
性能分析
DFSDFSDFS算法需要借助一个递归工作栈空间复杂度为O(∣V∣)O(|V|)O(∣V∣)。邻接矩阵表示时算法总的时间复杂度为O(∣V∣2)O(|V|^2)O(∣V∣2)。邻接表表示时算法总的时间复杂度为O(∣V∣∣E∣)O(|V||E|)O(∣V∣∣E∣)。 对于同一个图基于邻接矩阵的遍历所得到的DFSDFSDFS序列和BFSBFSBFS序列是唯一的由于邻接表不唯一所以基于邻接表的遍历所得到的DFSDFSDFS序列和BFSBFSBFS序列可能不唯一。 考点 19最小代价生成树
定义所有生成树的集合中边的权值之和最小的那棵生成树。
性质
最小生成树不唯一。当图中的各边权值互不相等时G 的最小生成树唯一。最小生成树所对应的边的权值之和总是唯一的而且是最小的。最小生成树是一棵无向连通带权图。
Prim 算法 每次在已选顶点的邻接边中选权值最小的边加入。 PrimPrimPrim算法的时间复杂度为O(∣V∣2)O(|V|^2)O(∣V∣2)不依赖于EEE适用于边稠密的图。
Kruskal 算法 不断选取当前未被选取的权值最小的边若其两个顶点不属于同一顶点集合则将该边放入生成树的边集同时将两个顶点所在的集合合并。 直到选取了n−1n-1n−1条边为止。 KruskalKruskalKruskal算法的时间复杂度为O(∣E∣log2∣E∣)O\left(|E| \log _{2}|E|\right)O(∣E∣log2∣E∣)适用于边稀疏而顶点较多的图。
考点 20最短路径
最短路径权值问题
单源最短路径问题求从给定源点到其他各个顶点的最短路径长度。点对点最短路径问题求每一对顶点之间的最短路径长度。
Dijkstra 算法
用邻接矩阵arcsarcsarcs表示带权有向图 arcs[i][j]{eij,eij为有向边 i,j的权值 ∞,不存在有向边 i,j\operatorname{arcs}[i][j]\left\{\begin{array}{ll} e_{i j}, e_{i j} \text { 为有向边 }i, j\text { 的权值 } \\ \infty, \text { 不存在有向边 }i, j \end{array}\right.arcs[i][j]{eij,∞,eij 为有向边 i,j 的权值 不存在有向边 i,j
算法过程 dist[]dist[]dist[]记录了从源点v0v_0v0到其他各顶点当前的最短路径长度。 集合 SSS 记录已求得的最短路径的顶点每趟确定一个最短路径。 Floyd 算法
算法过程 定义一个 n 阶方阵序列A(−1),A(0),⋯,A(n−1)。A^{(-1)}, A^{(0)}, \cdots, A^{(n-1)}。A(−1),A(0),⋯,A(n−1)。 A(−1)[i][j]arcs[i][j]A^{(-1)}[i][j]\operatorname{arcs}[i][j]A(−1)[i][j]arcs[i][j]arcs[i][j]\operatorname{arcs}[i][j]arcs[i][j]与迪杰斯特拉算法中的定义相同。 递推产生A(k)[i][j]Min{A(k−1)[i][j],A(k−1)[i][k]A(k−1)[k][j]},k0,1,⋯,n−1A^{(k)}[i][j]\operatorname{Min}\left\{A^{(k-1)}[i][j], \quad A^{(k-1)}[i][k]A^{(k-1)}[k][j]\right\}, \quad k0,1, \cdots, n-1A(k)[i][j]Min{A(k−1)[i][j],A(k−1)[i][k]A(k−1)[k][j]},k0,1,⋯,n−1。 A(k)[i][j]A(k)[i][j]A(k)[i][j]是从顶点viv_ivi到到到vjv_jvj、中间顶点的序号不大于kkk的最短路径的长度。 经过nnn次迭代后所得到的A(n−1)[i][j]A(n-1)[i][j]A(n−1)[i][j]就是viv_ivi到vjv_jvj 的最短路径长度。
Floyd 算法的时间复杂度为O(∣V∣3)O(|V|^3)O(∣V∣3)。
Floyd 算法允许图中有带负权值的边但不允许有包含带负权值的边组成的回路。
考点 21拓扑排序
定义
有向无环图的顶点组成的序列。每个顶点出现且只出现一次。每个有向无环图都有一个或多个拓扑序列。
算法过程
从有向无环图中选择一个没有前驱的顶点并输出。从图中删除该顶点和所有以它为起点的有向边。直到当前的图为空或当前图中不存在无前驱的项点为止环。
拓扑排序的时间复杂度为O(∣V∣∣E∣)O(|V||E|)O(∣V∣∣E∣)。
考点 22关键路径
AOE 网带权有向图以顶点表示事件有向边表示活动边上的权值表示完成该活动的开销。
关键路径AOE 网中从源点到汇点的最大路径长度的路径关键路径长度是整个工程所需的最短工期。
关键活动关键路径上的活动。
性质
可以通过加快关键活动缩短整个工程的工期。并非关键活动缩短多少工期就缩短多少因为缩短到一定的程度该关键活动可能变成非关键活动了。关键路径并不唯一。对于有几条关键路径的网只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。从源点到汇点的路径上所有具有最大路径长度的路径都是关键路径。所有“最长路径”关键路径上的所有活动都是关键活动。
求关键路径算法
参数定义
事件vkv_kvk的最早发生时间ve(k)ve(k)ve(k)从源点到顶点VkV_kVk的最长路径长度
ve(k){0,k0,vk是源点max{ve(j)Weight(vj,vk)},Weight(vj,vk)表示vj,vk上的权值\operatorname{ve}(k)\left\{\begin{array}{ll}0, k0, \mathrm{v}_{k} \text { 是源点} \\\max \left\{\operatorname{ve}(j)\text {Weight}\left(\mathrm{v}_{j},\mathrm{v}_{k}\right)\right\}, \text{Weight}\left(\mathrm{v}_{j}, \mathrm{v}_{k}\right) \text {表示}\left.\mathrm{v}_{j},\mathrm{v}_{k}\right.\text {上的权值}\end{array}\right. ve(k){0,max{ve(j)Weight(vj,vk)},k0,vk 是源点Weight(vj,vk)表示vj,vk上的权值
事件vkv_kvk的最迟发生时间vl(k)vl(k)vl(k):从顶点VkV_kVk到汇点的最短路径长度
vl(j){ve(n−1),jn−1,vj是汇点 min{vl(k)−Weight(vj,vk)},Weight(vj,vk)表示vj,vk的权值\operatorname{vl}(j)\left\{\begin{array}{ll} \mathrm{ve}(n-1), jn-1, \mathrm{v}_{j} \text { 是汇点 } \\ \min \left\{\mathrm{vl}(k)-\operatorname{Weight}\left(\mathrm{v}_{j}, \mathrm{v}_{k}\right)\right\}, \text { Weight}\left(\mathrm{v}_{j}, \mathrm{v}_{k}\right) \text {表示}\mathrm{v}_{j}, \mathrm{v}_{k}\text {的权值} \end{array}\right. vl(j){ve(n−1),min{vl(k)−Weight(vj,vk)},jn−1,vj 是汇点 Weight(vj,vk)表示vj,vk的权值
活动aia_iai的最早开始时间e(i)e(i)e(i)该活动的起点所表示的事件最早发生时间
e(i)ve(k)e(i)ve(k) e(i)ve(k)
活动aia_iai的最迟开始时间l(i)l(i)l(i)该活动的终点所表示的事件最迟发生时间与该活动所需时间之差
l(i)vl(j)−Weight(vk,vj)\mathrm{l}(i)\operatorname{vl}(j)-\operatorname{Weight}\left(\mathrm{v}_{k}, \mathrm{v}_{j}\right) l(i)vl(j)−Weight(vk,vj)
算法过程 求AOEAOEAOE网中所有事件的最早发生时间ve()ve()ve() 从源点出发到该顶点的最大长度。 求 AOE 网中所有事件的最迟发生时间vl()vl()vl() 事件的最迟发生时间关键路径长度-从该顶点到汇点的最大长度。 求 AOE 网中所有活动的最早开始时间e()e()e() 活动的最早开始时间该活动的起点所代表的事件的最早发生时间。也就是从源点出发到这条边的起始点的最大长度。 求 AOE 网中所有活动的最迟开始时间l()l()l() 活动的最迟开始时间关键路径长度-从这条边的终点到汇点的最大长度 这条边的长度)。 求 AOE 网中所有活动的差额d()l()−e()d()l()-e()d()l()−e()找出所有d()0d()0d()0最早开始时间最迟开始时间的活动构成关键路径。若活动的最迟开始时间 最早开始时间则该活动不是关键活动。
第七章 查找
考点 23查找的基本术语
查找在数据集合中寻找满足某种条件的数据元素的过程称为查找。查找的结果一般分为查找成功、查找失败。
查找表查找结构用于查找的数据集合称为查找表它由同一类型的数据元素或记录组成可以是一个数组或链表等数据类型。对查找表经常进行的操作一般有444 种
查询某个特定的数据元素是否在查找表中检索满足条件的某个特定的数据元素的各种属性在查找表中插入一个数据元素从查找表中删除某个数据元素
静态查找表若一个查找表的操作只涉及上述操作 ① 和 ②则无须动态地修改查找表此类查找表称为静态查找表需要动态地插入或删除的查找表称为动态查找表。适合静态查找表的查找方法有顺序查找、折半查找、散列查找等适合动态查找表的查找方法有二叉排序树的查找、散列查找等。二叉平衡树和 B 树都是二叉排序树的改进。
关键字数据元素中唯一标识该元素的某个数据项的值使用基于关键字的查找查找结果应该是唯一的。
平均查找长度在查找过程中一次查找的长度是指需要比较的关键字次数而平均查找长度则是所有查找过程中进行关键字的比较次数的平均值其数学定义为
ASL∑i1nPiCi\mathrm{ASL}\sum_{i1}^{n} P_{i} C_{i} ASLi1∑nPiCi
式中nnn是查找表的长度PiP_iPi是查找第iii个数据元素的概率一般认为每个数据元素的查找概率相等Pi1/nP_i1/nPi1/nCiC_iCi是找到第iii 个数据元素所需进行的比较次数。平均查找长度是衡量查找算法效率的最主要的指标。
考点 24顺序查找
算法逐个比较查找表中的元素直到找到目标元素或达到查找表的尽头为止时间复杂度为O(n)O(n)O(n)。 一般线性表 效率分析 查找成功时在等概率的情况下平均查找长度为ASL成功 ∑i1nPi(n−i1)n12\mathrm{ASL}_{\text {成功 }}\sum_{i1}^{n} P_{i}(n-i1)\frac{n1}{2}ASL成功 ∑i1nPi(n−i1)2n1。 查找不成功时平均查找长度为ASL不成功 n1\mathrm{ASL}_{\text {不成功 }}n1ASL不成功 n1。 算法代码 typedef struct( //查找表的数据结构ElemType *elem; //元素存储空间基址建表时按实际长度分配0号单元留空int TableLen; //表的长度}SSTable;int search seq(SSTab1e ST,ElemType key){ST.elem[0]key;for(iST.Tab1eLen;ST.elem[i]!key;--i);return i; //若表中不存在关键字为key的元素,将查找到i0时退出for循环}在算法中将下标为000的元素当作“哨兵”。引入它的目的是使得Search_SeqSearch\_SeqSearch_Seq内的循环不必判断数组是否会越界因为满足i0i0i0 时循环一定会跳出。 有序线性表 算法表内关键字有序的则查找失败时可以不用再比较到表的另一端就返回查找失败的信息。 查找判定树 圆形结点表示有序线性表中存在的元素。 矩形结点称为失败结点若有 n 个结点则相应地有 n1 个查找失败结点)描述的是那些不在表中的数据值的集合。 效率分析 查找成功时在等概率的情况下平均查找长度为ASL成功 ∑i1nPi(n−i1)n12\mathrm{ASL}_{\text {成功 }}\sum_{i1}^{n} P_{i}(n-i1)\frac{n1}{2}ASL成功 ∑i1nPi(n−i1)2n1。 查找不成功时平均查找长度为ASL不成功 12⋯nnn1n2nn1\mathrm{ASL}_{\text {不成功 }}\frac{12\cdotsnn}{n1}\frac{n}{2}\frac{n}{n1}ASL不成功 n112⋯nn2nn1n。
