基本概念

数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别(二进制0和1)和处理的符号的集合。数据是计算机程序加工的原料

数据元素是数据的基本单位，通常作为一个整体进行考虑和处理

一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位

结构是各个元素之间的关系

数据结构是相互之间存在一种或多种特定关系的数据元素的集合

数据对象是具有相同性质的数据元素的集合，是数据的一个子集

存储结构

集合：各个元素同属一个集合，别无其他关系

线性结构：数据元素之间是一对一的关系，除了第一个元素，所有元素都有前置元素；除了最后一个元素，所有元素都有后置元素

树形结构：数据元素之间是一对多的关系

图结构：数据元素之间是多对多的关系

顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元，元素之间的关系由存储单元的邻接关系来提现

链式存储：逻辑上相邻的元素在物理位置上可以不相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系

索引存储：在存储元素信息的同时，还建立附加的索引表。索引表中的每项称为索引项，索引项的一般形式是（关键字，地址）

散列存储：根据元素的关键字直接计算出该元素的存储地址，又称哈希（Hash）存储

算法

程序 = 数据结构 + 算法

数据结构：如何用数据正确地描述现实世界的问题，并存入计算机

算法：如何高效地处理这些数据，以解决实际问题

算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个操作

特性

• 有穷性。一个算法必须总在有穷步之后结束，且每一步都可在有穷时间内完成。

  • 注：算法必须是有穷的，而程序可以是无穷的

• 确定性。算法中每条指令必须有确切的含义，对于相同的输入只能得出相同的输出

• 可行性。算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。

• 输入。一个算法有零个或多个输入，这些输入取自某个特定的对象的集合

• 输出。一个算法有一个或多个输出，这些输出是与输入有着特定关系的量

度量

时间复杂度

如果我们想统计一种功能或者一种算法的使用时间，一般都称这里的时间是：时间复杂度

那么，通常计算这个时间，都是让算法先运行，事后统计运行时间

但是这种方案存在一些问题

• 和机器性能有关，越好的机器处理速度越快
• 和编程语言有关，越高级的语言执行效率越低
• 和编译程序产生的机器指令质量有关
• 有些算法是不能事后再统计的，如：导弹控制算法

算法的时间复杂度，通常是通过事前预估算法时间开销T(n)与问题规模n的关系(T表示“time”)

时间复杂度可以只考虑阶数高的部分

加法规则

多项相加，只保留最高阶的项，且系数变为1，譬如O(n) + O(1)，那么只会保留O(n)

常见数量集(从左到右依次递增)

三种复杂度

• 最坏时间复杂度：考虑输入数据“最坏”的情况
• 平均时间复杂度：考虑所有输入数据都等概率出现的情况
• 最好时间复杂度：考虑输入数据“最好”的情况

通常只考虑最坏时间复杂度和平均时间复杂度的情况

空间复杂度

无论问题规模怎么变，算法运行所需的内存空间都是固定的常量，算法空间复杂度为S(n) = O(1)

注：S表示“Space”

表

线性表

定义：数据结构

基本操作：运算

注：数据结构三要素--逻辑结构、数据的运算、存储结构（物理结构） 存储结构不同，运算的实现方式不同

定义

线性表是具有相同(每个数据元素所占空间一样大)数据类型的n(n>=0)个数据元素的有限序列(有次序)，其中n为表长，当n=0时线性表是一个空表。若用L命名线性表，则一般表示为->L={a1,a2,ai,ai+1,...,an}

几个概念：

ai是线性表中的“第i个”元素线性表中的位序

a1是表头元素，an是表尾元素

除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继

基本操作

InitList(&L)：初始化表。构造一个空的线性表L，分配内存空间

DestroyList(&L)：销毁操作。销毁线性表，并释放线性表L所占用的内存空间(从无到有，从有到无)

ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e

ListDelete(&L,i,&e)：删除操作。删除表L中的第i个位置的元素，并用e返回删除元素的值

LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素

GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值

其他常用操作：

Length(L)：求表长。返回线性表L的长度，即L中数据元素的个数

PrintList(L)：输出操作。按前后顺序输出线性表L的所有元素值

Empty(L)：判空操作。若L为空表，则返回true，否则返回false

顺序表

定义

线性表是具有相同(每个数据元素所占空间一样大)数据类型的n(n>=0)个数据元素的有限序列

顺序表--用顺序存储的方式实现线性表顺序存储

把逻辑相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来提现

通常来说，元素位置一般这样计算：

LOC->起始位置

n->第n个数

size->数据元素大小

第n个值的位置->LOC(L) + (n-1) * size

动态分配

声明结构体及头文件

#include <stdlib.h>
#define InitSize 10    // 默认的最大长度
typedef struct{
    // 指示动态分配数组的指针,这里的int可以改为任意的elementType，当然，后面对应的参数也需要同步修改
    int *data;    
    int MaxSize;    // 顺序表最大容量
    int length;        // 顺序表的当前长度
}SeqList;

初始化列表

void InitList(SeqList &L){
    // 用malloc 函数申请一片连续的存储空间
    // 初始化容量*类型大小 = 总空间
    L.data = (int *)malloc(InitSize*sizeof(int));
    // 声明数组长度
    L.length = 0;
    // 声明最大容量
    L.MaxSize = InitSize;
}

增加动态数组的长度

void IncreaseSize(SeqList &L,int len){
    // 将旧数据copy
    int *p = L.data;
    //  开辟新空间
    L.data = (int *)malloc((L.MaxSize+len)*sizeof(int));
    for (int i=0;i < L.length;i++){
        // 将数据复制到新区域
        L.data[i] = p[i]
    }
    L.MaxSize = L.MaxSize + len;    // 将顺序表最大长度增加len
    free(p);    // 释放旧空间
}

main函数启动

int main(){
    SeqList L;    //声明顺序表
    InitList(L);    //初始化顺序表
    // 插入元素...
    IncreaseSize(L, 5)
    return 0;
}

特点

1. 随机访问,即可以在O(1)时间内找到第i个元素
2. 存储密度高,每个节点只存储数据元素
3. 拓展容量不方便(即便采用动态分配的方式实现,拓展长度的时间复杂度也比较高)
4. 插入、删除操作不方便。需要移动大量元素

基本操作

插入

ListInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素e

这里采用静态分配方式实现的顺序表

静态分配是指在程序编译时，变量或数据结构所需要的内存空间就已经确定，并在程序运行期间保持不变

#define MaxSize 10    // 定义最大长度
typedef struct{
    ElemType data[MaxSize];    // 用静态的“数组”存放数据元素
    int length;    // 顺序表的长度
}SqList;    // 顺序表的类型定义

具体操作

void ListInsert(SqList &L,int i,int e){
    for(int j=L.length;j>=i;j--)    // 将第i个元素及之后的元素后移
        L.data[j]=L.data[j-1]
    L.data[i-1]=e;    // 在位置i处放入e
    L.length++;    // 长度+1
}

假设数组L内有元素{1,2,3},希望在第2个位置上插入4

那么，当前操作将会先让数组后移，若位置为2，则在索引1的位置上赋值，因为具体数据已经后移了，所以可以直接放入{1,4,2,3},再将长度+1

但是这种代码有一定的问题，比如元素满了，索引错误等，这里给出一个相对来说比较好的示例

bool ListInsert(SqList &L,int i,int e){
    if (i < 1|| i > L.length+1)    // 判断i的范围是否有效
        return false;
    if (L.length>=MaxSize)    // 查看当前存储空间是否已满
        return false;
    for(int j=L.length;j>=i;j--)    // 元素后移
        L.data[j]=L.data[j-1]
    L.data[i-1]=e;    // 放入e
    L.length++;    // 长度+1
    return true;
}

好的算法,应该具有健壮性.能够处理异常情况,并给使用者反馈

删除

ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值

bool ListDelete(SqList &L,int i,int &e){
    if (i < 1 || i>L.length)    // 判断i的范围是否有效
        return false;
    e=L.data[i-1]    // 将被删除的元素赋值给e
    for(int j=i;j<L.length;j++)    // 将第i个位置后的元素前移
        L.data[j-1]=L.data[j];
    L.length--;    //长度-1
    return true;
}

假设数组L中有元素{1,2,3},要被删除的是第二个元素，那么e则得到了L.data[1]，则是2

将第i个位置后的元素后移，则是2后面的元素前移

L.data[1]=Ldata[2],所以3移动到2的位置上，实现删除

查找

静态分配及动态分配

GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值

ElemType GetElem(SqList L,int i){
    return L.data[i-1];
}

LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素

// 在顺序表L中查找第一个元素值等于e的元素，并返回其位序
int LocateElem(SeqList L,int e){
    for(int i=0;i<L.length;i++)
        return i+1;
    return 0;
}

链表

单链表

存储结构图如下

struct LNode{    // 定义单链表结点类型
    ElemType data;    // 每个节点存放一个数据元素
    struct LNode *next;    // 指针指向下一个节点
}

• LNode：结点
• data：数据域
• next：指针域

struct LNode *p = (struct LNode*)malloc(sizeof(struct LNode)); 增加一个新的结点:在内存中申请一个结点所需空间,并用指针p指向这个结点

typedef 是 可以将某些类型改名的一种方式

通常typedef 类型 名称->譬如typedef int zhengshu，我们就可以使用zhengshu a = 1;来声明一个整数

那么我们也可以typedef struct LNode LNode、typedef struct LNode *LinkList

此时，要表示一个单链表时，只需声明一个头指针L，指向单链表的第一个节点

LNode * L->声明一个指向单链表第一个节点的指针

LinkList L->声明一个指向单链表第一个节点的指针(代码可读性更强)

强调这是一个单链表 -->使用LinkList

强调这是一个结点 -->使用LNode*

不带头节点

typedef struct LNode{    // 定义单链表节点类型
    ElemType data;    // 每个节点存放一个数据元素
    struct LNode *next;    //指针指向下一个节点
}LNode,*LinkList

//初始化一个空的单链表
bool InitList(LinkList &L){
    L = NULL;    // 空表，暂时还没有任何节点(防止脏数据)
    return true;
}

void test(){
    LinkList L;    //声明一个指向单链表的指针(注意，此处并没有创建一个结点)
    //初始化一个空表
    InitList(L);
}

// 判断单链表是否为空
bool Empty(LinkList L){
    return (L==NULL);
}

带头节点

typedef struct LNode{    // 定义单链表节点类型
    ElemType data;    // 每个节点存放一个数据元素
    struct LNode *next;    //指针指向下一个节点
}LNode,*LinkList

//初始化一个单链表(带头节点)
bool InitList(LinkList &L){
    L = (LNode *) malloc(sizeof(LNode));    //分配一个头节点
    if (L == NULL)
        return false;    //内存不足，分配失败
    L->next = NULL;    //头节点后暂无节点
    return true;
}

void test(){
    LinkList L;    //声明一个指向单链表的指针(注意，此处并没有创建一个结点)
    //初始化一个空表
    InitList(L);
}

插入

ListInsert(&L,i,e)：插入操作[携带头节点]。在表L中的第i个位置(找到第i-1个结点，将新结点插入其后)上插入指定元素e

定义单链表

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

具体实现

// 在第i个位置插入元素e(带头结点)
bool ListInsert(LinkList &L,int i,ElemType e){
    if (i < 1)    // 如果插入位置不正确，结束，插入位置由1开始
        return false;
    LNode *p;    // 指针p指向当前扫描到的结点
    int j=0;    // 当前p指向的是第几个结点
    p = L;    // L指向头结点，头结点是第0个结点(不存数据)
    while(p != NULL && j < i-1){    // 循环找到 i - 1个结点
        // 如果i = 1，说明插在表头，不进入循环
        // 如果i = 2，说明插入在第二个结点后
        // 所以p向下移动，结点位置变更
        p = p->next;
        j++;
    }
    // 如果i = 2，说明p此时在1的位置
    // 如果节点元素只有5个,但插入位置在7，此时p == NULL，i值不合法
    /*当p 在 第五个元素时，p->next就是NULL了
    我们找到的通常是i-1的位置
    这样就可以在最后一个元素的next处添加新元素了*/
    if (p == NULL)
        return false;    // i值不合法
    LNode *s = (LNode *)malloc(sizeof(LNode));    // 开辟空间
    s->data = e;    // 添加数据
    s->next=p->next;    // 让s.next -> p.next
    p->next = s;
    return true;
}

详细说明该代码过程，并配图

LNode *s = (LNode *)malloc(sizeof(LNode));    // 开辟空间
s->data = e;    // 添加数据
s->next=p->next;    // 让s.next -> p.next
p->next = s;
return true;

假设在i = 1添加 那么s.next -> p.next，p此时是头结点，p.next说明p.next = 第一个结点 s.next -> 第一个结点,s去指向了第一个结点，s此时可以算是第一个结点，而原第一个结点变为第二个结点 p.next -> s，此时头结点指向了第一个结点，第一个结点s.next->第二个结点 此时连接成功 i = other时也是同理，这里就不一一举例了，具体可看下图所示

ListInsert(&L,i,e):插入操作.在表L中的第i个位置(找到第i-1个结点，将新结点插入其后)上插入指定元素e

由于不存在头结点(第0个结点)因此i=1时需要特殊处理

结构体声明与上述一致,这里就不再赘述了

以下是具体代码实现

bool ListInsert(LinkList &L,int i,ElemType e){
    if (i < 1)    // 有效性判断
        return false;
    if(i == 1){
        // 由于没有头结点，第一个结点操作与其他结点操作不同
        LNode *s = (LNode *)malloc(sizeof(LNode));
        s->data = e;
        s->next = L;    
        L = s;    // 变为最新结点
        return true;
    }
    LNode *p;    // 指针p指向当前扫描到的结点
    int j = 1;    // 当前p指向第几个结点
    p = L;    // p指向第一个结点(注意：不是头结点)
    while(p!=NULL && j < i-1){
        p=p->next;
        j++;
    }
    if (p == NULL)
        return false;    // 不合法
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next=p->next;
    p->next;s;
    return true;
}

只有第一个结点有差别

前插操作

如果我们想在某个结点前插入一个结点,该怎么做呢?

直接贴代码

// 在p结点前插入元素e
bool InsertPriorNode(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;
}

详细介绍此处的内容

s->next=p->next;
 p->next=s;
 s->data=p->data;
 p->data=e;
 return true;

将s的下一个结点指向p的下一个结点，此时s就连接了p的下一个结点，p去指向了s

具体情况如下 p -> s -> p.next

此时已经互连了,想实现前插操作,就将两边的数据互换

p.data = s.data,s.data = p.data，也就意味着s -> p -> p.next

这样的时间复杂度是O(1)

删除

ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置(找到第i-1个结点，将其指针指向第i+1结点，并释放第i个结点)的元素，并用e返回删除元素的值

bool ListDelete(LinkList &L,int i,ElemType &e){
    if (i < 1)
        return false;
    LNode *p;    // 执行p扫描到的结点
    int j = 0;    //当前p指向的是第几个结点
    p = L;    //L指向头结点，头结点是第0个结点(不存数据)
    while (p != NULL && j < i-1){
        // 直到找到i-1个结点
        p = p->next;
        j++;
    }
    if (p==NULL)
        return false;    // i值不合法
    if (p->next == NULL)
        return false;    // i - 1个结点后无其他结点
    LNode *q = p->next;    //q指向被删除的结点
    e = q->data;    // 获取值
    p->next = q->next;    // 结点断开(删除)
    free(q);    // 释放结点
    return true;
}

删除指定结点p

bool DeleteNode(LNode *p){
    if (p==NULL)
        return false;
    LNode *q = p->next;    // 令q指向p的后继结点
    p->data = p -> next -> data    // 与后继结点交换数据域
    p->next = q -> next;    // 断开结点
    free(q);
    return true;
}

譬如想删除p，那么我们让q指向p->next

p的数据变成p下一个节点的数据，p的下一个节点，变成q的下一个节点

因为数据交换了，相当于p成了下一个节点，再让p去指向之前的q，因为q是p的下一个节点

