应试向的数据结构考试和实际写起代码来有很大区别。重复造轮子就不说了，更可怕的是，有时还需要应试者人脑模拟算法的执行过程。相对来说，对针对具体问题设计算法的考察较浅。

另外，有时王道书的代码风格奇特，我尽量改为了自己习惯的写法，这点需要特别注意。

本文中所有代码除非注明，均不保证能运行。

线性表

线性表：

  • 顺序存储
    • 顺序表
  • 链式存储
    • 单链表（指针实现）
    • 双链表（指针实现）
    • 循环链表（指针实现）
    • 静态链表（借助数组实现）

顺序表

线性表的顺序存储类型描述为：

const int MaxSize = 50;
struct SqList{
  ElemType data[MaxSize];
  int length;
};

动态分配：

const int InitSize = 100;
struct SeqList{
  ElemType* data;
  int MaxSize, length;
};

C++ 的初始动态分配语句为：

L.data = new ElemType[InitSize];

注意：动态分配并不是链式存储，它同样属于顺序存储结构，物理结构没有变化，依然是随机存取方式，只是分配的空间大小可以在运行时动态决定。

例：17 页第 11 题。 顺序表的插入算法中，当 n 个空间已满时，可再申请增加分配 m 个空间，若申请失败，则说明系统没有（n + m 个连续）可分配的存储空间。

顺序表的操作：插入、删除、按值查找。这部分的代码自己实现就行。

单链表

单链表的描述：

struct LNode{
  ElemType data;
  LNode* next;
};

动态分配：

LNode* p = (LNode*) malloc(sizeof(LNode));

要表示一个单链表时，需要一个头指针L：

LNode* L;

带头节点的单链表：

struct LNode{
  ElemType data;
  LNode* next;
};

bool InitList(LNode*& L){
  L = (LNode*) malloc(sizeof(LNode));  //分配一个头节点
  if(L==NULL) return false;    //内存不足，分配失败
  L->next = NULL;             //头节点之后暂时还没有节点
  return true;
}

bool isEmpty(LNode* L){
  if(L->next==NULL)
    return true;
  else
    return false;
}

void work(){
  LNode* L;
  InitList(L);
  // ...
}

按位序插入（带头节点）：

//头节点编号为0，有数据的节点编号从1开始
//插入完成后新元素的位置为 i
bool ListInsert(LNode*& L, int i, ElemType e){
  if(i<1)
    return false;
  LNode* p;  //指向当前扫描到的节点
  int j = 0; //当前p指向的是第几个节点
  p = L;  //指向头节点
  while(p!=NULL && j<i-1){
    p = p->next;
    j++;
  }
  if(p==NULL) //i值不合法
    return false;
  LNode* s = (LNode*) malloc(sizeof(LNode));
  s->data = e;
  s->next = p->next;
  p->next = s;
  return true;
}

上面代码中，若i=1，即是插在表头。

指定节点的后插操作：

bool InsertNextNode(LNode* p, ElemType e){
  if(p==NULL)
    return false;
  LNode* s = (LNode*) malloc(sizeof(LNode));
  s->data = e;
  s->next = p->next;
  p->next = s;
  return true;
}

此时，发现按位序插入（带头节点）的代码可以通过复用指定节点的后插操作的代码来简化：

bool InsertNextNode(LNode* p, ElemType e){
  if(p==NULL)
    return false;
  LNode* s = (LNode*) malloc(sizeof(LNode));
  s->data = e;
  s->next = p->next;
  p->next = s;
  return true;
}

bool ListInsert(LNode*& L, int i, ElemType e){
  if(i<1)
    return false;
  LNode* p;  //指向当前扫描到的节点
  int j = 0; //当前p指向的是第几个节点
  p = L;  //指向头节点
  while(p!=NULL && j<i-1){
    p = p->next;
    j++;
  }
  return InsertNextNode(p, e);
}

指定节点的前插操作：

//思路：使用后插，然后交换数据成员的内容
bool InsertPreNode(LNode* p, ElemType e){
  if(p==NULL)
    return false;
  LNode* s = (LNode*) malloc(sizeof(LNode));
  if(s==NULL) //内存分配失败，考试可以不写
    return false;
  s->next = p->next;
  p->next = s;
  s->data = p->data;
  p->data = e;
  return true;
}

按位序删除（带头节点）：

bool ListDelete(LNode*& L, int i, ElemType &e){
  if(i<1)
    return false;
  LNode* p;  //指向当前扫描到的节点
  int j = 0; //当前p指向的是第几个节点
  p = L;  //指向头节点
  while(p!=NULL && j<i-1){ //循环找到第 i-1 个节点
    p = p->next;
    j++;
  }
  if(p==NULL)  // i 值不合法
    return false;
  if(p->next==NULL) //第i-1个节点之后已无其他节点
    return false;
  LNode* q = p->next; //令q指向被删除节点
  e = q->data; //用e返回元素的值
  p->next = q->next;
  free(q);
  return true;
}
46-1.png
上面代码的图示

指定节点的删除：

//删除指定节点 p
bool DeleteNode(LNode* p){
  if(p==NULL)
    return false;
  LNode* q = p->next;
  p->data = p->next->data;
  p->next = q->next;
  free(q);
  return true;
}
46-2.png
46-2.png

注意上图中的代码有一个 bug，在边界情况（p 节点刚好是最后一个节点）下会产生错误。但是只是应试的话无所谓了，扣也最多一两分，甚至不扣。

单链表按位查找：

//按位查找，返回第i个元素的指针
LNode* GetElem(LNode*& L, int i){
  if(i<0)
    return NULL;
  LNode* p;  //指向当前扫描到的节点
  int j = 0; //当前p指向的是第几个节点
  p = L;  //指向头节点
  while(p!=NULL && j<i){
    p = p->next;
    j++;
  }
  return p;
}

按值查找：

LNode* LocateElem(LNode*& L, ElemType e){
  LNode* p = L->next;
  while(p!=NULL && p->data!=e)
    p = p->next;
  return p;
}

注意：如果ElemType是一个struct，需要自己定义比较运算符。

struct ElemType{
  int a;
  int b; //仅作举例 int
  bool operator != (const ElemType& rhs);
};
bool ElemType::operator != (const ElemType& rhs){
  return (a!=rhs.a || b!=rhs.b);
}

求表的长度：

int Length(LNode*& L){
  int len = 0;
  LNode* p = L;
  while(p->next!=NULL){
    p = p->next;
    len++;
  }
  return len;
}

尾插法建立单链表：

LNode* List_TailInsert(LNode*& L){
  int x;
  L = (LNode*) malloc(sizeof(LNode));
  LNode *s, *r=L;  // r 指向最后一个元素
  scanf("%d",&x);
  while(x!=9999){ // 9999是退出值
    s = (LNode*) malloc(sizeof(LNode));
    s->data = x;
    r->next = s;
    r = s;
    scanf("%d",&x);
  }
  r->next = NULL;
  return L;
}

头插法建立单链表：

//王道书的代码无法忍受，我自己写了。
void List_HeadInsert(LNode*& L){
  InitList(L);
  int x;
  scanf("%d",&x);
  while(x!=9999){ //9999 为退出值，当然也可以while(scanf("%d",&x)){} ，看具体情况
    InsertNextNode(L, x);
    scanf("%d",&x);
  }
  return;
}

总结：单链表的全部操作

struct LNode{
  ElemType data;
  LNode* next;
};

bool InitList(LNode*& L){
  L = (LNode*) malloc(sizeof(LNode));  //分配一个头节点
  if(L==NULL) return false;    //内存不足，分配失败
  L->next = NULL;             //头节点之后暂时还没有节点
  return true;
}

bool isEmpty(LNode* L){
  if(L->next==NULL)
    return true;
  else
    return false;
}

