数据结构（基础）笔记

第一章：绪论

1.基本概念

数据是信息的载体是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

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

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

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。（没有官方统一定义）

数据结构三要素：逻辑结构；数据的运算；物理结构（存储结构）

数据类型是一个值的集合和定义在此集合上的一组操作的总称。

1. 原子类型。其值不可再分的数据类型。
2. 结构类型。其值可以再分解为若干成分（分量）的数据类型。

抽象数据类型描述了数据的逻辑结构和抽象运算，通常用【数据对象、数据关系、基本操作集】这样的三元组来表示，从而构成一个完整的数据结构定义

算法是对特定问题求解步骤的一种描述。

算法的特性：

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

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

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

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

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

“好“算法的特质：

①正确性。算法应能够正确地解决求解问题。

②可读性。算法应具有良好的可读性，以帮助人们理解。

③健壮性。输入非法数据时，算法能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。

④高效率与低存储量需求。

2.算法的时间复杂度

定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。

3.算法的空间复杂度

定义：空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。

第二章：线性表

1.线性表

1.1 线性表的定义

线性表—具有相同数据类型的n（n≥0）个数据元素的有限序列，其中n为表长，n为0时线性表是一个空表。

1.2 基本操作

1.2.1 InitList(&L)

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

1.2.2 DestroyList(&L)

销毁操作。销毁线性表，并释放线性表L所占用的内存空间。

1.2.3 ListInsert(&L,i,e)

插入操作。在表L中的第i个位置上插入指定元素e。

1.2.4 ListDelete(&L,i,&e)

删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。

1.2.5 LocateElem(L,e)

按值查找操作。在表L中查找具有给定关键字值的元素。

1.2.6 GetElem(L,i)

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

1.2.7 其他常用操作

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

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

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

Tips：

①对数据的操作（记忆思路）——创销、增删改查

②C语言函数的定义—— <返回值类型> 函数名(<参数1类型>参数1，<参数2类型>参数2，……)

③实际开发中，可根据实际需求定义其他的基本操作

④函数名和参数的形式、命名都可改变（Reference：严蔚敏版《数据结构》）

⑤什么时候要传入引用“&”——对参数的修改结果需要“带回来”

2.顺序表

2.1 顺序表的定义

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

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

2.2 顺序表的实现

静态分配 && 动态分配

//静态分配
typedef struct{
    int data[10];  //用静态的数组存放数据元素
    int length;
}SqList;
void InitList(SqList &L){  //初始化一个顺序表
    for(int i=0;i<10;i++){
        L.data[i]=0;
    }
    L.length=0;
}

//动态分配
typedef struct{
    int *data;
    int MaxSize;
    int length;
}SeqList;
void IncreaseSize(SeqList &L,int len){  //增加动态数组的长度
    int *p = L.data;
    //动态申请内存空间
    //malloc函数返回一个指针，需要强制转型为你定义的数据元素类型指针
    //malloc函数头文件<stdlib.h>
    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;
    free(p);
}

2.3 顺序表的特点

① 随机访问 ，即可以在O(1)时间内找到第i个元素。

②存储密度高，每个节点只存储数据元素

③拓展容量不方便（即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高）

④插入、删除操作不方便，需要移动大量元素

2.4 顺序表的基本操作

2.4.1 插入

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

void ListInsert(SqList &L,int i,int e){
    for(int j=L.length;j>=i;j--){
        L.data[j] = L.data[j-1];
    }
    L.data[i-1] = e;
    L.length++;
}
//时间复杂度:O(n)

2.4.2 删除

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

void ListDelete(SqList &L,int i,int &e){
	e = L.data[i-1];
	for(int j=i;j<L.length;j++){
		L.dara[j-1] = L.data[j];
	}
	L.length--;
}
//时间复杂度:O(n)

2.4.3 按值查找

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

//在顺序表L中查找第一个元素值等于e的元素，并返回其位序
int LocateElem(SqList L,int e){
    for(int i=0;i<L.length;i++){
        if(L.data[i]==e){
            return i+1;  //返回位序
        }
    }
    return 0;
}
//时间复杂度:O(n)

2.4.4 按位查找

GetElem(L,i)—获取表L中第i个位置的元素的值。

int GetElem(SqList L,int i){
    return L.data[i-1];
}
//时间复杂度:O(1)

3.单链表

3.1单链表的定义

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

优点：不要求大片连续空间，改变容量方便

缺点：不可随机存取，要耗费一定空间存放指针

struct LNode{            //定义单链表结点类型
    int data;            //每个节点存放一个数据元素
    struct LNode *next;  //指针指向下一个结点
};
struct LNode *p = (struct LNode *)malloc(sizeof(struct Lnode));

//为了方便增加结点，可以用typedef来重命名
//把struct LNode重命名为LNode，用LinkList来表示指向struct LNode的指针
//LNode *L; 和 LinkList L；效果一样，但前者强调这是个结点，后者强调这是个单链表
typedef struct LNode{
    int data;
    struct LNode *next;
}LNode,*LinkList;

//初始化一个空的单链表（不带头结点）
bool InitList(Linklist &L){
    L = NULL;
    return true;
}

//初始化一个空的单链表（带头结点）
bool InitList(Linklist &L){
    L = (LNode *)malloc(sizeof(LNode)); //分配一个头结点
    if(L=NULL){
        return false;
    }
    L->next = NULL;
    return true;
}

3.2单链表的基本操作

3.2.1 插入

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

//按位序插入（带头结点）
bool ListInsert(LinkList &L,int i,int 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){ //i值不合法
        return false;
    }
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

////按位序插入（不带头结点）
bool ListInsert(LinkList &L,int i,int e){
    if(i<1){
        return false;
    }
    if(i==1){   //插入第1个结点的操作与其他结点操作不同
        LNode *s = (LNode *)malloc(sizeof(LNode));
        s->data = e;
        s->next = L;
        L = s;
        return true;
    }
    LNode *p;
    int j = 1;
    p = L;
    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;
}

//指定结点的后插操作
bool InsertNextNode(LNode *p,int 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;
}

//指定结点的前插操作
 bool InsertPriorNode(LinkList L,LNode *p,int 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;
}

3.2.2 删除

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

////按位序删除（带头结点）
bool ListDelete(LinkList &L,int i,int &e){
    if(i<1){
        return false;
    }
    LNode *p;
    int j=0;
    p = L;
    while(p!=NULL&&j<i-1){
        p=p->next;
        j++;
    }
    if(p==NULL){
        return false;
    }
    LNode *q = p->next;  //q指向被删除结点
    e = q->data;         //e返回删除元素的值
    p->next = q->next;   //将*q结点从链中断开
    free(q);             //释放结点存储空间
    return true;
}

//删除指定结点
//如果p是最后一个结点，就只能从表头开始依次寻找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;        //将*q结点从链中断开
    free(q);                  //释放后继结点存储空间
    return true;
}

3.2.3 查找

//按位查找，返回第i个元素（带头结点）
LNode *GetElem(LinkList L,int i){
    if(i<0){
        return NULL;
    }
    LNode *p;
    int j = 0;
    p = L;
    while(p!=NULL&&j<i){
        p=p->next;
        j++;
    }
    return p;
}

//按值查找，找到数据域==e的结点
LNode *LocateElem(LinkList L,int e){
    LNode *p = L->next;  //从第1个结点开始查找数据域为e的结点
    while(p!=NULL&&p->data!=e){
        p = p->next;
    }
    return p;
}

3.3 单链表的建立

核心就是初始化操作、指定结点的后插操作

3.3.1 尾插法

bool InitList(Linklist &L){
    L = (LNode *)malloc(sizeof(LNode));
    if(L=NULL){
        return false;
    }
    L->next = NULL;
    return true;
}
LinkList List_TailInsert(LinkList &L){
    int x;
    L = (LinkList)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;                             //r指向新的表尾结点
        scanf("%d",&x);
    }
    r->next = NULL;                        //尾结点指针置空
    return L;
}

3.3.2 头插法

bool InitList(Linklist &L){
    L = (LNode *)malloc(sizeof(LNode));
    if(L=NULL){
        return false;
    }
    L->next = NULL;
    return true;
}
LinkList List_HeadInsert(LinkList &L){
    LNode *s;
    int x;
    L = (LinkList)malloc(sizeof(LNode));   //建立头结点
    L->next = NULL;                        //初始为空链表
    scanf("%d",&x);                        //输入结点的值
    while(x!=9999){                        //输入9999表示结束
        s = (LNode)malloc(sizeof(LNode));
        s->data = x; 
        s->next = L->next; 
        L->next = s;                       //将新结点插入表中，L为头指针
        scanf("%d",&x);
    }
    return L;
}

4.双链表

双链表就是在单链表的基础上再增加一个指针域。

typedef struct DNode{
    int data;
    struct DNode *prior,*next;   //前驱和后继指针
}LNode,*DinkList;

//双链表的初始化
bool InitList(Dinklist &L){
    L = (DNode *)malloc(sizeof(DNode)); //分配一个头结点
    if(L=NULL){
        return false;
    }
    L->prior = NULL;                    //头结点的prioe永远指向NULL
    L->next = NULL;                     //头结点之后暂时没有结点
    return true;
}

//双链表的插入
//在p结点后插入s节点
bool InsertNextNode(DNode *p,DNode *s){
    if(p==NULL||s==NULL){
        return false;
    }
    s->next = p->next;
    if(p->next!=NULL){
        p->next->prior = s;
    }
    s->prior = p;
    p->next = s;
    return true;
}

//双链表的删除
bool DeleteNextNode(DNode *p){
    if(P==NULL){
        return false;
    }
    DNode *q = p->next;
    if(q==NULL){
        return false;
    }
    if(q->next!=NULL){
        q->next->prior=p;
    }
    free(q);
    return true;
}

5.循环链表

5.1 循环单链表

循环单链表：表尾结点的next指针指向头结点。

普通单链表无法找到前驱结点，循环单链表可以找到其他任何一个结点

typedef struct LNode{
    int 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;
}

5.2 循环双链表

循环双链表：表头结点的prior指向表尾结点，表尾结点的next指向头结点。

typedef struct DNode{
    int data;
    struct DNode *prior,*next;
}LNode,*DinkList;

//循环双链表的初始化
bool InitList(Dinklist &L){
    L = (DNode *)malloc(sizeof(DNode));
    if(L=NULL){
        return false;
    }
    L->prior = L;
    L->next = L;
    return true;
}

6.静态链表

单链表：各个结点在内存中星罗棋布、散落天涯。

静态链表：分配一整片连续的内存空间，各个结点集中安置。相当于用数组的方式实现的链表。

优点：增、删操作不需要大量移动元素

缺点：不能随机存取，只能从头结点开始依次往后查找；容量固定不可变

适用场景：

①不支持指针的低级语言；

②数据元素数量固定不变的场景（如操作系统的文件分配表FAT）

#define MaxSize 10  //静态链表最大长度
struct Node{             //静态链表结构类型的定义
    int data;       //存储数据元素
    int next;       //下一个元素的数组下标
};
void testLinkList(){
    struct Node a[MaxSize];
    //......后续代码
}

7.顺序表和链表的比较

逻辑结构

都属于线性表，都是线性结构。

存储结构

顺序表（顺序存储）：

优点：支持随机存取、存储密度高

缺点：大片连续空间分配不方便，改变容量不方便

链表（链式存储）：

优点：离散的小空间分配方便，改变容量方便

缺点：不可随机存取，存储密度低