那么q的下一个节点，就是如今p的next了，此时原先的p就被删除了

则q -> p.next，p.data = p.next.data,p.next = q.next

如果p是最后一个节点，此时只能从表头开始寻找，不然会出现问题

因为p->next->data会出现问题，这里会有NULL.data！！！

查找

本节仅探讨带头结点的情况

按位查找

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

按值查找

LNode * LocateElem(LinkList L,ElemType e){
    LNode *p = L->next;    // 获取第一个结点
    while(p != NULL && p->data != e)    // 当p不为空并且p的数据不为查找值时
        p = p->next;    // 向下查找
    return p;
}

建立

尾插法初始化带头结点的单链表

LinkList List_TailInsert(LinkList &L){    // 正向建立单链表
    int x;    // 设ElemType为整型
        L=(LinkList)malloc(sizeof(LNode));    // 建立投结点
    LNode *s,*r = L;    // r为表尾指针,s为新结点
    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;
}

举个栗子：

刚开始初始化的情况如下：r,s(头结点) -> NULL

假设第一次要输入10

• r(头结点) -> s(10)
• 头结点 -> r,s(10)

第二次输入15

• 头结点 -> r,s(10) -> s(15)
• 头结点 -> s(10) -> r,s(15)

第三次输入20

• 头结点 -> s(10) -> r,s(15) -> s(20)
• 头结点 -> s(10) -> s(15) -> r,s(20)

第四次输入9999结束

头结点 -> s(10) -> s(15) -> r,s(20) -> NULL

return L -> end;

头插法初始化带头结点的单链表

LinkList List_HeadInsert(LinkList &L){    // 逆向建立单链表
    LNode *s;
    int x;
    L=(LinkList)malloc(sizeof(LNode));    // 创建头结点
    L->next=NULL;    // 初始化为空链表
    scanf("%d",&x);    // 输入结点的值
    while(x!=9999){
        s=(LNode*)malloc(sizeof(LNode));    // 创建新结点
        s->data=x;
        s->next=L->next;
        L->next=s;
        scanf("%d",&x);
    }
    return L;
}

这里就简单一些了

s=(LNode*)malloc(sizeof(LNode));    // 创建新结点
s->data=x;
s->next=L->next;
L->next=s;
scanf("%d",&x);

具体叙述一下这里的情况

1. 创建新结点
2. 新结点指向头结点的下一个数据，即第一个结点
3. 头结点指向新结点

其实就是在第一个结点前，让新结点->next 指向 第一个结点，那么新结点就在第一个位置了，再让头结点->next指向新结点就行了

双链表

带头结点

构建结构体

typedef struct DNode{
    ElemType data;
    struct DNode *prior,*next;
}DNode,*DLinkList;

DNode * = DLinkList

初始化双链表

bool InitDLinkList(DLinklist &L){
    L = (DNode *)malloc(sizeof(DNode));    // 分配一个头结点
    if (L==NULL)
        return false;
    L->prior = NULL;    // 头结点的prior永远指向NULL
     L->next = NULL;    // 头结点之后暂时没有结点
    return true;
}

插入

// 在p结点之后插入s结点
bool InsertNextDNode(DNode *p,DNode *s){
    if (p == NULL || s == NULL)    // 非法参数
        return false;
    s->next=p->next;
    if (p->next != NULL)    // 如果p结点存在后继结点
        p->next->prior=s;
    s->prior=p;
    p->next=s;
    return true
}

先让s的下一个结点去指向p原先的下一个结点，即s 的下一个结点为 p.next

如果p存在后继结点，那么让p的后继结点的前结点为s，如果不存在，说明p是最后一个结点，则无需指向s

最后让s的前结点变为p，p的后继结点变为s

删除

// 删除p结点的后继结点
bool DeleteNextDNode(DNode *p){
    if (p==NULL)
        return false;
     DNode *q = p->next;    // 找到p的后继结点q
     if (q==NULL)
         return false;    // p没有后继
     p->next=q->next;    // p去跳过q这个结点
     if(q->next!=NULL)    // q不是最后一个结点
         q->next->prior=p;    // 那么q的下一个结点的上一个指向为p
     free(q);    // 释放空间
     return true;
}

遍历

查找等其他操作，都建立在遍历的基础上

后向遍历

while (p!=NULL){
    p=p->next
}

前向遍历

while (p!=NULL){
    p=p->prior
}

前向遍历(跳过头结点)

只要prior不为空，说明还没到头结点，如果为空，说明已经是头结点了，因为头结点的prior==NULL

while (p->prior!=NULL){
    p=p->prior
}

循环单链表

结构定义

typedef struct LNode{    // 订阅单链表结点类型
    ElemType data;    // 元素
    struct LNode *next;    // 下一个结点
}LNode, *LinkList;

初始化循环单链表

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

判断链表是否为空

bool Empty(LinkList L){
    if (L->next == L)
        return true;
    else
        return false;
}

如果只有L自己，说明是空

判断结点p是否为循环单链表的表尾结点

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

循环双链表

相当于闭环的双链表

表头结点的prior指向表尾结点；

表尾结点的next指向头结点；

插入

// 在p结点之后插入s结点
bool InsertNextDNode(DNode *p,DNode *s){
    s->next=p->next;    // 将s插入到p之后
     p->next->prior=s;    
     s->prior=p;
     p->next=s;
}

举例说明(如图所示)：

最麻烦的只有上面两句

解释一下，s->next=p->next，其实就是s的下一个结点是p的下一个结点，那么，s的下一个结点就拿到了p后面的值

p的下一个结点的上一个选择是s，其实一样的道理，因为p下一个结点只会有值，它是循环的链表

如果p是最后一个值，那么它的prior就是head，而head原先的prior是p，因为p是最后一个结点，也就是说，head替换了prior，将prior改为s，如果p不是最后一个值，那么其实就是将p的下一个结点的上一个结点的prior改为s，此时，s的下一个结点是p->next，p->next->prior是s，最后两行就是让p和s互相加一下线即可

删除

//删除p的后继结点q
p->next=q->next;
q->next->prior=p;
free(q);

p后面的结点直接跳过q，变成q后面的结点，q后面的结点的前置变为p，也就是跳过q，最后释放q

静态链表

静态链表：分配一整片连续的内存空间，各个结点集中安置

0号结点充当“头结点”

下一个结点的数组下标表示游标

游标为-1表示已经到达表尾，游标充当指针

#define MaxSize 10    // 静态链表的最大长度
typedef struct{    // 静态链表结构类型的定义
    ElemType data;    // 存储数据元素
    int next;    // 下一个元素的数组下标
}SLinkList[MaxSize];

等价于

#define MaxSize 10
struct Node{
    ElemType data;    
    int next;
}
typedef struct Node SLinkList[MaxSize]

typedef是别名的意思，如果我们声明SLinkList a;那么这里的a相当于Node a[MaxSize]的数组，有10个元素的结构体数组

查找：从头结点出发挨个往后遍历结点

插入位序为i的结点：

1. 找到一个空的结点，存入数据元素
2. 从头结点出发找到位序为i-1的结点
3. 修改新结点的next为-1
4. 修改i-1号结点的next

删除某个结点：

1. 从头结点出发找到前驱结点
2. 修改前驱结点的游标
3. 被删除结点next设为-2，即特殊数值充当空闲结点

静态链表：用数组方式实现的链表

栈

栈(Stack)是只允许在一端进行插入或删除操作的线性表

栈顶：允许插入和删除的一端

栈底：不允许插入和删除的一端

初始化

构建结构体

#define MaxSize 10    // 定义栈中元素的最大个数
typedef struct{
    ElemType data[MaxSize];    // 静态数组存放栈中元素
    int top;    // 栈顶指针
}SqStack;

初始化栈

void InitStack(SqStack &S){
    S.top=-1;
}

判断栈空

bool StackEmpty(SqStack S){
    return S.top==-1;
}

进栈

bool Push(SqStack &S,ElemType x){
    if (S.top == MaxSize-1)    // 栈满，报错
        return false;
    S.top = S.top + 1;
    S.data[S.top] = x;
    return true;
}

出栈

bool Pop(SqStack &S,ElemType &x){
    if (S.top==-1)
        return false;    // 栈空
    x=S.data[S.top];    // 栈顶元素先出栈
    S.top=S.top-1;    // 指针减1
    return true;
}

数据依然保存在内存中，但是在逻辑上删除了

读栈顶元素

bool GetTop(SqStack S,ElemType &x){
    if (S.top == -1)
        return false;
    x=S.data[S.top];
    return true;
}

链式存储实现

添加结点

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

队列

队列（Queue)是只允许在一端进行插入，在另一端删除的线性表

特点：先进入队列的元素先出队列（先进先出FIFO）

队头：允许删除的一端

队尾：允许插入的一端

顺序实现

初始化

#define MaxSize 10
typedef struct{
    ElemType data[MaxSize];    // 用静态数组存放队列元素
    int front,rear;    // 队头指针和队尾指针
}SqQueue;

// 初始化队列
void InitQueue(Squeue &Q){
    // 初始化时 队头队尾指针指向0
    Q.rear=Q.front=0;
}

void testQueue(){
    // 声明一个队列(顺序存储)
    SqQueue Q;
    InitQueue(Q);
}

// 判断队列是否为空
bool QueueEmpty(SqQueue Q){
    if (Q.rear==Q.front)
        return true;
    else 
        return false;
}

入队

bool EnQueue(SqQueue &Q,ElemType x){
    if ((Q.rear + 1) % MaxSize == Q.front)     // 判断队满
        return false;
    Q.data[Q.rear] = x;    // 新元素插入队尾
    Q.rear=(Q.rear + 1) % MaxSize;    // 队尾指针+1取模
}

通过模运算将存储空间在逻辑上变成了环状

举个栗子：假设有队列3个元素,那么我们模拟一下入队的效果

因为front和rear一开始都是在一个位置，那么通过该方法，先判断是否队满，那么队尾+1取余最大值3，结果是1，与front不同，所以队列未满，将元素插入队尾，并将队尾指针后移，此时rear是1

第二次也是同理，说说第三次，第三次时rear是2,rear + 1 取余3，结果为0，与front相同，说明队满

为什么只存了两个元素就队满呢，因为rear = front是判断队列是否为空的，若让rear = front，此时队列会为空，就不好做后续操作了，目前只能按照取余法，牺牲一个存储单位来判断

第二种方案，新加一个变量size，专门用来记录队列长度，入队size++，出队size--，当sizeMaxSize时队满，size0时队空

第三种方案，新加一个变量tag，用来标记是删除还是插入操作， 初始化时tag为0，每次删除操作成功后，都令tag=0，每次插入操作成功后，都令tag=1；队满条件：front rear && tag 1，因为只有插入操作，才可能导致队满，因为上一次是插入操作，而此时front rear，所以队满；队空条件：front rear && tag == 0，如果是删除操作，才可能导致队空，因为上一次是删除操作，所以队空

出队

// 出队（删除一个队头元素，并用x返回）
bool DeQueue(SQueue &Q,ElemType &x){
    if (Q.rear == Q.front)
        return false;    // 队空报错
    x=Q.data[Q.front];    // 获取队头元素
    Q.front = (Q.front + 1) % MaxSize;
}

举个栗子：假设有队列3个元素,那么我们模拟一下出队的效果

先判断是否为空，其实是队尾和队头相同时，我们假设队头为0，队尾为2，先进行一次出队看看，那么先判断队列，不为空，获取元素，front + 1，此时front为1

如果再获取一次，那么队头和队尾就相同了，所以我们进行一次入队操作，因为此时front = 1，rear = 2，那么判断rear + 1 取余 3，结果为0，与front不相同，说明此时队未满，那么2的位置插入一个元素，并且rear + 1是3，对MaxSize取余，循环回到0的位置，那么下一次若队列未满，也可继续进行入队操作

如果想获取队头元素，只需要移除出队操作中的Q.front = (Q.front + 1) % MaxSize;即可，不让队头元素后移

队列元素个数：(rear + MaxSize - front) % MaxSize

链式存储

初始化

typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}

typedef struct{
    LinkNode *front, * rear;
}LinkQueue;

// 初始化队列(带头结点)
void InitQueue(LinkQueue &Q){
    // 初始化时 front、rear都指向头结点
    Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
    Q.front ->next = NULL;
}

void testLinkQueue(){
    LinkQueue Q;    // 声明一个队列
    InitQueue(Q);    // 初始化队列
}

//判断队列是否为空
bool IsEmpty(LinkQueue Q){
    if(Q.front == Q.rear)
        return true;
    else
        return false;
}

不带头结点

// 初始化队列(不带头结点)
void InitQueue(LinkQueue &Q){
    // 初始化时 front、rear都指向NULL
    Q.front=NULL;
    Q.rear=NULL;
}

//判断队列是否为空(不带头结点)
bool IsEmpty(LinkQueue Q){
    if (Q.front == NULL)
        return true;
    else
        return false;
}

入队

// 新元素入队(带头结点)
void EnQueue(LinkQueue &Q,ElemType x){
    LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));
     s->data=x;
     s->next=NULL;
     Q.rear->next=s;    // 将新结点插入到rear之后
    Q.rear=s;    // 修改表尾指针为最新值
}

// 新元素入队(不带头结点)
void EnQueue(LinkQueue &Q,ElemType x){
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
     s->data=x;
     s->next=NULL;
     if (Q.front == NULL){    // 因为不带头结点的空队列，rear和front都是默认指向NULL的
         Q.front = s;    // 所以第一个元素需要特别处理，让front和rear同时指向第一个元素
         Q.rear = s;
     }
     else{
         Q.rear->next = s;    // 新结点插入到rear后
         Q.rear = s;    // 修改rear为最新结点
     }
}

出队

// 队头元素出队(不带头结点)
bool DeQueue(LinkQueue &Q,ElemType &x){
    if (Q.front == Q.rear)
        return false;    // 空队列
    LinkNode * p = Q.front->next;    // 因为带头结点，所以头结点的下一个结点就是第一个元素
    x=p->data;    // 返回队头元素
    Q.front->next=p->next;    // 修改头结点的next指针
     if (Q.rear==p)
         Q.rear = Q.front;    // 如果是最后一个结点，那么修改rear结点
     // 此时rear == front，队列为空
     free(p);    // 释放空间
     return true;
}

// 队头元素出队(不带头结点)
bool DeQueue(LinkQueue &Q,ElemType &x){
    if (Q.front == NULL)
        return false;    // 空队列
    LinkNode *p = Q.front;    // 指向此次出队的结点
    x=p->data;
    Q.front=p->next;    // 修改front，如果是第一个结点则回到NULL，如果后续有结点则指向后续结点
    if (Q.rear == p){    // 最后一个结点出队，front->rear->NULL
        Q.front = NULL;
        Q.rear = NULL;
    }
    free(p);
    return true;
}

双端队列

双端队列：只允许从两端插入、两端删除的线性表

输入受限的双端队列：只允许从一端插入、两端删除的线性表

输出受限的双端队列：只允许从两端插入、一端删除的线性表

考点：判断输出序列合法性

若数据元素输入序列为1,2,3,4，则哪些输出序列是合法的，哪些是非法的

栈是先进后出

栈中合法的序列，双端队列中也一定合法

括号匹配

括号匹配是匹配两边是否有对应存在的括号，像这种( ( ) )，就是可以匹配成功的，通常使用栈来实现该特性

代码详情

#define MaxSize 10    // 订阅栈中元素的最大个数
typedef struct{
    char data[MaxSize];    // 静态数组存放栈中元素
    int top;    // 栈顶指针
}SqStack;
// 初始化栈
void InitStack(SqStack &S)
// 判断栈是否为空
void StackEmpty(SqStack S)
// 新元素入栈
bool Push(SqStack &S,char x)
// 栈顶元素出栈，用x返回
bool Pop(SqStack &S,char &x)
bool bracketCheck(char str[],int length){
    SqStack S;
    InitStack(S);    // 初始化栈
    for(int i=0;i<length;i++){    // 遍历括号数组
        if (str[i] == '(' || str[i] == '[' || str[i] == '{'){
            Push(S,str[i]);    // 扫描到左括号，入栈
        }
        else{
            if (StackEmpty(S))    // 扫描到右括号且栈空
                return false;
            char topElem;
            Pop(S,topElem);    // 不为空，栈顶元素出栈
            if (str[i] == ')' && topElem != '(')
                return false;
            if (str[i] == ']' && topElem != '[')
                return false;
            if (str[i] == '}' && topElem != '{')
                return false;
        }
    }
    return StackEmpty(S);    // 检索完所有括号，栈空说明匹配成功
}

