408数据结构考点总结

第一章 绪论

考点 1：时间复杂度与空间复杂度

时间复杂度

定义：将算法中基本运算的执行次数的数量级作为时间复杂度，记为$O(n)$。

计算原则

• 加法法则：$T(n)=T_1(n)+T_2(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(f(n)g(n))$

计算方法

• 列方程法：用于递推实现的算法中，设基本运算运行$x$次，找出与问题规模$n$之间的方程关系式，解出$x=f\left(n\right)$，$f\left(n\right)$的最高次数为$k$，则算法的时间复杂度为$O\left(n^k\right)$。
• 递推公式法：用于递归实现的算法中，设$T\left(n\right)$是问题规模为$n$的算法的时间复杂度，$T(n-1)$是问题规模为$n-1$的算法的时间复杂度，建立$T(n)$与$T(n-1)$[或$T(n-2)$等]的递推关系式，根据关系式，解出$T(n)$。

空间复杂度

定义：指算法运行过程中所使用的辅助空间的大小，记为$S(n)$。算法原地工作是指算法所需辅助空间是常量，即$O(1)$。

递归算法特性：

• 一个算法直接或间接调用自身，称为递归调用。
• 必须有一个明确的递归结束条件，称为递归出口。
• 实现递归的关键是建立递归调用工作栈。栈的大小也就是递归深度和递归算法空间复杂度的。

第二章 线性表

考点 2：顺序表

定义：指用一组连续的存储单元，依次存储线性表中的各个元素，从而使得逻辑上相邻的元素在物理位置上也相邻，因此可以随机存取（根据首元素地址和元素序号）表中任何一个元素。

基本操作

• 结构

• 插入

  若表长为$n$,下标从0开始，则在第$i$位置插入元素$e$，则从$a_n$到$a_i$都要向后移动一个位置，共需移动$n-i+1$个元素，平均时间复杂度为$O(n)$。

  //判断1的范围是否有效，否则非法
  //判断当前存储空间是否已满，否则不能插入
  for(int j=L.length;j>=i;--)     //将第1个位置及之后的元素后移L.data[j]=L.data[j-1];
  L.data[i-1]=e;                 //在位置i处放入e,数组从0开始存储
  L.length++;                    //线性表长度加1
  

• 删除

  若表长为$n$,下标从$0$开始，当删除第$i个元素时，则从$$a_{i+1}$ 到$a_n$都要向前移动一个位置，共需移动$n-i$个元素，平均时间复杂度为$O(n)$。

  //判断1的范围是否有效
  for(int j=i;j<L.length;j++)     //将第i个位置及之后的元素前移L.data[j-1]=L.data[j];
  L.length--;                    //线性表长度减1
  

• 查找

  1. 按序号（下标）查找：顺序表具有随机存取（根据首元地址和序号）的特点，时间复杂度为$O(1)$。
  2. 按值查找：主要运算是比较操作，比较的次数与值在表中的位置和表长有关，平均比较次数为$(n+1)/2$，时间复杂度为$O(n)$。

考点 3：单链表

定义：为了建立元素之间的线性关系，对每个链表结点，除了存放元素自身的信息，还需要存放一个指向其后继的指针。

基本操作

• 查找

  只能从表中第一个结点出发顺序查找，顺着指针$next$域逐个往下搜索，直到找到满足条件的结点为止。时间复杂度为$O(n)$。

• 创建

  1. 头插法：从一个空表开始，然后将新结点插入到当前链表的表头，即头结点之后。

     

     s->next=L->next;  //①新结点的指针指向原链表的第一个结点
     L->next=s;        //②头结点的指针指向新结点，L为头指针
     

  2. 尾插法：将新结点插入到当前链表的表尾上，为此必须增加一个尾指针 $$r$$，使其始终指向当前链表的尾结点。

     

     r->next=s;  //原链表中的尾结点（r所指）的指针指向新结点
     r=s;        //r指向新的表尾结点
     

• 插入

  将值为$x$的新结点插入到单链表的第$i$个位置。先检查插入位置的合法性，然后找到待插入位置的前驱结点，即第$i-1$ 个结点，再在其后插入新结点。

  

  p=GetElem(L,i-1);   //查找插入位置的前驱结点
  s->next=p->next;    //①s的指针指向p的下一结点
  p->next-s;          //②p的指针指向s
  

• 删除

  将单链表的第$i$个结点删除。先检查删除位置的合法性，然后查找表中第$i-1$ 个结点，即被删结点的前驱结点，再将其删除。

  

  p=GetElem(L,i-1);    //查找删除位置的前驱结点
  q=p->next;           //令q指向被删除结点
  p->next=q->next;     //将*q结点从链中"断开"
  delete q;            //释放待删结点所占空间
  

• 求表长

  1. 不含头结点：从首结点开始依次顺序访问表中的每个结点，为此需要设置一个计数器变量，每访问一个结点，计数器加$1$，直到访问到$NULL$为止。
  2. 不带头结点的单链表的表长时，对空结点需要单独处理。

  len=0;    //1en表示单链表长度，初值设为0
  LNode *p=L->next;    //令p指向单链表的第一个结点
  while(p) {len++;p=p->next;}    //跳出循环时，len的值即为单链表的长度
  

第三章 栈和队列

考点 4：栈和队列的基本性质

术语	定义
栈	只允许在表的一端（栈顶）进行插入或删除的线性表。栈的操作特性为先进后出。
队列	只允许在表尾（队尾）插入，表头（队头）删除的线性表。队列的操作特性为先进先出。

$n$个不同的元素进栈，则不同出栈序列个数为$\frac{1}{n+1}{C}_{2n}^n$。

考点5：循环队列

定义：把顺序存储的队列从逻辑上视为一个环，称为循环队列。通常利用除模取余运算$(\%)$来实现循环。

基本操作

• 元素出队：Q.front=(Q.front+1)%MaxSize

• 元素入队：Q.rear=(Q.rear+l)%MaxSize

• 队列长度：(Q.rear-Q.front+-MaxSize)%MaxSize（$front$指向第一个元素、$rear$指向最后一个元素的下一位置)