使用场景

链表——表长难以预估、经常要增加/删除元素

顺序表 ——表长可预估、查询（搜索）操作较多

第三章：栈和队列

1.栈

1.1 栈的定义

栈（Stack）—是只允许在一端进行插入或删除操作的线性表。

（特性：后进先出）

空栈—栈中没有任何数据元素。

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

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

1.2 栈的基本操作

栈的基本操作和线性表基本操作类似。（创、销、增、删、查）

InitStack(&S)：初始化栈。构造一个空栈S，分配内存空间。

DestroyStack(&S)：销毁栈。销毁并释放栈S所占用的内存空间。

Push(&S,x)：进栈，若栈S未满，则将x加入使之成为新栈顶。

Pop(&S,&x)：出栈，若栈S非空，则弹出栈顶元素，并用x返回。

GetTop(S,&x)：读栈顶元素。若栈S非空，则用x返回栈顶元素

其他常用操作：

StackEmpty(S)：判断一个栈S是否为空。若S为空，则返回true，否则返回false。

注： 卡特兰数
$$
n个不同元素进栈，出栈元素不同排列的个数为 \frac{1}{n+1}C_{2n}^{n}
$$

1.3 栈的顺序存储实现

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

//初始化栈
void InitStack(SqStack &S){
    S.top = -1;          //初始化栈顶指针
}

//判断栈空
bool StackEmpty(SqStack S){
    if(S.top==-1){
        return true;
    }else{
        return false;
    }
}

//新元素入栈
bool Push(SqStack &S,int x){
    if(S.top==Maxsize-1){
        return false;    //栈满，报错
    }
    S.top = S.top+1;     //指针先加1
    S.data[S.top] = x;   //新元素入栈
    return true;
}

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

//顺序栈大大小不可变，可以用共享栈的方式来提高空间的利用率
//共享栈会定义两个栈顶指针，一个初始为-1，另一个初始为MaxSize

1.4 栈的链式存储实现

链式存储实现的栈本质上就是一个单链表，只不过我们规定只允许在“单链表”的一端进行操作。

typedef struct Linknode{
    int data;
    Struct Linknode *next;
}*Listack;

2.队列

2.1 队列的定义

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

（特性：先进先出）

空队列—队列中没有任何数据元素。

队头—允许删除的一端。

队尾—允许插入的一端。

2.2 队列的基本操作

InitQueue(&Q)：初始化队列，构造一个空队列Q。

DestroyQueue(&Q)：销毁队列。销毁并释放队列Q所占用的内存空间。

EnQueue(&Q,x)：入队，若队列Q未满，将x加入，使之成为新的队尾。

DeQueue(&Q,&x)：出队，若队列Q非空，删除队头元素，并用x返回。

GetHead(Q,&x)：读队头元素，若队列Q非空，则将队头元素赋值给x。

其他常用操作：

QueueEmpty(Q)：判队列空，若队列Q为空返回true，否则返回false。

2.3 队列的顺序存储实现

#define MaxSize 10       //定义队列中元素的最大个数
typedef struct{          
    int dara[MaxSize];   //静态数组存放队列元素
    int front,rear;      //队头指针和队尾指针
}SqQueue;

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

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

//入队
bool EnQueue(SqStack &S,int x){
    if((Q.rear+1)%MaxSize == Q.front){
        return false;                 //队满，报错
    }
    Q.data[Q.rear] = x;               //将x插入队尾
    Q.rear = (Q.rear+1)%MaxSize;      //队尾指针后移
    return true;
}

//出队
bool DeQueue(SqStack &S,int &x){
    if(Q.rear == Q.front){
        return false;    //队列空，报错
    }
    x = x.data[Q.front];
    Q.front = (Q.front+1)%MaxSize;    //队头指针后移
    return true;
}

//用“Q.front = (Q.front+1)%MaxSize”判断队列是否已满会牺牲一个存储空间
//解决办法：

//第一种方法：在队列结构中定义size（初始为0，每次进队size++，出队size--）
//队满条件：size==MaxSize；队空条件：size==0; 

//第二种方法：在队列结构中定义tag（每次删除操作成功时，都令tag=0； 每次插入操作成功时，都令tag=1）
//队满条件：front==rear&&tag==1；队空条件：front==rear&&tag==0 

2.4 队列的链式存储实现

队列和单链表相比，无非是在插入和删除操作中，它只能分别在队尾和队头进行，单链表的插入和删除却是可以在任何一个位置进行的，队列就相当于一个单链表的“阉割”版。

typedef struct Linknode{     //链式队列结点
    int data;
    Struct Linknode *next;
}*LinkNode;
typedef struct{              //链式队列
    LinkNode *front,*rear;   //队列的队头和队尾指针
}LinkQueue;

//初始化队列（带头节点）
void InitQueue(LinkQueue &Q){
    //初始时，front、rear都指向头节点 
    Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));
    Q.front->next=NULL;
}
//判断队列是否为空（带头节点）
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){   //也可以判断Q.rear==NULL
        return true;
    }else{
        return false;
    }
}

//新元素入队（带头节点）
void EnQueue(LinkQueue &Q,int 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,int x){
    LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));
    s->data=x;
    s->next=NULL;
    //不带头结点的队列，第一个元素入队需要特别处理
    if(Q.front==NULL){
        Q.front=s;
        Q.rear=s;
    }else{
        Q.rear->next=s;
    	Q.rear=s;
    }  
}

//队头元素出队（带头节点）
bool DeQueue(LinkQueue &Q,int &x){
    if(Q.front==Q.rear){
        return false;          //判空
    }
    LinkNode *p=Q.front->next;
    x=p->data;                 //用x返回队头元素
    Q.front->next=p->next;     //修改头结点的next指针
    if(Q.rear==p){             //此次是最后一个结点出队
        Q.rear=Q.front;        //修改rear指针
    }
    free(p);                   //释放结点空间
    return true;
}
//队头元素出队（不带头节点）
bool DeQueue(LinkQueue &Q,int &x){
    if(Q.front==NULL){
        return false;          //判空
    }
    LinkNode *p=Q.front;       //p指向这次出队的结点
    x=p->data;                 //用x返回队头元素
    Q.front=p->next;           //修改front指针
    if(Q.rear==p){             //此次是最后一个结点出队
        Q.front=NULL;
        Q.rear=NULL;
    }
    free(p);                   //释放结点空间
    return true;
}

2.5 双端队列

栈：只允许从一端插入和删除的线性表。

队列：只允许从一端插入、另一端删除的线性表。

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

另一方面，双端队列也可以衍生出其他变种

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

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

3.栈的应用

3.1 栈在括号匹配中的应用

在写代码的过程中，代码中的()、[]、{}都是成双成对出现的，这就是所谓的括号匹配。

(((((  )))))

最后出现的左括号最先被匹配（与栈的先进后出异曲同工）

思路：遇到左括号就入栈，遇到右括号就出栈（“消耗”一个左括号）。

#define MaxSize 10
typrdef struct{
    char data[MaxSize];
    int top;
}SqStack;

//初始化栈
void InitStack(SqStack &S)
//判断栈空
bool 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);       //检索完全部括号后，栈空说明匹配成功
}

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

((15/(7-(1+1)))*3)-(2+(1+1))

算术表达式由三个部分组成：操作数、运算符、界限符（必不可少）。

1924年，一个波兰的数学家突发奇想，可以不用界限符也能无歧义地表达运算顺序。

也就是 Reverse Polish notation（逆波兰表达式=后缀表达式）和 Polish notation（波兰表达式=前缀表达式）。

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

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

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

3.2.1 后缀表达式

（1）中缀转后缀

• 中缀转后缀的手算方法：

① 确定中缀表达式中各个运算符的运算顺序

② 选择下一个运算符，按照「左操作数 右操作数 运算符」的方式组合成一个新的操作数

③ 如果还有运算符没被处理，就继续 ②

【为保证运算顺序唯一，建议采用**“左优先”原则**—只要左边的运算符能先计算，就优先算左边的】

• 中缀转后缀的机算方法：

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

从左到右处理各个元素，直到末尾。

可能遇到三种情况：

① 遇到操作数。直接加入后缀表达式。

② 遇到界限符。遇到“(”直接入栈；

遇到“)”则依次弹出栈内运算符并加入后缀表达式，直到 弹出“(”为止。

注意：“(”和”)“不加入后缀表达式。

③ 遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式， 若碰到“(” 或栈空则停止。之后再把当前运算符入栈。

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

（2）后缀表达式的计算

• 后缀表达式的手算方法：

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

【注意两个操作数的左右顺序】

• 后缀表达式的机算方法

最后出现的操作数先被运算，与栈的后进先出的特性吻合。

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

①从左往右扫描下一个元素，直到处理完所有元素

②若扫描到操作数则压入栈，并回到①；否则执行③

③若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到①

【注意先出栈的是“右操作数”】

3.2.2 前缀表达式

（1） 中缀转前缀

• 中缀转前缀的手算方法：

① 确定中缀表达式中各个运算符的运算顺序

② 选择下一个运算符，按照「运算符 左操作数 右操作数」的方式组合成一个新的操作数

③ 如果还有运算符没被处理，就继续 ②

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

• 中缀转前缀的机算方法：

初始化两个栈，分别用于保存暂时还不能确定运算顺序的运算符S1和中间结果S2。

从右往左处理各个元素，直到末尾。

可能遇到三种情况：

① 遇到操作数。直接入S2栈。

② 遇到界限符。遇到“)”直接入S1栈；

遇到“(”则依次弹出S1栈顶运算符并加入S2栈，直到遇到“)”为止。

注意：“(”和”)“不加入前缀表达式。

③ 遇到运算符。依次弹出S1栈中优先级高于当前运算符的所有运算符，并加入S2栈， 若碰到“)” 或栈S1空则停止。之后再把当前运算符入栈S1。

按上述方法处理完所有字符后，将S1栈中剩余运算符依次弹出，并加入S2栈，最后在依次弹出S2栈的元素并输出，加入前缀表达式。

（2） 前缀表达式的计算

• 前缀表达式的手算方法

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

【注意两个操作数的左右顺序】

• 前缀表达式的机算方法

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

①从右往左扫描下一个元素，直到处理完所有元素

②若扫描到操作数则压入栈，并回到①；否则执行③

③若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到①

【注意先出栈的 是“左操作数“】

3.2.3 中缀表达式

（1） 中缀表达式的计算

• 中缀表达式的手算

中缀表达式是人们常用的算术表示方法，手算方法不再赘述。

• 中缀表达式的机算

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

从左往右依次处理各个元素，直到末尾。

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

②若扫描到运算符或界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈

（期间也会弹出运算符，每当弹出一个运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应运算，运算结果再压回操作数栈）

3.3 栈在递归中的应用

递归算法就是递归函数调用自身的过程。在递归过程中，最后被调用的函数最先执行结束，和栈的后进先出类似。

适合用”递归“算法解决：可以把原始问题转换为属性相同，但规模较小的问题，例如阶乘、斐波那契数列······

函数调用时，需要用一个栈存储：

① 调用返回地址

② 实参

③ 局部变量

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

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

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

缺点：效率低，太多层递归可能会导致栈溢出；可能包含很多重复计算

4.队列的应用

队列应用——树的层次遍历

在后面”树“的笔记里会详细介绍

队列应用——图的广度优先遍历

在后面”图“的笔记里会详细介绍

队列在操作系统中的应用