总结：

用栈实现括号匹配

依次扫描所有字符，遇到左括号入栈，遇到右括号则弹出栈顶元素检查是否匹配。

匹配失败的情况：

1. 左括号单个
2. 右括号单个
3. 左右括号不匹配

栈在表达式中的应用

中缀表达式：运算符在两个操作数中间，例如a+b

后缀表达式：运算符在两个操作数后面，例如ab+

前缀表达式：运算符在两个操作数前面，例如-ab

中缀转后缀的手算方法：

1. 确定中缀表达式中各个运算符的运算顺序
2. 选择下一个运算符，按照[左操作数 右操作数 运算符]的方式组合成一个新的操作数
3. 如果还有运算符没被处理，就继续2的操作

这里有两个中缀表达式转后缀的情况，我们发现有一个运算式却存在着两个结果，通常来说，因为运算顺序不唯一，因此对应的后缀表达式也不唯一

所以我们都会遵循左优先原则，只要左边的运算符可以运算，就优先算左边的，这就是左优先原则，比如我们看左式和右式，其实括号内和最右边的除法都可以先算，但是括号更靠近左边，所以优先算括号内的

摘自王道考研数据结构与算法的一句话：右边的没有错，只是不合适。就像你一样，你也没有错，只是你不合适

中缀表达式转后缀表达式（机算）

初始化一个栈，用于保存暂时还不能确定运算顺序的运算符

从左到右处理各个元素，直到末尾。可能遇到三种情况：

1. 遇到操作数。直接加入到后缀表达式
2. 遇到界限符。遇到“（”直接入栈；遇到“）”则依次弹出栈内运算符并加入后缀表达式，直到弹出“（”为止。注意“（”不加入后缀表达式
3. 遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到“（”或栈空则停止。之后再把当前运算符入栈。

按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式。

后缀表达式的手算方法

• 从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应运算，合体为一个操作数
• 注意：两个操作数的左右顺序

中缀转前缀的手算方法：

1. 确定中缀表达式中各个运算符的运算顺序
2. 选择下一个运算符，按照[运算符 左操作数 右操作数]的方式组合成一个新的操作数
3. 如果还有运算符没被处理，就继续②

右优先原则：只要右边的运算符能先计算，就优先算右边的

后缀表达式

用栈实现后缀表达式的计算：

1. 从左往右扫描下一个元素，直到处理完所有元素
2. 若扫描到操作数则压入栈，并回到①的操作；否则执行③
3. 若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到①

若表达式合法，则最后栈中只会留下一个元素，就是最终结果

前缀表达式

用栈实现前缀表达式的计算：

1. 从右往左扫描下一个元素，直到处理完所有元素
2. 若扫描到操作数则压入栈，并回到①，否则执行③
3. 若扫描到运算符，则弹出两个栈顶元素，执行相应操作，运算结果压回栈顶，回到①

中缀表达式

用栈实习中缀表达式的计算：

初始化两个栈，操作数栈和运算符栈

若扫描到操作数，压入操作数栈

若扫描到运算符或界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈（期间也会弹出运算符，每当弹出应该运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应运算，运算结果再压回操作数栈）

栈在递归中的应用

递归算法计算阶乘

// 计算正整数 n!
int factorial(int n){
    if (n==0 || n==1)
        return 1;
    else
        return n*factorial(n-1);
}
int main(){
    int x = factorial(10);
    return 0;
}

递归调用时，函数调用栈可称为“递归工作栈”

每进入一层递归，就将递归调用所需信息压入栈顶

每退出一层递归，就从栈顶弹出相应信息

举个栗子：比如最开始是main函数，main函数里调用func1，func1里调用func2，很显然它们是依次入栈的

main -> func1 -> func2，也就是说，最先从栈顶被释放的是func2

递归算法求斐波那契数列

int Fib(int n){
    if (n == 0)
        return 0;
    else if(n == 1)
        return 1;
    else
        return Fib(n-1)+Fib(n-2);
}
int main(){
    int x = Fib(4);
    return 0;
}

总结：

• 函数调用的特点：最后被调用的函数最先执行结束（LIFO）
• 函数调用时，需要用一个“函数调用栈”存储：
  1. 调用返回地址
  2. 实参
  3. 局部变量
• 递归调用时，函数调用栈可称为“递归工作栈”，每进入一层递归，就将递归调用所需信息压入栈顶，每退出一层递归，就从栈顶弹出相应信息
• 缺点：效率低，太多层递归可能会导致栈溢出：可能包含很多重复计算
• 可以自定义栈将递归算法改为非递归算法

特殊矩阵的压缩存储

一维数组

ElemType a[10]; // ElemType型一维数组

起始地址：LOC

各数组元素大小相同，且物理上连续存放。

数组元素a[i]的存放地址=LOC+i*sizeof(ElemType) (0<=i<=10)

二维数组

ElemType b[2] [4];

行优先存储：将数组数据一行一行的存

M行N列的二维数组b[M] [N]中，若按行优先存储，则b[i] [j]的存储地址=LOC+(i*N+j)*sizeof(ElemType)

这个公式是让初始地址去加上后续的数组字节来找到对应的行优先数组值

列优先存储：将数组数据一列一列的存

M行N列的二维数组b[M] [N]中，若按列优先存储，则b[i] [j]的存储地址=LOC+(j*M+i)*sizeof(ElemType)

对称矩阵

若n阶方阵[n×n的矩阵，行列数相同的矩阵]中任意一个元素aij都有aij=aji，则该矩阵为对称矩阵

策略：只存储主对角线+下三角区

按行优先原则将各元素存入一维数组

如果我们想获取压缩矩阵的某个值，那我们可以编写一个矩阵下标->一维数组下标的方法

简单解释一下这个公式，按照行优先原则，那么下三角区的行位置，第一行0个，第二行1个，第n行n-1个，以此类推

那么我们想计算出对应的位置，就要知道它大概在哪个位置，则1+2+3+4+n-1....(计算等差公式)而列的位置就是第几个了

数组下标就根据这个公式算，因为一维数组下标是从0开始，所以-1，矩阵下标无需-1

上三角算法其实也是类似的，也是列元素依次增加计算，最后加上行的位置

三角矩阵

下三角矩阵：除了主对角线和下三角区，其余的元素都相同

压缩存储策略：按行优先原则将橙色区元素存入一维数组中。并在最后一个位置存储常量c

下三角矩阵的下三角区及主对角线元素其实和对称矩阵没差别，但是上三角区的元素都是常量，并且只在最后一个位置存储这些相同的值，所以只需要找到最后一个位置，也就是一维数组的最后一个值

上三角矩阵：除了主对角线和上三角区，其余的元素都相同

第一行有n个元素，第二行有n-1个元素，如果我们需要找到第i个元素，就要拿到i-1行的空间，那么就该计算1->i-1个行的位置，那么如果我们想找到i-1个行的位置，此时就需要通过n-i+2的方式，因为找的是i-1的位置，所以i不能为1，i为1时这个就不成立了，因为i=1时，计算的就是第0行的空间了，很显然没有第0行

请不要疑惑，因为这里计算的是i-1个元素，也就是说，i=2时，计算的是第一行的空间，因为i=2计算的是i-1个行的空间，即第一行的空间！！！

并且最后需要加入j-i个元素，也就是行前面还需要多少的元素

我认为这里需要重点说明一下公式：n-i+2

我们需要知道每一行有几个元素

第一行：有n个元素

第二行：有n-1个元素

第i行有n-i+1个元素

那么，多出来的1从哪来的呢？

我们要计算的是到某一行的整体个数

则进行公式替换，因为i = i -1

故公式为：n - (i - 1) + 1 = n - i + 1 + 1 = n - i + 2

我们最后从逻辑上来解释

比如说，我们假设k = i - 1

如果说，我们想算第三行的元素，就得拿到前两行一共有多少个元素，再加进去，那么i - 1 = 2，公式的目的是计算任意k(i)行的元素个数，那么这里-1其实是一样的，-1更方便了，因为它直接就算出了前i行所需的个数，然后加入进去，就可以得出结果了

三对角矩阵

三对角矩阵，又称带状矩阵：

当|i-j| > 1时，有aij = 0(1<=i,j<=n)

什么意思呢，也就是说，行号-列号的绝对值大于1时，那么这个元素为0

如图所示

压缩存储策略：

按行优先(或列优先)原则，只存储带状部分

前i-1行共有3(i-1)-1个元素

解释一下这个公式

这个公式计算的是第i行开始前，我们存储了多少个元素

因为我们想计算第i个元素，就得跳过其前面的元素

除了第一行和最后一行是2个元素，其他都是3个元素

假设第1行到i-1行元素都是3个元素，那么前i行就是3i了，而前i-1行就是3(i-1)了

但是！第一行是个特例，所以我们需要从总数里减去1

因此，前i-1行的元素个数就是3*(i-1)-1

当i = 2时，第2行开始前的元素就是3*1 - 1 = 2，没问题，第一行的元素确实是2

当然这里的i = 1就不成立了，因为i = 1是第一行前的元素，这个计算是没有意义的

aij是i行第j - i + 2个元素

这个公式说明aij是它自己所在的这一行里，第几个被存储的非0元素

比如说，我们看第i行的非零元素，它们通常是a[i,i-1],a[i,i],a[i,i+1]

那么带入公式

• 列号是j = i - 1，代入公式(i-1) - i + 2 = 1，这是第一个
• 列号是j = i，代入公式i - i + 2 = 2，这是第二个
• 列号是j = i + 1，代入公式(i + 1) - i + 2 = 3，这是第三个

现在很显然，我们可以很清楚的知道，第aij个元素是第几个非0元素

aij是第2i+j-2个元素

这个公式是前面两个公式相加后的简化，目的是最终的位置在哪，因为第一个公式是计算前i-1行的元素，我们再加上它在列的位置，就知道它在哪了

(3(i - 1) - 1) + (j - i + 2)

= (3i - 3 - 1) + (j - i + 2)

= 3i - 4 + j - i + 2

= 2i +j -2

若已知数组下标k，如何得到i,j?【反向求解】

第k + 1个元素，在第几行？第几列

前i - 1行共3(i-1)-1个元素

前i行共3i-1个元素

[

3i-1计算的是第一行+其他i-1行的个数(除去第一行的总个数)

很显然其他i-1行是3(i-1)，为什么呢？

因为我们去除了第一行，其他的元素个数都是3，除最后一行

第一行是2个，那么相加即为3i - 3 + 2 = 3i - 1

]

显然，3(i-1)-1< k + 1 <= 3i-1

k会大于前i-1行的元素个数，并小于等于前i行的元素个数

把不等式解出来得i为下述公式

i=(k+2)/3 -> 向上取整 或 i = (k+1)/3+1 -> 向下取整

由k = 2i+j-3[该公式由上述推导]，得

j = k-2i+3

我们确认一下这里的元素，k是第k个元素，i是行，j是列

稀疏矩阵

稀疏矩阵：非零元素远远少于矩阵元素的个数

压缩存储策略：

顺序存储--三元组<行，列，值>

方法二：十字链表法

一图胜千言

定义两个指针数组，分别指向每一列和每一行

串

串，即字符串（String）是由零个或多个字符组成的有限序列。一般记为

S='a1a2a3......an'(n>=0)

其中S是串名，单引号括起来的字符序列是串的值；

ai可以是字母、数字或其他字符；

串中字符的个数n称为串的长度

n=0时的串称为空串（用空集表示）

例：

S=“HelloWorld”[注：有的地方用双引号，有的地方用单引号]

T=‘Phone’

子串：串中任意个连续的字符组成的字序列。

Eg：'Pho'，'one'是串T的子串

主串：包含子串的串。

Eg：T是'Pho'的主串

字符在主串中的位置：字符在串中的序号

Eg：h在T中的位置是2（第一次出现）

子串在主串中的位置：子串的第一个字符在主串中的位置

Eg：'hone'在T中的位置为2，其实就是子串首个字符出现的位置

注意：位序从1开始，而不是从0

当然，空串和空格串是不一样的

M=''，M是空串

N=' 'N是由三个空格字符组成的空格串，每个空格字符占1B

串是一种特殊的线性表，数据元素之间呈线性关系

串的数据对象限定为字符集（如中文字符、英文字符、数字字符、标点字符等）

串的基本操作，如增删改查等通常以子串为操作对象

基本操作

假设有串T=“”，S=“iPhone 11 Pro Max?”，W=“Pro”

StrAssign(&T,chars)：赋值操作。把串T赋值为chars中的内容

StrCopy(&T,S)：复制操作。把串S复制到串T

StrEmpty(S)：判空操作。若S为空串，则返回TRUE，否则返回FALSE

StrLength(S)：求串长。返回串S的元素个数

ClearString(&S)：清空操作。将S清为空串

DestroyString(&S)：销毁串。将串S销毁（回收存储空间）

Concat(&T,S1,S2)：串联接。用T返回由S1和S2联接而成的新串

SubString(&Sub,S,pos,len)：求子串。用Sub返回串S的第pos个字符起长度为len的子串

Index(S,T)：定位操作。若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置；否则返回0

StrCompare(S,T):比较操作。若S>T，则返回值>0；若S=T，则返回值=0；若S<T，则返回值<0

这里的比较操作是针对字符大小来判断的，

Eg：d>a，因为d在a的后面

abstract<abstraction，长串前缀相同时，长串更大

任何数据存到计算机中一定是二进制数。

需要确定一个字符和二进制数的对应规则，这就是编码

“字符集”：

• 英文字符---ASCII字符集
• 中英文---Unicode字符集

英文字符大小通常根据ASCII字符集来确定

存储结构

顺序存储

顺序存储其实就是通过顺序表来存储，而ElemType改为了char

#define MAXLEN 255    // 预定义最大串为255
typedef struct{
    char ch[MAXLEN];    // 每个分量存储一个字符,静态数组实现(定长顺序存储)
    int length;    // 串的实际长度
}SString;

typedef struct{
    char *ch;    // 按串长分配存储区，ch指向串的基地址(动态数组实现堆分配存储)
    int length;    // 串的长度
}HString;
HString S;
S.ch = (char *)malloc(MAXLEN * sizeof(char));
S.length = 0;

上述说明的是方案一，写明Length，写明数组

方案二

在ch[0]，即数组首位充当Length，优点：字符的位序和数组下标相同

方案三

没有Length变量，以字符'\0'表示结尾（对应ASCII码的0）

类似这样：w a n g \0

方案四

舍弃ch[0]，由ch[1]开始存储数据，并专门声明Length用来表示字符串有多长

这样就可以截取方案一、二的优点了

链式存储

typedef struct StringNode{
    char ch;    // 每个结点存1个字符
    struct StringNode * next;    // 在32位的系统中，此处占用4个字节
}StringNode, * String;

此时就出现了一个问题

我们存储内容只存一个字节，而辅助存储的next指针却要4个字节，我们称这种情况为

存储密度低：每个字符1B，每个指针4B

如何解决该问题呢？

我们可以让每个结点存储多个字符，以此来提高存储密度

typedef struct StringNode{
    char ch[4];    // 此处存储的信息可以更多
    struct StringNode * next;    // 在32位的系统中，此处占用4个字节
}StringNode, * String;

操作实现

以下操作采用顺序存储方案四

SubString(&Sub,S,pos,len)：求子串。用Sub返回串S的第pos个字符起长度为len的子串

结构

#define MAXLEN 255
typedef struct{
    char ch[MAXLEN];    // 每个分量存储一个字符
    int length;
}SString;