void work(){  //或者认为是 main() 函数也勉强可以
  LNode* L;
  InitList(L);
  // ...
}

bool InsertNextNode(LNode* p, ElemType e){ //指定节点的后插操作
  if(p==NULL)
    return false;
  LNode* s = (LNode*) malloc(sizeof(LNode));
  s->data = e;
  s->next = p->next;
  p->next = s;
  return true;
}

//思路：使用后插，然后交换数据成员的内容
bool InsertPreNode(LNode* p, ElemType e){  //指定节点的前插操作
  if(p==NULL)
    return false;
  LNode* s = (LNode*) malloc(sizeof(LNode));
  if(s==NULL) //内存分配失败，考试可以不写
    return false;
  s->next = p->next;
  p->next = s;
  s->data = p->data;
  p->data = e;
  return true;
}

//按位查找，返回第i个元素的指针
LNode* GetElem(LNode*& L, int i){
  if(i<0)
    return NULL;
  LNode* p;  //指向当前扫描到的节点
  int j = 0; //当前p指向的是第几个节点
  p = L;  //指向头节点
  while(p!=NULL && j<i){
    p = p->next;
    j++;
  }
  return p;
}

LNode* LocateElem(LNode*& L, ElemType e){ //按值查找
  LNode* p = L->next;
  while(p!=NULL && p->data!=e)  //注意细节，往上翻
    p = p->next;
  return p;
}

//插入完成后新元素的位置为 i
bool ListInsert(LNode*& L, int i, ElemType e){ //按位序插入
  if(i<1)
    return false;
  LNode* p = GetElem(L, i-1);
  return InsertNextNode(p, e);
}

bool ListDelete(LNode*& L, int i, ElemType &e){ //按位序删除
  if(i<1)
    return false;
  LNode* p = GetElem(L, i-1);
  if(p==NULL)  // i 值不合法
    return false;
  if(p->next==NULL) //第i-1个节点之后已无其他节点
    return false;
  LNode* q = p->next; //令q指向被删除节点
  e = q->data; //用e返回元素的值
  p->next = q->next;
  free(q);
  return true;
}

//删除指定节点 p
bool DeleteNode(LNode* p){
  if(p==NULL)
    return false;
  LNode* q = p->next;
  p->data = p->next->data;
  p->next = q->next;
  free(q);
  return true;
}

int Length(LNode*& L){ //求表的长度
  int len = 0;
  LNode* p = L;
  while(p->next!=NULL){
    p = p->next;
    len++;
  }
  return len;
}

LNode* List_TailInsert(LNode*& L){ //尾插法建立单链表
  int x;
  L = (LNode*) malloc(sizeof(LNode));
  LNode *s, *r=L;  // r 指向最后一个元素
  scanf("%d",&x);
  while(x!=9999){ // 9999是退出值
    s = (LNode*) malloc(sizeof(LNode));
    s->data = x;
    r->next = s;
    r = s;
    scanf("%d",&x);
  }
  r->next = NULL;
  return L;
}

void List_HeadInsert(LNode*& L){ //头插法建立单链表
  InitList(L);
  int x;
  scanf("%d",&x);
  while(x!=9999){ //9999 为退出值，当然也可以while(scanf("%d",&x)){} ，看具体情况
    InsertNextNode(L, x);
    scanf("%d",&x);
  }
  return;
}

双链表

双链表的描述：

struct DNode{
  ElemType data;
  DNode *pre, *next;
};

初始化：

bool InitDList(DNode*& L){
  L = (DNode*) malloc(sizeof(DNode));
  if(L==NULL)
    return false; //内存不足，分配失败
  L->pre = NULL;
  L->next = NULL;
  return true;
}

bool isEmpty(DNode* L){
  if(L->next==NULL)
    return true;
  else 
    return false;
}

void work(){
  DNode* L;
  InitDList(L);
  //...
}

双链表的插入：

46-3.png
46-3.png
//在 p 节点之后插入 s 节点
bool InsertAfter(DNode* p, DNode* s){
  if(p==NULL || s==NULL) //非法参数
    return false;
  s->next = p->next;
  if(p->next != NULL)
    p->next->pre = s;
  s->pre = p;
  p->next = s;
  return true;
}

双链表的删除和销毁：

46-4.png
46-4.png
//删除 p 节点的后继节点
bool DeleteAfter(DNode* p){
  if(p==NULL)
    return false;
  DNode* q = p->next;
  if(q==NULL)
    return false;
  p->next = q->next;
  if(q->next!=NULL)
    q->next->pre = p;
  free(q);
  return true;
}
//销毁
void DestoryList(DNode*& L){
  while(L->next!=NULL)
    DeleteAfter(L);
  free(L);
  L = NULL;
}

双链表的遍历：

//后向遍历
while(p!=NULL){
  //do something on p
  p = p->next;
}

//前向遍历
while(p!=NULL){
  //do something on p
  p = p->pre;
}

//前向遍历（不处理头节点）
while(p->pre!=NULL){
  //do something on p
  p = p->pre;
}

循环链表

循环单链表：

struct LNode{
  ElemType data;
  LNode* next;
};

bool InitList(LNode*& L){
  L = (LNode*) malloc(sizeof(LNode));  //分配一个头节点
  if(L==NULL) return false;    //内存不足，分配失败
  L->next = L;
  return true;
}

bool isEmpty(LNode* L){
  if(L->next==L)
    return true;
  else
    return false;
}

bool isTail(LNode* L, LNode* p){
  if(p->next==L)
    return true;
  else
    return false;
}
46-5.png
46-5.png

具体代码可以自己实现，不再赘述。

循环双链表：

46-6.png
46-6.png
46-7.png
46-7.png
struct DNode{
  ElemType data;
  DNode *pre, *next;
};

bool InitDList(DNode*& L){
  L = (DNode*) malloc(sizeof(DNode));
  if(L==NULL)
    return false;
  L->pre = L;
  L->next = L;
  return true;
}

void work(){
  DNode* L;
  InitDList(L);
  //do something...
}

bool isEmpty(DNode* L){
  if(L->next==L)
    return true;
  else 
    return false;
}

bool isTail(DNode* L, DNode* p){
  if(p->next==L)
    return true;
  else 
    return false;
}

后插操作：

//在 p 节点之后插入 s 节点
bool InsertAfter(DNode* p, DNode* s){
  s->next = p->next;
  p->next->pre = s;
  s->pre = p;
  p->next = s;
}

删除操作：

46-8.png
46-8.png
//删除 p 的后继节点 q
p->next = q->next;
q->next->pre = p;
free(q);

静态链表

46-9.png
46-9.png
const int Maxsize = 10;
struct Node{
  ElemType data;
  int next;  //下一个元素的数组下标
};

void work(){
  Node a[Maxsize];
  //do something...
}
46-10.png
46-10.png

栈、队列、数组

这 tm 还要学？

理论

顺序栈：代码自己实现。

共享栈：

46-11.jpg
46-11.jpg

链栈：通常采用不带头节点的单链表实现，所有操作在表头进行。

46-12.png
链栈

队列：

46-13.jpg
46-13.jpg

循环队列：

46-14.jpg
46-14.jpg
const int MaxSize = 50;
struct myQueue{
  ElemType data[MaxSize];
  int front, rear;
};

void InitQueue(myQueue& qwq){ //初始化
  qwq.rear = qwq.front = 0;
}

bool isEmpty(myQueue qwq){
  if(qwq.rear==qwq.front) return true;
  else return false;
}

bool EnQueue(myQueue& qwq, ElemType x){ //入队
  if((qwq.rear+1)%MaxSize==qwq.front)
    return false;   //队满则报错
  qwq.data[qwq.rear] = x;
  qwq.rear = (qwq.rear+1) % MaxSize;
  return true;
}

