2021数据结构复习

考试范围

数据结构 算法时间复杂度空间复杂度分析

  1. 线性表
    1. 顺序表示
    2. 链式表示
      1. 线性链表
      2. 循环链表
      3. 双向链表
    3. 一元多项式（实验内容）
  2. 栈
    1. 数值转换，括号匹配，行编辑程序，迷宫求解，表达式求值
  3. 队列
    1. 定义
    2. 链队列
    3. 循环队列
  4. 串
    1. 定长顺序存储
    2. 堆分配存储
    3. 串的块链存储
  5. 数组
    1. 顺序表示
    2. 特殊存储：特殊矩阵，稀疏矩阵
  6. 广义表
    1. 定义和存储结构
    2. *广义表的递归算法
      1. 求广义表深度
      2. 复制广义表
      3. 建立广义表的存储结构
  7. 树和二叉树
    1. 二叉树
      1. 定义，性质，存储结构
      2. 遍历二叉树
      3. 线索二叉树
    2. 树和森林
      1. 树的存储结构
      2. 树和二叉树之间的转换
      3. 树和森林的遍历
    3. Huffman树相关问题
  8. 图
    1. 定义和术语
    2. 存储结构
      1. 数组表示法
      2. 邻接表
      3. 十字链表
      4. 邻接多重表
    3. 图的遍历
      1. DFS
      2. BFS
    4. 图的连通性问题
      1. 无向图连通分量和生成树
      2. 最小生成树
    5. 最短路径问题
      1. 从某一点到其他各个顶点的最短距离
      2. 每一对顶点之间的最短路径

  9. 查找

    1. 静态查找表
      1. 顺序表查找
      2. 有序表查找
      3. 索引顺序表查找
    2. 动态查找
      1. 二叉排序树和 *平衡二叉树
      2. B-树和B+树
    3. 哈希表
      1. 构造方法
      2. 处理冲突
      3. 查找

    `#define INFEASIBLE -1

    `#define OVERFLOW -2

线性表

顺序表

逻辑上相邻，物理上相邻，随机存取

#define LIST_SIZE 100
#define LISTINCREMENT 10
typedef struct {
   ElemType *elem;
   int length;
   int listsize;
}SqList;

动态分配：

void *malloc();
free(void *p);
void *realloc(void *p,unsigned int size);//可变大/变小

基本操作略

链表表示

逻辑上相邻不代表物理上相邻，非随机存取

（区别不同逻辑结构的插入删除操作）

单链表

typedef struct LNode {
	elemtype data;
   struct LNode *next;
}Lnode ,*LinkList;

基本操作：

Status GetElem_L(LinkList L,int i,ElemType &e);
Status ListInsert_L(LinkList &L,int i，ElemType e);
//获取结点的前驱耗时间，T(N)=O(N)
Status ListDelete_L(LinkList &L,int i，ElemType &e);
Status CreateList_L(LinkList &L);

创建：头插法（$T(N)=O(N)$），尾插法($T(N)=O(N^2)$)(头插法创建较好)

作业习题：就地逆置单链表

有头结点：L指向头结点，除头结点各点均有前驱；

无头结点：空表时L为NULL；

循环链表

  1. 便于从一个结点出发，访问全部的结点
  2. 在O(1)的时间内找到链表的第一个结点和最后一个结点（头指针==尾指针）

静态链表和动态链表

静态链表(若语言不支持指针类型的存储的情况)

#define MAXSIZE 1000
typedef struct{
   ElemType data;
   int cur;//代替指针域
}component,SLinkList[MAXSIZE];

数组的第0个分量可以视为（备用链的）头结点；

静态链表的模拟动态分配与释放（未利用的点i[cur]=0;)

动态链表与静态链表的运用：例：求差集

双向链表

typedef struct DuLNode{
   ElemType data;
   struct DuLNode *prior;
   struct DuLNode *next;
}DuLNode ,*DuLinkList;

可带头结点，可不带（多半是带的）。

其他表示

根据题目要求规定进行设计，如同时存储单链表的头和尾，特殊线性表——有序表。

例题