// 求子串
bool SubString(SString &Sub,SString S,int pos,int len){
    // 子串范围越界
    if (pos + len - 1 > S.length)    // 如果第pos个字符+len-1大于总长度时，说明字符越界
        return false;
    for (int i=pos;i<pos+len;i++){
        Sub.ch[i-pos+1] = S.ch[i];    // 这里的第一个位置是不放内容的
    }
    Sub.length = len;
    return true;
}

StrCompare(S,T)：比较操作。若S>T，则返回值>0；若S=T，则返回值=0；若S<T，则返回值<0

int StrCompare(SString S,SString T){
    for (int i = 1;i <= S.length && i <= T.length;i++){
        // 如果长度小于这两个数组，此时说明还未结束
        if (S.ch[i] != T.ch[i])    // 若字符不同
            return S.ch[i] - T.ch[i];    // ASCII码字符相减
    }
    // 扫描过的所有字符都相同，则长度长的串更大
    return S.length-T.length;
}

Index(S,T)：定位操作。若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置；否则函数值为0

int Index(SString S,SString T){
    int i=1,n=StrLength(S),m=StrLength(T);    // 获取两个字符串的长度
    SString sub;    //暂存字符串
    while(i<=n-m+1){    // n-m+1是为了计算可以获取到的子串次数，依次向后，这里+1是把第一次包含进去
        SubString(sub,S,i,m);    // 截取子串
        if(StrCompare(sub,T)!=0) ++i;    // 比对子串
        else return i;    // 返回位置
    }
    return 0;    // 不存在子串
}

朴素模式匹配算法

字符串模式匹配：在主串中找到与模式串相同的子串，并返回其所在位置

主串：123456

模式串：56

模式串：78

子串与模式串不同

• 子串---主串的一部分，一定存在
• 模式串---不一定在主串中能找到

朴素模式匹配算法：暴力解决问题

主串长度为n，模式串长度为m

朴素模式匹配算法，将主串中所有长度为m的子串依次与模式串对比，直到找到一个完全匹配的子串，或所有的子串都不匹配为止。

而我们最多能对比n-m+1个子串，这里+1是第一次的对比加入进去

看到这里是不是感觉有些熟悉呢？

其实在操作实现中的Index方法里，我们已经实现了朴素模式匹配算法，但这是通过字符串的基本方法来实现的

接下来我们将通过数组下标实现朴素模式匹配算法

直接上代码解析

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]){    // 模式串和主串相同
            ++i;++j;    // 继续比较后继字符
        }
        else{
            i=i-j+2;    // 主串来到原字符下一个位置
            // 通常来说是+1，即向后一位，但这里采用的是模式四，第0位被舍弃了，所以+2
            j=1;    // 模式串回到首位
        }
    }
    // 如果j超过了模式串的长度，说明已经找到了，返回位置
    if (j>T.length)
        return i-T.length;
    else 
        return 0;
}

这样的时间复杂度最坏会达到O(nm)

KMP算法

KMP算法相当于朴素模式匹配算法的优化版

简单说明一下旧版的KMP算法

原方法是遍历主串，对应的遍历模式串，如果主串与模式串不符合，就让主串后移，模式串回到原位，这种方法确实稳妥，但是太慢了

KMP算法只需要看模式串，我们会额外声明一个next数组作为辅助使用

拿google为例，如果两个字符匹配，则i，j，i是主串,j是模式串

若j=1时发生不匹配，让i++，而j依然是1

若j=2 时发生不匹配，则应让j回到1

若j=3时发生不匹配，则应让j回到1

若j=4时发生不匹配，则应让j回到1

若j=5时发生不匹配，则应让j回到2，这里是因为google，j=5时，数据为l，很显然前面已经有了g，符合第一个g的标准，就没有必要从原先的g重新开始了，而是直接让j回到o，相当于少匹配一次g


若j=6 时发生不匹配，则应让j回到1

而j=next[k]，其实是说明了上述的情况

具体代码如下：

int Index_KMP(SString S,SString T,int next[]){
    int i = 1,j = 1;    // 初始化主串、模式串序号
    while(i<=S.length && j<=T.length){
        if(j==0 || S.ch[i]==T.ch[j]){    
            // 当j为next[1]时，说明首字符不匹配，两者后移，让主串后移，并让模式串回到首位
            ++i;
            ++j;
        }else{
            j=next[j];    // 模式串后移
        }
    }
    if(j>T.length)
        return i-T.length;    // 匹配成功
    else
        return 0;    
}

串的前缀：包含第一个字符，且不包含最后一个字符的子串

例如：abcdefg，前缀就有：a、ab、abc、abcd、abcde、abcdef

串的后缀：包含最后一个字符，且不包含第一个字符的子串

例如：abcdefg，后缀就是g、fg、efg、defg、cdefg、bcdefg

我们主要看最长相等的匹配前后缀，通过匹配的前后缀就可以填充next数组了

举个栗子，我们以ababaa来制作next数组

那么next数组就是[0,0,1,2,3,1]

特别的，next[0]是为0的

当然，我们是把next[1]来作为第一个字符使用的，所以通常来说，next[1]=0

我们务必要知道最长相等的前后缀长度

另一种方法：当第j个字符匹配失败，由前1~j-1个字符组成的串记为S，则next[j]=S的最长相等前后缀长度+1

比如拿ababaa来说，如果在索引5的a时匹配失败，那么由ababa组成S

S的最长相等前后缀是：aba aba，那么长度是3，3+1是4

next[5]=4

这两个情况不同，但得到的结果都是对的

在考研处学习的是第二种方法

这里给出相应代码

// 求模式串T的next数组
void get_next(SString T,int next[]){
    int i=1,j=0;    // i是模式串，j是记录公共前缀长度
    next[1]=0;    // 无前后缀必为0
    while(i<T.length){
        if(j==0||T.ch[i]==T.ch[j]){    // 首位或字符相同，只有字符相同，才会走下去
            ++i;++j;    // 模式串前进，并且公共前缀长度增加
            // 若pi=pj，则next[j+1]=next[j]+1
            next[i]=j;    // 对应的模式串赋予公共前缀长度
        }
        else
            // 否则令j=next[j]，循环继续
            // 并且第一个子串next[1]必定是回到第一个位置，会让串向后走
            j=next[j];    //回溯到上一个正确的前后缀位置
    }
}

//KMP算法
int Index_KMP(SString S,SString T){
    int i=1,j=1;
    int next[T.length+1];
    get_next(T,next);    // 求next数组
    while(i<=S.length && j<=T.length){
        if (j==0 || S.ch[i]==T.ch[j]){
            ++i;++j;    // 继续比较后续字符
        }else
            j=next[j];    // 模式串移动
    }
    if (j >　T.length)
        return i-T.length;    // 匹配成功，返回索引
    else 
        return 0;
}

最后在这里说一下自己对于next数组的理解

next数组真的是最重点的内容了，只要掌握了next数组，就掌握了KMP

next数组的第一个位置存放的是0，这是绝对的，因为如果j在第一个字符就匹配失败了，就需要让模式串做重开操作，并让对应主串往后，第二个位置存放的是1，这是绝对的，因为一般来说，第二个位置匹配失败的话，都会回到第一个位置重新匹配公共前后缀，不同就让主串后移，因为第二个匹配失败了，第一个也失败了，第三个乃至后面的，都是根据是否匹配成功来决定，如果匹配成功，说明了一点，此时的前后缀相同，那么长度，并记录回归位置，如果匹配失败，回到上一次位置，因为上一次位置有成功匹配过的前后缀，对其继续匹配，如果成功，说明前后缀相同，长度，不同就继续回归，直到回到最前面

求nextval数组

先求next数组，再由next数组求nextval数组

nextval[1] = 0;
for(int j=2;j<=T.length;j++){
    if (T.ch[next[j]]==T.ch[j])
        nextval[j]=nextval[next[j]];
    else
        nextval[j]=next[j];
}

树

基本概念

树：从树根生长，逐级分支

空树：结点数为0的树

非空树的特性

• 有且仅有一个根节点
• 前驱：前面的结点，比如C的前驱是A
• 后继：后面的结点，比如A的后继是C
• 没有后继的结点称为“叶子结点”（或终端结点）
• 有后继的结点称为“分支结点”（或非终端结点）

树除了根节点外，任何一个结点有且仅有一个前驱，如果存在多于一个前驱，说明它不是树

树是一个n(n>=0)个结点的有限集合，n=0时，称为空树，这是一种特殊情况。在任意一棵非空树中应满足：

1. 有且仅有一个特定的称为根的结点
2. 当n>1时，其余结点可分为m(m>0)个互不相交的有限集合T1,T2......Tn，其中每个集合本身又是一棵树，并且称为根节点的子树

属性：

• 结点的层次（深度）---从上往下数[默认从1开始]
• 结点的高度 ---从下往上数
• 树的高度（深度） ---总共多少层
• 结点的度 ---有几个孩子（分支）
• 树的度 ---各结点的度的最大值

有序树---逻辑上看，树中结点的各子树从左至右是有次序的，不能互换

无序树---逻辑上看，树中结点的各子树从左至右是无次序的，可以互换

如图所示，左侧为有序树，右侧为无序树

森林是(m>0)棵互不相交的树的集合,m可为0，空森林

如图所示，左侧为森林，右侧为树

常考性质

结点数=总度数+1

结点的度---结点有几个孩子(分支)

度为m的树、m叉树的区别

树的度---各结点的度的最大值

m叉树---每个结点最多只能有m个孩子的树

度为m的树，至少有应该结点的度=m，并且不能为空，至少有m+1个结点

m叉树可以为m叉空树，度也是任意的，可以为空

高度为h的m叉树至少有h个结点。

高度为h、度为m的树至少有h+m-1个结点

存储结构

顺序存储

双亲表示法

思路：用数组顺序存储各个结点。每个结点中保存数据元素、指向双亲结点（父结点）的“指针”

#define MAX_TREE_SIZE 100    // 树中最多结点数
typedef struct{    // 树的结点定义
    ElemType data;    // 数据元素
    int parent;    // 双亲位置域
}PTNode;
typedef struct{    // 树的类型定义
    PTNode nodes[MAX_TREE_SIZE];    // 双亲表示
    int n;    // 结点数
}PTree;

森林。森林是m(m>=0)棵互不相交的树的集合

也可以通过这种形式来表示

这样的话，根节点就是多个-1组成，其他的就找到对应的父结点的位置即可

优点：找双亲（父结点很方便）

缺点：找孩子不方便，只能从头到尾遍历整个数组

适用于找“父亲”多，找“孩子”少的应用场景。如：并查集

孩子表示法

孩子表示法：用数组顺序存储各个结点。每个结点中保存数据元素、孩子链表头指针

如下图所示

存储了元素，每个元素都会有与之对应的子结点的索引，可以很方便的找到子元素

因为既使用到了数组，又使用到了链表，所以孩子表示法算是一种顺序存储+链式存储的组合

struct CTNode{
    int child;    // 孩子结点在数组中的位置
    struct CTNode *next;    // 下一个孩子
}
typedef struct{
    ElemType data;
    struct CTNode *firstChild;    // 第一个孩子
}CTBox;
typedef struct{
    CTBox nodes[MAX_TREE_SIZE];
    int n,r;    // 结点数和根的位置
}CTree;

该方法也可运用于森林

注：用孩子表示法存储森林，需要在结构体中记录多个根的位置

优点：找孩子很方便

缺点：找双亲（父结点）不方便，只能遍历每个链表

适用于找“孩子”多，找“父亲”少的应用场景。如：服务流程树

孩子兄弟表示法

typedef struct CSNode{
    ElemType data;    // 数据域
    struct CSNode *firstchild,*nextsibling;    // 第一个孩子和右兄弟指针
}CSNode,*CSTree

也可以用于存储森林，该方法从存储视角来看形态与二叉树类似

二叉树

二叉树是n(n>=0)个结点的有限集合：

1. 或者为空二叉树，即n=0
2. 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一颗二叉树。

特点：

1. 每个结点至多只有两棵子树
2. 左右子树不能颠倒（二叉树是有序树）

特殊类型

满二叉树

特点：

1. 只有最后一层有叶子结点
2. 不存在度为1的结点
3. 按层序从1开始编号，结点i的左孩子为2i，右孩子为2i+1；结点i的父节点为[i/2]（如果有的话）

完全二叉树

当且仅当其每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应时，称为完全二叉树

特点：

1. 只有最后两层可能有叶子结点
2. 最多只有一个度为1的结点
3. 同上③
4. i<=[n/2]为分支结点，i>[n/2]为叶子结点

二叉排序树

一颗二叉树或者是空二叉树，或者是具有如下性质的二叉树：

左子树上所有结点的关键字均小于根节点的关键字；

右子树上所有结点的关键字均大于根节点的关键字；

左子树和右子树又各是一棵二叉排序树。

二叉排序树可用于元素的排序、搜索

平衡二叉树

平衡二叉树。树上任一结点的左子树和右子树的深度之差不超过1

平衡二叉树能有更高的搜索效率

性质

二叉树

假设树中结点总数为n，则

1. $$1. n=n_0+n_1+n_2 \\ 2. n=n_1+2n_2+1$$

完全二叉树

总结

存储结构

顺序存储

二叉树的顺序存储中，一定要把二叉树的结点编号与完全二叉树对应起来

• i的左孩子 ---2i

• i的右孩子 ---2i+1

• $$- i的父节点 ---\left \lfloor i/2 \right \rfloor$$

结论：二叉树的顺序存储结构，只适合存储完全二叉树，因为一旦它只有右孩子，就有很多的空单元

链式存储

// 二叉树的结点（链式存储）
typedef struct BiTNode{
    ElemType data;    // 数据域
    struct BiTNode *lchild,*rchild;    // 左、右孩子指针
}BiTNode,*BiTree;

n个结点的二叉链表共有n+1个空链域

遍历

二叉树的递归特性：

1. 要么是个空二叉树
2. 要么就是由“根节点+左子树+右子树”组成的二叉树

• 先序遍历（先根遍历）->根左右（NLR）
• 中序遍历->左根右（LNR）
• 后序遍历->左右根（LRN）

先序遍历（PreOrder）的操作过程如下：

1. 若二叉树为空，则什么也不做
2. 若二叉树非空：
   1. 访问根结点
   2. 先序遍历左子树
   3. 先序遍历右子树

结构体如下

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

具体算法如下

void PreOrder(BiTree T){
    if(T!=NULL){
        visit(T);    // 访问根结点
        PreOrder(T->lchild);    // 递归遍历左子树
        PreOrder(T->rchild);    // 递归遍历右子树
    }
}

中序遍历和后序遍历跟前序遍历的差别不是很大,只是改了顺序

其实就是递归调用自身去找左右结点

层序遍历

从根结点开始自左向右依次变为一个顺序的数据

算法思想:

1. 初始化一个辅助队列
2. 根结点入队
3. 若队列非空,则队头结点出队,访问该结点,并将其左、右孩子插入队尾（如果有的话）
4. 重复③直到队列为空

// 层序遍历
void LevelOrder(BiTree T){
    LinkQueue Q;
    InitQueue(Q);    // 初始化辅助队列
    BiTree p;
    EnQueue(Q,T);    // 将根节点入队
    while(!IsEmpty(Q)){    // 队列不空则循环
        DeQueue(Q,p);    // 队头结点出队
        visit(p);    // 访问出队结点
        if(p->lchild != NULL)
            EnQueue(Q,p->lchild);    // 左孩子入队
        if(p->rchild != NULL)
            EnQueue(Q,p->rchild);    // 右孩子入队
    }
}

由遍历序列构建二叉树

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

因为一种序列会存在着多种形态，没法逆推

前序+中序遍历序列

举个栗子：

• 前序遍历序列：A D B C E
• 中序遍历序列：B D C A E

前序遍历是：根 左 右，那么这说明第一个必然是根结点，也就是说，A肯定是根结点

中序遍历是：左 根 右，那么根左边就是左子树，右边是右子树