bool DeQueue(myQueue& qwq, ElemType& x){  //出队
  if(qwq.rear==qwq.front) return false; //队空则报错
  x = qwq.data[qwq.front];
  qwq.front = (qwq.front+1) % MaxSize;
  return true;
}

队列的链式存储（左开右闭？）：

通常采用带头节点的单链表。

46-15.png
46-15.png
struct LNode{
  ElemType data;
  LNode* next;
};
struct LinkQueue{
  LNode* front;
  LNode* rear;
};

void InitQueue(LinkQueue& qwq){
  qwq.front = qwq.rear = (LNode*) malloc(sizeof(LNode)); //建立头节点
  qwq.front->next = NULL;
}

void work(){
  LinkQueue qwq;  //声明一个队列
  InitQueue(qwq);
  //do something...
}

bool isEmpty(LinkQueue qwq){
  if(qwq.front==qwq.rear) return true;
  else return false;
}

void EnQueue(LinkQueue& qwq, ElemType x){  //入队
  LNode* s = (LNode*) malloc(sizeof(LNdoe));
  s->data = x;
  s->next = NULL;
  qwq.rear->next = s;
  qwq.rear = s;
}

bool DeQueue(LinkQueue& qwq, ElemType& x){ //出队
  if(qwq.front==qwq.rear) return false;  //空队，失败
  LNode* p = qwq.front->next;
  x = p->data;
  qwq.front->next = p->next;
  if(qwq.rear==p) qwq.rear = qwq.front;
  free(p);
  return true;
}

应用

栈在括号匹配中的应用：

46-16.png
46-16.png

栈在表达式求值中的应用：

Reverse Polish notation（逆波兰表达式 = 后缀表达式）

Polish notation（波兰表达式 = 前缀表达式）

46-17.png
46-17.png
46-18.png
46-18.png
46-18dot5.png
46-18dot5.png
46-19.png
46-19.png
46-20.png
46-20.png
46-21.png
46-21.png

将中缀转后缀和后缀表达式求值两个算法结合起来：

46-22.png
46-22.png

树、二叉树

基本概念

有序树和无序树：

46-23.png
46-23.png

注意：此课程中度的概念和离散数学中不同。（万恶的图论名词差异）

46-24.png
46-24.png

树的一些性质：（注意这里的“度数”是歧义概念）

  1. 树中的节点数等于所有节点的度数之和加 1
  2. 度为 m 的树中第 i 层上至多有 $m^{i-1}$ 个节点（$i\geqslant 1$）
  3. 高度为 h 的 m 叉树至多有 $\frac{m^h-1}{m-1}$ 个节点
  4. 具有 n 个节点的 m 叉树最小高度为 $\left \lceil \log_m(n(m-1)+1) \right \rceil$

结论 4 的推导：

假设高度为 $h$ , 由结论3 ：

$$\frac{m^{h-1}-1}{m-1}< n \leqslant \frac{m^h-1}{m-1}$$
$$m^{h-1}<n(m-1)+1\leqslant m^h$$
$$h-1<\log_m(n(m-1)+1)\leqslant h$$
$$h_{\min}=\left \lceil \log_m(n(m-1)+1) \right \rceil$$

满二叉树、完全二叉树的性质：

46-25.png
46-25.png

二叉排序树：

46-26.png
46-26.png

平衡二叉树：

46-27.png
46-27.png

二叉树的性质

设非空二叉树中度（歧义概念）为 0、1、2 的节点个数分别为 n0、n1、n2 , 则 $n_0=n_2+1$ （叶子节点比二分枝节点多一个）。推导如下：

假设树中节点总数为 n , 则：

  • $n = n_0 + n_1 + n_2$
  • $n = n_1 + 2n_2 + 1$

具有 n 个（n>0）节点的完全二叉树的高度 h 为 $\left \lceil \log_2(n+1) \right \rceil$ 或 $\left \lfloor \log_2n \right \rfloor +1$. （推导不难）

某个性质：

46-28.png
46-28.png

二叉树的存储

顺序存储（绝大多数情况下不会使用）：

46-29.png
46-29.png

完全二叉树的此种存储结构的操作：

46-30.png
46-30.png

对于非完全二叉树：

46-31.png
丑陋的做法

链式存储：

46-32.png
46-32.png

代码实现：

struct ElemType{
  int value;
};

struct BinoTree{
  ElemType data;
  BinoTree* lchild;
  BinoTree* rchild;
  //可以根据需要加上指向父节点的指针
};

//定义一棵空树
BinoTree* root = NULL;

//插入根节点
root = (BinoTree*) malloc(sizeof(BinoTree));
root->data = {1};
root->lchild = NULL;
root->rchild = NULL;

//插入新节点（例子）
BinoTree* p = (BinoTree*) malloc(sizeof(BinoTree));
p->data = {2};
p->lchild = NULL;
p->rchild = NULL;
root->lchild = p;

上面代码对应的图：

46-33.png
46-33.png

先、中、后序遍历

  • 先序遍历：根、左、右（NLR）
  • 中序遍历：左、根、右（LNR）
  • 后序遍历：左、右、根（LRN）

例子：

46-34.png
46-34.png

和表达式的联系：

46-35.png
46-35.png

代码：

//先序遍历
void preOrder(BinoTree* T){
  if(T!=NULL){
    visit(T);             //访问根节点
    preOrder(T->lchild);  //访问左孩子
    preOrder(T->rchild);  //访问右孩子
  }
}

//中序遍历
void inOrder(BinoTree* T){
  if(T!=NULL){
    inOrder(T->lchild);  //访问左孩子
    visit(T);            //访问根节点
    inOrder(T->rchild);  //访问右孩子
  }
}

//后序遍历
void postOrder(BinoTree* T){
  if(T!=NULL){
    postOrder(T->lchild);  //访问左孩子
    postOrder(T->rchild);  //访问右孩子
    visit(T);              //访问根节点
  }
}

层次遍历

其实就是 BFS 。

46-36.png
46-36.png

执行算法：

  1. 初始化一个辅助队列
  2. 根节点入队
  3. 若队列非空，弹队首，访问弹出的节点，并将其孩子（若有）入队
  4. 重复 3 直至队列为空

伪代码：

//注意：我使用了自己习惯的写法
void bfs(){
  queue<node> qwq;
  node temp;
  //do something...
  qwq.push(temp);
  while(!qwq.empty()){
    node head = qwq.front(); //取队首
    qwq.pop();               //弹队首
    //do something...
    qwq.push((node){/*...*/});
  }
}

一个 BFS 剪枝的实例：

//https://www.luogu.com.cn/problem/P1126 
#include<iostream>
#include<queue>
using namespace std;