多个进程争抢着使用有限的系统资源时，FCFS（FirstComeFirstService，先来先服务—可用队列实现）是一种常用策略。

例如：CPU资源的分配，打印数据缓冲区

5.特殊矩阵的压缩存储

5.1 数据的存储结构

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

二维数组——”行优先“存储和”列优先“存储

5.2 特殊矩阵

普通矩阵的存储——可以用二维数组存储。

某些特殊矩可以压缩存储空间。

5.2.1 对称矩阵

对阵矩阵：n阶方阵中任意一个元素a(i,j)=a(j,i)

压缩存储策略：只存储主对角线+下三角区 （或主对角线+上三角区），按行优先（或列优先）原则将各元素存入一维数组中。

站在程序员的角度，为了方便使用，可以实现一个**“映射”函数**。

（矩阵下标—>一维数组下标）

5.2.2 三角矩阵

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

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

压缩存储策略：与对称矩阵类似，行优先（或列优先）原则将主对角线和下（上）三角区存入一维数组中，并在最后一个位置存储常量c

5.2.3 三对角矩阵

三对角矩阵，又称带状矩阵： 当|i-j|>1时，有a(i,j)=0 （1≤i,j≤n）

压缩存储策略： 按行优先（或列优先）原则，只存储带状部分

5.2.4 稀疏矩阵

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

压缩存储策略：

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

②链式存储——十字链表法

第四章：串

1.串的定义和基本操作

1.1 串的定义

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

一些术语：

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

主串： 包含子串的串。

字符在主串中的位置： 字符在串中的序号（从1开始计数）。

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

1.2 串的基本操作

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

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

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

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的子串。

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

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

2.串的存储结构

2.1 串的顺序存储

#define MAXSIZE 100
typedef struct{
    char ch[MAXSIZE];   //静态数组实现（定长顺序存储）
    int length;
}SString;

typedef struct{
    char *ch;           //动态数组实现（堆分配存储）
    int length; 
}HString;
Hstring s;
S.ch = (char *)malloc(MAXSIZE * sizeof(char));  //用完需要手动free
S.length = 0;

2.2 串的链式存储

/*
typedef struct StringNode{
    char ch;
    int StringNode *next;
}StringNode,*String;

char一个字符只占1个字节，在32位电脑中，指针占4个字节。
这意味着你用1个字节存储你想要的信息，用4个字节来存储辅助信息，这种情况称之为存储密度低，所以不太建议采用这种方式
*/
typedef struct StringNode{
    //每个结点存储多个字节，为了避免存储密度低
    //如果某些结点填不满，可以用特殊字符填充，例如'#'，'\0'
    char ch[4];
    int StringNode *next;
}StringNode,*String;

2.3 基本操作的实现

以顺序存储的动态数组实现的串为例

#define MAXSIZE 255
typedef struct{
    char *ch;   //动态数组实现（堆分配存储）
    int length;
}HString;

//赋值操作。把串T赋值为chars。
int StrAssign(HString &T, char chars[])
{
	int i = 0;
	for(i = 0;*(chars+i);i++);
    if(i == 0){
        T.ch = NULL;
        T.length = 0;
    }else{
        T.ch = (char *)malloc(i*sizeof(char));
        if(!T.ch){
            printf("内存分配失败！\n");
            return 0;
        }else{
            for(int j = 0;j < i;j++){
                *(T.ch+j) = *(chars+j);
            }
            T.length = i;
        }
    }
    return 0;
}

//复制操作。由串S复制得到串T。
void StringCopy(HString &T, HString &S)
{
    if(T.ch){
        free(T.ch);
        T.ch = NULL;
    }
    T.length = 0;
    T.ch = (char *)malloc(S.length*sizeof(char));
	for (int i = 0; i < S.length; i++){
		T.ch[i] = S.ch[i];
	}
	T.length = S.length;
}

//判空操作。若S为空串，则返回TRUE，否则返回FALSE。
bool StrEmpty(HString &S){
    if(!S.length){
        return true;
    }else{
        return false;
    }
}

//求串长。返回串S的元素个数。
int StrLength(HString &S){
    return S.length;
}

//清空操作。将S清为空串。
void ClearString(HString &S){
    if(s.ch)
    {
        free(s.ch);
        s.ch = NULL;
    }
    s.length = 0;
}

//销毁串。将串S销毁（回收存储空间）。
void DestroyString(HString &S){
    free(s.ch);
} 

//串联接。用T返回由S1和S2联接而成的新串
int Concat(HString &T,HString s1,HString s2){
    int i,j;
    if(T.ch){
		free(T.ch); 
    }
    if(!(T.ch = (char*)malloc((s1.length + s2.length)*sizeof(char)))){
        return 0;
    }
    T.length = s1.length + s2.length;
    for(i = 0;i < s1.length;i++){
        *(T.ch+i) = *(s1.ch+i);
    }
    for(j = 0;j < s2.length;j++){
           *(T.ch+s1.length+j) = *(s2.ch + j);
    }
    return 0;
} 

//求子串。用Sub返回串S的第pos个字符起长度为len的子串。
int SubString(HString &Sub,HString S,int pos,int len){
    int i;
    if(len < 0 || len > S.length ||pos < 1  || pos > S.length-pos+1){
        printf("Error!\n");
        return 0;
    }
    if(len == 0){
        Sub.ch = NULL;
        Sub.length = 0;
    }else{
        Sub.ch = (char *)malloc(len *sizeof(char));
        for(i = 0;i < len;i++)
        {
            *(Sub.ch+i) = *(S.ch+pos+i-1);
        }
        Sub.length = n;
    }
    return 0;
}

//比较操作。若S>T，则返回值>0；若S=T，则返回值=0；若S<T，则返回值<0。 
int StrCompare(HString S,HString T){
    for(int i = 0;i < S.length && i < T.length;i++){
        if(S.ch[i]!=T.ch[i]){
            return S.ch[i]-T.ch[i];
        }      
    }       
    return S.length-T.length;
}

//定位操作。若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置；否则函数值为-1。
int Index(HString S,HString T){
    HString a;
    int m = S.length;
    int n = T.length;
    int i = 1;
    while(i<=m-n+1){
        SubString(sub,S,i,n);
        if(StrCompare(sub,T)!=0){
            i++;
        }else{
            return i;
        }
    }
    return -1;
}

3.字符串模式匹配

⼦串——主串的⼀部分，⼀定存在

模式串——不⼀定能在主串中找到

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

3.1 朴素模式匹配算法

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

朴素模式匹配算法：将主串中所有⻓度为m的⼦串依次与模式串对⽐，直到找到⼀个完全匹配的⼦串， 或所有的⼦串都不匹配为⽌。

【最多对⽐ n-m+1 个⼦串】

之前介绍过的串的定位操作其实已经实现了朴素模式的算法匹配，不过我们使用了两个字符串的基本操作

//定位操作。若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置；否则函数值为-1。
int Index(HString S,HString T){
    HString a;
    int n = S.length;
    int m = T.length;
    int i = 1;
    while(i<=n-m+1){   //最多对⽐ n-m+1 个⼦串
        //取出从位置i开始，⻓度为m的⼦串
        SubString(sub,S,i,n);
        //⼦串和模式串对⽐，若不匹配，则匹配下⼀个⼦串 
        if(StrCompare(sub,T)!=0){
            i++;
        }else{
            return i;
        }
    }
    return -1;
}

接下来，我们不使⽤字符串的基本操作，直接通过数组下标实现朴素模式匹配算法。

int Index(HString S,HString T){
    int i=0;
    int j=0;
    while(i<S.length && j<T.length){
        if(S.ch[i]==T.ch[j]){
            i++;
            j++;
        }else{
            i=i-j+1;
            j=0;
        }
    }
    if(j>=T.length){
        return i-T.length+1;     //+1是因为返回的是位置而不是下标
    }else{
        return -1;
    }
}

3.2.KMP算法

KMP算法是由朴素模式匹配算法优化而来的。

由D.E.Knuth，J.H.Morris和V.R.Pratt提出，因此称为KMP算法。

根据模式串T，求出 next 数组，然后利⽤next数组进⾏匹配 （主串指针不回溯）。

【当模式串T(j)字符匹配失败时，令模式串的指针j=next(j)，继续往后匹配】

3.2.1 手算next数组

举例：

//模式串T（第一行数组下标j，第二行内容T(j)）
0	1	2	3	4	5	6	7
A	B	A	B	A	A	A	B

如果模式串T(0)不匹配，找前面公共前后缀（无字符），将模式串T(0)与主串的下一位进行匹配

如果模式串T(1)不匹配，找前面公共前后缀（A，长度0），将模式串T(0)与主串当前位置进行匹配

如果模式串T(2)不匹配，找前面公共前后缀（AB，长度0），将模式串T(0)与主串当前位置进行匹配

如果模式串T(3)不匹配，找前面公共前后缀（ABA，长度1），将模式串T(1)与主串当前位置进行匹配

如果模式串T(4)不匹配，找前面公共前后缀（ABAB，长度1），将模式串T(2)与主串当前位置进行匹配

如果模式串T(5)不匹配，找前面公共前后缀（ABABA，长度3），将模式串T(3)与主串当前位置进行匹配

如果模式串T(6)不匹配，找前面公共前后缀（ABABAA，长度1），将模式串T(1)与主串当前位置进行匹配

如果模式串T(7)不匹配，找前面公共前后缀（ABABAAA，长度1），将模式串T(1)与主串当前位置进行匹配

所以求出next数组的结果如下：

//next[]数组（第一行数组下标，第二行内容）
0	1	2	3	4	5	6	7	
-1	0	0	1	2	3	1	1

3.2.2 完整代码

//由模式串t求出next值
void GetNext(HString t,int next[])
{
	int j=0;
    int k=-1;
	next[0]=-1;   //第一个字符前无字符串，给值-1
	while (j<t.length-1){
    //因为next数组中j最大为t.length-1,而每一步next数组赋值都是在j++之后
	//所以最后一次经过while循环时j为t.length-2
		if (k==-1 || t.ch[j]==t.ch[k]){	   ////k为-1或比较的字符相等时
			j++;k++;
			next[j]=k;
       	}else{
			k=next[k];
		}
	}
}

int Index_KMP(HString S,HString T,int next[]){
    int i=0;
    int j=0;
    while(i<S.length && j<T.length){
        if(j==-1||S.ch[i]==T.ch[j]){
            i++;
            j++;
        }else{
            j=next[j];           //匹配失败时，主串指针i不回溯
        }
    }
    if(j>=T.length){
        return i-T.length+1;     //+1是因为返回的是位置而不是下标
    }else{
        return -1;
    }
}

第五章：树

1.树

1.1 基本概念

树是n（n≥0）个结点的有限集合，n= 0时，称为空树，这是一种特殊情况。

在任意一棵非空树中应满足：

①有且仅有一个特定的称为根的结点。

②当n> 1时，其余结点可分为m（m> 0）个互不相交的有限集合T1, T2,…, Tm，其中每个集合本身又是一棵树，并且称为根结点的子树。

1.2 基本术语

• 结点之间的关系描述

祖先结点：从一个结点出发，一直往上走，直至根节点，这条路上所有的结点都是该结点的祖先结点。

子孙结点：从一个结点出发，它的所有分支都是该结点的子孙结点。

双亲结点（父节点）：一个结点的直接前驱就是双亲结点（父节点）。

孩子结点：一个结点的直接后继就是孩子结点。

兄弟结点：双亲结点（父节点）相同的结点互为兄弟结点。