则前序遍历中的：D B C是左子树，E是右子树

且中序遍历中的：B D C是左子树，E是右子树

那么E已经定下来了，接着区分左子树的根节点，前序遍历中：D B C，D是根结点，B是左，C是右

中序遍历中的左是B，根是D，C是右

最终结果为

后序的也是类似的，后序遍历的根节点在最后

我们就可以通过后序+中序来完整的找出这棵树

后序不赘述了，跟前序是一样的

层序+中序

层序是根左右依次往下，只要找到根，就可以通过中序来找出所有的

结论：前序、后序、层序的两两组合是唯一无法确定的一棵二叉树

线索二叉树

概念

指向前驱、后继的指针称为线索

指向前驱的称为前驱线索

指向后继的称为后继线索

n个结点的二叉树，有n+1个空链域，可用来记录前驱、后继的信息

将其对应的空置的左、右孩子结点，左孩子指向前驱，右孩子指向后继(此处指的是中序线索二叉树)

二叉树也可以叫二叉链表

线索二叉树又叫线索链表

代码示例

// 二叉树的结点(链式存储)
typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

// 线索二叉树结点
typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode *lchild,*rchild;
    int ltag,rtag;    // 左右线索标志
}ThreadNode,*ThreadTree;

• tag==0，表示指针指向孩子
• tag==1，表示指针是线索

其他的二叉树是类似的

线索化

中序线索化

// 全局变量pre，指向当前访问结点的前驱
ThreadNode *pre=NULL;

// 线索二叉树结点
typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode *lchild,*rchild;
    int ltag,rtag;    // 左、右线索标志
}ThreadNode,* ThreadTree;

// 中序线索化二叉树T
void CreateInThread(ThreadTree T){
    pre=NULL;    // pre初始化为NULL
    if(T!=NULL){    // 非空二叉树才能线索化
        InThread(T);    // 中序线索化二叉树
        if (pre -> rchild == NULL)
            pre->rtag=1;    // 处理遍历的最后一个结点
    }
}

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

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;    // 向前移动pre指针
}

前序和后序是类似的

但是前序会有一个问题，当访问的是根结点时，根结点恰好左结点是空的，那么就会将左结点->前驱结点指向上一个结点，对吧，如果上一个结点是根结点，并且它的左结点是之前这个所谓的"根结点"

此时会按照根，左，右的顺序访问，这样访问的问题就是下一个访问的是左结点，那么这个左结点又会按照根左右的顺序回头继续这样

导致无限循环

这个问题解决起来其实不难，在该根结点做了前驱线索化后，存在一个tag标记，只要这里有tag标记，不进行左结点回头就行了

if (T->tag == 0)
    PreThread(T->lchild);    // lchild不是前驱线索

寻找前驱后继

中序

中序线索二叉树找中序后继(后继是该结点的下一个结点)

在中序线索二叉树找到指定结点*p的中序后继next

1. 若p->rtag==1，则next=p->rchild，因为此时右结点被线索化了，说明它是后继结点
2. 若p->rtag==0
   1. p必有右孩子
   2. next = p的右子树中最左下的结点，因为中序结点最先访问的是左结点

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

// 在中序线索二叉树中找到结点p的后继结点
ThreadNode *Nextnode(ThreadNode *p){
    // 右子树中最左下结点
    if(p->rtag==0)return Firstnode(p->rchild);
    else return p->rchild;    // rtag==1直接返回后继线索
}

// 对中序线索二叉树进行中序遍历(利用线索实现的非递归算法)
void Inorder(ThreadNode *T){
    for(ThreadNode *p=Firstnode(T);p!=NULL;p=Nextnode(p))
        visit(p);
}

中序线索二叉树找中序前驱(前驱是该结点的下一个结点)

在中序线索二叉树中找到指定结点*p的中序前驱pre

1. 若p->ltag==1，则pre=p->lchild
2. p->ltag==0
   1. p必有左孩子
   2. pre = p的左子树中最右下结点

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

// 在中序线索二叉树中找到结点p的前驱结点
ThreadNode *Prenode(ThreadNode *p){
    // 左子树最右下结点
    if(p=>ltag==0)return Lastnode(p->lchild);
    else return p->lchild;    // ltag==1直接返回前驱线索
}

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

先序

在先序线索二叉树中找到指定结点*p的后继

1. 若p->rtag==1，则next = p->rchild
2. 若p->rtag==0
   1. 若p有左孩子，则先序后继为左孩子
   2. 若p没有左孩子，则先序后继为右孩子

它跟中序差别很大，因为它是按照根、左、右的顺序来的，所以无论是哪个，都不需要继续往后找，因为左孩子和右孩子都会是根结点

在先序线索二叉树中找到指定结点*p的前驱pre

1. 若p->ltag==1，则next = p->lchild
2. 若p>ltag==0

此时出现了一个问题，左右子树中的结点只可能是后继，不可能是前驱

因为是按照根、左、右的顺序来的，所以没办法

除非从头开始先序遍历，一个个的找

假设能找到父结点(该假设建立在可以逆向寻找父结点的情况下)，具体情况如下

后序

在后序线索二叉树中找到指定结点*p的后序前驱pre

1. 若p->ltag==1，则pre = p->lchild
2. 若p->ltag==0
   1. p必有左孩子
      1. 若p有右孩子，则后序前驱为右孩子，因为根是最后访问的，前驱指的是前一个，所以是右孩子
      2. 若p没有右孩子，则后序前驱为左孩子

因为后序是左、右、根来遍历的

在后序线索二叉树中找到指定结点*p的后序后继next

1. 若p->rtag==1，则next = p->rchild
2. 若p->rtag==0
   1. p必有右孩子
      1. 后序遍历中，左右子树中的结点只可能是根的前驱，不可能是后继

因为左右遍历完了才到根，所以没法找到后序的后继，除非从头开始遍历

假设能找到父结点(该假设建立在可以逆向寻找父结点的情况下)，具体情况如下

总结

除非用三叉链表，或者从头开始遍历寻找

树、森林、二叉树的转换

树->二叉树

1. 先在二叉树中，画一个根节点
2. 按“树的层序”依次处理每个结点

处理一个结点的方法是：如果当前处理的结点在树中有孩子，就把所有孩子结点“用右指针串成糖葫芦”，并在二叉树中把第一个孩子挂在当前结点的左指针下方

森林->二叉树

注意：森林中各棵树的根节点视为平级的兄弟关系

森林->二叉树转换技巧

1. 先把所有树的根节点画出来，在二叉树中用右指针串成糖葫芦
2. 按森林的层序依次处理每个结点

处理一个结点的方法是：如果当前处理的结点在树中有孩子，就把所有孩子结点“用右指针串成糖葫芦”，并在二叉树中把第一个孩子挂在当前结点的左指针下方

二叉树->树

二叉树->树 转换技巧：

1. 先画出树的根节点
2. 从树的根节点开始，按“树的层序”恢复每个结点的孩子

如何恢复一个结点的孩子：在二叉树中，如果当前处理的结点有左孩子，就把左孩子和“一整串右指针糖葫芦”拆下来，按顺序挂在当前结点的下方

二叉树->森林

注意：森林中各棵树的根节点视为平级的兄弟关系

二叉树->森林转换技巧：

1. 先把二叉树的根节点和“一整串右指针糖葫芦”拆下来，作为多棵树的根节点
2. 按“森林的层序”恢复每个结点的孩子

如何恢复一个结点的孩子：在二叉树中，如果当前处理的结点有左孩子，就把左孩子和“一整串右指针糖葫芦”拆下来，按顺序挂在当前结点的下方

树、森林的遍历

树的先根遍历

先根遍历又称深度优先遍历

先根遍历：若树为空，先访问根结点，再依次对每棵子树进行先根遍历

// 树的先根遍历
void PreOrder(TreeNode *R){
    if(R!=NULL){
        visit(R);    // 访问根结点
        while(R还有下一个子树T)
            PreOrder(T);    //继续先根遍历下一棵子树
    }
}

树的先根遍历序列与这棵树相应二叉树的先序序列相同

树的后根遍历

后根遍历又称深度优先遍历

后根遍历。若树为空，先依次对每棵子树进行后根遍历，最后再访问根结点

// 树的后根遍历
void PostOrder(TreeNode *R){
    if (R!=NULL){
        while(R还有下一个子树T)
            PostOrder(T);    // 后根遍历下一棵子树
        visit(R);    // 访问根结点
    }
}

树的后根遍历序列与这棵树相应二叉树的中序序列相同

树的层次遍历

层次遍历（用队列实现）

层次遍历又称广度优先遍历

1. 若树非空，则根结点入队
2. 若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队
3. 重复②直到队列为空

森林的先序遍历

先序遍历森林

1. 若森林非空，则按如下规则进行遍历
2. 访问森林中第一棵树的根节点
3. 先序遍历第一棵树中根节点的子树森林
4. 先序遍历除去第一棵树之后剩余的树构成的森林

效果等同于依次对各个树进行先根遍历

森林的中序遍历

中序遍历森林

1. 若森林非空，则按如下规则进行遍历：
2. 中序遍历森林中第一棵树的根结点的子树森林
3. 访问第一棵树的根结点
4. 中序遍历除去第一棵树之后剩余的树构成的森林

效果等同于依次对二叉树进行中序遍历

哈夫曼树

带权路径长度

结点的权：有某种现实含义的数值（如：表示结点的重要性等）

结点的带权路径长度：从树的根到该结点的路径长度（经过的边数）与该结点上权值的乘积

树的带权路径长度：树中所有叶结点的带权路径长度之和（WPL，Weighted Path Length）

计算公式如下：

具体示例如下，其实就是将结点的带权路径长度统一相加了而已：

在含有n个带权叶结点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树，也称最优二叉树

构造

1. 将这n个结点分别作为n棵仅含一个结点的二叉树，构成森林F
2. 构造一个新结点，从F中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和
3. 从F中删除刚才选出的两棵树，同时将新得到的树加入F中
4. 重复步骤2和3，直到F中只剩下一棵树为止

具体示例如下

1. 每个初始结点最终都称为叶结点，且权值越小的结点到根结点的路径长度越大
2. 哈夫曼树的结点总数为2n-1
3. 哈夫曼树中不存在度为1的结点
4. 哈夫曼树并不唯一，但WPL必然相同且为最优

哈夫曼编码

固定长度编码：每个字符用相等长度的二进制位表示

可变长度编码：允许对不同字符用不等长的二进制位表示

若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码

由哈夫曼树得到哈夫曼编码---字符集中的每个字符作为一个叶子结点，各个字符出现的频率作为结点的权值，根据之前介绍的方法构造哈夫曼树

哈夫曼树不唯一，因此哈夫曼编码不唯一

并查集

基本功能

集合的两个基本操作---“并”和“查”

Find---查操作：确定一个指定元素所属集合

Union---并操作：将两个不相交的集合合并为一个

注：并查集（Disjoint Set）是逻辑结构---集合的一种具体实现，只进行并和查两种基本操作

// 初始化,刚开始所有集合都是独立的子集
int UFSets[SIZE];    // 集合元素数组

// 初始化并查集
void Initial(int S[]){
    for(int i=0;i<SIZE;i++)
        S[i]=-1;
}

// Find "查"操作，找x所属集合(返回x所属根结点)
int Find(int S[],int x){
    while(S[x]>=0)
        x=S[x];    // 循环寻找x的根
    return x;    // 根的S[]小于0
}

// Union "并"操作，将两个集合合并为一个
void Union(int S[],int Root1,int Roo2){
    // 要求Root1与Root2是不同的集合
    if (Root1 == Root2) return;
    // 将根Root2连接到另一根Root1下面
    S[Root2]=Root1;
}

但是这样的查操作有时候会出现一个问题，最好的情况是O(1)，最坏的情况是O(n)，因为如果树是高的，从最下面找到最上面就相当麻烦

优化思路：在每次Union操作构建树的时候，尽可能让树不长高

1. 用根结点的绝对值表示树的结点总数
2. Union操作，让小树合并到大树

//Union 合并操作优化
void Union(int S[],int Root1,int Root2){
    if(Root1 == Root2)return;
    if (S[Root2] > S[Root1]){    // Root2结点数更少
        S[Root1] += S[Root2];    // 累加结点总数
        S[Root2] = Root1;    // 从小树合并到大树
    }else{
        S[Root2] += S[Root1];    // 累加结点总数
        S[Root1] = Root2;    //从小树合并到大树
    }
}

优化

Find优化

Find操作优化(压缩路径)

压缩路径---Find操作，先找到根结点，再将查找路径上所有结点都挂到根结点下

// Find 查操作优化，先找到根结点，再进行压缩路径
int Find(int S[],int x){
    int root = x;
    while(S[root] >= 0) root = S[root];
    while(x!=root){    // 压缩路径
        int t = S[x];    // t指向x的父结点
        S[x] = root;    // x挂在根结点下
        x = t;
    }
    return root;
}

图

定义

注意：线性表可以是空表，树可以是空树，但图不可以是空，即V一定是非空集，E可以是空集，即边集可以是空集

无向图、有向图

无向图其实就是没有指明方向的图

有向图就是有方向的图

简单图、多重图

简单图

1. 不存在重复的边
2. 不存在顶点到自身的边

下面所有的图，只探讨简单图

多重图：图G中某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联，则G为多重图

具体情况如下图所示：

顶点的度、入度、出度

对于无向图：顶点v的度是指依附于该顶点的边的条数，记为TD(v)

无向图的全部顶点的度之和等于边数的2倍

对于有向图：

• 入度是以顶点v为终点的有向边的数目，记为ID(v)
• 出度是以顶点v为起点的有向边的数目，记为OD(v)
• 顶点v的度等于其入度和出度之和，即TD(v)=ID(v)+OD(v)

顶点->顶点的关系描述

无向图可能不存在路径

有向图的路径也是有向的 $$ 回路：第一个顶点和最后一个顶点相同的路径称为回路或环 \ 简单路径：在路径序列中，顶点不重复出现的路径称为简单路径 \ 简单回路：除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路 \ 路径长度：路径上边的数目 \ 点到点的距离：从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离。若从u到v根本不存在路径\ 则记该距离为无穷 $$ 无向图中，若顶点v到顶点w由路径存在，则称v和w是连通的

有向图中，若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是强连通的

连通图、强连通图

若图G中任意两个顶点都是连通的，则称图G为连通图，否则称为非连通图

若图中任何一对顶点都是强连通的，则称此图为强连通图 $$ 对于n个顶点的无向图G，若G是连通图，则最少有n-1条边 \ 若G是非连通图，则最多可能有C^2_{n-1}条边 $$

子图

有向图和无向图在子图的概念里是一致的

连通分量

无向图中的极大连通子图称为连通分量

如图所示

强连通分量

有向图中的极大强连通子图称为有向图的强联通分量

子图必须强连通，同时保留尽可能多的边

如图所示

生成树

连通图的生成树是包含图中全部顶点的一个极小连通子图

边要尽可能的少，但是要保持连通

若图中顶点数为n，则它的生成树含有n-1条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一条回路

生成森林

在非连通图中，连通分量的生成树构成了非连通图的生成森林

多个生成树构成了一个生成森林

边的权、带权图/网

边的权---在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值

带权图/网---边上带有权值的图称为带权图，也称网

带权路径长度---当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度

特殊的图

无向完全图与有向完全图

稀疏图和稠密图

树和有向树

邻接矩阵法

在领接矩阵求对应的度

无向图：第i个结点的度=第i行(或第i列)的非零元素个数

有向图：

• 第i个结点的出度=第i行的非零元素个数
• 第i个结点的入度=第i列的非零元素个数
• 第i个结点的度=第i行、第i列的非零元素个数之和

如图所示

领接矩阵存储带权图

如图所示

邻接表法

如图所示

十字链表、邻接多重表

十字链表用于存储有向图，邻接多重表用于存储无向图

十字链表法存储有向图

如图所示

如何找到指定顶点的所有出边？---顺着绿色线路找