int n,m,sx,sy,ex,ey;
char face; bool ok=true;
int a[53][53],ans;
int fx[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
bool vis[53][53];
struct node{
    int x,y;
    int dir,step;
    bool chan;
};

inline int changedir(int dirt,int xia)
{
    if(xia==0)return (dirt+1)%4;
    else if(xia==233)return (dirt+2)%4;
	else return (dirt-1+4)%4;
}

inline bool check(int x,int y)
{
    if(x<1||x>=n||y<1||y>=m)return false;
    if(a[x][y]||a[x+1][y])return false;
    if(a[x][y+1]||a[x+1][y+1])return false;
    return true;
}

inline bool bfs()
{
    queue<node> qwq;
    node temp;
    temp.x=sx;temp.y=sy;
    if(face=='E')temp.dir=0;
    if(face=='S')temp.dir=1;
    if(face=='W')temp.dir=2;
    if(face=='N')temp.dir=3;
    temp.step=0; temp.chan=false;
    qwq.push(temp);
    vis[temp.x][temp.y]=true;
    
    while(!qwq.empty())
    {
        node head=qwq.front();
        qwq.pop();
        for(int i=1;i<=3;i++)
        {
            int nx=head.x+fx[head.dir][0]*i;
            int ny=head.y+fx[head.dir][1]*i;
            if(!check(nx,ny))break;
            if(vis[nx][ny])continue;
            if(nx==ex&&ny==ey)
            {
                ans=head.step+1;
                return true;
            }
            qwq.push((node){nx,ny,head.dir,head.step+1,false});
            vis[nx][ny]=true;
        }
        if(head.chan)continue;
        int dirti=changedir(head.dir,0);
        int dirti2=changedir(head.dir,1);
        qwq.push((node){head.x,head.y,dirti,head.step+1,true});
        qwq.push((node){head.x,head.y,dirti2,head.step+1,true});
        if(ok)
		{
        	ok=false;
        	int dirti3=changedir(head.dir,233);
        	qwq.push((node){head.x,head.y,dirti3,head.step+2,true});
        }
    }
    return false;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    cin>>a[i][j];
    cin>>sx>>sy>>ex>>ey>>face;
    
    if(sx==ex&&sy==ey)cout<<0;
    else if(bfs())cout<<ans;
    else cout<<"-1";
    return 0;
}

注意在树或者图中需要在具体的数据结构上实现 BFS ，例如链式前向星。

有必要给出应试代码，以下代码只适合二叉树：

46-37.png
46-37.png

由遍历序列构造二叉树

若只给出一棵二叉树的 前/中/后/层 序遍历序列中的一种，不能唯一确定一棵二叉树。

由二叉树的遍历序列构造二叉树，需已知以下三种信息中的任一种：

  • 前序+中序 遍历序列
  • 后序+中序 遍历序列
  • 层序+中序 遍历序列

由前序+中序遍历序列确定二叉树：

46-38.png
46-38.png

由后序+中序遍历序列确定二叉树：

46-39.png
46-39.png

由层序+中序遍历序列确定二叉树：

46-40.png
46-40.png

补充说明：

46-41.png
46-41.png

线索二叉树

问题的引入：

46-42.png
46-42.png

线索二叉树的概念：

46-43.png
46-43.png

线索二叉树的存储结构：

struct ThreadNode{
  ElemType data;
  TreadNode* lchild;
  TreadNode* rchild;
  bool ltag, rtag;
};
// tag==0 , 表示指针指向孩子
// tag==1 , 表示指针是“线索”
46-44.png
46-44.png

先序线索二叉树：

46-45.png
46-45.png

后序线索二叉树：

46-46.png
46-46.png

中序线索化代码实现：

struct ThreadNode{
  ElemType data;
  TreadNode* lchild;
  TreadNode* rchild;
  bool ltag, rtag;
};

ThreadNode* pre = NULL;

void visit(ThreadNode* q){
  if(q->lchild==NULL){ //左子树为空，建立前驱线索
    q->lchild = pre;
    q->ltag = 1;
  }
  if(pre!=NULL && pre->rchild==NULL){
    pre->rchild = q;
    pre->rtag = 1;
  }
  pre = q;
}

void inThread(ThreadNode* T){ //中序遍历二叉树，一边遍历一边线索化
  if(T!=NULL){
    inThread(T->lchild);  //访问左孩子
    visit(T);             //访问根节点
    inThread(T->rchild);  //访问右孩子
  }
}

void CreateInThread(ThreadNode* T){ //最后调用这个函数即可
  pre = NULL;
  if(T!=NULL){ //二叉树非空
    inThread(T);
    if(pre->rchild==NULL){
      pre->rtag = 1; //处理遍历的最后一个节点
    }
  }
}

先序线索化代码：

struct ThreadNode{
  ElemType data;
  TreadNode* lchild;
  TreadNode* rchild;
  bool ltag, rtag;
};

ThreadNode* pre = NULL;

void visit(ThreadNode* q){
  if(q->lchild==NULL){ //左子树为空，建立前驱线索
    q->lchild = pre;
    q->ltag = 1;
  }
  if(pre!=NULL && pre->rchild==NULL){
    pre->rchild = q;
    pre->rtag = 1;
  }
  pre = q;
}

void preThread(ThreadNode* T){
  if(T!=NULL){
    visit(T);
    if(T->ltag==0)   //防止原地转圈
      preThread(T->lchild);
    preThread(T->rchild);
  }
}

void CreatePreThread(ThreadNode* T){
  pre = NULL;
  if(T!=NULL){
    preThread(T);
    if(pre->rchild==NULL)
      pre->rtag = 1;
  }
}

后序线索化代码：

struct ThreadNode{
  ElemType data;
  TreadNode* lchild;
  TreadNode* rchild;
  bool ltag, rtag;
};

ThreadNode* pre = NULL;

void visit(ThreadNode* q){
  if(q->lchild==NULL){ //左子树为空，建立前驱线索
    q->lchild = pre;
    q->ltag = 1;
  }
  if(pre!=NULL && pre->rchild==NULL){
    pre->rchild = q;
    pre->rtag = 1;
  }
  pre = q;
}

void postThread(ThreadNode* T){ //中序遍历二叉树，一边遍历一边线索化
  if(T!=NULL){
    postThread(T->lchild);  //访问左孩子
    postThread(T->rchild);  //访问右孩子
    visit(T);               //访问根节点
  }
}

void CreatePostThread(ThreadNode* T){ //最后调用这个函数即可
  pre = NULL;
  if(T!=NULL){ //二叉树非空
    postThread(T);
    if(pre->rchild==NULL){
      pre->rtag = 1; //处理遍历的最后一个节点
    }
  }
}

中序线索二叉树找中序后继：

ThreadNode* firstNode(ThreadNode* p){
  //找到以p为根的子树中，第一个被中序遍历的节点
  //循环找到最左下节点（不一定是叶子节点）
  while(p->ltag==0) p = p->lchild;
  return p;
}

ThreadNode* nextNode(ThreadNode* p){
  //在中序线索二叉树中找到节点p的后继节点
  if(p->rtag==0) return firstNode(p->rchild);
  else return p->rchild;
}

void inOrderScan(ThreadNode* T){
  //对中序线索二叉树进行中序遍历
  for(ThreadNode* p=firstNode(T); p!=NULL; p=nextNode(p)){
    visit(p);
  }
}

中序线索二叉树找中序前驱思路（上面找后继的思路类似，不回头补了）：

46-47.png
46-47.png

中序线索二叉树找中序前驱代码：

ThreadNode* lastNode(ThreadNode* p){
  //找到以p为根的子树中，最后一个被中序遍历的节点
  //循环找到最右下节点（不一定是叶子节点）
  while(p->rtag==0) p = p->rchild;
  return p;
}

ThreadNode* preNode(ThreadNode* p){
  //在中序线索二叉树中找到节点p的前驱节点
  if(p->ltag==0) return lastNode(p->lchild);
  else return p->lchild;
}

void revInOrderScan(ThreadNode* T){
  //对中序线索二叉树进行逆向中序遍历
  for(ThreadNode* p=lastNode(T); p!=NULL; p=preNode(p)){
    visit(p);
  }
}

先序线索二叉树找先序后继：

46-48.png
46-48.png

先序线索二叉树找先序前驱：

46-49.png
46-49.png

可以发现，按照之前的思路无法实现。但是，如果每个节点增加指向其父节点的指针，则可以有如下思路：

46-50.png
46-50.png

后序线索二叉树找后序前驱：

46-51.png
46-51.png

后序线索二叉树找后序后继：

46-52.png
46-52.png

可以发现，按照之前的思路无法实现。但是，如果每个节点增加指向其父节点的指针，则可以有如下思路：

46-53.png
46-53.png

总结：

46-54.png
46-54.png

树、森林

孩子兄弟表示法（很怪，感觉不实用）：

46-55.png
46-55.png

树和二叉树的转化：

46-56.png
46-56.png

森林和二叉树的转换：

46-57.png
46-57.png

树的遍历：先根遍历、后根遍历、层序遍历。

46-58.png
46-58.png

森林的遍历：先序遍历、中序遍历。

46-59.png
46-59.png

特别提醒： 以上只是一个应试的可选补充，熟悉 OI 代码直接在纸上写 OI 代码即可。例如树的遍历，采用链式前向星：

struct Edge{int v,w,next;}edge[MAXM];
int tot,head[MAXN];

void addedge(int x,int y,int z){
    edge[++tot].v=y;
    edge[tot].w=z;
    edge[tot].next=head[x];
    head[x]=tot;
}

// 访问所有与 x 相接的点
for(int i=head[x];i;i=edge[i].next){
    int y=edge[i].v;
    //do something...
}

树与二叉树的应用

Huffman树：https://dropsong.cc/post/9e22caea/#huffman%E6%A0%91

性质：n 个叶子节点最终构成的 Huffman 树节点总数为 2n-1 .

Huffman 编码：

46-60.png
46-60.png

并查集：https://dropsong.cc/post/9e22caea/

#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN=10010;
int uset[MAXN];

void makeset(int size){
    for(int i=0;i<size;i++)uset[i]=i;
}

int find(int x){
    if(x!=uset[x])uset[x]=find(uset[x]);
    return uset[x];
}

void unionset(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y)return;
    uset[x]=y;
}