1.双向循环链表的自身变换，如将$L=\{a_1,a_2,…..a_n\}$变换为$L’=\{a_1,a_3,….a_n,…a_4,a_2\}$

​ (顺着后向链，前向链进行插入)

栈与队列

难点：递归与非递归实现，循环队列

栈

LIFO 只能在Top端进行插入删除操作

Traverse操作是从栈底到栈顶进行访问

多为顺序栈：约定：S.top指向栈顶元素的下一个位置

#define STACK_INT_SIZE 100
#define STACKINCREMENT 10
typedef struct {
   ElemType *base;
   ElemType *top;
   int stacksize;//当前分配容量
}SqStack；

栈空：S.base==S.top

栈满：S.top-S.base>=S.stacksize

入栈：S.top++; 出栈: S.top - - ；

链栈：无栈满问题，可以不必引入头结点（在第一个结点处进行插入删除操作）。

栈的基本应用

1.数制转换

2.行编辑程序（已不常用）

​ 用栈保存终端输入的一行字符进行逐行处理；遇到‘#’退一格（出栈），遇到‘@’退一行（清空栈ClearStack），其他字符入栈，最后遍历，清空栈。

3.表达式求值

表达式表示方法：

  • 中缀表达式，记得加括号
  • 前缀表达式（波兰式）-+abc d-ea
  • 后缀表达式（逆波兰式）ab+cdea- -

表达式求值也可以用二叉树表示：分支保存运算符，叶子结点保存操作数，中序访问：中缀表达式；先序访问：前缀表达式；后序访问：后缀表达式

要先确保中缀表达式合法：括号匹配 默认运算式结尾为’#’

可以进行的操作：中缀表达式转化为先/后缀表达式，先/后缀表达式求值，中缀表达式直接求值。注意：不涉及中缀表达式的运算不需考虑优先级。

[1]中缀表达式转后缀表达式：运算符入栈

[2]中缀表达式求值：运算符（包括左括号）和运算数两个栈，按照操作符优先级进行运算，'#'优先级最低。

[3]前缀表达式串求值：运算符和运算数入同一个栈，如果有两个运算数则进行运算

[4]前缀表达式与后缀表达式相互转化：思路相反，同样用栈，类似波兰式/逆波兰式求值，将字符串视作运算数。

[5]后缀表达式求值：运算数入栈

4.栈与递归的实现

应用：构建其他数据结构：表，图，树和二叉树

​ 问题求解：Hanoi塔问题，迷宫问题/N皇后问题（回溯）

队列

FIFO，允许在队尾rear插入，队头head删除（获取队头元素GetHead(L,&e),遍历操作Traverse(L，visit())从head到rear）.

链队列（通常）

typedef struct QNode{
   ElemType data;
   struct QNode *next;
}QNode,*QueuePtr;
typedef struct {
   QueuePtr front;
   QueuePtr rear;
}LinkQueue;

（最好是引入头结点——队空：L.front ==L.rear）

循环队列(处理假溢出)

#define MAXSIZE 100
typedef struct{
   ElemType *base;
   int front;
   int rear;//指向队尾元素的下一个位置
}SqQueue；

队空标志：Q.front==Q.rear

多申请一个空间，队满标志：Q.front==(Q.rear+1)%MAXSIZE

INCREMENT：重新分配空间，并遍历原队列进行复制

应用：离散事件模拟

串

概念：串的长度，空串，子串，主串，子串/字符在串中的位置

是特殊的线性表：处理对象为个体（字符）或整体（子串）

操作：

StrAssign(S,"...");//赋值
StrCpoy(T,S);//复制串
StrCompare(S,T);//比较
ConCat(T,"...");//拼接
SubString(Sub,S,i,j);//取子串Sub为Si,...Sj
Index(s,"a",i);//返回S中i后第一层出现子串的首个字母的位置
Replace(S,"..","..");//将子串全部替换为目标子串
StrInsert(S,i,"...");//在i处插入子串
StrDelete(S,i,j);//删除Si到Sj的子串

具体存储结构