如何找到指定顶点的所有入边？---顺着橙色线路找

直到为空，说明找到底了

注意：十字链表法只能存储有向图

邻接多重表存储无向图

如图所示

删除边、删除节点等操作很方便

例如删除A针对B的边只需要将A针对B的边后移一位，跳过B即可

如果是删除结点，则需要正常移除当前结点，并对拥有该结点的指针往后一位指，如果有值，指向值，如果没值，指向空

注意：邻接多重表只适合存储无向图

基本操作

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

无向图

• 以B,D为例
• 使用邻接矩阵来存储，找到B和D对应的那个值是否为1即可
• 使用邻接表来存储，检查B的边结点有没有D对应的索引值

有向图与无向图是一样的

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

无向图

• 以B为例
• 使用邻接矩阵来存储，找到B这一行中值为1的结点即可
• 使用邻接表来存储，遍历该结点下的所有结点，都是邻接的边

有向图

• 以B为例
• 使用邻接矩阵来存储，想找到入边，遍历B这一行中值为1的结点即可，出边遍历B的这一列即可
• 使用邻接表来存储，遍历该结点下的所有结点，都是邻接的入边，如果找出边，就需要遍历所有结点，来找到指向B的结点

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

无向图

• 在保存数据的位置(数组)写入一个新数值即可，邻接矩阵中不需要其他操作，因为数组初始化的值为0,
• 邻接表需要在最下方插入新结点，并将它的其他连接点置为空(NULL)

有向图也是类似的

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

无向图

• 邻接矩阵中只需要移除对应的元素要删除的行和列，并在数组的标志中标记为空(NULL)
• 领接表中如果要删除数据，需要先删除当前需要删除的值，再删除其他结点中存在该删除的值的索引

有向图

• 邻接矩阵和无向图的一致
• 邻接表如果要删除出边，只需要删除当前需要删除的索引值即可
• 邻接表如果要删除入边，需要遍历其他结点，找到当前结点进行删除

AddEdge(G,x,y)：若无向边(x,y)或有向边<x,y>不存在，则向图G中添加该边

无向图

• 邻接矩阵直接向指定位置赋值为1即可
• 邻接表直接使用头插法或者尾插法将对应的索引插入到两边(是两边)对应的位置

有向图是类似的

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

无向图

• 邻接矩阵只需要扫描对应的这一行的第一个1，若有则返回顶点号，否则-1
• 邻接表只需要找到对应索引链表的根结点

有向图

• 领接矩阵找入边是列，找出边是行，找到第一个1
• 邻接表找出边跟无向图是一样的，找入边需要遍历整个链表，找到第一个指向该结点的位置

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

【说人话就是找到这个领接点的下一个领接点结点】

无向图

• 领接矩阵只需要遍历找到下一个结点
• 领接表只需要对应的结点往后找一位就行了

有向图类似

Get_edge_value(G,x,y)：获取图G中边(x,y)或<x,y>对应的权值

Set_edge_value(G,x,y,v)：设置图G中边(x,y)或<x,y>对应的权值为v

广度优先遍历

算法

图的广度优先遍历与树其实是类似的，也叫层序遍历，一层一层的访问相邻结点

如图所示

树的层序遍历就是1,2,3,4,5,6,7,8依次下去，因为相邻结点被依次的遍历了

而图假设从2开始，那么是2,1,6,5,3,7,4,8这样，也和树极其相似

当然它俩是有区别的

树是不存在回路的，搜索相邻结点时，不可能搜到已经访问过的结点

图搜索相邻顶点时，有可能搜到已经访问过的顶点

当然，我们可以给遍历过的结点做一个标记，在回头找其他结点时，直接跳过被遍历的结点

广度优先遍历（Breadth-First-Search，BFS）要点

1. 找到与一个顶点相邻的所有顶点
2. 标记哪些顶点被访问过
3. 需要一个辅助队列

具体实现代码如下

bool visited[MAX_VERTEX_NUM];    //访问标记数组

// 广度优先遍历
void BFS(Graph G,int v){    // 从顶点v出发，广度优先遍历图G
    visit(v);    // 访问初始顶点v
    visited[v]=TRUE;    // 对v做已访问标记
    Enqueue(Q,v);    // 顶点v入队列Q
    while(!isEmpty(Q)){
        DeQueue(Q,v);
        for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
            // 检测v所有邻接点
            if(!visited[w]){    // w为v的尚未访问的领接顶点[根据visited数组中对应的值来判断]
                visit(w);    // 访问顶点w
                visited[w]=TRUE;    // 对w做已访问标记
                EnQueue(Q,w);    // 顶点w入队列
            }// if
        }// for
    }// while
}

访问标记数组长这样

举个栗子

以该图为例，右侧是图

假设初始顶点v是2，那么访问2，并将visited数组对应的结点设为TRUE，将顶点v加入队列Q

当队列Q不为空时，顶点v，也就是2出队

循环找到顶点v的邻接点，1和6，并检查结点是否已经被访问过了，很显然都没被访问过

访问这俩结点，并设置为已访问，进行入队

继续for循环，找到邻接点，以1为例，判断领接点是否被访问

1的邻接点为2和5

2被访问过，不走2,5入队

接着回到while,6号出队

后面的都是类似，不再赘述了

当然，这些都建立在使用邻接矩阵来存储的条件下

邻接表是不同的

因为邻接表对应的链表存储的顺序可能不同，拿2来说，它对应的可以是1,6，也可以是6,1

所以我们得到一个结论

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

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

如果是非连通图，此时我们没法去遍历另外的结点了，因为它们并不连通

解决该问题的方法是，去检查visited数组中是否还存在未遍历的数组值，对未遍历的值进行BFS，直到不存在未遍历的数组值即可

void BFSTraverse(Graph G){    // 对图G进行广度优先遍历
    for(i=0;i<G.vexnum;++i)
        visited[i]=FALSE    // 访问标记数组初始化
    InitQueue(Q);    // 初始化辅助队列Q
    for(i=0;i<G.vexnum;++i)    // 从0顶点开始遍历
        if(!visited[i])    // 对每个连通变量都调用一次BFS
            BFS(G,i);    // 未访问过，则进行BFS
}

结论：对于无向图，调用BFS函数的次数=连通分量数

广度优先生成树

如图所示

广度优先生成森林

对非连通图的广度优先遍历，可得到广度优先生成森林

其实就是将其分别遍历得到了不同的树，组成一个森林

深度优先遍历

图的深度优先遍历类似树的深度优先遍历

具体代码如下

bool visited[MAX_VERTEX_NUM];    // 访问标记数组
void DFS(Graph G,int v){    // 从顶点v出发，深度优先遍历图G
    visit(v);    // 访问顶点v
    visited[v]=TRUE;    // 设置为已访问
    for(w=FirstNeighbor(G,v);w>=0;w=NextNeighor(G,v,w))
        if(!visited[w]){    // w为尚未访问的邻接顶点
            DFS(G,w);    
        }
}

在深度优先遍历算法中，也存在着与广度优先生成算法同样的问题，即非连通图无法遍历完所有结点，处理办法是一样的

void DFSTraverse(Graph G){
    for(v=0;v<G.vexnum;++v)
        visited[v]=FALSE;    //初始化已访问标记数据
    for(v=0;v<G.vexnum;++v)
        if(!visited[v])
            DFS(G,v);
}

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

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

深度优先生成树和深度优先生成森林是类似的，这里不再赘述了

最小生成树

概念

最小生成树也称最小代价树

对于一个带权连通无向图G=(V,E)，生成树不同，每棵树的权（即树中所有边上的权值之和）也可能不同。设R为G的所有生成树的集合，若T为R中边的权值之和最小的生成树，则T称为G的最小生成树（Minimum-Spanning-Tree,MST）

• 最小生成树可能有多个，但边的权值之和总是唯一且最小的
• 最小生成树的边数=顶点数 - 1。砍掉一条则不连通，增加一条则会出现回路
• 如果一个连通图本身就是一棵树，则其最小生成树就是它本身
• 只有连通图才有生成树，非连通图只有生成森林

Prim(普里姆)

从某一个顶点开始构建生成树；

每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止

Kruskal(克鲁斯卡尔)

每次选择一条权值最小的边，使这条边的两头连通（原本已经连通的就不选）

直到所有结点都连通

最短路径问题

BFS

BFS求无权图的单源最短路径

注：无权图可以视为一种特殊的带权图，只是每条边的权值都为1

// 求顶点u到其他顶点的最短路径
void BFS_MIN_Distance(Graph G,int u){
    // d[i]表示从u到i结点的最短路径
    for(i=0;i<G.vexnum;++i){
        d[i]=∞;    // 初始化路径长度
        path[i]=-1;    // 最短路径从哪个顶点过来
    }
    d[u]=0;
    visited[u]=TRUE;
    EnQueue(Q,u);
    while(!isEmpty(Q)){    // BFS算法主过程
        DeQueue(Q,u);    // 队头元素u出队
        for(w=FirstNeighbor(G,u);w>=0;w=NextNeighbor(G,u,w)){
            if(!visited[w]){    // w为u的尚未访问的邻接顶点
                d[w]=d[u]+1;    // 路径长度加1
                path[w]=u;    // 最短路径应从u到w
                visited[w]=TRUE;    // 设置已访问标记
                EnQueue(Q,w);    // 顶点w入队
            }//if
        }//for
    }//while
}

数组d是用来记录路径长度的，path是记录前驱结点

当访问到某个结点后，d就会根据前一个结点在根结点的距离上+1

而path会记录前一个结点

Dijkstra

BFS不适用于带权图

回顾一些概念

带权路径长度---当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度

不好说明这里的代码，理解起来跟BFS差不多，丢视频链接了：https://www.bilibili.com/video/BV1b7411N798/?p=67&spm_id_from=333.1007.top_right_bar_window_history.content.click&vd_source=b39debcbe1026bb04f6c19f233bab974

如果存在负权值，该方法可能会失效

Floyd

Floyd算法：求出每一对顶点之间的最短路径

使用动态规划思想，将问题的求解分为多个阶段
对于n个顶点的图G，求任意一对顶点Vi一>Vj 之间的最短路径可分为如下几个阶段：


#初始：不允许在其他顶点中转，最短路径是？

0：若允许在Vo中转，最短路径是?

1：若允许在Vo、V1 中转，最短路径是？

2：若允许在Vo、V1、V2中转，最短路径是？

n-1：若允许在Vo、V、V2...Vn-1 中转，最短路径是?

如图所示

图中有两个二维数组

A是对应顶点与其他顶点之间的路径长度，path是中转点，其实就是前面一个结点

代码不难，但是for循环太多了，这里不写了

简单说明一下，其实就是针对A数组进行遍历，看看是否存在无中转点和有中转点的权值比较有更好的情况，如果有中转点权值更小，就采用后者，并更新path数组的中转点以及A数组的路径长度

如果存在多结点，也就是说，不像图中这样只有3个结点，而是七八个

如果v0到v3没有直接路径，需要中转，那么假设从v0先到v1，此时path和A都会更新至v1的情况，从v1继续过去，如果v1无法直接到v3，需要通过v2才能到v3，那么我们还是会像之前一样遍历，但是信息存储的是v1到v2的情况，最后从v2到v3算出最短路径

Floyd算法不能解决带有“负权回路”的图（有负权值的边组成的回路）。这种图有可能没有最短路径

总结

有向无环图描述表达式

有向无环图：若一个有向图中不存在环，则称为有向无环图，简称DAG图(Directed Acyclic Graph)

左边这个图无法回到之前的位置,没有环路,就是有向无环图

右边这个图可以回到之前的位置,存在环路,不是有向无环图

拓扑排序

AOV网(Activity On Vertex NetWork，用顶点表示活动的网)：

用DAG图(有向无环图)表示一个工程。顶点表示活动，有向边<Vi,Vj>表示活动Vi必须先于活动Vj进行

拓扑排序：在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序：

1. 每个顶点出现且只出现一次
2. 若顶点A在序列中排在顶点B的前面，则在图中不存在从顶点B到顶点A的路径

或定义为：拓扑排序是对有向无环图的顶点的一种排序，它使得若存在一条从顶点A到顶点B的路径，则在排序中顶点B出现在顶点A的后面。每个AOV网都有一个或多个拓扑排序序列。

拓扑排序：找到做事的先后顺序

拓扑排序的实现：

1. 从AOV网中选择一个没有前驱(入度为0)的顶点并输出
2. 从网中删除该顶点和所有以它为起点的有向边
3. 重复①和②直到当前AOV网为空或当前网中不存在无前驱的顶点为止

当前所有顶点入度>0，说明原图存在回路

代码如下

// 结构
#define MaxVertexNum 100 // 图中顶点数目的最大值
typedef struct ArcNode{
    int adjvex;    // 该弧指向的顶点的位置
    struct ArcNode * nextarc;    // 指向下一条弧的指针
    // InfoType info;    // 网的边权值
}ArcNode;
typedef struct VNode{    // 顶点表结点
    VertexType data;    // 顶点信息
    ArcNode *firstarc;    // 指向第一条依附该顶点的弧的指针
}VNode,AdjList[MaxVertexNum];
typedef struct{
    AdjList vertices;    // 邻接表
    int vexnum,arcnum;    // 图的顶点数和弧度
}Graph;    // Graph是以邻接表存储的图类型

// 算法
bool TopologicalSort(Graph G){
    InitStack(S);    // 初始化栈，存储入度为0的顶点
    for(int i=0;i<G.vexnum;i++)
        if(indegree[i]==0)
            Push(S,i);    // 将所有入度为0的顶点进栈
    int count = 0;    // 计数，记录当前已经输出的顶点数
    while(!IsEmpty(S)){    // 栈不空，则存在入度为0的顶点
        Pop(S,i);    // 栈顶元素出栈
        print[count++]=i;    // 输出顶点i
        for(p=G.vertices.firstarc;p;p=p->p->nextarc){
            // 将所有i指向的顶点的入度减1，并且将入度减为0的顶点压入栈S
            v=p->adjvex;
            if(!(--indegree[v]))    // 如果不存在入度，则会入栈排序
                Push(S,v);    // 入度为0，则入栈
        }
    }
    if(count->G.vexnum)    // vexnum是顶点个数,count是排序个数
        // 如果排序个数小于顶点个数，说明存在回路
        return false;    // 排序失败，有向图存在回路
    else
        return true;
}

indegree存储对应顶点的入度，print数组存储拓扑序列排序的每个位置，最后会输出print数组

逆拓扑排序

对一个AOV网逆拓扑排序：

1. 从AOV网中选择一个没有后继(出度为0)的顶点并输出
2. 从网中删除该顶点和所有以它为终点的有向边
3. 重复①和②直到当前AOV网为空

关键路径

在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动所需的时间），称之为用边表示活动的网络，简称AOE网(Activity On Edge NetWork)

AOE网具有以下两个性质：

1. 只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始
2. 只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生

另外，有些活动是可以并行进行的

在AOE网中仅有一个入度为0的顶点，称为开始顶点(源点)，它表示整个工程的开始；

也仅有一个出度为0的顶点，称为结束顶点(汇点)，它表示整个工程的结束

从源点到汇点的有向路径可能有多条，所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动

活动ai的最早开始时间e(i)---指该活动弧的起点所表示的事件的最早发生时间

活动ai的最迟开始时间l(i)---它是指该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差

活动ai的时间余量d(i)=l(i)-e(i),表示在不增加完成整个工程所需总时间的情况下，活动ai可以拖延的时间

若一个活动的时间余量为零，则说明该活动必须要如期完成，d(i)=0即l(i)=e(i)的活动ai是关键活动

由关键活动组成的路径是关键路径

1. 求所有事件的最早发生时间
   • 按拓扑排序序列，依次求各个顶点的ve(k);
   • ve(源点)=0
   • ve(k)=Max{ve(j)+Weight(vj,vk)}，vj为vk的任意前驱
2. 求所有事件的最迟发生时间vl
   • 按逆拓扑排序序列，依次求各个顶点的vl(k)
   • vl(汇点)=ve(汇点)
   • vl(k)=Min{vl(j)-Weight(vk,vj)}，vj为vk的任意后继