堂兄弟结点：同一层的不是兄弟结点的结点。

两个结点之间的路径：路径是单向（自上往下）的。

路径长度：经过了几条边。

• 结点、树的属性描述

结点的层次（深度）：从上往下数（默认从1开始，但也有些教材是从0开始）

结点的高度：从下往上数

树的高度（深度）：总共多少层

结点的度：有几个孩子（分支）

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

• 有序树、无序树

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

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

• 森林

森林：森林是m（m≥0）棵互不相交的树的集合

1.3 树的性质

①结点数=总度数+1

结点的度：结点有几个孩子（分支）

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

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

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

度为m的树	m叉树
任意结点的度≤m（最多m个孩子）	任意结点的度≤m（最多m个孩子）
至少有一个结点度=m（有m个孩子）	允许所有结点的度都 ＜m
一定是非空树，至少有m+1个结点	可以是空树

③度为m的树第i层至多有m^(i-1)个结点（i≥1）;

​ m叉树第i层至多有m^(i-1)个结点（i≥1）。

④高度为h的m叉树至多有(m^h-1)/(m-1)个结点

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

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

⑥具有n个结点的m叉树的最小高度为
$$
[log_m(n(m-1)+1)]
$$
​ 高度最小的情况——所有结点都有m个孩子

2.二叉树

2.1 定义和基本术语

二叉树是n（n≥0）个结点的有限集合：

① 或者为空二叉树，即n= 0。

② 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。

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

二叉树的五种状态：空二叉树；只有左子树；只有右子树；左右子树都有；只有根结点。

特殊的二叉树：

满二叉树：一棵高度为h，且含有2^h - 1个结点的二叉树

特点：

①只有最后一层有叶子结点

②不存在度为1的结点

③按层序从1开始编号，结点i的左孩子为2i，右孩 子为2i+1；结点i的父节点为𝑖/2（如果有的话）

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

特点：

①只有最后两层可能有叶子结点

②最多只有一个度为1的结点

③按层序从1开始编号，结点i的左孩子为2i，右孩 子为2i+1；结点i的父节点为𝑖/2（如果有的话）

④i≤ 𝑛/2为分支结点，i>𝑛/2为叶子结点

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

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

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

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

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

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

2.2 性质

二叉树：

①设非空二叉树中度为0、1和2的结点个数分别为n0、n1和n2， 则 n0 = n2 + 1

（叶子结点比二分支结点多一个）

②二叉树第i层至多有2^(i-1)个结点（i≥1）

​ m叉树第i层至多有m^(i-1)个结点（i≥1）

③高度为h的二叉树至多有2^h−1个结点（满二叉树）

​ 高度为h的m叉树至多有(m^h-1)/(m-1)个结点

完全二叉树：

①具有n个（n > 0）结点的完全二叉树的高度h为
$$
[log_2(n+1)] 或 [log_2n]+1
$$
②对于完全二叉树，可以由的结点数n推出度为0、1和2的结点个数为n0、n1和n2

【突破点：完全二叉树最多只会有一个度为1的结点】

若完全二叉树有2k个（偶数）个结点，则必有n1=1，n0=k，n2=k-1

若完全二叉树有2k-1个（奇数）个结点，则必有n1=0，n0=k，n2=k-1

2.3 存储结构

2.3.1 顺序存储

#define MaxSize 100;
struct TreeNode{
    int value;     //结点的数据元素
    bool isEmpty;  //结点是否为空
};

TreeNode t[MaxSize];
//定义一个长度为MaxSize的数组t
//按照从上至下、从左至右的顺序依次存储完全二叉树中的各个结点

for(int i=0;i<MaxSize;i++){
    t[i].isEmpty = true;
}
//初始化时所有 结点标记为空

2.3.2 链式存储

typedef struct BiTNode{
    int data;                            //数据域
    struct BiTNode *lchild,*rchild;      //左、右孩子指针
}BiTNode,*BiTree;

//定义一棵空树
BiTree root = NULL;

//插入根节点
root = (BiTree)malloc(sizzeof(BiTNode))
root->data={1};
root->lchild = NULL;
root->rchild = NULL;

//插入新结点
BiTNode *p=(BiTNode*)malloc(sizeof(BiTNode));
p->data={2};
p->lchild = NULL;
p->rchild = NULL;
root->lchild = p;  //作为根节点的左孩子

在这个链表中，找到指定结点的左/右孩子很简单，但要找到指定结点的父结点就只能从根节点开始遍历。

为了方便查找父亲结点，我们可以在结构体中定义一个父节点指针

typedef struct BiTNode{
    int data;
    struct BiTNode *lchild,*rchild;
    struct BitNode *parent;              //父节点指针
}BiTNode,*BiTree;

这个就被称为三叉链表。

2.4 二叉树的先中后序遍历

先序遍历：根 左 右

中序遍历：左 根 右

后序遍历：左 右 根

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

//先序遍历
void PreOrder(BiTree T){
    if(T!=NULL){
        visit(T);//访问根节点
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

//中序遍历
void InOrder(BiTree T){
    if(T!=NULL){
        InOrder(T->lchild);
        visit(T);
        InOrder(T->rchild);
    }
}

//后序遍历
void PostOrder(BiTree T){
    if(T!=NULL){
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        visit(T);
    }
}

小应用

//求树的深度
int treeDepth(BiTree T){
    if(T == NULL){
        return 0;
    }else{
        int l = treeDepth(T->lchild);
        int r = treeDepth(T->rchild);
        return l>r ? l+1 : r+1;
    }
}

2.5 二叉树的层次遍历

算法思想：

• 初始化一个辅助队列

• 根节点入队

• 若队列非空，则对头结点出队，访问该结点，并将其左、右孩子插入队尾（如果有）

• 重复上一步，直至队列为空

//二叉树结点
typedef struct BiTNode{
    int data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

//链式队列结点
typedef struct LinkNode{
    BiTNode* data;
    struct LinkNode* next;
}LinkNode;

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

//层次遍历
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);
    }
}

3.线索二叉树

3.1 二叉树的线索化

在二叉树的结点上加上线索的二叉树称为线索二叉树.

对二叉树以某种遍历方式（如先序、中序、后序或层次等）进行遍历，使其变为线索二叉树的过程称为对二叉树进行线索化。

线索链表解决了无法直接找到该结点在某种遍历序列中的前驱和后继结点的问题，解决了二叉链表找左、右孩子困难的问题。

用土办法找到中序前驱

//辅助全局变量，用于查找结点p的前驱
BiTNode* p;                //p指向目标结点
BiTNode* pre = NULL;       //pre指向当前访问结点的前驱
BiTNode final = NULL;      //用于记录最终结果

//中序遍历
void InOrder(BiTree T){
    if(T!=NULL){
        InOrder(T->lchild);
        visit(T);
        InOrder(T->rchild);
    }
}

//访问结点q
void visit(BiTNode* q){
    if(q==p)
        final = pre;
    else
        pre = q;
}

以中序线索化为例，先序后序过程类似，不一一赘述。

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

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

//中序遍历二叉树，一边遍历，一边线索化
void visit(ThreadNode *q){
    if(q->lchild == NULL){   //左子树为空，建立前驱线索
        q->lchild = pre;
        q->ltag = 1;
    }
    if(pre != NULL && pre->rchild == NULL){
        pre->child = q;   //建立前驱结点的后继线索
        pre->rtag = 1;
    }
    pre = q;
}
void InThread(Thread T){
    if(T!=NULL){
        InThread(T->lchild);
        visit(T);    //在visit()中完成线索化
        InThread(T->rchild);
    }
}

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

3.2 在线索二叉树中找前驱后继

3.2.1 中序线索二叉树

• 中序后继

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

①若 p->rtag == 1，则 next = p->rchild

②若 p->rtag == 0，则 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){            //T为根节点指针
   for(ThreadNode *p = Firstnode(T); p!=NULL; p = Nextnode(p))
      visit(p);
}

• 中序前驱

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

①若 p->ltag == 1，则 pre = p->lchild

②若 p->ltag == 0，则 next = 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 Revorder(ThreadNode *T){            //T为根节点指针
   for(ThreadNode *p = Lastnode(T); p!=NULL; p = Prenode(p))
      visit(p);
}

3.2.2 先序线索二叉树

• 先序后继

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

①若 p->rtag == 1，则 next = p->rchild

②若 p->rtag == 0，则 next = 左孩子(有左孩子) / 右孩子(没有左孩子)

• 先驱前驱

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

①若 p->ltag == 1, 则 next = p->lchild;

②若 p->ltag == 0, 则 p必有左孩子，但是先序遍历中，左右子树的结点只可能是根的后继，不可能是前驱，所以不能从左右孩子里寻找p的先序前驱，（除非从头开始遍历 / 三叉链表）

case1: 如果能够找到p的父节点，且p是左孩子 —— p的父节点就是p的前驱；

case2: 如果能够找到p的父节点，且p是右孩子，且其左兄弟为空 —— p的父节点就是p的前驱；

case3: 如果能够找到p的父节点，且p是右孩子，且其左兄弟非空 ——p的前驱为左兄弟子树中最后一个被先序遍历到的结点（根节点出发，先往右，右没有往左，找到最下一层的结点）；

case4: p没有父节点，即p为根节点，则p没有先序前驱

3.2.3 后序线索二叉树

• 后序前驱

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

①若 p->ltag == 1, 则 next = p->lchild;

②若 p->ltag == 0, 则 p 必有左孩子（不知道有没有右孩子）

case1: 若p有右孩子 ——— 后序前驱：右孩子

case2: 若p没有右孩子 ——— 后序前驱：左孩子

• 后序后继

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

①若 p->rtag == 1, 则 next = p->rchild;

②若 p->rtag == 0, 则 p 必有右孩子, 左孩子不知道, 但是在后序遍历中，左右子树中的结点只有可能是根的前驱，而不可能是根的后继，所以找不到后继，（除非从头开始遍历 / 三叉链表）

case1: 如果能找到p的父节点，且p是右孩子 —— p的父节点即为其后继

case2: 如果能找到p的父节点，且p是左孩子，其右兄弟为空 —— p的父节点即为其后继

case3: 如果能找到p的父节点，且p是左孩子，其右兄弟非空 —— p的后继为其右兄弟子树中第一个被后序遍历的结点；

case4: p没有父节点，即p为根节点，则p没有后序后继；

4.树的存储

4.1 双亲表示法（顺序存储）

双亲表示法：每个结点中保存指向双亲的“指针”

#define MAX_TREE_SIZE 100         //树中最多结点数

typedef struct{                   //树的结点定义
   ElemType data;                 //数据存储
   int parent;                    //双亲位置域
}PTNode;

typedef struct{                   //树的类型定义
   PTNode nodes[MAX_TREE_SIZE];   //双亲表示
   int n;                         //结点数
}PTree;

增：新增数据元素，无需按逻辑上的次序存储；（需要更改结点数n）

删（叶子结点）：将伪指针域设置为-1；或者 用后面的数据填补；（需要更改结点数n）

删（非叶子结点）：还需要删除该结点的子孙结点统统删除

查询：优点-查指定结点的双亲很方便；缺点-查指定结点的孩子只能从头遍历，空数据导致遍历更慢；

4.2 孩子表示法（顺序+链式存储）

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;

4.3 孩子兄弟表示法（链式存储）

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

孩子兄弟表示法也可以相当于把树转化成二叉树