顺序映像存储密度低

  • 定长顺序存储，下表为0的位置存储串的长度（basic)或串值最后加入无关字符，如’\0’ (C)。

  • 堆分配存储——顺序映像

    typedef struct{
   char *ch;//malloc() 动态分配
   int length;
}HString;

  • ​ 块链存储——链式映像

    typedef struct Chunk{
   char ch[CHUNKSIZE];
   struct Chunk *next;
}Chunk;
typedef struct{
   Chunk *head,*tail;
   int curlen
}LString;

    块链存储中的插入，删除，寻找子串，定位，拼接算法复杂化处理（作业题目）

串的模式匹配算法

好像不考。

应用举例

应用于文本编辑，页插入/删除，行插入/删除，页表，行表，起始地址，长度…

建立关键词词索引表

数组和广义表

数组的操作貌似也不考，补充三元表，特殊数组在后续算法课中。

广义表

广义表是线性表的推广，元素类型可以是原子或子表，习惯上用大写字母表示子表，小写字母表示原子。（也可以看作特殊定义的图）

表处理语言LISP中，将广义表视作基本的数据结构。

表头：表中的第一个元素 GetHead(L)

表尾：除去第一个元素外的其余元素组成的表 GetTail(L)

基本定义

  • 空表 A=( )
  • 长度：元素个数，如B=(a,(b,c,d))长度为2，第二个元素为表
  • A=(a,A) 可以递归定义的表
  • GetHead(((())))=(()); GetTail((()))=()
  • 深度：括号的重数的最大值

广义表的存储结构

数据元素不同，难以用顺序表存储。

头尾链表存储

typedef enum{ATOM,LIST}ElemTag;
typedef struct GLNode{
   ElemTag tag;
   union{
      AtomType atom;
      struct {GLNode *hp,*tp;}ptr;
   };
}*GList;

image-20211229111630880

拓展线性链表存储

typedef enum{ATOM,LIST}ElemTag;
typedef struct GNode{
   ElemTag tag;
   union{
      AtomType atom;
      struct GLNode *hp;
   };
   struct GLNode *tp;
}*GLIst;

image-20211229111642454

广义表的相关操作

此部分不考代码设计，可能有读代码分析的题目

递归算法，归纳思维

广义表的深度

规定：LS为原子：DEPTH=0；

​ LS为空表：DEPTH=1；

​ 归纳项：$DEPTH(LS)=1+Max\{DEPTH(a_i)\},\ n>=1$

假设采用头尾链表存储：

int GListDepth(GLIst L)//递归
{
   if(!L)
      return 1;
   if(L->tag==ATOM)
      return 0;
   for(max=0,pp=L;pp;pp=pp->ptr.tp)
   {
      dep=GListDepth(pp->ptr.hp);
      if(dep>max) max=dep;
   }
   return max+1;
}
//可以用队列实现非递归算法，在每层开始处设置标志

复制广义表

归纳：复制LS—>复制表头+复制表尾

Status CpoyList(GList &T,GList L)
{//假定头尾链表存储
   if(!L)
   {   T=NULL;
      return OK;}
   T=(GList)malloc(sizeof(GLNode));
   T->tag=L->tag;
   if(T->tag==ATOM)
   {T->atom=L->atom;	return OK:}
   CopyList(T->ptr.hp,L->ptr.hp);
   CopyList(Y->ptr.tp,L->ptr.tp);
   return OK;
}

可以用栈实现非递归算法。

广义表结构的建立

由字符串建立广义表

表头+表尾递归处理

...

其他应用

作业题目：就地逆置广义表(逆转所有子表)递归处理

```



注：广义表的存储格式一般可以自选

常见思路：1.将广义表看作表头表尾两部分进行递归处理

​					2.将广义表看作n个并列子表组成的表

## 树和二叉树

**二叉树的遍历，二叉树和森林的相互转换等相关算法设计**

### 定义

空树n=0;

表示方法：

树形表示，嵌套表示，广义表表示，凹入表示

术语：高度，层次（1，2，...，h），度，祖先，子孙，有序树，无序树，终端结点，非终端结点，内部结点...

操作：

```c++
TreeDepth(T);
Parent(T,cur_e);
LeftChild(T,cur_e);
RightSibling(T,cur_e);
InsertChild(&T,p,i,c);//插入子树
DeleteChild(&T,p,i);
TraverseTree(T,visit());