3. 求所有活动的最早发生时间e()
   • 若边<vk,vj>表示活动ai，则有e(i)=ve(k)
4. 求所有活动的最迟发生时间
   • 若边<vk,vj>表示活动ai，则有l(i)=vl(j)-Weight(vk,vj)

查找

概念

查找---在数据集合中寻找满足某种条件的数据元素的过程称为查找

查找表(查找结构)---用于查找的数据集合称为查找表，它由同一类型的数据元素(或记录)组成

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

• 仅关注查找速度：静态查找表
• 除了查找速度，也要关注插/删操作是否方便实现

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

平均查找长度---所有查找过程中进行关键字的比较次数的平均值

顺序查找

顺序查找，又叫线性查找，通常用于线性表

其实很简单，就是挨个找

直接上代码吧，其实并不复杂

typedef struct{    // 查找表的数据结构(顺序表)
    ElemType *elem;    // 动态数组基址
    int TableLen;    // 表的长度
}SSTable;

// 顺序查找
int Search_Seq(SSTable ST,ElemType key){
    int i;
    for(i = 0;i<ST.TableLen && ST.elem[i] != key;++i);
    return i == ST.TableLen ? -1 : i;
}

顺序查找---哨兵

// 顺序查找
int Search_Seq(SSTable ST,ElemType key){
    ST.elem[0]=key;
    int i;
    for(i=ST.TableLen;ST.elem[i]!=key;--i);    // 从后往前找
    return i;    // 查找成功,则返回元素下标；查找失败，则返回0
}

还有另一种方式，通过二叉树，将小值放在右边，大值放在左边，也可以方便的查找，但是这个有前提，需要有序

折半查找

折半查找，又称“二分查找”，仅适用于有序的顺序表

其实就是找该顺序表的中间，然后比较与要查找的数字的大小，大了说明在右边，小了说明在左边

typedef struct{    // 查找表的数据结构(顺序表)
    ElemType *elem;    // 动态数组的基址
    int TableLen;    // 表的长度
}
// 折半查找
int Binary_Search(SSTable L,ElemType key){
    int low=0,high=L.TableLen-1,mid;
    while(low <= high){
        mid=(low+high)/2;    // 取中间位置
        if(L.elem[mid]==key)
            return mid;    // 查找成功则返回所在位置
        else if(L.elem[mid]>key)
            high=mid-1;    // 从前半部分继续查找
        else
            low=mid+1;    // 从后半部分继续查找
    }
    return -1;
}

当然，这里的查找算法并不通用，需要根据情况来编写，比如升序、降序的情况

如果当前low和high之间有奇数个元素，则mid分隔后，左右两部分元素个数相等

如果当前low和high之间有偶数个元素，则mid分隔后，左半部分比右半部分少一个元素

分块查找

分块查找会将一个一个表内的元素，分成一块一块的内容，索引表中会保存每个分块的最大关键字和分块的存储区间

特点：块内无序、块间有序

如上图所示

// 索引表
typedef struct{
    ElemType maxValue;
    int low,high;
}Index;
// 顺序表存储实际元素
ElemType List[100];

先从索引表找到对应的分块区域，再从区域里查找

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

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

若索引表中不包含目标关键字，这折半查找索引表最终停在low>high，要在low所指分块中查找

原因：最终low左边一定小于目标关键字，high右边一定大于目标关键字。而分块存储的索引表中保存的是各个分块的最大关键字

二叉排序树(BST)

二叉排序树，又称二叉查找树(BST,Binary Search Tree)

一棵二叉树或者是空二叉树，或者是具有如下性质的二叉树：

• 左子树上所有结点的关键字均小于根结点的关键字
• 右子树上所有结点的关键字均大于根结点的关键字
• 左子树和右子树各自是一棵二叉排序树

查找

若树为空，目标值与根结点的值比较：

• 若相等，则查找成功；
• 若小于根结点，则在左子树上查找，否则在右子树上查找

查找成功，返回结点指针；查找失败返回NULL

// 在二叉排序树中查找值为key的结点
BSTNode *BST_Search(BSTree T,int key){
    while(T!=NULL && key!=T->key){    // 若树空或等于根结点值，则结束
        if(key < T->key) T=T->lchild;    // 小于，则在左子树上查找
        else T=T->rchild;    // 大于，则在右子树上查找
    }
    return T;
}

// 在二叉排序树中查找值为key的结点(递归实现)
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);    // 右子树查找
}

插入

若原二叉排序树为空，则直接插入结点；否则，若关键字k小于根结点，则插入到左子树，若关键字k大于结点只，则插入到右子树

// 在二叉排序树插入关键字为k的新结点(递归实现)
int BST_Insert(BSTree &T,int k){
    if (T==NULL){    // 原树为空，新插入的结点为根结点
        T=(BSTree)malloc(sizeof(BSTNode));
        T->key=k;
        T->lchild=T->rchild=NULL;
        return 1;
    }
    else if(k==T->key)    // 树中存在相同关键字结点,插入失败
        return 0;
    else if(k<T->key)    // 插入到T的左子树
        return BST_Insert(T->lchild,k);
    else    // 插入到T的右子树
        return BST_Insert(T->rchild,k);
}

// 在二叉排序树插入关键字为k的新结点
int BST_Insert(BSTree &T,int key){
    BSTree p = T;    // 拷贝结点，目的是不影响原结点
    BSTree parent = NULL;    // 父结点
    while (p!=NULL){    // 循环遍历，直到树的尽头
        if (key==p->key)    // 结点相同插入失败
            return 0;
        parent = p;    // 记录父结点
        if (key < T->key) T=T->lchild;
        else T=T->rchild;
    }
    BSTree new_node =(BSTree)malloc(sizeof(BSTNode));
    new_node->key=k;
    new_node->lchild=new_node->rchild=NULL;
    if (parent == NULL){
        // 如果parent为NULL，说明原树为NULL
        T = new_node;
    }
    else if (key < parent->key){
        // 当前key小于父结点左子树的key
        parent->lchild = new_node
    }else
        parent->rchild = new_node;
    return 1;
}

构造

void Creat_BST(BSTree &T,int str[],int n){
    T=NULL;    // 初始时T为空树
    int i=0;
    while(i<n){    // 依次将每个关键字插入到二叉排序树中
        BST_Insert(T,str[i]);
        i++;
    }
}

删除

先搜索找到目标结点：

1. 若被删除结点z是叶结点，则直接删除，不会破坏二叉排序树的性质
2. 若结点z只有一棵左子树或右子树，则让z的子树称为z父结点的子树，替代z的位置(因为z被删除了，子树前移)
3. 若结点z有左、右两棵子树，则令z的直接后继(或直接前驱)代替z，然后从二叉排序树中删去这个直接后继(或直接前驱)，这样就转换成了第一或第二种情况

平衡二叉树

平衡二叉树(Balanced Binary Tree)，简称平衡树(AVL树)---树上任一结点的左子树和右子树的高度之差不超过1

结点的平衡因子=左子树高-右子树高

只要有任一结点的平衡因子绝对值大于1，就不是平衡二叉树

在二叉排序树上插入结点后，查找路径上的所有结点都可能受到影响，从插入点往回找到第一个不平衡结点，调整以该结点为根的子树

每次调整的都是最小不平衡子树

在插入操作中，只要将最小不平衡子树调整平衡，则其他祖先结点都会恢复平衡

调整最小不平衡子树

LL

在A的左孩子的左子树中插入导致不平衡

LL平衡旋转(右单旋转)。由于在结点A的左孩子(L)的左子树上插入了新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要一次向右旋转的操作。将A的左孩子B向右上旋转代替A成为根结点，将A结点向右下旋转成B的左子树的根结点，而B的原右子树，则作为A结点的左子树

具体如图所示，其实就是将B作为了根结点，A变为了它的右子树，剩下的结点根据大小顺序来进行排列即可

RR

在A的右孩子的右子树中插入导致不平衡

和LL几乎一样，只是换了个方向

代码思路

包含LL及RR

LR

在A的左孩子的右子树中插入导致不平衡

如上图所示，我们向左孩子的右结点插入了相应的新结点，会破坏原父结点的平衡因子

接着我们将BR看作C，那么CL是左孩子，CR是右孩子

RL

在A的右孩子的左子树中插入导致不平衡

LR和RL是类似的

插入&删除

平衡二叉树的插入操作：

• 插入新结点后，要保持二叉排序树的特性不变(左<中<右)
• 若插入新结点导致不平衡，则需要调整平衡(LL、RR、LR、RL)

平衡二叉树的删除操作也是如此

具体步骤如下：

1. 删除结点(方法同“二叉排序树”)
   • 若删除的结点是叶子，直接删
   • 若删除的结点只有一个子树，用子树顶替删除位置
   • 若删除的结点有两棵子树，用前驱(或后继)结点顶替，并转回为对前驱(后继)结点的删除
2. 一路向北找到最小不平衡子树，找不到就完结撒花
3. 找最小不平衡子树下，“个头”最高的儿子、孙子
4. 根据孙子的位置，调整平衡
   • 孙子在LL：儿子右单旋
   • 孙子在RR：儿子左单旋
   • 孙子在LR：孙子先左旋，再右旋
   • 孙子在RL：孙子先右旋，再左旋
5. 如果不平衡继续向上传导，继续②
   • 对最小不平衡子树的旋转可能导致树变矮，从而导致上层祖先不平衡(不平衡向上传递)

红黑树

概念

平衡二叉树AVL：插入/删除 很容易破坏“平衡”特性，需要频繁调整树的形态。

如插入操作导致不平衡，则需要先计算平衡因子，找到最小的不平衡子树，再进行LL/RR/LR/RL 调整

红黑树RBT：插入/删除 很多时候不会破坏“红黑”特性，无需频繁调整树的形态。即便需要调整，一般都可以在常数级时间内完成

平衡二叉树：适用于以查为主、很少插入/删除的场景

红黑树：适用于频繁插入、删除的场景，实用性更强

红黑树是二叉排序树：左子树结点值<=根结点值<=右子树结点值

特点

1. 每个结点是红色的，或是黑色的
2. 根结点是黑色的
3. 叶结点(外部结点、NULL结点、失败结点)均是黑色的
4. 不存在两个相邻的红结点（即红结点的父节点和孩子结点均是黑色）
5. 对每个结点，从该节点到任一叶结点的简单路径上，所含黑结点的数目相同

struct RBnode{    // 红黑树的结点定义
    int key;    // 关键字值
    RBnode* parent;    // 父节点指针
    RBnode* lChild;    // 左孩子指针
    RBnode* rChild;    // 右孩子指针
    int color;    // 结点颜色，如：可用0/1 表示 黑/红，也可使用枚举型enum表示颜色
}

结点的黑高（bh）---从某结点触发(不含该结点)到达任一空叶结点的路径上黑结点总数

插入

• 先查找，确定插入位置(原理同二叉排序树)，插入新结点
• 新结点是根---黑色
• 新结点非根---红色
  • 若插入新结点后依然满足红黑树定义，则插入结束
  • 若插入新结点后不满足红黑树定义，需要调整，使其重新满足红黑树定义
    • 如何调整：看新结点叔叔的颜色
    • 黑叔：旋转+染色
      • LL型：右单旋，父换爷+染色
      • RR型：左单旋，父换爷+染色
      • LR型：左、右双旋，儿换爷+染色
      • RL型：右、左双旋，儿换爷+染色
    • 红叔：染色+变新
      • 叔父爷染色，爷变新结点

删除

重要考点

B树

概念

策略：m叉查找树中，规定除了根节点外，任何结点至少有[m/2]个分叉，即至少含有[m/2]-1个关键字

若每个结点内关键字太少，导致树变高，要查找更多层结点，效率低

查找规则是：在一层数组内查找，如果没找到就根据key是大还是小，往下面的树继续查找，小是左子树，大是右子树，如此循环，并且，如果整个树只有1个元素，那么根节点只有两个分叉

B树示例图如下

B树，又称多路平衡查找树，B树中所有结点的孩子个数的最大值称为B树的阶，通常用m表示。一棵m阶B树或为空树，或为满足如下特性的m叉树：

1. 树中每个结点至多有m棵子树，即至多含义m-1个关键字
2. 若根结点不是终端结点，则至少有两棵子树
3. 除根结点外的所有非叶结点至少有[m/2]棵子树，即至少含义[m/2]-1个关键字
4. 所有叶结点都出现在同一层次上，并且不带信息（可以视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空）

失败结点通常称为叶子结点，含义实际数据的被称为终端结点

比如五叉查找树，相当于五阶B树，根据最大分叉来定

问题：含n个关键字的m阶B树，最小高度、最大高度是多少？

算B树的高度一般不包括叶子结点

最小高度---让每个结点尽可能的满，有m-1个关键字，m个分叉

最大高度就需要让各层分叉尽可能的少

插入&删除

没超过上限就正常插入

在插入key后，若导致原结点关键字数超过上限，则从中间位置[m/2]将其中的关键字分为两部分，左部分包含的关键字放在原结点中，右部分包含的关键字放在新结点中，中间位置[m/2]的结点插入原结点的父结点

其实就是进行一个分裂操作

若被删除关键字在非终端节点，则用直接前驱或直接后继来替代被删除的关键字

直接前驱：当前关键字左侧指针所指子树中“最右下”的元素

直接后继：当前关键字右侧指针所指子树中“最左下”的元素

兄弟够借。若被删除关键字所在结点删除前的关键字个数低于下限，且与此结点右(或左)兄弟结点的关键字个数还很宽裕，则需要调整该结点、左(右)兄弟结点及其双亲结点(父子换位法)

兄弟不够借。若被删除关键字所在结点删除前的关键字个数低于下限，且此时与该结点相邻的左、右兄弟结点的关键字个数均=[m/2]-1，则将关键字删除后与左(右)兄弟结点及双亲结点中的关键字进行合并

在合并过程中，双亲结点中的关键字个数会减1。若其双亲结点是根结点且关键字个数减少至0（根结点关键字个数为1时，有2棵子树），则直接将根结点删除，合并后的新结点称为根；若双亲结点不是根结点，且关键字个数减少到[m/2]-2，则又要与它自己的兄弟结点进行调整或合并操作，并重复上述步骤，直至符合B树的要求为止

B+树

如图所示

一棵m阶的B+树需要满足下列条件：

1. 每个分支结点最多有m棵子树(孩子结点)
2. 非叶根结点至少有两棵子树，其他每个分支结点至少有[m/2]棵子树
3. 结点的子树个数与关键字个数相同
4. 所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来
5. 所有分支结点中仅包含它的各个子结点中关键字的最大值及指向其子结点的指针

我们一般将最下面的结点称为叶子结点

非叶根结点：如果一个B+树，只有一个根结点，那么它是根结点也是叶子结点，如果它不止一个根结点，就说明它是非叶根结点

B+树中，无论查找成功与否，最终一定都要走到最下面一层结点，因为上面的分支结点只是一个指针，并不能代表叶子结点所对应的记录

m阶B树和B+树的区别

B树

• 结点中的n个关键字对应n+1棵子树
• 根结点的关键字数n∈[1,m-1]
• 其他结点的关键字数n∈[<m/2是向上取整的>[m/2]-1,m-1]
• 在B树中，各结点中包含的关键字是不重复的
• B树的结点中都包含了关键字对应的记录的存储地址

B+树

• 根结点的关键字数n∈[1,m]
• 其他结点的关键字数n∈[<m/2是向上取整的>[m/2],m]
• 在B+树中，叶结点包含全部关键字，非叶结点中出现过的关键字也会出现在叶结点中
• 叶结点包含信息，所有非叶结点仅起索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址
• 在B+树中，非叶结点不含有该关键字对应记录的存储地址。可以使一个磁盘块可以包含更多个关键字，使得B+树的阶更大，树高跟矮，读磁盘次数更少，查找更快

散列表

概念