森林和二叉树的转换：把各个树的根节点视为兄弟关系

5.树和森林的遍历

5.1 树的遍历

• 先根遍历：若树非空，先访问根结点，再依次对每棵子树进行先根遍历；（与对应二叉树的先序遍历序列相同）

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);             //访问根节点
   }
}

• 层序遍历（队列实现）（广度优先遍历）

若树非空，则根结点入队；

若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队；

重复以上操作直至队尾为空；

5.2 森林的遍历

• 先序遍历：等同于依次对各个树进行先根遍历；也可以先转换成与之对应的二叉树，对二叉树进行先序遍历；
• 中序遍历：等同于依次对各个树进行后根遍历；也可以先转换成与之对应的二叉树，对二叉树进行中序遍历；

6.树与二叉树的应用

6.1二叉排序树(BST)

二叉排序树：左子树结点值 < 根结点值 < 右子树结点值（左子树、右子树同样是二叉排序树）

6.1.1 查找

typedef struct BSTNode{
   int key;
   struct BSTNode *lchild, *rchild;
}BSTNode, *BSTree;

//在二叉排序树中查找值为key的结点（非递归）
//最坏空间复杂度：O(1)
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的结点（递归）
//最坏空间复杂度：O(n)
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);
}

6.1.2 插入

//在二叉排序树中插入关键字为k的新结点（递归）
//最坏空间复杂度：O(n)
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)                 
      return BST_Insert(T->lchild,k);
   else 
      return BST_Insert(T->rchild,k);
}
//新插入的结点一定是叶子结点

6.1.3 二叉排序树的构造

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

6.1.4 删除

①若被删除结点z是叶子结点，则直接删除

②若被删除结点z不是叶子结点只有一棵左子树或右子树，则让z的子树替代z的位置即可

③若被删除结点z有左、右两棵子树，则令z的直接后继（或直接前驱）替代z，然后从二叉排序树中删除这个直接后继（或直接前驱），这样就转换成了第一或第二种情况。

z的直接后继：z的右子树中最左下的结点（该结点一定没有左子树）

z的直接前驱：z的左子树中最右下的结点（该结点一定没有右子树）

6.1.5 查找效率分析

查找长度：查找运算中，需要对比关键字的次数，反映了查找操作时间复杂度；

查找成功的平均查找长度ASL

查找失败的平均查找长度ASL

6.2 平衡二叉树(AVL)

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

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

平衡二叉树平衡因子绝对值不大于1

//平衡二叉树结点
typedef struct AVLNode{
   int key;         //数据域
   int balance;     //平衡因子
   struct AVLNode *lchild; *rchild; 
}AVLNode, *AVLTree;

在二叉排序树中插入新结点后，如何保持平衡？

从插入点往回找到第一个不平衡结点，调整以该结点为根的子树。

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

6.2.1 调整最小不平衡子树

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

调整： A的左孩子结点右上旋代替A成为根结点

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

调整： A的右孩子结点左上旋代替A成为根结点

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

调整： A的左孩子的右孩子，先左上旋替代A的左孩子，再右上旋替代A结点

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

调整： A的右孩子的左孩子，先右上旋替代A的右孩子，再左上旋替代A结点

6.2.2 平衡二叉树的查找与效率分析

若树高为h，则最坏情况下，查找一个关键字最多需要对比h次，即查找操作的时间复杂度不可能超过O(h);

平衡二叉树的最大深度为O(log₂n)，平衡二叉树的平均查找长度为O(log₂n)

6.3 哈夫曼树

6.3.1 带权路径长度

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

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

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

6.3.2 哈夫曼树的定义

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

6.3.3 哈夫曼树的构造

给定n个权值分别为w₁,w₂,…,wn的结点，构造哈夫曼树的算法描述如下：

① 将n个结点作为n棵仅含有一个根结点的二叉树，构成森林F；

② 生成一个新结点，并从森林F中找出根结点权值最小的两棵树作为新结点的左右子树，且令新结点的权值为两棵子树的根结点的权值之和；

③ 从森林F中删除选择的这两棵树，并将新生成的树加入到F中；

④ 重复②和③的步骤，直到F中只有一棵树为止，此时即为哈夫曼树。

哈夫曼树的性质：

①每个初始结点都会成为叶结点，双支结点都为新生成的结点；

②权值越大离根结点越近，权值越小离根结点越远；

③ 哈夫曼树中没有度为1的结点；

④n个叶子结点的哈夫曼树的结点总数为2n-1，其中度为2的结点数为n-1，这n-1个结点都是新结点。

6.3.4 哈夫曼编码

在数据通信中，若对每个字符用相等长度的二进制位表示，称这种编码方式为固定长度编码。

若允许对不同字符用不等长的二进制位表示，则这种编码方式称为可变长度编码。

若编码中没有一个编码是其他编码的前缀，则称这样的编码为前缀编码。

可变长度编码比固定长度编码要好得多，其特点是对频率高的字符赋以短编码，而对频率较低的字符则赋以较长一些的编码，从而可以使字符的平均编码长度减短，起到压缩数据的效果。

哈夫曼编码是一种被广泛应用而且非常有效的数据压缩编码。

将字符集中的每个字符作为一个叶子结点，各个字符出现的频率作为结点的权值，构造哈夫曼树（哈夫曼树不唯一，哈夫曼编码不唯一）。

第六章：图

1.图的基本概念

图G由顶点集V和边集E组成，记为G = (V, E)。

其中V(G)表示图G中顶点的有限非空集；E(G)表示图G中顶点之间的关系（边）集合。

若V = {v1, v2, … , vn}，则用|V|表示图G中顶点的个数，也称图G的阶，E = {(u, v) | u∈V, v∈V}，用|E|表示图G中边的条数。

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

若E是无向边（简称 边）的有限集合时，则图G为无向图；边是顶点的无序对，记为(v, w)或(w, v)。

若E是有向边（也称 弧）的有限集合时，则图G为有向图；弧是顶点的有序对，记为<v, w>。

简单图：

① 不存在重复边；

② 不存在顶点到自身的边

（本章只讨论简单图）

多重图：

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

顶点的度、入度、出度：

对于无向图：

顶点v的度是指依附于该顶点的边的条数，记为TD(v)。

所有顶点的度之和等于 2|E|

对于有向图：

入度是以顶点v为终点的有向边的数目，记为ID(v)；

出度是以顶点v为起点的有向边的数目，记为OD(v)。

顶点v的度等于其入度和出度之和，即TD(v) = ID(v) + OD(v)。

所有顶点的入度之和 = 所有顶点的出度之和 = |E|

顶点- 顶点的关系描述：

• 路径——顶点Vp到顶点Vq之间的一条路径是指顶点序列

• 回路——第一个顶点和最后一个顶点相同的路径称为回路或环

• 简单路径——在路径序列中，顶点不重复出现的路径称为简单路径。

• 简单回路——除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。

• 路径长度——路径上边的数目

• 点到点的距离——从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离。若从u到v根本不存在路径，则记该距离为无穷（∞）。

• 无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的

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

连通图、强连通图

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

对于n个顶点的无向图G，

若G是连通图，则最少有 n-1 条边，

若G是非连通图，则最多可能有 (n-1)(n-2)/2 条边

若图中任何一对顶点都是强连通的，则称此图为强连通图

对于n个顶点的有向图G，若G是强连通图，则最少有 n 条边（形成回路）

子图、生成子图

设有两个图G = (V, E)和G‘ = (V’, E‘)，若V¢是V的子集，且E’是E的子集，则称G‘是G的子图。
若有满足V(G’) = V(G)的子图G‘，则称其为G的生成子图。

连通分量、强连通分量

极大连通子图：子图必须连通，且包含尽可能多的顶点和边

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

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

生成树

连通图的生成树是包含图中全部顶点的一个极小连通子图（边要在连通的前提下尽可能少）。
若图中顶点数为n，则它的生成树含有 n-1 条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。

生成森林

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

边的权、带权图/网

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

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

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

几种特殊的图

无向完全图——无向图中任意两个顶点之间都存在边

有向完全图——有向图中任意两个顶点之间都存在方向相反的两条弧

稀疏图——边数很少的图

稠密图——边数很多的图

（没有绝对的界限，一般来说，|E| < |V|log|V|时，可以将G视为稀疏图 ）

树——不存在回路，且连通的无向图

有向树——一个顶点的入度为0、其余顶点的入度均为1的有向图，称为有向树。

2.图的存储

2.1 邻接矩阵

	A	B	C
A	0	1（A和B之间存在边）	0
B	1（B和A之间存在边）	0	1
C	0	1	0

#define  MaxVertexNum 100                   //顶点数目的最大值
typedef struct{
    char Vex[MaxVertexNum];                 //顶点表
    //也可以用bool或枚举类型来表示边
    int Edge[MaxVertexNum][MaxVertexNum];   //邻接矩阵，边表
    int vexnum,arcnum;                      //图的当前顶点数和边数/弧数
}MGraph;

邻接矩阵的空间复杂度只和顶点数相关，适合用于存储稠密图。

无向图：

第i个结点的度 = 第i行（或第i列）的非零元素个数

有向图：

第i个结点的出度 = 第i行的非零元素个数

第i个结点的入度 = 第i列的非零元素个数

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

邻接矩阵法存储带权图（网）

存在边——边上的权值。

不存在边——用∞来表示，在代码中，可以用int的上限来表示“无穷”。

邻接矩阵的性质

设图G的邻接矩阵为A（矩阵元素为0/1），则 A^n 的元素 A^n[i][j] 等于由顶点 i 到顶点 j 的长度为 n 的路径的数目（说明i）

2.2 邻接表

（顺序+链式存储）

data	first
(0)A	->(1)B ->(2)C [存在A指向B与A指向C的边]
(1)B	->(0)A
(2)C	->(0)A

边的先后顺序可以改变，所以邻接表表示方法并不唯一。

邻接表适合用于稀疏图。

2.3 十字链表

（存储有向图）

①画邻接表

②增加弧结点的域

③自己指向自己

顶点结点	data	firstin	firstout
	数据域	该顶点作为弧头的第一条弧	该顶点作为弧尾的第一条弧

弧结点	尾	头	同头	同尾
	弧尾顶点编号	弧头顶点编号	弧头相同的下一条弧	弧尾相同的下一跳弧
			用箭头指（没有就空^）	用箭头指（没有就空^）

2.4 邻接多重表

（存储无向图）

顶点结点	data	firstedge
	数据域	与该顶点相连的第一条边（用箭头指）

弧结点	i	iLink	j	jLink
	边的顶点编号	依附于顶点 i 的下一条边	边的顶点编号	依附于顶点 j 的下一条边
		用箭头连线（没有就空^）		用箭头连线（没有就空^）

3.图的基本操作

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

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

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

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

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

RemoveEdge(G,x,y)：若无向边(x, y)或有向边<x, y>存在，则从图G中删除该边。

FirstNeighbor(G,x)：求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-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。

4.图的遍历算法

4.1 广度优先遍历（BFS）

广度优先搜索（BFS）类似于二叉树的层序遍历算法。

它的基本思想是：首项访问起始顶点v，接着由v出发，依次访问v的各个未访问过的邻接顶点w1,w2,w3,…,wi，然后依次访问它们所有未被访问过的邻接顶点……以此类推，知道所有顶点都被访问过位置。

类似的思想还将应用于Dijkstra单源最短路径算法和prime最小生成树算法。

广度优先搜索生成的树为广度优先生成树

要点：