int main()
{
    int n,m; cin>>n>>m;
    makeset(n+1);
    
    int z,x,y;
    while(m--)
    {
        scanf("%d%d%d",&z,&x,&y);
        if(z==1)unionset(x,y);
        else if(z==2){
            if(find(x)==find(y))
            printf("Y\n");
            else printf("N\n");
        }
    }
    
    return 0;
}

图

基本概念

邻接矩阵的某个性质（建议配合离散数学食用）：

46-61.png
46-61.png

类似地，有：

46-62.png
46-62.png

邻接表法：

46-63.png
丑陋的做法

十字链表存储有向图，空间复杂度 $O(|V|+|E|)$

  • 只用于存储有向图
  • 找到指定顶点的所有出边：顺着绿色线路找
  • 找到指定顶点的所有入边：顺着橙色线路找
46-64.png
非常丑陋的做法

邻接多重表存储无向图，空间复杂度 $O(|V|+|E|)$

  • 只能用于存储无向图
  • 删除边、删除节点等操作“很方便”
46-65.png
让人怀疑这个世界其实不算糟

我选择，链式前向星。希望阅卷老师能看懂。

图的基本操作

Adjacent(G, x, y) ：判断图 G 是否存在边<x,y>或(x,y)

  • 无向图
    • 邻接矩阵时间复杂度 $O(1)$
    • 邻接表时间复杂度 $O(1)\rightarrow O(|V|)$
  • 有向图
    • 邻接矩阵时间复杂度 $O(1)$
    • 邻接表时间复杂度 $O(1)\rightarrow O(|V|)$

Neighbors(G, x) ：列出图 G 中与节点 x 邻接的边

  • 无向图
    • 邻接矩阵时间复杂度 $O(|V|)$
    • 邻接表时间复杂度 $O(1) \rightarrow O(|V|)$
  • 有向图
    • 邻接矩阵时间复杂度 $O(|V|)$
    • 邻接表时间复杂度
      • 出边 $O(1) \rightarrow O(|V|)$
      • 入边 $O(|E|)$

InsertVertex(G, x) ：在图 G 中插入顶点 x

  • 无向图和有向图时间复杂度相同
    • 邻接矩阵时间复杂度 $O(1)$
    • 邻接表时间复杂度 $O(1)$

DeleteVertex(G, x) ：从图 G 中删除顶点 x

  • 无向图
    • 邻接矩阵时间复杂度 $O(|V|)$
    • 邻接表时间复杂度 $O(1) \rightarrow O(|E|)$
  • 有向图
    • 邻接矩阵时间复杂度 $O(|V|)$
    • 邻接表时间复杂度
      • 删出边 $O(1) \rightarrow O(|V|)$
      • 删入边 $O(|E|)$

AddEdge(G, x, y) ：加边

  • 无向图和有向图类似
    • 邻接矩阵 $O(1)$
    • 邻接表 $O(1)$ （头插法）

FirstNeighbor(G, x) ：求图 G 中顶点 x 的第一个邻接点，若有返回顶点号；若没有或者根本不存在 x ，返回 -1

  • 无向图
    • 邻接矩阵 $O(1) \rightarrow O(|V|)$
    • 邻接表 $O(1)$
  • 有向图
    • 邻接矩阵 $O(1) \rightarrow O(|V|)$
    • 邻接表
      • 找出边邻接点 $O(1)$
      • 找入边邻接点 $O(1) \rightarrow O(|E|)$

NextNeighbor(G, x, y) ：假设图 G 中顶点 y 是顶点 x 的一个邻接点，返回除 y 外顶点 x 的下一个邻接点的顶点号，若 y 是 x 的最后一个邻接点，返回 -1

  • 无向图
    • 邻接矩阵 $O(1) \rightarrow O(|V|)$
    • 邻接表 $O(1)$
  • 有向图类似

Get_edge_value(G, x, y) ：获取图 G 中边对应的权值。 $\quad$ Set_edge_value(G, x, y, v) ：设置图 G 中边对应的权值为 v

  • 与Adjacent(G, x, y)（判断是否存在边）雷同，核心在于找到边。因此时间复杂度为：
    • 邻接矩阵 $O(1)$
    • 邻接表 $O(1) \rightarrow O(|V|)$

图的遍历

一、BFS

对教科书代码留个印象：

46-66.png
46-66.png

同一个图的邻接矩阵表示方式唯一，因此广度优先遍历序列唯一。同一个图的邻接表表示方式不唯一，因此广度优先遍历序列不唯一。

复杂度分析：

46-67.png
46-67.png

广度优先生成树：

46-68.png
46-68.png

广度优先生成森林：

46-69.png
46-69.png

二、DFS

对教科书代码留个印象：

46-70.png
46-70.png

复杂度分析：

46-71.png
46-71.png

同一个图的邻接矩阵表示方式唯一，因此深度优先遍历序列唯一。同一个图的邻接表表示方式不唯一，因此深度优先遍历序列不唯一。

深度优先生成树、深度优先生成森林，与之前提到的类似，不再赘述。

最小生成树

一睹芳容：

46-72.png
46-72.png

Prim 算法的实现思想：

46-73.png
46-73.png

下面给出 kruscal 代码：

//kruscal
#include<cstdio>
#include<algorithm>
using namespace std;

const int MAXN = 5000+10;
const int MAXM = 200000+10;
struct Edge{int u,v,w;}edge[MAXM];
int uset[MAXN],n,m,ans;

int find(int x){
    if(uset[x]!=x)uset[x]=find(uset[x]);
    return uset[x];
}

void unionset(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y)return;
    uset[x]=y;
}

bool cmp(Edge x,Edge y){return x.w<y.w;}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        edge[i].u=x;
        edge[i].v=y;
        edge[i].w=z;
    }
    
    sort(edge+1,edge+1+m,cmp);
    for(int i=0;i<=n;i++)uset[i]=i;
    
    int cnt=0;
    for(int i=1;i<=m;i++)
    {
        int x=find(edge[i].u);
        int y=find(edge[i].v);
        if(x==y)continue;
        ans+=edge[i].w;
        unionset(x,y);
        if(++cnt==n-1)break;
    }
    
    if(cnt<n-1)printf("orz");
    else printf("%d",ans);
    return 0;
}

最短路径问题