为了区分是队空还是队满，通常采用牺牲一个存储单元的方法，约定以“队头指针在队尾指针的下一位置作为队满的标志”。

队满条件：(Q.rear+1)%MaxSize==Q.front

队空条件：Q.front==Q.rear

考点6：双端队列

定义：允许两端都可以进行入队和出队操作的队列，即每个元素仅有一个前驱结点和一个后继结点（首位元素除外）。将队列的两端分别称为前端和后端。

基本操作

• 进队：前端进的元素排在后端进的元素的前面，后端进的元素排在前端进的元素的后面。

• 出队：无论是前端出队还是后端出队，先出的元素排列在后出的元素的前面。

输出受限的双端队列

定义：允许在一端进行插入和删除，但在另一端只允许插入的双端队列。

输入受限的双端队列

定义：允许在一端进行插入和删除，但在另一端只允许删除的双端队列。

考点7：栈与队列的应用

栈的应用	队列的应用
数制转换	层序遍历二叉树
括号匹配	缓冲区
表达式求值	进程的就绪队列
给定进栈和出栈顺序确定该栈的最小容量（最大深度）	广度优先遍历$BFS$

考点 8：特殊矩阵的存储

存储方式

1. 按行优先存储
2. 按列优先存储

特殊矩阵

1. 对称矩阵

   存储方式：只存放主对角线和下三角区的元素。

2. 三角矩阵

   • 下三角矩阵：上三角区的所有元素均为同一常量，存储完下三角区和主对角线上的元素之后，紧接着存储对角线上方的常量一次。

     

   • 上三角矩阵：下三角区的所有元素均为同一常量，存储完上三角区和主对角线上的元素之后，紧接着存储对角线下方的常量一次。

     

第四章 串

考点 9：串的模式匹配算法