①找到与⼀个顶点相邻的所有顶点

②标记哪些顶点被访问过

③需要⼀个辅助队列

#define MaxVertexNum 100
bool visited[MaxVertexNum];    //标记访问数组
void BFSTraverse(Graph G)      //对图G进行广度优先遍历
{
    for(int i=0;i<G.vexnum;i++)// 遍历一下所有的顶点
        visited[i] = false;    // 将所有的顶点都设为未访问标志。
    InitQueue(Q);
    for(int i=0;i<G.vexnum;i++)// 从0号顶点开始遍历
        if(!visited[i])        // 对每个连通分量调用一次BFS
            BFS(G,i);
}
//广度优先遍历
void BFS(Graph G,int v)        //从顶点v出发
{
    visit(v);                  //访问初始顶点
    visited[V]=true;           //对v做已访问标记
    EnQueue(Q,v);              //顶点v入队列Q
    while(!isEmpty(Q))
    {
        Dequeue(Q,v);          //顶点v出队列
        for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
            //检测v所有邻接点
            if(!visited[w])        //w为v的尚未访问的邻接顶点
            {
                visit(w);          //访问顶点w
                visited[w]=true;   //对w做已访问标记
                EnQueue(Q,w);      //顶点w入队列
            }
    }
}

4.2 深度优先遍历（DFS）

与广度优先搜索不同，深度优先搜索(DFS)(DFS)类似于树的先序遍历。正如其名称中所暗含的意思一样，这种搜索算法所遵循的策略是尽可能“深”的搜索一个图。

它的基本思想如下：首先访问图中某一起始顶点v，然后从v出发，访问与v邻接且未被访问的任一定点w1，再访问与w1邻接且未被访问的任意顶点w2，……重复上述过程。当不能再继续向下访问时，一次退回到最近被访问的顶点，若他还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，知道搜索顶点均被访问过为止。

深度优先搜索生成的树为深度优先生成树

#define MAX_VERTEX_NUM 100
bool visited[MAX_VERTEX_NUM];   //访问标记数组
void DFSTraverse(Graph G)       //对图G进行深度优先遍历
{
    for(v=0;v<G.vexnum;i++)
        visited[v]=false;       //初始化已访问标记数据
    for(v=0;v<G.vexnum;i++)     //从v=0开始遍历
        if(!visited[v])
            DFS(G,v);
}
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为u的尚未访问的邻接顶点
            DFS(G,w);
}

5.最小生成树

5.1 最小生成树的概念

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

• 最⼩⽣成树可能有多个，但边的权值之和总是唯⼀且最⼩的

• 最⼩⽣成树的边数 = 顶点数 - 1。砍掉⼀条则不连通，增加⼀条边则会出现回路

• 如果⼀个连通图本身就是⼀棵树，则其最⼩⽣成树就是它本身

• 只有连通图才有⽣成树，⾮连通图只有⽣成森林

5.2 Prim算法

Prim 算法（普⾥姆）：

从某⼀个顶点开始构建⽣成树；

每次将代价最⼩的新顶点纳⼊⽣成树，直到所有顶点都纳⼊为⽌。

时间复杂度：O(|V|²)，适用于边稠密图

5.3 Kruskal算法

Kruskal 算法（克鲁斯卡尔）：

每次选择⼀条权值最⼩的边，使这条边的两头连通（原本已经连通的就不选），直到所有结点都连通。

时间复杂度：O(|E|log₂|E|)，适用于边稀疏图

6.最短路径算法

6.1 BFS算法

（无权图的单源最短路径）

//求顶点u到其他顶点的最短路径
void BFS_MIN_Ditance(Graph G,int u){
    //d[i]表示从u到i结点的最短路径
    for(i=0;i<G.vexnum;++i){
        d[i]=∞;          //初始化路径长度（∞可以用int最大值代替）
        path[i]=-1;      //最短路径从哪个顶点过来
    }
    d[u]=0;              //把顶点u设为0
    visited[u]=TRUE;
    EnQueue(Q,u);
    while(!isEmpty(Q)){
        DeQueue(Q,v);              //顶点u出队列
        for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
            if(!visited[w])        //w为u的尚未访问的邻接顶点
            {
                d[w]=d[u]+1;       //路径长度+1
                path[w]=u;         //最短路径应从u到w
                visited[w]=TRUE;   //设已访问标记
                EnQueue(Q,w);      //顶点w入队
            }
    }
}

6.2 Dijkstra算法

迪杰斯特拉（1972年图灵奖得主）

（无权图、带权图的单源最短路径）

和Prime是一样的，不过Prime是最小生成树，计算的是将这些点连起来花费的最小代价。而Dijkstra计算的是，从某点开始到其他点花费的最小代价。

但是Dijkstra算法不适用于有负权值的带权图

①从V₀开始，初始化三个数组信息。

令 final[0]=ture; dist[0]=0; path[0]=-1；

其余顶点final[k]=false; dist[k]=arcs[0][k]; path[k]= (arcs[0][k]==∞) ? -1 : 0

final[] ：标记各顶点是否已找到最短路径

dist[] ：最短路径长度

path[] ：路径上的前驱

②循环遍历所有结点，找到还没确定最短路径，且dist 最⼩的顶点Vi，令final[i]=ture。

③检查所有邻接⾃ Vi 的顶点，若其 final 值为false，则更新 dist 和 path 信息 。

若 final[j]==false 且 dist[i]+arcs[i][j] < dist[j]，

则令 dist[j]=dist[i]+arcs[i][j] ; path[j]=i。

（注： arcs[i][j]表示 Vi 到 Vj 的弧的权值）

④重复②③直至final全为true

6.3 Floyd算法

弗洛伊德（1978年图灵奖得主）

（无权图、带权图的各顶点间的最短路径）

Floyd可以用于有负权值的带权图。

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

对于n个顶点的图G，求任意⼀对顶点 Vi —> Vj 之间的最短路径可分为如下⼏个阶段：

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

A(-1)——目前来看，各顶点间的最短路径长度

path(-1)——两个顶点之间的中转点

#0：若允许在 V0 中转，最短路径是？

检查所有元素

若 A(k−1)[i][j] > A(k−1)[i][k] + A(k−1)[k][j]

则 A(k)[i][j] = A(k−1)[i][k] + A(k−1)[k][j]；path(k)[i][j] = k

否则 A(k) 和 path(k) 保持原值

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

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

…

#n-1：若允许在 V0、 V1、 V2 …… Vn-1 中转，最短路径是？

//Floyd核心算法
for(k=0;k<n;k++)
{             
	for(i=0;i<n;i++)       //所有的路都让k加进去试试  
	{
		for(j=0;j<n;j++)   //如果从i到j的路上有k走的会更轻松的话,那就让k去吧 
		{
			if(A[i][j]>A[i][k]+A[k][j])    //判断是否会更加轻松       
			{
				A[i][j] = A[i][k]+A[k][j]; //更新最短路径长度
				path[i][j] = k;            //中转点
            }
        }
	}
}

7.有向无环图

有向无环图：若一个有向图中不存在环，则称为有向无环图，简称DAG图

有向无环图可以用来描述表达式

8.拓扑排序

AOV网

用顶点表示活动的网

用DAG表示一个工程；顶点表示活动；有向边 <Vi，Vj>表示活动Vi必须先于活动Vj进行

8.1 拓扑排序

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

①每个顶点出现且只出现一次

②若顶点A在序列中排在顶点B的前面，则在图中不存在从顶点B到顶点A的路径。

拓扑排序的实现：

①从DAG图中选择一个没有前驱的顶点并输出。

②从图中删除该顶点和所有以它为为起点的有向边。

③重复①和②直到当前的DAG图为空或当前图中不存在无前驱的顶点为止。（而后一种情况则说明有向图中必然存在环）

注意：有回路的图不适合用拓扑排序

//拓扑排序
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[i].firstarc;p;p=p->nextrac){
			//将所有i指向的顶点的入度减1，并将入度减为0的顶点压入栈S
			v=p->adjvex;
			if(!(--indegree[v]))
				Push(S,v);  //入度为0，则入栈
		}
	}
	if(count<G.vexnum)
		return false;		//排序失败，有向图中有回路
	else 
		return true;		//拓扑排序成功
}

8.2 逆拓扑排序

逆拓扑排序的实现

①从AOV网中选择一个没有后继（出度为O)的顶点并输出。

②从网中删除该顶点和所有以它为终点的有向边。

③重复①和②直到当前的AOV网为空。

//逆拓扑排序
void DFSTraverse(Graph G){ 	//对图G进行深度优先遍历
	for(v=0; v<G.vexnum; ++v)
		visited[v]=FALSE;   //初始化已访问标记数据
	for(v=0; v<G.vexnum; ++v)//本代码中是从v=0开始遍历
		if(!visited[v])
			DFS(G,v);
}
void DFS(Graph G,int v){	//从顶点v出发，深度优先遍历图G
	visited[v]=TRUE;		//设已访问标记
	for(w=FirstNeighbor(G,v);w>=0; w=NextNeighor(G,v,w))
		if(!visited[w]){	// w为u的尚未访问的邻接顶点
			DFS(G,w);
		}
	print(v );		        //输出顶点
}

9.关键路径

AOE网

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

AOE网的两个性质

①只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始;

②只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。另外，有些活动是可以并行进行的。

在AOE网中仅有一个入度为0的顶点，称为开始顶点〈源点)，它表示整个工程的开始;
也仅有一个出度为0的顶点，称为结束顶点（汇点)，它表示整个工程的结束。

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

完成整个工程的最短时间就是关键路径的长度，若关键活动不能按时完成，则整个工程的完成时间就会延长。

• 事件vk的最早发生时间ve(k)——决定了所有从vk开始的活动能够开工的最早时间。

• 事件vk的最迟发生时间vl(k)——它是指在不推迟整个工程完成的前提下，该事件最迟必须发生的时间。

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

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

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

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

第七章：查找

1.查找的基本概念

查找 —— 在数据集合中寻找满⾜某种条件的数据元素的过程称为查找
查找表（查找结构）—— ⽤于查找的数据集合称为查找表，它由同⼀类型的数据元素（或记录）组成
关键字 —— 数据元素中**唯⼀**标识该元素的某个数据项的值，使⽤基于关键字的查找，查找结果应该是唯⼀的。

对查找表的常见操作

①查找符合条件的数据元素

②插⼊、删除某个数据元素

查找算法的评价指标

①查找⻓度——在查找运算中，需要对⽐关键字的次数称为查找⻓度
②平均查找⻓度（ASL, Average Search Length）—— 所有查找过程中进⾏关键字的⽐较次数的平均值

2.顺序查找

2.1 算法思想

顺序查找，⼜叫“线性查找”，通常⽤于线性表。

算法思想：从头到 jio 挨个找（或者反过来也OK）

2.2 算法实现

typedef struct{        //查找表的数据结构（顺序表）
    Elemtype *elem;    //动态数组基址
    int TableLen;      //表的长度
}SSTable;
//顺序查找
int Search_Seq(SSTable ST, ElemType key){
    // 引入哨兵元素，在创建查找表时，0号单元留空，预留给带查找元素关键字
	// 引入哨兵元素的目的是使得循环不必判断数组是否越界，可以避免很多不必要的判断语句，提高效率 
	ST.elem[0] = key;                               //“哨兵”  
	int i;
	for(i = ST.TableLen; ST.elem[i] != key; --i);   //从后往前找
	return i;    //查找成功，返回元素下标；查找失败，则返回0
}