SPFA 算法（用于求单源最短路径）：

  • AKA, 队列优化的 Bellman-Ford 算法
  • 允许图中存在负权边
  • 不可求负环，可判断负环
  • 在稀疏图上效率较高，时间复杂度 $O(km)$ , k 为较小的常数
  • 在稠密图或特殊构造的网格图上，算法可能退化为 $O(nm)$
// SPFA
#include<bits/stdc++.h>
#define MAXM 500010
#define MAXN 10010
#define INF 2147483647
using namespace std;

int n,m,s,dis[MAXN];
bool inq[MAXN];
struct Edge{int v,w,next;}edge[MAXM];
int tot,head[MAXN];

inline void addedge(int x,int y,int z){
    edge[++tot].v=y;
    edge[tot].w=z;
    edge[tot].next=head[x];
    head[x]=tot;
}

void spfa()
{
    queue<int> qwq;
    for(int i=1;i<=n;i++)dis[i]=INF;
    
    qwq.push(s);
    dis[s]=0;inq[s]=true;
    
    while(!qwq.empty())
    {
        int x=qwq.front();
        qwq.pop(); inq[x]=false;
        
        for(int i=head[x];i;i=edge[i].next){
            int y=edge[i].v;
            if(dis[y]>dis[x]+edge[i].w){
                dis[y]=dis[x]+edge[i].w;
                if(!inq[y]){qwq.push(y);inq[y]=true;}
            }
        }
    }
}

int main()
{
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        addedge(x,y,z);
    }
    
    spfa();
    
    for(int i=1;i<=n;i++)
     if(s==i)printf("0 ");
     else printf("%d ",dis[i]);
    
    return 0;
}

Dijkstra 算法（用于求单源最短路径）：

  • 要求图的边权为正
  • 可以求环
  • 时间复杂度：
    • 考试中可认为（也就是未优化的算法版本）复杂度是 $O(n^2)$
    • 若用二叉堆（C++ STL priority_queue）维护 dist 数组，最终可以得到 $O((m+n)\log n)$ 的复杂度
46-74.png
Dijkstra算法执行流程
// Dijkstra
#include<cstdio>
#include<queue>
#define MAXM 200010
#define MAXN 100010
using namespace std;

const int INF =2147483647;
int n,m,s,dis[MAXN];
bool done[MAXN];
int tot,head[MAXN];
struct Edge{int v,w,next;}edge[MAXM];

inline void addedge(int x,int y,int z)
{
    edge[++tot].v=y;
    edge[tot].w=z;
    edge[tot].next=head[x];
    head[x]=tot;
}

struct node{
    int u,dist;
    bool operator<(const node& v)const{
        return dist>v.dist;
    }
};

priority_queue<node> qwq;
inline void dijkstra()
{
    for(int i=1;i<=n;i++)dis[i]=INF;
    dis[s]=0;
    qwq.push((node){s,0});
    
    while(!qwq.empty())
    {
        node front=qwq.top(); qwq.pop();
        int u=front.u,dist=front.dist;
        if(done[u])continue;
        done[u]=true;
        for(int i=head[u];i;i=edge[i].next)
        {
            int y=edge[i].v,z=edge[i].w;
            if(dis[u]+z<dis[y])
            {
                dis[y]=dis[u]+z;
                qwq.push((node){y,dis[y]});
            }
        }
    }
}

int main()
{
    scanf("%d%d%d",&n,&m,&s);
    int x,y,z;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        addedge(x,y,z);
    }
    
    dijkstra();
    
    for(int i=1;i<=n;i++)printf("%d ",dis[i]);
    return 0;
}

Dijkstra 输出路径：

46-75.png
46-75.png

Floyd 算法：

喜闻乐见的人脑模拟算法执行：

46-76.png
46-76.png

找路径：

46-77.png
46-77.png

Floyd 代码实现：

#include <cstdio>
#define MIN(a,b) ((a)<(b)?(a):(b))

const int MAXN = 103;
const int MAXM = 4503;
const int INF = (0x7fffffff>>1)-10;

int dis[MAXN][MAXN],n,m;

int main() {
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i!=j)dis[i][j] = INF;
    
    for(int i=1; i<=m; i++){
        int x, y, z;
        scanf("%d%d%d",&x, &y, &z);
        dis[x][y] = dis[y][x] = z;
    }

    for(int k=1; k<=n; k++)
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                dis[i][j]=dis[j][i]=MIN(dis[i][j], dis[i][k]+dis[k][j]);

    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            printf("%d ",dis[i][j]);
        }
        putchar('\n');
    }

    return 0;
}

小结：

46-78.png
46-78.png

有向无环图描述表达式

知识里的你，再弱小也是真的：

46-79.png
46-79.png

看一眼真题：

46-80.png
46-80.png

此类题目的解题方法：

46-81.png
46-81.png

最后看一个特例：

46-82.png
46-82.png

从上面的特例（左）可以发现，允许重边；另外，可以画出的图不唯一。

拓扑排序

一个概念，AOV 网：

46-83.png
46-83.png

拓扑排序是对有向无环图的所有顶点，生成一个线性的序列，来表达这个图的顶点之间的先后关系：

46-84.png
46-84.png

通常使用 BFS 实现拓扑排序，流程如下：

  • 首先建立空队列，把所有入度为 0 的节点加入队列
  • 从队列中取出一个节点，将从其出发的所有边删除。在编程上，即将边所连到的点入度减一，判断该边通向的节点是否入度变为 0 ，若是，则加入队列
  • 重复以上步骤，直至队列中不剩下任何节点为止
queue<int> qwq;
void topoSort() {
    for(int i = 0; i < N; i++)
        if(inDegree[i] == 0) qwq.push(i);
  
    while(!qwq.empty()) {
        int v = qwq.front();
        qwq.pop();
        cout << v << " ";
        for(list<int>::iterator it = edge[v].begin(); it != edges[v].end(); it++) {
            inDegree[*it]--;
            if(!inDegree[*it]) qwq.push(*it);
        }
    }
}

对于稍复杂的情况或使用链式前向星数据结构的代码，请参考：https://dropsong.cc/post/9e22caea/

拓扑排序是对有向无环图而言的。如果需要判断图中是否存在环，则可以统计是否所有的顶点都入过队列，若存在未入过队的节点，代表图中存在环。

如果你愿意看王道的代码的话也不是不行：

46-85.png
46-85.png

以上代码的时间复杂度为 $O(|V|+|E|)$ ，若采用邻接矩阵，则为 $O(|V|^2)$ .

逆拓扑排序：

46-86.png
46-86.png

逆拓扑排序代码实现：

46-87.png
46-87.png

以上代码中，无论从哪一个顶点出发进行 DFS 都可以得到正确输出。

关键路径

概念，AOE 网：

46-88.png
46-88.png

AOE 网两个简单的性质：

  • 仅有一个入度为 0 的顶点，称为“开始顶点（源点）”，它表示整个工程的开始
  • 仅有一个出度为 0 的顶点，称为“结束顶点（汇点）”，它表示整个工程的结束

从源点到汇点的有向路径可能有多条，所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动。完成整个工程的最短时间就是关键路径的长度，若关键活动不能按时完成，则整个工程的完成时间就会延长。

算法思路：

46-89.png
46-89.png

大致实现思路：

46-90.png
46-90.png

若缩短关键活动的时间，可以缩短工期。但当缩短到一定程度时，关键活动可能会变成非关键活动。

可能有多条关键路径，只提高一条关键路径上的关键活动速度并不一定能缩短整个工程的工期。 只有加快那些包括在所有关键路径上的关键活动才能缩短工期。

最后，贴一个看起来像关键路径、但其实可以用拓扑排序的题目：P1113 杂务

查找

查找长度：在查找运算中，需要对比关键字的次数称为查找长度。