散列表(哈希表，Hash Table)：是一种数据结构。特点是：可以根据数据元素的关键字计算出它在散列表中的存储地址

散列函数(哈希函数)：Addr=H(key)建立了“关键字”->“存储地址”的映射关系

冲突(碰撞)：在散列表中插入一个数据元素时，需要根据关键字的值确定其存储地址，若该地址已经存储了其他元素，则称这种情况为“冲突(碰撞)”

同义词：若不同的关键字通过散列函数映射到同一个存储地址，则称它们为“同义词”

如何减少冲突？

• 构造更适合的散列函数，让各个关键字尽可能地映射到不同的存储位置，从而减少冲突

如何处理冲突

• 拉链法（又称链接法、链地址法）：把所有“同义词”存储在一个链表中

• 开放定址法：如果发生冲突，就给新元素找另一个空闲位置

构造散列函数

注意点

设计散列函数时应该注意什么？

1. 定义域必须涵盖所有可能出现的关键字。
2. 值域不能超出散列表的地址范围
3. 尽可能减少冲突。散列函数计算出来的地址应尽可能均匀分布在整个地址空间
4. 散列函数应尽量简单，能够快速计算出任意一个关键字对应的散列地址

对应反例如下

除留余数法

H(key) = key % p

散列表表长为m，取一个不大于m但最接近或等于m的质数p

注：质数又称素数。指除了1和此整数自身外，不能被其他自然数整除的数，和素数相对的是合数

适用场景：较为通用，只要关键字是整数即可

原因：对质数取余，可以分布更均匀，从而减少冲突

• 对合数取余，散列地址分布不均匀，易发生冲突
• 对质数取余，散列地址分布均匀，不易发生冲突

直接定址法

H(key) = key or H(key) = a*key + b

其中，a和b是常数。这种方法计算最简单，且不会产生冲突。若关键字分布不连续，空位较多，则会造成存储空间的浪费

适用场景：关键字分布基本连续

数字分析法

选取数码分布较为均匀的若干位作为散列地址

设关键字是r进制数(如十进制数)，而r个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀一些，每种数码出现的机会均等；而在某些位上分布不均匀，只有某几种数码经常出现，此时可选取数码分布较为均匀的若干位作为散列地址

适用场景：关键字集合已知，且关键字的某几个数码位分布均匀

平方取中法

取关键字的平方值的中间几位作为散列地址

具体取多少位要视实际情况而定。这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀

适用场景：关键字的每位取值都不够均匀

拉链法

拉链法（又称链接法、链地址法）：把所有同义词存储在一个链表中

如何在散列表（拉链法解决冲突）中插入一个新元素？

1. 结合散列函数计算新元素的散列地址
2. 将新元素插入散列地址对应的链表（可用头插法，也可用尾插法）

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

开放定址法

概念

开放定址法：如果发生冲突，就给新元素找另一个空闲位置

为什么叫“开放定址”？---一个散列地址，既对同义词开放，也对非同义词开放

思路：需确定一个“探测的顺序”，从初始散列地址出发，去寻找下一个空闲位置

eg：d0=0，d1=1，d2=-1，d3=2，d4=-2，......

注：di表示第i次发生冲突时，下一个探测地址与初始散列地址的相对偏移量

那么我们如何找到下一个空闲位置

Hi=(H(key) + di) % m

• Hi：发生第i次冲突时的散列地址
• H(key)：初始散列地址
• di：偏移量
• m：散列表表长

注意：采用“开放定址法”时，删除元素不能简单地将被删元素的空间置为空，否则将截断在它之后的探测路径，可以做一个“已删除”标记，进行逻辑删除

带来的问题：查找效率低下，散列表看起来很满，实则很空

线性探测法

di=0,1,2,3,...，m-1

带入上述公式->Hi=(H(key) + di) % m

依次向后推断，插入，直到不冲突

而查找也是类似的，带入公式依次向后找

平方探测法

查找依然是类似的

带入公式即可

双散列法

伪随机序列法

di是一个伪随机序列，由题目可知di=0,5,3,11,...

这里的随机序列是人为设计的

排序

概念

排序，字面意思，将各元素按关键字递增/或递减顺序重新排列

稳定性：关键字相同的元素经过排序后相对顺序是否会改变

排序分为内部排序和外部排序

• 内部排序：数据都在内存中
• 外部排序：数据太多，无法全部放入内存

插入排序

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

// 直接插入排序
void InsertSort(int A[],int n){
    int i,j,temp;
    for(i=1;i<n;i++){    // 将各元素插入已排好序的序列中
        if(A[i] < A[i-1]){    // 如果A[i]关键字小于前驱
            temp=A[i];    // 暂存A[i]
            for(j=i-1;j>=0 && A[j]>temp;--j){    // 检查所有前面已排好序的元素
                A[j+1]=A[j];    // 所有大于temp的元素都向后挪位
            }
            A[j+1]=temp;
        }
    }
}

// 直接插入排序(带哨兵)
void InsertSort(int A[],int n){
    int i,j;
    for(i=2;i<=n;i++){    // 依次将A[2]~A[n]插入到前面已排序序列
        if(A[i]<A[i-1]){    // 若A[i]关键码小于前驱，将A[i]插入有序表
            A[0]=A[i];    // 复制为哨兵，A[0]不存放元素
            for(j=i-1;A[0]<A[j];--j){    // 从后往前查找待插入位置
                A[j+1]=A[j];    // 向后挪位
            }
            A[j+1]=A[0];    // 复制到插入位置
        }
    }
}

想优化这个算法比较简单

因为前面的序列都是排好序的，所以可以通过折半查找进行更高效的查找

当low>high时，应将[low,i-1]内的元素全部右移，接着将哨兵处A[0]复制到low所指位置

其实就是后移，将内容迁入即可

当A[mid]=A[0]时，为了保证算法的“稳定性”，应继续在mid所指位置右边寻找插入位置

希尔排序

希尔排序：先追求表中元素部分有序，再逐渐逼近全局有序

先将待排序表分割成若干形如L[i,i+d,i+2d,...,i+kd]的“特殊子表”，对各个子表分别进行直接插入排序。缩小增量d，重复上述过程，直到d=1为止

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[i]插入有序增量子表
                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];    // 插入
            }
        }
    }    
}

冒泡排序

基于“交换”的排序：根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置

从后往前（或从前往后）两两比较相邻元素的值，若为逆序(即A[i-1]>A[i])，则交换它们，直到序列比较完。称这样过程为“一趟”冒泡排序

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

// 交换
void swap(int &a,int &b){
    int temp = a;
    a = b;
    b = temp;
}

// 冒泡排序
void BubbleSort(int A[],int n){
    for(int i = 0;i<n-1;i++){
        bool flag = false;
        for(int j=n-1;j>i;j--){
            if(A[j-1]>A[j]){
                swap(A[j-1],A[j]);
                flag=true;
            }
        }
        if(!flag)
            return;
    }
}

快速排序

算法思想：在待排序表L[1...n]中任取一个元素pivot作为枢轴（或基准，通常取首元素），通过一趟排序将待排序表划分为独立的两部分L[1...k-1]和L[k+1...n]，使得L[1...k-1]中所有元素小于pivot，L[k+1...n]中的所有元素大于等于pivot，则pivot放在了其最终位置L(k)上，这个过程称为一次“划分”。然后分别递归地对两个子表重复上述过程，直至每部分只有一个元素或空为止，即所有元素放在了其最终位置上

简单来说，就是将比pivot小的元素放到pivot左边，而比pivot大的元素放到pivot的右边

当然，这是有规律的，如果检测到比pivot小的元素，先放到对应的low指针位置，让low指针右移

直到找到更大的元素，先放到对应的high指针位置，再转为high指针，让high左移，继续判断

如果本身就是在high指针并且元素比pivot更大，就不用移动，如果是在low指针且比pivot更小，那么也不用移动

相当于high和low互相切换，直到low=high

此时pivot找到了最终的位置，接着就对左右子表继续进行操作即可

// 用第一个元素将待排序序列划分为左右两个部分
int Partition(int A[],int low,int high){
    int pivot=A[low];    // 第一个元素作为枢轴
    while(low < high){    // 用low、high搜索枢轴的最终位置
        while(low<high && A[high] >= pivot) --high;
        A[low]=A[high];    // 比枢轴小的元素移动到左端
        while(low<hight && A[low] <= pivot) ++low;
        A[high]=A[low];    // 比枢轴大的元素移动到右端
    }
    A[low]=pivot;    // 枢轴元素存放到最终位置
    return low;    // 返回枢轴最终位置
}

// 快速排序
void QuickSort(int A[],int low,int high){
    if(low<high){    // 递归跳出的条件
        int pivotpos=Partition(A,low,high);    // 划分
        QuickSort(A,low,privotpos-1);    // 左子表
        QuickSort(A,privotpos+1,high);    // 右子表
    }
}

简单选择排序

每一趟在待排序元素中选取关键字最小的元素加入有序子序列

// 简单选择排序
void SelectSort(int A[],int n){
    for(int i=0;i<n-1;i++){    // 一共进行n-1趟
        int min=i;    // 记录最小元素位置
        for(int j=i+1;j<n;j++)    // 在A[i...n-1]中选择最小的元素
            if(A[j]<A[min]) min = j;    // 更新最小元素位置
        if(min != i) swap(A[i],A[min]);    // 移动元素
    }
}

堆排序

概念

若n个关键字序列[1...n]满足下面某一条性质，则称为堆(Heap)：

1. 若满足：L(i)>=L(2i)且L(i)>=L(2i+1) (1<=i<=n/2) --- 大根堆(大顶堆)
2. 若满足：L(i)<=L(2i)且L(i)<=L(2i+1) (1<=i<=n/2) --- 小根堆(小顶堆)

可能直接理解不是很明白，直接看图

逻辑层面上相当于是二叉树的形式，左子树是L(2i)，右子树是L(2i+1)

大根堆：完全二叉树中，根>=左、右

小根堆就是反过来了

建立大根堆

思路：把所有非终端结点都检查一遍，是否满足大根堆的要求，如果不满足，则进行调整

检查当前结点是否满足根>=左、右

若不满足，将当前结点与更大的一个孩子互换

• i的左孩子 --- 2i
• i的右孩子 --- 2i+1
• i的父节点 --- i/2(向上取整)

若元素互换破坏了下一级的堆，则采用相同的方式继续往下调整(小元素不断“下坠”)

// 建立大根堆
void BuildMaxHeap(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){    // 沿key较大的子结点向下筛选,2*k是指向左孩子
        if(i<len && A[i] < A[i+1])    // i<len保证当前结点是存在右兄弟的
            i++;    // 取key较大的子结点下标
        if(A[0] >= A[i]) break;
        else{
            A[k]=A[i];    // 将A[i]调整到双亲结点上
            k=i;    // 修改k值，以便向下筛选
        }
    }
    A[k]=A[0];
}

// 堆排序的完整逻辑
void HeapSort(int A[],int len){
    BuildMaxHeap(A,len);    // 初始建堆
    for(int i=len;i>1;i--){    // n-1趟的交换和建堆过程
        swap(A[i],A[1]);    // 堆顶元素和堆底元素互换
        HeadAdjust(A,1,i-1);    // 把剩余的待排序元素整理成堆
    }
}

插入删除

对于小根堆，新元素放到表尾，与父节点对比，若新元素比父节点更小，则二者互换。新元素就这样一路上升，直到无法继续上升为止

被删除的元素用堆底元素替代，然后让该元素不断“下坠”，直到无法下坠为止

归并排序

归并：把两个或多个已经有序的序列合并成一个

将i和j指向对应的数组所指元素位置初始位置->0，选择更小的一个放入k所指位置，并让其指针后移

当指针超出后，说明一侧数组已经全部存放完毕，直接将另一侧数组的结果存入剩下的空间内

k是由两个数组大小合并新建的一个数组的初始位置

两个数组合并叫2路归并，四个数组合并叫4鲁归并

4路归并 --- 每选出一个小元素注意需要对比关键字3次

结论：m路归并，每选出一个元素需要对比关键字m-1次

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

// 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];    // 将A中所有元素复制到B中
    for(i=low,j=mid+1,k=i;i<=mid && j<=high;k++){
        if(B[i] <= B[j])
            A[k]=B[i++];    // 将极小值复制到A中
        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);    // 归并
    }
}

归并排序会递归的将内部的相邻子元素一一排序，使其成为有序序列，最后对有序序列排序

基数排序

基数排序其实很简单

先构造一个辅助数组，存储0~9的数字

然后根据个、十、百位来依次进行比对，最终得到结果 $$ 基数排序得到递减序列的过程如下 \ 初始化：设置r个空队列，Q{r-1}，Q{r-2}，...，Q0 按照各个关键字位 权重递增的次序(个、十、百)\ 对d个关键字位分别做“分配”和“收集”\ 分配：顺序扫描各个元素，若当前处理的关键字位=x，则将元素插入Q_x队尾\ 收集：把Q{r-1}、Q_{r-2}，...，Q_0各个队列中的结点依次出队并链接 $$ 基数排序说起来比较抽象和麻烦，建议直接看视频简单点：https://www.bilibili.com/video/BV1b7411N798?spm_id_from=333.788.player.switch&vd_source=b39debcbe1026bb04f6c19f233bab974&p=99(基数排序)

计数排序

实现

上图说明了计数排序元素根据辅助数组计算元素出现次数及通过C[i]比对前置元素计算对应情况的累积元素

而基于上述数据进行的排序其实非常巧妙

我们会再声明一个B数组，用于存储最终的结果，B数组大小和A数组一样，可以看做是空的A数组

基于A数组从后往前进行排序，保证计数排序算法的稳定性

简单推理部分算法情况

首先找到A[7]，也就是3,3在C中是7，也就是说它属于第7个元素，那么它应该存放在B[6]的位置，B[6]相当于第7个位置

我们可以让B[--i]，也就是7自减后，存到B[6]的位置

接着A[6]，也就是0,0在C中是2，也就是说继续进行这样的操作，B[--i]，也就是2自减后，存到B[1]的位置

以此类推，后面不再赘述

// A是输入数组(待排序数组)
// B是输出数组
// n是A[]的长度
// k是反映A[]的取值范围

// 计数排序
void CountSort(int A[],int B[],int n,int k){
    int i,C[k];    // 辅助数组C的长度取决于待排序元素取值范围[0,k)
    for(i=0;i<k;i++)    // 初始化计数数组
        C[i]=0;
    for(i=0;i<n;i++)    // 遍历待排序数组，统计每个关键字的出现次数
        C[A[i]]++;
    for(i=1;i<k;i++)    // 再次处理辅助数组，统计不大于i的元素个数
        C[i]=C[i]+C[i-1];    // C[i]保存的是小于或等于i个元素个数
    for(i=n-1;i>=0;i--){    // 利用辅助数组C实现计数排序(从后往前处理)
        C[A[i]]=C[A[i]]-1;
        B[C[A[i]]]=A[i];    // 将元素A放在输出数组B[]的正确位置上
    }
}

外部排序

外部排序：数据元素太多，无法一次全部读入内存进行排序

具体看视频吧，有点抽象

https://www.bilibili.com/video/BV1b7411N798?spm_id_from=333.788.player.switch&vd_source=b39debcbe1026bb04f6c19f233bab974&p=101

败者树

优化归并问题

败者树---可视为一棵完全二叉树(多了一个头头)

k个叶结点分别是当前参加比较的元素，非叶子结点用来记忆左右子树中的“失败者”，而让胜者往上继续进行比较，一直到根结点

置换-选择排序

晕倒：https://www.bilibili.com/video/BV1b7411N798?spm_id_from=333.788.player.switch&vd_source=b39debcbe1026bb04f6c19f233bab974&p=103

最佳归并树

最后一节了，不记了：https://www.bilibili.com/video/BV1b7411N798?spm_id_from=333.788.player.switch&vd_source=b39debcbe1026bb04f6c19f233bab974&p=104

总结

很有精神的课，学起来很累，麻蛋，算法真他娘的不是人学的，拜拜了您嘞！