时间复杂度：O(n)

3.折半查找

3.1 算法思想

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

基本思想：

首先将给定值key于表中间位置的元素进行比较，若相等，则查找成功，返回元素位置；若不等，则目标元素只能在中间元素以外的前半部分或后半部分，然后在缩小的范围内继续同样的查找。

3.2 算法实现

typedef struct{        //查找表的数据结构（顺序表）
    Elemtype *elem;    //动态数组基址
    int TableLen;      //表的长度
}SSTable;
//折半查找（以升序为例）
int binnarySearch(SSTable L, ElemType key){
	int low = 0;
	int high = L.TableLen - 1;
	int mid;
	while(low <= high){
		mid = (low + high) / 2;      //取中间位置（向下取整）
		if(L.elem[mid] == key)       //查找成功直接返回
			return mid;
		else if(L.elem[mid] < key)
			low = mid + 1;           //从后半部分开始查找
		else
			high = mid - 1;          //从前半部分开始查找
	} 
	return -1;  // 查找失败，返回-1    
}

时间复杂度O(log₂n)

3.3 折半查找判定树

构造：

由mid所指元素将原有元素分割到左右子树中

key：右子树结点数 - 左子树结点树 的绝对值小于等于1

特性：

折半查找判定树是平衡的二叉排序树

折半查找判定树，只有最下面一层是不满的

若查找表有n个关键字，则失败结点有 n+1 个

树高h=[log₂(n+1)] （不包含失败结点）

4.分块查找

4.1 算法思想

基本思想：

将查找表分为若干子块，块内元素可以无序，但块之间是有序的，即前一块中的最大关键字小于后一块中的最小关键字。再建立一个索引表，索引表中的每个元素含有各块中的最大关键字和各块中的第一个元素的地址，索引表按关键字有序排序。

分块查找吸取了顺序查找和折半查找各自的优点，既有动态结构，又适合于快速查找。

查找分为两步，第一步是在索引表中确定待查记录所在的块，可以使用顺序查找或折半查找；第二部是在块内顺序查找。

5.B树

B树，又称多路平衡查找树，所有结点的最大孩子数称为阶。一般用m来指代

//5叉查找树的结点定义
struct Node{
    Elemtype keys[4];       //最多四个关键字
    struct Node* child[5];  //最多5个孩子
    int num;                //结点中有几个关键字
}

5.1 B树的性质

对于m阶的B树：

• 根节点的⼦树数∈[2, m]，关键字数∈[1, m-1]。

  其他结点的⼦树数∈[ , m]；关键字数∈[ -1, m-1]

• 对任⼀结点，其所有⼦树⾼度都相同

• 关键字的值：⼦树0<关键字1<⼦树1<关键字2<⼦树2<…. (类⽐⼆叉查找树 左<中<右)

• 所有叶节点都位于同一层，并且是不带信息的

5.2 B树的查找

B树的查找可分为两步

1.在B树中找结点(磁盘上进行)

2.在结点内找关键字(内存上进行)，可采用顺序查找法或折半查找法。

5.3 B树的插入

通过B树的查找算法确定查找失败的位置，这个位置就是应该插入的位置。

开始进行插入，如果要插入结点的关键字数量小于m，直接插入即可。如果大于等于m，那就不符合B树的特性了，那就要进行分裂。

分裂的方法是：位置为”向上取整m/2”的关键字，给到父节点，这个关键字的左部分保持在原来结点，右部分放到一个新节点。

如果给到父节点关键字后，父节点的关键字数量也大于等于m了，那么就要进行二次分裂。

5.4 B树的删除

删除可分为两种情况，被删的关键字在与不在终端结点中。

• 不在终端结点中

如果要删关键字k，找到k的直接前驱（左侧指针所指⼦树中“最右下”的元素 ）或直接后继（右侧指针所指⼦树中“最左下”的元素 ）来替代被删除的关键字。

• 在终端结点中，又分为三种情况

①直接删除。 当将要被删除关键字所在结点的关键字数量大于等于“向上取整m/2”，代表删掉之后就是“向上取整m/2”-1，依旧符合B树特性，可以直接删掉。
借兄弟一手。 顾名思义，为啥要借，就是自身不符合前面直接删除的条件(删掉之后不符合B树特性了)，所以要借兄弟的，那兄弟够借嘛？所以又可以分为两种

②兄弟够借。若被删除关键字所在结点删除前的关键字个数低于下限，且与此结点右（或左）兄弟结点的关键字个数还很宽裕，则需要调整该结点、右（或左）兄弟结点及其双亲结点（⽗⼦换位法）

③兄弟不够借。若被删除关键字所在结点删除前的关键字个数低于下限，且此时与该结点相邻的左、右兄弟结点的关键字个数均=⌈m/2⌉ - 1，则将关键字删除后与左（或右）兄弟结点及双亲结点中的关键字进⾏合并

在合并过程中，双亲结点中的关键字个数会减1。若其双亲结点是根结点且关键字个数减少⾄0（根结点关键字个数为1时，有2棵⼦树），则直接将根结点删除，合并后的新结点成为根；若双亲结点不是根结点，且关键字个数减少到 ，则⼜要与它⾃⼰的兄弟结点进⾏调整或合并操作，并重复上述步骤，直⾄符合B树的要求为⽌

6.B+树

B+树是专门为数据库设计的。

B+树的查找、插入、删除与B树类似，但是B+树查找到关键字后，并不终止，而是继续向下查找，直到叶节点上的关键字为止。

6.1 B+树的性质

⼀棵m阶的B+树需满⾜下列条件：

• 每个分⽀结点最多有m棵⼦树（孩⼦结点）。

• ⾮叶根结点⾄少有两棵⼦树，其他每个分⽀结点⾄少有 棵⼦树。

• 结点的⼦树个数与关键字个数相等。

• 所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按⼤⼩顺序排列，并且相邻叶结点按⼤⼩顺序相互链接起来。

• 所有分⽀结点中仅包含它的各个⼦结点中关键字的最⼤值及指向其⼦结点的指针。

6.2 B+树 vs B树

相同点：

• 除根节点外，最少 [m/2] 个分叉（确保结点不要太“空”）

• 任何⼀个结点的⼦树都要⼀样⾼（确保“绝对平衡”）

不同点：

	m阶B树	m阶B+树
类比	⼆叉查找树的进化——>m叉查找树	分块查找的进化——>多级分块查找
关键字与分叉	n个关键字对应n+1个分叉（⼦树）	n个关键字对应n个分叉
节点包含的信息	所有结点中都包含记录的信息	只有最下层叶⼦结点才包含记录的信息 （可使树更矮）
查找方式	不⽀持顺序查找。查找成功时，可能停在 任何⼀层结点，查找速度“不稳定”	⽀持顺序查找。查找成功或失败都会到达 最下⼀层结点，查找速度“稳定

7.散列查找

7.1 概念

散列表（Hash Table），⼜称哈希表。是⼀种数据结构，特点是：数据元素的关键字与其存储地址直接相关 。

散列函数：把查找表中的关键字映射成该关键字对应地址的函数，记为Addr=Hash（key）。这里的地址可以是数组下标、索引或内存地址等。

若不同的关键字通过散列函数映射到同⼀个值，则称它们为**“同义词”**

通过散列函数确定的位置已经存放了其他元素，则称这种情况为**“冲突”**

理想情况下，散列表的查找时间复杂度为O(1)，即与表中元素的个数无关。

7.2 构造散列函数

①除留余数法

H(key) = key % p

假定散列表表长为m，取一个不大于m但最接近m的质数p

(取质数的话大多数情况下能让冲突发生得更少，分布得更均匀，参见《数论》)

②直接定址法

H(key) = key 或 H(key) = a*key + b

其中，a和b是常数。这种⽅法计算最简单，且不会产⽣冲突。它适合关键字的分布基本连续的情况，若关键字分布不连续，空位较多，则会造成存储空间的浪费。

③数字分析法

选取数码分布较为均匀的若⼲位作为散列地址

设关键字是r进制数（如⼗进制数），⽽r个数码在各位上出现的频率不⼀定相同，可能在某些位上分布均匀⼀些，每种数码出现的机会均等；⽽在某些位上分布不均匀，只有某⼏种数码经常出现。

此时可选取数码分布较为均匀的若⼲位作为散列地址。这种⽅法适合于已知的关键字集合，若更换了关键字，则需要重新构造新的散列函数。

④平⽅取中法

取关键字的平⽅值的中间⼏位作为散列地址。

具体取多少位要视实际情况⽽定。

这种⽅法得到的散列地址与关键字的每位都有关系。

因此使得散列地址分布⽐较均匀，适⽤于关键字的每位取值都不够均匀或均⼩于散列地址所需的位数。

例：存储学生的身份证号

7.3 处理冲突的办法

7.3.1 拉链法

⽤拉链法（⼜称链接法、链地址法）处理“冲突”： 把所有“同义词”存储在⼀个链表中

散列表的查找过程于构造散列表的过程基本一致。根

据散列函数和关键字可以计算出记录的散列地址。

若散列地址上：

①无记录，说明查找失败；

②若有记录且关键字相同，则查找成功；

③若有记录但关键字不同，使用给定的处理冲突方法计算下一个散列地址，再次进行比较。

装填因子：定义一个表的装满程度，即α = 表中记录数/散列表长度

7.3.2 开放定址法

开放定址法，是指可存放新表项的空闲地址既向它的同义词表项开放，⼜向它的⾮同义词表项开放。

数学递推公式：

Hi = (H(key) + di) % m

i = 0, 1, 2,…, k（k≤m - 1）， m表示散列表表⻓； di为增量序列； i 可理解为“第i次发⽣冲突”

取定某一增量序列di后，对应的处理方法就是确定的。通常有以下4种取法

①线性探测法（线性探测再散列法）

di = 0，1，2，···，m-1

• 冲突发生时，顺序查看表中下一个单元，直到找出一个空单元或查遍全表（此时表已满）。

• 线性探查法可能使第 i 个散列地址的同义词存入第 i+1 个散列地址，这样本应存入第 i+1 个散列地址的元素就要争夺 i+2 个散列地址。造成大量元素在相邻的散列地址上聚集（堆积）起来，大大降低了查找效率。

• 采⽤“开放定址法”时，删除结点不能简单地将被删结点的空间置为空，否则将截断在它之后填⼊散列表的同义词结点的查找路径，可以做⼀个“删除标记”，进⾏逻辑删除

②平方探测法（二次探测再散列法）

di = 0²，1²，-1²，2²，-2²，···，k²，-k²（k≤m/2）

• 散列表长度m必须是一个可以表示为4k+3的素数。
• 是一种处理冲突的较好方法，可以避免出现堆积问题。
• ⼩坑：散列表⻓度m必须是⼀个可以表示成4j + 3的素数，才能探测到所有位置，参加《数论》

③再散列法（双散列法）

Hi = RHi(Key) i=1,2,3….,k

• 除了原始的散列函数 H(key) 之外，多准备⼏个散列函数，当散列函数冲突时，⽤下⼀个散列函数计算⼀个新地址，直到不冲突为⽌

④伪随机序列法：

di为伪随机数序列

第八章：排序

1.排序的基本概念

排序（Sort） ，就是重新排列表中的元素，使表中的元素满⾜按关键字有序的过程。

排序算法的评价指标

算法的稳定性。