平均查找长度（ASL, Average Search Length）：所有查找过程中，进行关键字的比较次数的平均值。

$$ASL=\sum_{i=1}^nP_iC_i$$

上式中，n 为数据元素个数；$P_i$ 为查找第 i 个元素的概率；$C_i$ 为查找第 i 个元素的查找长度。

一般来说，题目中若无特别说明，默认查找任何一个元素的概率都相同。

顺序查找

某个小技巧：

46-91.png
46-91.png

查找判定树：

46-92.png
46-92.png

折半查找

二分查找的实现细节需要特别注意，在某些特殊的情况下，不正确的写法会导致死循环或是其他的错误。王道的代码就是错误的。

我们直接来看正确的做法：总是将查找区间设为左闭右开的。以题目P1824 进击的奶牛为例，该题的做法是二分答案，给出代码如下：

#include<iostream>
#include<algorithm>
using namespace std;
int a,b,p[1000010];

inline bool check(int x)
{
    int cnt=0,pre=-1500000000;
    for(int i=1;i<=a;i++)
    {
        if(p[i]-pre>=x){
            cnt++;
            pre=p[i];
        }
    }
    if(cnt>=b)return true;
    else return false;
}

int main()
{
    cin>>a>>b;
    for(int i=1;i<=a;i++)cin>>p[i];
    sort(p+1,p+1+a);

    int left=0,right=0x7fffffff;
    while(right!=left+1)
    {
        int mid=(left+right)>>1;
        if(check(mid))left=mid;
        else right=mid;
    }
    
    cout<<left;
    return 0;
}

查找效率分析：

46-93.png
46-93.png

关于折半查找判定树：

  • 判定树节点关键字：左<中<右，满足二叉排序树的定义
  • 失败节点：n+1 个（等于成功节点的空链域数量）
46-94.png
46-94.png

分块查找

特点：块内无序，块间有序。

46-95.png
46-95.png

分块查找，又称索引顺序查找，算法过程如下：

  • 在索引表中确定待查记录所属的分块（可顺序、可折半）
  • 在块内顺序查找

折半查找索引表的例子：

46-96.png
46-96.png

以上是王道书的讲解，是丑陋并且有可能出错的。 但是为了应试，应当了解。如果采用我上面提到的折半查找的方式，查找索引表的方式会完全不同。

效率分析：

46-97.png
46-97.png

拓展思考：

46-98.png
46-98.png

二叉排序树（BST）

定义：

46-99.png
46-99.png

查找：

46-100.png
46-100.png

上面是非递归的实现，下面给出递归版本：

// 王道的代码
BSTNode* BSTsearch(BSTree T, int key) {
  if(T==NULL)
    return NULL;   //查找失败
  if(key==T->key)
    return T;      //查找成功
  else if (key < T->key)
    return BSTsearch(T->lchild, key);  //在左子树中查找
  else
    return BSTsearch(T->rchild, key);  //在右子树中查找
}
//最坏空间复杂度为 O(h) ，h 为树的高度

插入新节点：

46-101.png
46-101.png

构造：

46-102.png
46-102.png

删除某一个节点：

  1. 先找到目标节点
  2. 若被删除节点是叶子节点，则直接删除。不会破坏二叉排序树的性质。
  3. 若被删除节点只有一棵左子树或右子树，则让其子树替代之。依然可以保证二叉排序树的性质。
  4. 若被删除节点既有左子树，又有右子树。有两种方法：
    • 找到右子树中值最小的节点 p（即右子树中最左下的节点，该节点一定没有左子树），替代将被删除的节点。然后删除原来的节点 p（情况同第 3 步）.
    • 找到左子树中值最大的节点 p（即左子树中最右下的节点，该节点一定没有右子树），替代将被删除的节点。然后删除原来的节点 p（情况同第 3 步）.

效率分析：

46-103.png
46-103.png

平衡二叉树（AVL）

一些概念：

46-104.png
46-104.png

二叉排序树中插入新节点时如何保持平衡：

46-105.png
46-105.png

调整最小不平衡子树：

46-106.png
46-106.png

续图：

46-107.png
46-107.png

总结：

46-108.png
46-108.png

一个小坑：

46-109.png
46-109.png

练习题：

46-110.png
46-110.png

查找效率分析：

46-111.png
46-111.png

平衡二叉树的删除

平衡二叉树的删除操作：

  • 删除节点后，要保持二叉排序树的性质不变（左 < 中 < 右）
  • 若删除节点导致不平衡，则需要调整平衡

平衡二叉树的删除操作的具体步骤：

  1. 删除节点（方法同“二叉排序树”）
  2. 一路向上找到最小不平衡子树，若找不到则结束算法
  3. 找最小不平衡子树下，“个头”最高的儿子、孙子
  4. 根据孙子的位置，调整平衡（LL / RR / LR / RL）
    • 孙子在 LL: 儿子右单旋
    • 孙子在 RR: 儿子左单旋
    • 孙子在 LR: 孙子先左旋，再右旋
    • 孙子再 RL: 孙子先右旋，再左旋
  5. 如果不平衡向上传导，转到 2
    • 解释：对最小不平衡子树的旋转可能导致树变矮，从而导致上层祖先不平衡（不平衡向上传导）

在步骤 2 即结束算法的例子：

46-112.png
46-112.png

执行到第 4 步算法结束的例子：

46-113.png
46-113.png

不平衡向上传导一次的例子：

46-114.png
46-114.png

两种选择的例子，可以看到，无论挑选哪个作为“个头”最高的孙子，都可以达到目的：

46-115.png
46-115.png

平衡二叉树的删除操作的时间复杂度是 $O(log_2n)$ .

红黑树的定义和性质

BST AVL Tree Red-Black Tree
生日 1960 1962 1972
查 O(n) O(log_2^n) O(log_2^n)
插 O(n) O(log_2^n) O(log_2^n)
删 O(n) O(log_2^n) O(log_2^n)

红黑树的优势？

  • 平衡二叉树（AVL）的劣势：插入/删除 操作很容易破坏“平衡”特性，需要频繁调整树的形态。如：插入操作导致不平衡，则需要先计算平衡因子，找到最小不平衡子树（时间开销大），再进行 LL/RR/LR/RL 调整。
  • 相比之下，红黑树的优势：插入/删除 操作很多时候不会破坏“红黑”特性，无须频繁调整树的形态。即便需要调整，一般都可以在常数时间内完成。
  • 平衡二叉树，适用于以查找为主，很少插入、删除的场景（实际也很少使用了）。
  • 红黑树，适用于频繁插入、删除的场景，实用性更强。

红黑树的定义：

  • 红黑树是二叉排序树
  • 每个节点或是红色，或是黑色
  • 根节点是黑色的
  • 叶节点（外部节点、NULL节点、失败节点）都是黑色的
    • 在红黑树中，当我们提到叶子节点的时候，通常是指失败节点（又称“NULL节点”、“外部节点”）
  • 不存在两个相邻的红节点（即红节点的父节点和孩子节点都是黑色的）
  • 对每个节点，从该节点到任一叶子节点的简单路径上，所含黑节点的数目相同
46-116.png
46-116.png

粗略地用一个结构体定义一下：

struct RBnode {
  int key;
  RBnode* parent;
  RBnode* lchild;
  RBnode* rchild;
  int color;
};

补充概念，“黑高”：

46-117.png
46-117.png

红黑树的性质：

  1. 从根节点到叶子节点的最长路径不大于最短路径的 2 倍
  2. 有 n 个内部节点（n 个关键字）的红黑树高度 $h\leqslant 2 \log _2(n+1)$
    • 由此得到红黑树的查找操作的时间复杂度为 $O(\log _2n)$