二叉树

每个结点最多有两个子树，度数一定是2，分左右。

性质：

  • 第i层最多有$2^{n-1}$个结点
  • 深度为h的二叉树最多$2^{h}-1$个结点（上述两条可以推广到n叉树的情况）
  • $n_0=n_2+1;\ \ \ n=n_0+n_1+n_2;\ \ \ n-1=n_1+n_2$
  • 若包含n个结点的树只有叶子结点和度数为k的结点，则树中包含的叶子结点为：$n_0=n-(n-1)/k$
  • 满二叉树：深度为h且含有$2^{h}-1$个结点的二叉树
  • 完全二叉树：前k-1层为满二叉树，第k层结点全在靠左边
  • 具有n个结点的完全二叉树的深度：$h=[log_2n]+1$
  • 若对一有n个结点的完全二叉树按层序编号，则对任意结点有：
    • 若i=1，为根结点，无双亲；若i>1，双亲结点为[i/2]
    • 若2i>n,则结点i无左孩子，否则左孩子为2i。
    • 若2i+1>n，则i无右孩子，否则右孩子是2i+1.
    • 上述结论可以大致推广到k叉树

二叉树的存储结构：

顺序存储：空间开销大

链式存储：二叉链（保存双亲结点变成三叉链）

typedef struct{
   ElemType data;
   struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

二叉树的相关算法

遍历

先/中/后序遍历：每个结点均被访问三次

递归/非递归（栈）算法实现。

最好使用函数调用的结果而不是返回值：为实现函数出现异常时改变Status及时终止

相关运用：

  • 创建二叉树：类比先序访问

    清空释放二叉树，或以某个结点为祖先的子树：后序访问

  • 先序/后序拓补序列可以唯一确定一个二叉树。

  • 非递归后序遍历要注意：设置访问标志tag

  • 求深度

层次遍历递归/非递归（队列）实现

​ ——先访问的结点，子结点也会优先访问

  • 对二叉树进行层次遍历可以判断该二叉树是否为完全二叉树。
  • 找到距离x最近的叶子子孙及距离：从x开始进行层次遍历，找到第一个叶子结点即可（每层末尾加一个虚结点进行计算距离
  • 输出距离x最近的所有叶子及其数目
  • 输出x到最近叶子子孙结点的路径：修改原队列：不释放已经遍历的结点并记录每个结点的双亲信息

二叉树的创建

  • 完全二叉树的顺序映射
  • 先序拓扑序列
  • 先序+中序或后序+中序也可唯一确定的一棵二叉树—-线索化二叉树

线索二叉树

利用叶子结点的未使用的指针域，加两个标记

typedef enum{Link,Thread}PointerTag;
typedef struct BiThrNode
{
   ElemType data;
   struct BiThrNode *lchild,*rchild;
   PointerTag ltag,rtag;
}BiThrNode,*BiThrTree;

先序/中序/后序线索化二叉树：对应遍历顺序的相应前驱，后继，其算法可以类比相应的遍历算法。

中序线索化中规中矩，基本是中序遍历的拓展，左孩子为前驱，右孩子为后继；

先序/后序线索化二叉树 相互对称，难点：找前驱和后继

后序找到前驱的方法：

  • 若该结点无左孩子，前驱由lchild指向
  • 若该结点有左右孩子，前驱为右孩子
  • 若该结点只有左孩子，前驱为左孩子

后序找到结点的后继

  • 若结点为根结点，后继为空
  • 若结点为双亲的右孩子或没有右兄弟，后继为双亲
  • 若为有右兄弟的左孩子，且右兄弟为叶子结点，后继为右兄弟
  • 若为有右兄弟的左孩子，且右兄弟不是叶子结点，则后继为右兄弟后序遍历的第一个结点

后序找到结点的后继

  • 若结点为根结点，前驱为空
  • 若结点为双亲的左孩子或没有左兄弟，前驱为双亲
  • 若为有左兄弟的右孩子，且左兄弟为叶子结点，前驱为左兄弟
  • 若为有左兄弟的右孩子，且左兄弟不是叶子结点，则前驱为左兄弟先序遍历的最后一个结点

先序找到后继的方法

  • 若该结点无右孩子，后继由右孩子指向
  • 若该节有左右孩子，其后继为左孩子
  • 若该结点有右孩子且无左孩子，其后继为右孩子

涉及求结点的双亲的问题———三叉链表

树的存储结构

双亲表示法

可以用于顺序存储

#define MAX_TREE_SIZE 100
typedef struct{
   ElemType data;
   int parent;
}PTNode;
typedef struct{
   PTNode nodes[MAX_TREE_SIZE];
   int n;//结点数
}PTree;

孩子表示法

#define MAX_TREE_SIZE 100
typedef struct{
  int child;
   struct CTNode *next;
}*ChildPtr;
typedef struct{
   ElemType data;
   ChildPtr firstchild;
}CTBox;
typedef struct {
   CTBox nodes[MAX_TREE_SIZE];
   int n,r;//结点数和根的位置
}CTree;

孩子兄弟表示法

typedef struct CSNode{
   ElemType data;
   struct CSNode *firstchild,*nextsibling;
}CSNode,*CSTree;

树的遍历

先根遍历<—->二叉树的先序遍历

后根遍历<—->二叉树的中序遍历

应用：通常以孩子-兄弟链表示

  • 统计树的高度
  • 统计树中叶子结点的个数（叶子结点的标志：Firstchild为空）
  • 求树的度

树和森林与二叉树之间的转换…没讲，不知道考不考

Huffman树

相关概念：最优树，路径长度（带权），结点带权路径长度，$WPL=\sum_{i=1}^nw_il_i$

Huffman编码（算法应该不考，考也无所谓）

开拓问题求解相关思路

课本没讲？。？应该不考OvO

划分等价类，回溯法求解问题，树的计数/编号

图

相关概念：有向图，无向图，带权/无权图路径和连通性，连通和强连通，子图，生成树，顶点/弧（相关概念复习图论再写）

一般算法中不考虑带权图的权值为负数的情况

基本操作 PS:操作包含对点vex，对边arc的操作

Status LocateVex(G,u);
Status GetVex(G,v);
Status FirstAdjVex(G,v);
Status NextAdjVex(G,v,w);
Status InsertVex(G,v);
Status InsertArc(&G,v,w);
Status DeleteVex(&G,v);
Status DeleteArc(&G,v,w);
Status DFSTraverse(G,v,Visit());
Status BFSTraverse(G,v,Visit());

图的存储结构

用顺序表存储顶点集，不是顺序映像

最常用的还是邻接表

用以下方法存储关系集合

数组表示—邻接矩阵

#define INFINITY INT_MAX
typedef enum{DG,DN,AG,AN}GraphKind;//有向/无向，带权/无权
typedef struct ArcCell{
   //带权图：adj代表权值，INFINITY代表不相邻
   //无权图0代表不相邻，1代表相邻
   int adj;
   InfoType *info;//指向相关信息的指针
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VEXTEX_NUM];
typedef struct {
   VextexType vexs[MAX_VEXTEX_NUM];
   AdjMatrix arcs;
   int vexnum;
   int arcnum;
   GraphKind kind;
}MGraph;

无向图的邻接矩阵：对阵矩阵

链表表示—邻接表/逆邻接表

typedef struct ArcNode{
   int adjvex;
   struct ArcNode *nextarc;
   InfoType *info;
}ArcNode;
typedef struct {
   VexType data;
   ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct{
   AdjList vertices;
   int vexnum,arcnum;
   GraphKind kind;
}ALGraph;

对于有向图，比较容易计算的是顶点的出度，而入度要对所有的边进行遍历才能求出（反之为逆邻接表）。

对于稀疏图（$v>log_2a$），多采用邻接表，避免空间浪费，否则可以选用邻接矩阵。

十字链表—有向图

弧结点数=弧数

方便求出顶点的入度和 出度

typedef struct ArcBox{
   int tailvex,headvex;
   struct ArcBox *hlink,*tlink;
   InfoType *info;
}ArcBox;
typedef struct VexNode{
   VextexType data;
   ArcBox *firstin,*firstout;
}VexNode;
typedef struct{
   VexNode xlist[MAX_VERTEX_NUM];
   int vexnum,arcnum;
}OLGraph;

邻接多重表—无向图

邻接表中：边结点数==2*边数

临界多重表：边结点数==边数

typedef enum{unvisited ,visited}VisitIf;
//边结点
typedef struct EBox{
   VisitIf mark;
   int ivex,jvex;
   struct Ebox *ilink,jlink;
   InfoType *info;
}EBox;
//顶点结点
typedef struct VexBox{
   VexType data;
   EBox *firstedge;
}VexBox;
//临界多重表
typedef struct {
   VexBox adjmulist[MAX_VEXTEX_NUM];
   int vexnum,edgenum;
}AMLGraph;

图的遍历

对顶点的遍历——引入标记数组visitd[0,…n-1]，防止顶点被多次访问。

访问结束可以得到图的生成树（连通图可以从一个顶点完成全部的遍历，非连通图要在外部加循环确保所有顶点均被访问，有向图注意强连通），后续连通性模块将讨论。

可以基于图的多种存储结构进行相似的遍历，算法可以基于ADT Graph（调用ADT的函数，如FirstAdjVex，NextAdjVex等）或某种存储结构写。

DFS

深度优先遍历——树的先序遍历

生成从起点v出发的深度优先生成树，v可能存在多个子树

非递归实现：利用栈及时进行现场保护和现场维护

BFS

广度优先遍历——树的层次遍历

  • 判断两个顶点是否存在路径
  • 得到某点到任意一个顶点之间的最短路径（无权）
  • 求距离v的最短距离最长/最短的顶点
  • 求距离v距离为k的所有顶点

遍历算法的应用

  • 求一条包含图中所有顶点的简单路径
    • 不一定存在，基于DFS寻找，是否能找到与具体顶点的选择有关
    • 对DFS的修改：要回溯，添加计数器记录当前路径的结点数n，查找失败时恢复原来的状态，n--
    • 可以修改算法，选择输出一条路径或者全部路径（最好是一条？），统计最短路径的条数
  • 求距离v的最短距离最长的顶点和最长的路径值
    • 对BFS进行修改，在每层结尾入队一个特殊元素
    • 最后一个出队列的一定是路径最长的顶点

图的连通性问题

基本概念：连通分量的顶点集，生成树，DFS生成树，BFS生成树，生成森林

同样可以基于ADTGraph或具体的存储方式写出不同的算法

  • BFS/DFS生成树/生成森林
  • 有向图的强连通分量
    • 从某顶点出发，以该顶点为尾做DFS，按照其所有邻接点的搜索都完成的顺序（退出DFS的顺序）存储到数组
    • 从存储到数组的顶点出发，沿着该顶点为头的弧进行逆向DFS，能访问到的顶点则在同一个强连通分量中
    • 复杂度近似和DFS遍历的复杂度相同
  • 最小生成树MST——无向连通网的最小代价生成树
    • “若（u，v)为具有最小权值的边，则必存在包含该边的最小生成树”
    • Prim算法——最小生成树不断壮大的过程
      • 适用于稠密图$T(N,e)=O(N^2)$
    • Kruskal算法——连通分量不断合并的过程
      • 适用于稀疏图$T(N,e)=O(N*log (e))$
  • 关节点和重连通分量
    • 关节点：删除v后一个连通分量变为两个/两个以上
      • 若生成树的根至少有两棵或两棵以上的子树，则该结点必是关节点
      • 若生成树的某非叶子结点v的某棵子树的结点均没有指向v的祖先的边，则v为关节点
      • 叶子结点一定不是关节点
    • 重连通图：不含关节点的图，保证了任意两个顶点至少存在两条路径
    • 连通度：若连通图G至少删去K个顶点才能变成不连通，则该图的连通度为k
    • 改造DFS可以得到图的关节点，判断是否为重连通图
      • 引入数组low[v]:生成树中以v为根的子树中结点到v的祖先的边所关联的祖先的最小次序号
      • 若对于v，v的孩子结点w有low[w]>=visited[v]，则说明v为关节点

有向无环图（ DAG）的应用

  • 检测有向图中是否有环：
    • 从顶点v出发，若DFS结束前发现出现u到v的回边，则有环

DAG是描述一项活动或系统的进行过程的工具：

​ 顶点—子工程，边—子工程之间的约束

应用：

拓扑排序

问题描述：偏序->全序

偏序：集合X上的元素是自反的，反对称的，传递的

一、AOV网：Activity on vextex network

进行拓扑排序的方法：

  1. 在有向图中选取一个没有前驱的顶点并输出
  2. 在图中删除该顶点和以该顶点为尾的弧
  3. 转1，除非已经输出全部顶点或不存在无前驱的顶点

有向无环图保证了该图存在拓扑排序，存在拓扑排序保证了有向图中没有环

对于一个有向无环图，进行DFS遍历，第一个退出循环的顶点即为出度为0的顶点，（可以）是拓扑排序的最后一个顶点

若有向图的邻接矩阵为三角矩阵，则该途中存在拓扑有序序列

二、AOE网：Activity on edge network

问题：完成整项工程的最短时间/关键路径/事件的最早发生时间

关键活动：最早发生时间（e(i)）==最晚发生时间（l(i)）

最早发生时间：拓扑有序

最晚发生时间：逆拓扑有序

关键路径：输出关键活动（可能不止一条）

最短路径

无权图的最短路径：广度优先搜索

带权有向图的最短路径——dijkstra算法

按路径长度递增的顺序产生最短路径

求任意两个顶点的最短路径

对Dijkstra算法进行循环：$O(T,e)=O(n^3)$

具体实现应该不会考，会考画图？

Floyd（Wallshall算法）：求vi，vj之间的最短路径，依次使得中间路径序号不大于k的最短路径，k依次递增。

查找Search Table

操作：检索/查找（静态），插入/删除（动态）

关键字：主关键字唯一，次关键字不唯一

静态查找

顺序查找

通过顺序表/线性链表进行查找

0的位置设置“哨兵”：避免每一次查找都要判断是否查找完毕，减少比较次数

查找成功：ASL=$(n+1)/2$

查找不成功：ASL=n+1

有序表的查找

  1. 折半查找
    1. 基本思想：用low/high做标记，查找区间折半缩小
    2. 性能分析：查找过程可以用二叉树判定树表示，判定树的形态与n直接相关（不是完全二叉树但胜似完全二叉树），查找层次即为二叉树的层次，也代表ASL
    3. 查找成功或不成功：$ASL<=[log_2n]+ 1$
    4. n>=50时，可近似得到结果：$ASL_{bs}\approx log_2(n+1)-1$
  2. 斐波那契查找
    1. 根据斐波那契的特征对标进行分割:开始表中的记录个数比斐波那契数小1，则将定值与F(n-1)进行比较，类似折半查找
    2. 特点：分割时只需进性加减运算
    3. 平均性能比折半查找好，但最坏的情况比折半查找糟糕
  3. 插值查找
    1. $i=\frac{key-ST.elem[l].key}{ST.elem[h].key-ST.elem[l].key}(h-l+1)$
    2. 只适用于关键字均匀分布的情况，这种情况下平均性能优于折半查找
  4. 静态树表查找
    1. 根据各个记录的查找概率求ASL
    2. PH值：判定树内带权路径长度$PH=\sum_{i=1}^nw_ih_i$,其中$w_i=c*p_i$为权，$h_i$为层次
    3. PH值最小：静态最优查找树——构造需要的时间开销过高
    4. 构造较好的次优查找树
    5. …写到这里发现查找树表不考，再见
  5. 索引顺序表
    1. 起因：顺序查找表效率低而折半查找等要求查找表有序
    2. 思想：分块有序——索引有序（索引包含最大项和起始指针）
    3. 过程：先折半查找记录所在的块，再顺序查找元素
    4. $ASL_{bs}=L_b(查找块)+L_w(查找元素)$

动态查找

二叉查找树BST

Binary Search Tree查找算法可以基于二叉树的先序遍历算法写出

中序遍历BST可以得到关键字的有序序列

BST的插入算法：查找失败的同时添加叶子结点

BST的删除算法：

  1. 若P为叶子结点，直接删除并修改双亲的指针域
  2. 若P只有左子树或右子树，将P删除并使P的双亲指针域指向P的孩子
  3. 若P有左右子树，将P与P的右子树的最左边的元素进行互换（中序遍历的首个元素），换言之，将P与P在树中中序访问序列的直接前驱或直接后继进行交换即可，避免树的长高

BST的建立：二叉树的形态与输入的次序直接相关，若原本有序将得到每层只有一个结点的糟糕情况

平均性能分析：$P(n)<=2(1+1\frac{1}{n})ln\ n$

平衡二叉树AVL树

深度与log(N)同量级

引入平衡因子BF：-1，0，1

AVL树的旋转部分不会单独考察算法设计，理解过程即可

  • LL型旋转：在A结点的左孩子的左子树插入结点
  • RR型旋转：在A结点的右孩子的右子树插入结点
  • LR型旋转：在A结点的左孩子的右子树插入结点，先左转再右转
  • RL型旋转：在A结点的右孩子的左子树插入结点，先右转再左转

在对AVL树进行插入和删除操作时及时维护平衡

性能分析：$T(N)=O(log\ N)$

B-树

定义：

  • 每个结点至多有m个子树
  • 若根结点不是叶子结点，至少有两棵子树
  • 除根结点外的非得终端结点至少$\lceil m/2\rceil$个子树
  • 非终端结点包含以下信息：$(n,A_0,K_1,A_1,K_2,…,K_n,A_n)$，其中n为关键字数目，$K_i$为关键字，$A_i$为指针，且$A_{i-1}$指向的所有结点的关键字小于$K_i$,大于$K_{i-1}$
  • 所有叶子结点都出现在同一层次上,且不携带信息，可以视作查找失败，指向这些结点的指针为空，图中表示为F

相关算法

查找：纵向查结点，横向查关键字

通常存储在磁盘中，是数据库的主要索引结构

查找效率的首要因素：层次

通常取m=3，此时又称为2-3树

含有N个关键字的m阶B-树的最大深度：$log_{\lceil m/e\rceil}(\frac{N+1}{2})$

较为特殊的插入删除操作：

…应该不考察算法，要会画图

B+树

B-树的变形树，具体区别：

  • 有n棵子树的结点包含了n个关键字
  • 所有叶子结点包含了关键字的信息，以及指向这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大排序
  • 非终端结点为索引部分，结点仅含有最大或者最小关键字

B+树不是树；支持顺序查找（横向），随机查找（纵向）

键树

好像不考键树

哈希表

Hash函数：H(key)

便于一次存取确定所查记录

将一组关键字利用H(key)和处理冲突的函数映射到有限的连续地址——hash表（散列）

Hash函数的构造方法：

  • 直接定址法（x)
  • 数字分析法/平方取中法
  • 折叠发：移位叠加，间界叠加
  • 除留余数法
  • 随机数法
  • …

处理冲突的方法：s

  • 开放定址法
    • 线性探测再散列+1，+2，…
    • 平方探测再散列+1,-1,+4,-4
    • 伪随机探测再散列
  • 链地址法：关键字为同义词的的各个元素存储在线性链表中
  • 再哈希法：$H_i=RH_i(key),i=1,2,..k$不易产生聚集，但会增加计算的时间
  • 建立公共溢出区域：发生冲突都填入溢出表

​ 二次聚集：在处理同义词冲突的过程中又添加了非同义词的冲突的现象

Hash表的查找算法

根据Hash函数以及冲突处理方法确定

查找的ASL：分成功与不成功计算，时间复杂度为未知

装填因子$\alpha=$记录数/Hash表表长

通常Hash表长m和除留余数法的p的关系：

p<=m,且p为素数或最小不包含小于20的质因子的合数。