若待排序表中有两个元素Ri和Rj，其对应的关键字相同即keyi = keyj，且在排序前Ri在Rj的前⾯，若使⽤某⼀排序算法排序后， Ri仍然在Rj的前⾯，则称这个排序算法是稳定的，否则称排序算法是不稳定的。

排序算法的分类

• 内部排序——数据都在内存中

关注如何使算法时间、空间复杂度更低

• 外部排序——数据太多，无法全部放入内存

还要关注如何使读/写磁盘次数更少

2.插入排序

2.1 算法思想

每次将⼀个待排序的记录按其关键字⼤⼩插⼊到前⾯已排好序的⼦序列中，直到全部记录插⼊完成。

2.2 算法实现

//不带“哨兵”
void InsertSort(int A[], int n){   //A中共n个数据元素
    int i,j,temp;
    for(i=1; i<n; i++)
        if(A[i]<A[i-1]){           //A[i]关键字小于前驱
            temp = 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){          //A中从1开始存储，0放哨兵
    int i,j;
    for(i=2; i<n; i++)
        if(A[i]<A[i-1]){    
            A[0] = A[i];                  //复制为哨兵
            for(j=i-1; A[0] < A[j]; --j)  //从后往前查找待插入位置
                A[j+1] = A[j];            //向后挪动
            A[j+1] = A[0];                //复制到插入位置
        }
}

空间效率：空间复杂度=O(1)

时间效率: 平均时间复杂度=O(n²)

稳定性：插入排序是一种稳定的排序方法

2.3 算法优化

折半插入排序：先⽤折半查找找到应该插⼊的位置，再移动元素

当 low>high 时折半查找停⽌，应将 [low, i-1] 内的元素全部右移，并将 A[0] 复制到 low 所指位置 （即high+1）

当 A[mid]==A[0] 时，为了保证算法的“稳定性”，应继续在 mid 所指位置右边寻找插⼊位置

void InsertSort(int A[], int n){ 
    int i,j,low,high,mid;
    for(i=2;i<=n;i++){
        A[0] = A[i];                    //将A[i]暂存到A[0]
        low = 1; high = i-1;            //折半查找的范围

        while(low<=high){               //折半查找
            mid = (low + high)/2;       //取中间点
            if(A[mid]>A[0])             //查找左半子表
                high = mid - 1;
            else                        //查找右半子表
                low = mid + 1;
        }
        
        for(j=i-1; j>high+1;--j)        //统一后移元素，空出插入位置
            A[j+1] = A[j];
        A[high+1] = A[0]
    }
}

3.希尔排序

3.1 算法思想

先追求表中元素部分有序，再逐渐逼近全局有序。

先将待排序表分割成若⼲形如 L[i, i + d, i + 2d,…, i + kd] 的“特殊”⼦表，对各个⼦表分别进⾏直接插⼊排序。缩⼩增量d，重复上述过程，直到d=1为⽌。

3.2 算法实现

void ShellSort(int A[], int n){
    //A[0]为暂存单元，不是哨兵
    for(d=n/2; d>=1; d=d/2){   //步长递减（看具体要求，一般是1/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;]             //插入
            }
        }
    }
}

空间效率：空间复杂度=O(1)

时间效率: 平均时间复杂度=O(n²)

稳定性：希尔排序是一种不稳定的排序方法

4.冒泡排序

冒泡排序是基于交换的排序

4.1 算法思想

• 第一趟排序使关键字值最小的一个元素“冒”到最前面（其最终位置）

• 每趟冒泡的结果是把序列中最小（或最大）元素放到序列的最终位置，这样最多做n-1趟冒泡就能把所有元素排好序；

• 为保证稳定性，关键字相同的元素不交换；

4.2 算法实现

//交换
void swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
}
//冒泡排序
void BubbleSort(int A[], int n){   //从0开始存放
    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==false)
            return;//本趟遍历后没有发生交换，说明表已经有序，可以结束算法
    }
}

空间效率：空间复杂度=O(1)

时间效率: 平均时间复杂度=O(n²)

稳定性：冒泡排序是一种稳定的排序方法

5.快速排序

快速排序也是基于交换的排序

5.1 算法思想

在待排序表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)上， 这个过程称为⼀次“划分”。

然后分别递归地对两个⼦表重复上述过程，直⾄每部分内只有⼀个元素或空为⽌，即所有元素放在了其最终位置上。

5.2 算法实现

//用第一个元素将待排序序列划分为左右两个部分
int Partition(int A[], int low, int high){
    int pivot = A[low];     //用第一个元素作为枢轴
    while(low<high){
        while(low<high && A[high]>=pivot) --high; //high所指元素大于枢轴，high左移
        A[low] = A[high];   //high所指元素小于枢轴，移动到左侧

        while(low<high && A[low]<=pivot)  ++low;  //low所指元素小于枢轴，low右移
        A[high] = A[low];   //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, pivotpos - 1);         //划分左子表
    	QuickSort（A, pivotpos + 1, high);        //划分右子表
    }
}

空间效率：最好空间复杂度=O(log₂n)，最坏空间复杂度=O(n)

时间效率: 平均时间复杂度=O(nlog₂n)

稳定性：快速排序是一种不稳定的排序方法

快速排序是所有内部排序算法中平均性能最优的排序算法

6.简单选择排序

简单选择排序 和 堆排序 都属于选择排序

选择排序：每⼀趟在待排序元素中选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列

6.1 算法思想

每⼀趟在待排序元素中选取关键字最⼩的元素加⼊有序⼦序列。

6.2 算法实现

//交换
void swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
}
//简单选择排序
void SelectSort(int A[], int n){       //A从0开始
    for(int i=0; i<n-1; i++){          //一共进行n-1趟，i指向待排序序列中第一个元素
        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]);         //交换
    }
}

空间效率：空间复杂度=O(1)

时间效率：时间复杂度=O(n²)

稳定性：简单选择排序是一种不稳定的排序方法

7.堆排序

堆排序是选择排序中的一种

什么是堆？

若n个关键字序列L[1…n] 满⾜下⾯某⼀条性质，则称为堆（Heap） ：

① 若满⾜：L(i)≥L(2i) 且 L(i)≥L(2i+1) （1 ≤ i ≤n/2 ） —— ⼤根堆（⼤顶堆）

② 若满⾜：L(i)≤L(2i) 且 L(i)≤L(2i+1) （1 ≤ i ≤n/2 ） —— ⼩根堆（⼩顶堆）

堆从逻辑上来看，就是一棵顺序存储的完全二叉树

大根堆：完全二叉树中，根≥左、右

大根堆：完全二叉树中，根≤左、右

注意：在顺序存储的完全⼆叉树中， ⾮终端结点编号 i≤⌊n/2⌋

​ i 的左孩子 2i ；i 的右孩子 2i+1 ；i 的父节点 [i/2] ；

7.1 算法思想

每一趟在待排序元素中选取关键字最小（或最大）的元素加入有序子序列，堆顶元素的关键字最大或最小 （以下以大根堆为例）

① 将给定初始序列(n个元素)，建立初始大根堆：把所有非终端结点 从后往前都检查一遍，是否满足大根堆的要求——根 ≥ 左、右，若不满足，则将当前结点与更大的孩子互换

② 基于大根堆进行排序：每一趟将堆顶元素加入有序子序列中，堆顶元素与待排序序列中最后一个元素交换后，即最大元素换到末尾，之后该位置就不用改变，即移出完全二叉树(len=len-1)，把剩下的待排序元素序列再调整为大根堆；————“一趟处理”

③ 剩下最后一个元素则不需要再调整；

7.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]暂存子树的根结点
    //i为当前所选根结点的左孩子，i*=2是为了判断调整后再下一层是否满足大根堆
    for(int i=2*k; i<=len; i*=2){     //沿key较大的子结点向下筛选
        //i<len是为了保证i是有右兄弟的
        if(i<len && A[i]<A[i+1])      //判断：当前所选根结点的左、右结点哪个更大
            i++;                      //取key较大的子结点的下标
        if(A[0] >= A[i]) 
            break;                    //筛选结束：i指向更大的子结点
        else{
            A[k] = A[i];              //将A[i]调整至双亲结点上
            k=i;                      //修改k值，以便继续向下筛选
        }
    }
    A[k] = A[0]                       //被筛选的结点的值放入最终位置
}

//交换
void swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
}

//基于大根堆进行排序
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);       //把剩余的待排序元素整理成堆
    }
}

空间效率：空间复杂度=O(1)

时间效率: 平均时间复杂度=O(nlog₂n)

稳定性：堆排序是一种不稳定的排序方法

8.归并排序

归并：把两个或多个已经有序的序列合并成一个

8.1 算法思想

k路归并：每选出一个元素，需对比关键字k-1次；

外部排序通常采用归并排序，内部排序一般采用2路归并；

8.2 算法实现

//创建辅助数组B
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];     //将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只会执行一个 
    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);     //归并
    }if
}

空间效率：空间复杂度=O(n)

时间效率: 平均时间复杂度=O(nlog₂n)

稳定性：堆排序是一种稳定的排序方法

9.基数排序

9.1 算法思想

基数排序是一种非比较的稳定的算法，其原理是将整数按每个位数分别比较。它利用了桶的思想。

9.2 算法实现

#include<stdio.h>
#include<string.h>
#define N 10	//数组长度
#define D 10	//最大位数
int GetDigit(int M, int i) //取整数M的第i位数
{
	while(i > 1)
	{
		M /= 10;
		i--;
	}
	return M % 10;
}
void RadixSort(int num[], int len)
{
	int i, j, k, l, digit;
	int allot[10][N];//《分配数组》
	memset(allot, 0, sizeof(allot));//初始化《分配数组》
	for(i = 1; i <= D; i++)
	{
		//分配相应位数的数据，并存入《分配数组》
		for(j = 0; j < len; j++)	
		{			
			digit = GetDigit(num[j], i);
			k = 0;
			while(allot[digit][k])
				k++;
			allot[digit][k] = num[j];
		}
		//将《分配数组》的数据依次收集到原数组中
		l = 0; 
		for(j = 0; j < 10; j++)	
		{	
			k = 0;
			while(allot[j][k] > 0)
			{
				num[l++] = allot[j][k];
				k++;
			}
		}
		//每次分配，收集后初始化“分配数组”，用于下一位数的分配和收集
		memset(allot, 0, sizeof(allot));
	}
}
int main()
{
	int num[N] = {52, 20, 4, 10, 17, 39, 8, 300, 60, 81};
	RadixSort(num, N);
	for(int i = 0; i < N; i++)
		printf("%d ", num[i]);
	printf("\n");
	return 0;
}

10.外部排序

10.1 外部排序的原理

外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。

10.2 影响外部排序效率的因素

外部排序时间开销 = 读写外存时间 + 内部排序时间 + 内部归并时间

可以尝试用多路归并，减少归并的趟数，减少读写外村时间。

如果采用k路平衡归并的策略，，选出一个最小的元素需要对比关键字（k-1）次，同样也会导致内部归并时间的增加。

①可以用败者树，使得k路平衡归并所需要对比关键字次数减少

败者树（类似比赛）（k路归并）

• 可以视为一棵完全二叉树，k个叶子结点分别是当前比较的元素，非叶子结点用来记忆左右子树中的“失败者”，而让胜者往上继续比较，直到根结点。
• 构造完败者树后，选出最小（最大）元素，只需要对比关键字[log₂k]次

②也可以用置换-选择排序，从而让归并段的总数变少

③同样可以用最佳归并树减少读/写次数