红黑树的查找：与 BST、AVL 相同，从根出发，左小右大，若查找到一个空叶子节点，则查找失败。

关于红黑树的更多内容，由于考纲不考，时间有限，我就放过自己了，下面只给出一些链接：

B 树

一、引入

能否将二叉查找树（BST）拓展为 m 叉查找树？

46-118.png
46-118.png

如何保证查找效率：

46-119.png
46-119.png

二、定义

46-120.png
46-120.png

三、高度

46-121.png
46-121.png

B 树的插入、删除

一、插入

46-122.png
46-122.png

二、删除

46-123.png
46-123.png

续图：

46-124.png
46-124.png

B+ 树

定义：

46-125.png
46-125.png

查找：略。

注意点：在 B+ 树中，叶节点包含信息，所有非叶子节点仅起索引作用。

B+树 和 B树 的一点区别：

46-126.png
46-126.png

B+树的优点和应用场景：

46-127.png
46-127.png

总结：

46-128.png
46-128.png

散列查找

一睹芳容：

46-129.png
46-129.png

查找操作：略。

ASL 分析、装填因子：

46-130.png
46-130.png

设计散列函数的方法（模质数）：

46-131.png
46-131.png

其他方法：

46-132.png
46-132.png

处理冲突的另一种方法，开放定址法：

46-133.png
46-133.png

线性探测法（实际没用，考试爱考）：

46-134.png
46-134.png

平方探测法：

46-135.png
46-135.png

伪随机序列法：

46-136.png
46-136.png

处理冲突的另另一种方法，再散列法（再哈希法）： 除了原始的散列函数 H(key) 之外，多准备几个散列函数。当散列函数冲突时，用下一个散列函数计算一个新地址，直到不冲突为止：

$$H_i=RH_i(Key) \quad i=1,2,3, \cdots k$$

以上总结：

46-137.png
46-137.png

小优化：

46-138.png
46-138.png

排序

46-139.png
46-139.png

插入排序

算法思想：每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中，直到全部记录插入完成。

46-140.png
46-140.png

代码实现：

// 直接插入排序
void insertSort(int A[], int n){
  int i, j, temp;
  for(i=1; i<n; i++){
    if(A[i]<A[i-1]){
      temp = A[i];
      for(j=i-1; j>=0 && A[j]>temp; j--){
        A[j+1] = A[j];
      }
      A[j+1] = temp;
    }
  }
}

代码实现（带哨兵）：

46-141.png
46-141.png

最好时间复杂度：$O(n)$ 最坏时间复杂度：$O(n^2)$ 平均时间复杂度：$O(n^2)$ 算法稳定性（这里指，排序稳定性）：稳定

一个小优化：

46-142.png
46-142.png

注意： 上图中王道的代码是有 bug 的，实际中不能这么写。

补充——对链表进行插入排序： 移动元素的次数变少了，但是关键字对比的次数依然是 $O(n^2)$ 数量级，整体来看时间复杂度依然是 $O(n^2)$ .

希尔排序（Shell Sort）

算法思想来源：

46-143.png
46-143.png

图示：

46-144.png
46-144.png

代码实现：

// 希尔排序
void shellSort(int A[], int n){
  int d, i, j;
  // A[0] 只是暂存单元，不是哨兵。当 j<=0 时，插入位置已到
  for(d=n/2; d>=1; d=d/2)  // 步长变化
    for(i=d+1; i<=n; i++)
      if(A[i]<A[i-d]){
        A[0] = A[i];
        for(j=i-d; j>0 && A[0]<A[j]; j-=d)
          A[j+d] = A[j];
        A[j+d] = A[0];
      }
}

注意上面代码中，每次让i++，也就是轮流地切换着来处理不同的几个子表。下图选取几个关键时刻展示：

46-145.png
46-145.png

空间复杂度：$O(1)$ .

时间复杂度：

  • 和增量序列 $d_1,d_2,d_3,\cdots $ 的选择有关
  • 目前无法用数学手段证明确切的时间复杂度
  • 最坏时间复杂度为 $O(n^2)$ ，如该算法退化为插入排序时
  • 当 n 在某个范围时，可达到 $O(n^{1.3})$ .

希尔排序仅适用于顺序表，不适用于链表。

稳定性：

46-146.png
46-146.png

冒泡排序

若某一趟排序没有发生“交换”，说明此时已经整体有序。

46-147.png
46-147.png

冒泡排序适用于链表。

快速排序

算法思想：

46-148.png
46-148.png

代码实现：

void quickSort(int A[], int low, int high){
  if(low<high){
    int pivotPos = Partition(A, low, high); // 划分
    quickSort(A, low, pivotPos-1);
    quickSort(A, pivotPos+1, high);
  }
}

int Partition(int A[], int low, int high){
  int pivot = A[low];  // 第一个元素作为枢轴
  while(low<high){
    while(low<high && A[high]>=pivot) high--;
    A[low] = A[high];
    while(low<high && A[low]<=pivot) low++;
    A[high] = A[low];
  }
  A[low] = pivot;  // 枢轴元素放到最终位置
  return low;
}

性能分析：

46-149.png
46-149.png

快速排序不稳定。

一个应试的小疑惑：

46-150.png
46-150.png

简单选择排序

46-151.png
46-151.png

简单选择排序既可以用于顺序表，也可以用于链表。

堆排序

前置知识：

46-152.png
46-152.png

大根堆的建立：

46-153.png
46-153.png

建立大根堆的代码： （此处代码的动画演示参见王道视频_大根堆的建立）

// 建立大根堆
void build_maxHeap(int A[], int len){
  for(int i=len/2; i>0; i--)
    headAdjust(A, i, len);
}

// 将以 k 为根的子树调整为大根堆
void headAdjust(int A[], int k, int len){
  A[0] = A[k]; // A[0] 暂存子树的根节点
  for(int i=2*k; i<=len; i*=2){
    if(i<len && A[i]<A[i+1]) i++; // 选取 key 较大的子节点的下标
    if(A[0]>=A[i]) break;
    else {
      A[k] = A[i];
      k = i;
    }
  }
  A[k] = A[0];
}

基于大根堆进行排序：

46-154.png
46-154.png

基于大根堆进行排序（代码）：

void build_maxHeap(int A[], int len);

void headAdjust(int A[], int k, int len);

void heapSort(int A[], int len){
  build_maxHeap(A, len);
  for(int i=len; i>1; i--){
    swap(A[i], A[1]);
    headAdjust(A, 1, i-1);
  }
}

效率分析：

46-155.png
46-155.png

堆的插入、删除

46-156.png
46-156.png

归并排序

46-157.png
46-157.png

代码实现：

int *B = (int*) malloc(n*sizeof(int)); // 辅助数组

// A[low...mid] 和 A[mid+1...high] 各自有序，将两个部分归并
void merge(int A[], int low, int mid, int high){
  int i, j, k;
  for(k=low; k<=high; k++)
    B[k] = A[k];
  for(i=low,j=mid+1,k=i; i<=mid&&j<=high; k++){
    if(B[i]<=B[j])  // 保证了稳定性
      A[k] = B[i++];
    else 
      A[k] = B[j++];
  }
  while(i<=mid) A[k++] = B[i++];
  while(j<=high) A[k++] = B[j++];
}

void mergeSort(int A[], int low, int high){
  if(low<high){
    int mid = (low+high)/2;
    mergeSort(A, low, mid);
    mergeSort(A, mid+1, high);
    merge(A, low, mid, high);
  }
}

性能分析：

46-158.png
46-158.png

基数排序（Radix Sort）

46-159.png
46-159.png

效率分析：

46-160.png
46-160.png

应用：

46-161.png
46-161.png

完结撒花

外部排序考试不要求掌握，前面的区域，以后再来探索吧：

https://www.bilibili.com/video/BV1b7411N798/?p=96