• 简单模式匹配算法

  算法思想：从主串$S$的第一个字符起，与模式$T$的第一个字符比较，若相等，则继续逐个比较后续字符；否则从主串的下一个字符起，重新和模式的字符比较；以此类推，直至模式$T$中的每个字符依次和主串$S$ 中一个连续的字符序列相等，则称匹配成功，否则称匹配不成功。简单模式匹配算法的最坏时间复杂度为$O(mn)$。

  算法代码

  int Index(SString S,SString T){int i=1,j=1;while(i<=S.length && j<=T.length){ if(S.ch[i]==T.ch[j]){ ++1；++j;//继续比较后继字符 }else{ i=i-j+2;j=1;//指针后退重新开始匹配 }}if(j>T.length) return i-T.length;else return 0;
  }
  

• $KMP$ 算法

  前缀：指除最后一个字符以外，字符串的所有头部子串。

  后缀：指除第一个字符外，字符串的所有尾部字串。

  部分匹配值：字符串的前缀和后缀的最长相等前后缀长度。

  匹配失败时子串需要向后移动的位数：移动位数=已匹配的字符数-最后一位匹配字符对应的部分匹配值。

  Next 数组计算

  1. 计算模式串中每个位置所对应的字串的最长前缀长度（最后一个位置所对应的字串无须计算)，记为$next1$。
  2. $next1$右移$1$位，第$1$位补$-1$，得$next$数组。

第五章 树与二叉树

考点 10：树的基本性质

树的基本术语

术语	定义
结点的度	树中一个结点的子结点个数
树的度	树中结点的最大度数
分支结点	度大于 0 的结点称为分支结点
叶子结点	度等于 0 的结点称为叶子结点
结点的深度	从根结点到该结点的路径上结点的个数之和（根结点深度为 1）
树的高度	树中结点的最大层数（根结点为第一层）
路径	树中两个结点之间所经过的结点序列
路径长度	路径上所经过的边的条数

1. 树可以是空树（结点数=0）。
2. 森林可以是空森林（树个数=0）。

树的基本性质

1. 树中的结点总数等于总度数加 1（结点总数=边总数 +1）。
2. 度为$m$的树中第$h$层最多有$m^{h-1}$个结点。
3. 高度为$h$的$m$叉树最多有$(m^k-1)/(m-1)$个结点。
4. 具有$n$个结点的$m$叉树的最小高度为$\lceil {\log }_m\left(n\left(m-1\right)+1\right)\rceil$。

考点 11：特殊二叉树的定义与性质

特殊二叉树

术语	定义
满二叉树	一棵高度为$h$，并且含有$2^h-1$个结点的二叉树称为满二叉树。满结点。
完全二叉树	一棵高度为$h$，有$n$个结点的二叉树，仅当其每个结点都与高度为$h$个结点的二叉树，仅当其每个结点都与高度为$h$的满二叉树中编号为$1\sim n$ 的结点一一对应，称为完全二叉树。

完全二叉树的性质

1. 最后一个分支结点（非叶结点）的编号：$\lfloor n/2\rfloor$。
2. 叶子结点只可能在层次最大的两层上出现。
3. 如果有度为$1$ 的结点，只可能有一个，且该结点只有左孩子。
4. 若$n$为奇数，则每个分支结点都有左子女和右子女；若$n$ 为偶数，则编号最大的分支结点只有左子女。
5. 结点$i$所在层次（深度）为$\lfloor {\log }_{2}i\rfloor +1$。
6. 具有$n$个$(n>0)$结点的完全二叉树的高度为$\lfloor {\log }_2(n+1)\rfloor$或$\lfloor {\log }_{2}n\rfloor +1$。
7. 编号为$i$的结点的双亲结点的编号为$\lfloor i/2\rfloor$；左孩子编号为$2i$；右孩子编号为$2i+1$。

考点 12：二叉树的遍历

遍历方式

1. 先序遍历：先访问根结点，再访问左子树，最后访问右子树。
2. 中序遍历：先访问左子树，再访问根结点，最后访问右子树。
3. 后序遍历：先访问左子树，再访问右子树，最后访问根结点。
4. 层序遍历：按自顶向下、自左向右的顺序来逐层访问树中结点。

构造二叉树

1. 中序序列与前序序列。
2. 中序序列与后序序列。
3. 中序序列与层序序列。

唯一确定一棵二叉树的序列组合（都需要中序序列）

考点 13：树、森林与二叉树的转换

规则：左结点指向孩子结点，右结点指向兄弟结点（左孩子右兄弟）。

考点 14：线索二叉树

结点结构

线索：利用空链域存放指向直接前驱或直接后继的指针。

线索化：对二叉树遍历使其变为线索二叉树。线索化时，若无左子树，则令$Ichild$指向其前驱结点；若无右子树，则令$rchild$指向其后继结点。两个$tag$标志域表明当前指针域所指对象是指向左（右）子结点还是直接前驱（后继）。
$$\text{ ltag }=\{\begin{array}{ll}0,& \text{ lchild域指示结点的左孩子 }\\ 1,& \text{ lchild域指示结点的前驱 }\end{array}\mathrm{rtag}=\{\begin{array}{ll}0,& \text{ rchild域指示结点的右孩子 }\\ 1,& \text{ rchild域指示结点的后继 }\end{array}$$

在有 N 个结点的二叉树中，有 N+1 个空指针域。

考点 15：哈夫曼

哈夫曼树

树的带权路径长度：树中所有叶结点的带权路径长度之和。$w_i$是第$i$个叶结点所带的权值；$l_i$是该叶结点到根结点的路径长度。
$$\mathrm{WPL}=\sum _{i=1}^n{w}_i{l}_i$$

哈夫曼树：带权路径长度最小的二叉树。

构造哈夫曼树

1. 构造一个新结点，选取两个权值最小的结点作为新结点的左、右子树，新结点的权值置为左、右子树上根结点的权值之和。
2. 从序列中删除刚才选出的两个结点，同时将新结点加入序列。

哈夫曼树特点

1. 每个初始结点最终都成为叶结点，并且权值越小的结点到根结点的路径长度越大。
2. 哈夫曼树中结点总数为$2N-1$。
3. 哈夫曼树中不存在度为$1$的结点。
4. 同一序列构造的哈夫曼树不唯一，但带权路径长度唯一且最优。

哈夫曼编码

前缀编码：没有一个编码是另一个编码的前缀。

哈夫曼编码构造

1. 根据待编码元素构造对应的哈夫曼树。

2. 从根至该字符的路径上进行标记，“左孩子”的边标记为$0$，“右孩子”的边标记为$1$。

3. 从根结点到待编码元素结点的路径形成的$0$、$1$序列就是哈夫曼编码。

第六章 图

考点 16：图的基本概念

基本术语

• 无向图	有向图
  边：顶点的无序对，记为$(v,w)$或$(w,v)$	弧：顶点的有序对，记为$<v,w>$，$v$称为弧尾，$w$ 称为弧头
  无向图：若$E$是无向边（简称边）的有限集合时，则图$G$为无向图	有向图：若$E$是有向边（也称弧）的有限集合时，则图$G$为有向图
  顶点的度：指依附于该顶点的边的数量，记为$TD(v)$	顶点的度：入度和出度之和（入度是以$v$为终点的有向边的数目；出度是以$v$为起点的有向边的数目）
  连通：从顶点$v$到顶点$w$有路径存在，则称$v$和$w$ 是连通的	强连通：从顶点$v$到顶点$w$和从顶点$w$到顶点$v$之间都有路径，则称$v$和$w$ 是强连通的
  连通图：图中任意两个顶点都是连通的，则称图$G$为连通图，否则为非连通图	强连通图：图中任意一对项点都是强连通的，则称此图为强连通图
  连通分量：图的极大连通子图称为连通分量	强连通分量：图的极大强连通子图称为有向图的强连通分量
  无向完全图：任意两个顶点之间都存在边，共有$(n-1)/2$条边	有向完全图：任意两个顶点之间都存在方向相反的两条弧，共有$n(n-1)$条有向边

术语	定义
生成树	连通图的生成树是包含图中全部顶点的一个极小连通子图
生成森林	非连通图的连通分量的生成树构成了非连通图的生成森林
回路（环）	第一个顶点和最后一个顶点相同的路径称为回路或环

• 极大连通子图：包含了图中尽可能多的顶点以及尽可能多的边
• 极小连通子图：包含图中全部顶点且包含边最少

图的基本性质

1. 无向图中任意顶点的入度等于出度。
2. 无向图中（无论是否连通），所有顶点的度数之和等于边数的两倍。
3. 在有向图中，全部顶点的“入度之和”=“出度之和”=边数。
4. 图的邻接矩阵表示中，各顶点的度等于矩阵中该结点对应的行（对应出度）和列（对应入度）的非零元素数量之和。

考点 17：图的存储及基本操作

邻接矩阵存储法

方式：用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息

特点

• 无向图的邻接矩阵一定是一个对称矩阵，可采用压缩存储。有向图的邻接矩阵不一定是对称矩阵，有向完全图的邻接矩阵是对称矩阵。

• 对于无向图，邻接矩阵的第$i$行（或第$i$列）非零元素（或非$\infty$元素）的个数正好是第

  $i$个顶点的度。

• 对于有向图，邻接矩阵的第$i$行（或第$i$列）非零元素（或非$\infty$元素）的个数正好是第$i$个顶点的出度（或入度）。

• 对于无权图的邻接矩阵$A$（矩阵中各位置的值为$0$或$1$），$A^n[i][j]$的值表示由顶点$i$到顶点$j$的路径长度为$n$的路径的数量。

• 稠密图适合使用邻接矩阵的存储表示。

邻接表存储法

方式

• 将图中所有邻接于顶点$v$的顶点链成一个单链表，这个单链表就称为顶点$v$ 的邻接表。
• 将所有顶点的邻接表的表头放到数组中，就构成了图的邻接表。

特点：

• 若无向图有$n$个顶点、$e$条边，则其邻接表仅需$n$个头结点和$2e$个表结点。

• 对于无向图，顶点$v_i$的度等于第$i$个链表中的结点数；对于有向图，第$i$ 个链表中的结点数只是顶点$v_i$的出度，求入度，必须遍历整个邻接表。

• 在邻接表上容易找到任一顶点连接的所有边。但要判定任意两个顶点（$v_i$和$v_j$）之间是否有边或弧相连，则需搜索第$i$个或第$j$ 个链表，在这方面不及邻接矩阵方便。

• 图的邻接表不唯一，取决于建立邻接表的算法以及边的输入次序。

考点 18：图的遍历

广度优先搜索 BFS

遍历过程

1. 访问起始顶点$v$。
2. 依次访问顶点$v$未访问过的邻接顶点$v_2$，$v_3$。直到图中所有和$v$连通的顶点都被访问过为止。
3. 另选一个未被访问过的顶点作为起始顶点 $v$，重新开始，直至所有顶点都被访问。

性能分析

• $BFS$算法需要借助一个辅助队列，空间复杂度为$O(|V|)$。
• 邻接矩阵表示时，算法总的时间复杂度为$O(|V{|}^2)$。
• 邻接表表示时，算法总的时间复杂度为$O(|V|+|E|)$。

深度优先搜索 DFS

遍历过程

1. 访问起始顶点$v$。
2. 访问与顶点$v$邻接且未被访问过的任一邻接顶点$v_2$。再访问与$v_2$邻接且未被访问的任一顶点$v_3$。
3. 当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问，则从该顶点重新开始，直到图中所有顶点均被访问过为止。

性能分析

• $DFS$算法需要借助一个递归工作栈，空间复杂度为$O(|V|)$。
• 邻接矩阵表示时，算法总的时间复杂度为$O(|V{|}^2)$。
• 邻接表表示时，算法总的时间复杂度为$O(|V|+|E|)$。

对于同一个图，基于邻接矩阵的遍历所得到的$DFS$序列和$BFS$序列是唯一的；由于邻接表不唯一，所以基于邻接表的遍历所得到的$DFS$序列和$BFS$序列可能不唯一。

考点 19：最小（代价）生成树

定义：所有生成树的集合中边的权值之和最小的那棵生成树。

性质

• 最小生成树不唯一。
• 当图中的各边权值互不相等时，G 的最小生成树唯一。
• 最小生成树所对应的边的权值之和总是唯一的，而且是最小的。
• 最小生成树是一棵无向连通带权图。

Prim 算法

• 每次在已选顶点的邻接边中选权值最小的边加入。

• $Prim$算法的时间复杂度为$O(|V{|}^2)$，不依赖于$E$，适用于边稠密的图。

Kruskal 算法

• 不断选取当前未被选取的权值最小的边，若其两个顶点不属于同一顶点集合，则将该边放入生成树的边集，同时将两个顶点所在的集合合并。

• 直到选取了$n-1$条边为止。

• $Kruskal$算法的时间复杂度为$O\left(|E|{\log }_2|E|\right)$，适用于边稀疏而顶点较多的图。

考点 20：最短路径

最短路径（权值）问题

• 单源最短路径问题：求从给定源点到其他各个顶点的最短路径长度。
• 点对点最短路径问题：求每一对顶点之间的最短路径长度。

Dijkstra 算法

用邻接矩阵$arcs$表示带权有向图 $\mathrm{arcs}[i][j]=\{\begin{array}{ll}{e}_{ij},& e_{ij}\text{ 为有向边 }<i,j>\text{ 的权值 }\\ \infty ,& \text{ 不存在有向边 }<i,j>\end{array}$

算法过程

• $dist[]$：记录了从源点$v_0$到其他各顶点当前的最短路径长度。

• 集合 $S$ 记录已求得的最短路径的顶点，每趟确定一个最短路径。

Floyd 算法

算法过程

1. 定义一个 n 阶方阵序列：$A^{(-1)},A^{(0)},\cdots ,A^{(n-1)}。$

2. $A^{(-1)}[i][j]=\mathrm{arcs}[i][j]$$（$$\mathrm{arcs}[i][j]$与迪杰斯特拉算法中的定义相同$）$。

3. 递推产生$A^{(k)}[i][j]=\mathrm{Min}\left\{A^{(k-1)}[i][j],A^{(k-1)}[i][k]+A^{(k-1)}[k][j]\right\},k=0,1,\cdots ,n-1$。

• $A(k)[i][j]$是从顶点$v_i$$到$$v_j$、中间顶点的序号不大于$k$的最短路径的长度​。

• 经过$n$次迭代后所得到的$A(n-1)[i][j]$就是$v_i$到$v_j$ 的最短路径长度。

Floyd 算法的时间复杂度为$O(|V{|}^3)$。

Floyd 算法允许图中有带负权值的边，但不允许有包含带负权值的边组成的回路。

考点 21：拓扑排序

定义

• 有向无环图的顶点组成的序列。
• 每个顶点出现且只出现一次。
• 每个有向无环图都有一个或多个拓扑序列。

算法过程

1. 从有向无环图中选择一个没有前驱的顶点并输出。
2. 从图中删除该顶点和所有以它为起点的有向边。
3. 直到当前的图为空或当前图中不存在无前驱的项点为止（环）。

拓扑排序的时间复杂度为$O(|V|+|E|)$。

考点 22：关键路径

AOE 网：带权有向图以顶点表示事件，有向边表示活动，边上的权值表示完成该活动的开销。

关键路径：AOE 网中从源点到汇点的最大路径长度的路径，关键路径长度是整个工程所需的最短工期。

关键活动：关键路径上的活动。

性质

1. 可以通过加快关键活动缩短整个工程的工期。并非关键活动缩短多少工期就缩短多少，因为缩短到一定的程度，该关键活动可能变成非关键活动了。
2. 关键路径并不唯一。对于有几条关键路径的网，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。
3. 从源点到汇点的路径上，所有具有最大路径长度的路径，都是关键路径。所有“最长路径”（关键路径）上的所有活动，都是关键活动。

求关键路径算法

参数定义

1. 事件$v_k$的最早发生时间$ve(k)$：从源点到顶点$V_k$的最长路径长度

ve⁡(k)={0,k=0,vk是源点max⁡{ve⁡(j)+Weight(vj,vk)},Weight(vj,vk)表示<vj,vk>上的权值\operatorname{ve}(k)=\left\{\begin{array}{ll}0, & k=0, \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​)},​k=0,vk​ 是源点Weight(vj​,vk​)表示<vj​,vk​>上的权值​

1. 事件$v_k$的最迟发生时间$vl(k)$:从顶点$V_k$到汇点的最短路径长度

vl⁡(j)={ve(n−1),j=n−1,vj是汇点 min⁡{vl(k)−Weight⁡(vj,vk)},Weight(vj,vk)表示<vj,vk>的权值\operatorname{vl}(j)=\left\{\begin{array}{ll} \mathrm{ve}(n-1), & j=n-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​)},​j=n−1,vj​ 是汇点  Weight(vj​,vk​)表示<vj​,vk​>的权值​

1. 活动$a_i$的最早开始时间$e(i)$：该活动的起点所表示的事件最早发生时间

$$e(i)=ve(k)$$

1. 活动$a_i$的最迟开始时间$l(i)$：该活动的终点所表示的事件最迟发生时间与该活动所需时间之差

$$\mathrm{l}(i)=\mathrm{vl}(j)-\mathrm{Weight}\left({\mathrm{v}}_k,{\mathrm{v}}_j\right)$$

算法过程

1. 求$AOE$网中所有事件的最早发生时间$ve()$

   从源点出发，到该顶点的最大长度。

2. 求 AOE 网中所有事件的最迟发生时间$vl()$

   事件的最迟发生时间=关键路径长度-从该顶点到汇点的最大长度。

3. 求 AOE 网中所有活动的最早开始时间$e()$

   活动的最早开始时间=该活动的起点所代表的事件的最早发生时间。也就是从源点出发，到这条边的起始点的最大长度。

4. 求 AOE 网中所有活动的最迟开始时间$l()$

   活动的最迟开始时间=关键路径长度-（从这条边的终点到汇点的最大长度 + 这条边的长度)。

5. 求 AOE 网中所有活动的差额$d()=l()-e()$，找出所有$d()=0$（最早开始时间=最迟开始时间）的活动构成关键路径。若活动的最迟开始时间 > 最早开始时间，则该活动不是关键活动。

第七章 查找

考点 23：查找的基本术语

查找：在数据集合中寻找满足某种条件的数据元素的过程称为查找。查找的结果一般分为查找成功、查找失败。

查找表（查找结构）：用于查找的数据集合称为查找表，它由同一类型的数据元素（或记录）组成，可以是一个数组或链表等数据类型。对查找表经常进行的操作一般有$$4$$ 种：

• 查询某个特定的数据元素是否在查找表中
• 检索满足条件的某个特定的数据元素的各种属性
• 在查找表中插入一个数据元素
• 从查找表中删除某个数据元素

静态查找表：若一个查找表的操作只涉及上述操作 ① 和 ②，则无须动态地修改查找表，此类查找表称为静态查找表；需要动态地插入或删除的查找表称为动态查找表。适合静态查找表的查找方法有顺序查找、折半查找、散列查找等；适合动态查找表的查找方法有二叉排序树的查找、散列查找等。二叉平衡树和 B 树都是二叉排序树的改进。

关键字：数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。

平均查找长度：在查找过程中，一次查找的长度是指需要比较的关键字次数，而平均查找长度则是所有查找过程中进行关键字的比较次数的平均值，其数学定义为

$$\mathrm{ASL}=\sum _{i=1}^n{P}_i{C}_i$$

式中，$n$是查找表的长度；$P_i$是查找第$i$个数据元素的概率，一般认为每个数据元素的查找概率相等，$P_i=1/n$；$C_i$是找到第$i$ 个数据元素所需进行的比较次数。平均查找长度是衡量查找算法效率的最主要的指标。

考点 24：顺序查找

算法：逐个比较查找表中的元素，直到找到目标元素或达到查找表的尽头为止，时间复杂度为$O(n)$。

1. 一般线性表

   • 效率分析

   查找成功时，在等概率的情况下，平均查找长度为${\mathrm{ASL}}_{\text{成功 }}={\sum }_{i=1}^n{P}_i(n-i+1)=\frac{n+1}{2}$。

   查找不成功时，平均查找长度为${\mathrm{ASL}}_{\text{不成功 }}=n+1$。

   • 算法代码

     typedef struct(         //查找表的数据结构ElemType *elem;    //元素存储空间基址，建表时按实际长度分配，0号单元留空int TableLen;     //表的长度}SSTable;int search seq(SSTab1e ST,ElemType key){ST.elem[0]=key;for(i=ST.Tab1eLen;ST.elem[i]!=key;--i);return i;      //若表中不存在关键字为key的元素,将查找到i==0时退出for循环}
     

   在算法中，将下标为$0$的元素当作“哨兵”。引入它的目的是使得$Search\_Seq$内的循环，不必判断数组是否会越界，因为满足$i==0$ 时，循环一定会跳出。

2. 有序线性表

   • 算法：表内关键字有序的，则查找失败时可以不用再比较到表的另一端就返回查找失败的信息。

   • 查找判定树

     

     圆形结点表示有序线性表中存在的元素。

     矩形结点称为失败结点（若有 n 个结点，则相应地有 n+1 个查找失败结点)，描述的是那些不在表中的数据值的集合。

   • 效率分析

     查找成功时，在等概率的情况下，平均查找长度为${\mathrm{ASL}}_{\text{成功 }}={\sum }_{i=1}^n{P}_i(n-i+1)=\frac{n+1}{2}$。

     查找不成功时，平均查找长度为${\mathrm{ASL}}_{\text{不成功 }}=\frac{1+2+\cdots +n+n}{n+1}=\frac{n}{2}+\frac{n}{n+1}$。