数据结构

发表于 2021-03-14 更新于 2022-09-26 阅读次数：

第一章绪论

1.1 数据结构的基本概念

$数据结构（三要素）\begin{cases}逻辑结构\begin{cases}线性结构：线性表、栈、队列\\\\ 非线性结构：数，图，集合\end{cases}\\\\ 存储结构（物理结构）\\\\ 数据的运算\end{cases}$

1.2 算法的基本概念

1.2.1 时间复杂度

　　事前预估算法时间开销T(n)与问题规模n的关系。分析算法操作的执行次数x和问题模型n的关系x=f(n)。

常见数量级关系：（常对幂指阶）

$O(1)<O(\log_2n)<O(n)<O(nlog_2n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)$

6boW7T

1.2.2 空间复杂度

　　无论问题规模怎么变，算法运行所需的内存空间都是固定的常量。

第二章线性表

顺序表和链表对比

	顺序表	链表
优点	支持随机存储，存储密度高	不需要使用地址连续的存储单元
缺点	插入和删除操作需要移动大量元素	不可随机存储，存储密度低

2.1 线性表的基本概念

　　由零个或多个相同数据类型的数据元素组成的有限序列。

　　特性：有序，类型相同，有限。

2.1.1 数学定义

　　线性表是具有相同类型的n(n≥0)个数据元素的有限序列（a1,a2,a3,…,an-1,an），ai是表项，n是表长度。存在前驱后继。

2.1.2 线性表的操作

创建线性表
销毁线性表
清空线性表
将元素插入线性表
将元素从线性表中删除
获取线性表中某个位置的元素
获取线性表的长度

线性表的抽象数据类型定义：

ADT线性表（List）
    
Data
　　线性表的数据对象集合为{a1,a2,a3,...,an-1,an}，其中，除第一个元素a1外，每个元素有且只有一个直接前驱元素，直接后继元素同理，数据元素之间的关系是一一对应的。
    
Operation（操作）

//初始化，建立一个空的线性表L
InitList(&L);

//若线性表为空，返回true，否则返回false
ListEmpty(L);

//将线性表清空
ClearList(&L);

//将线性表L中的第i个位置的元素返回
GetElem(L,i);

//在线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素在表中序号表示成功，否则返回0表示失败
LocateElem(L,e)

//在线性表L中的第i个位置插入新元素e
ListInsert(&L,i,e);

//删除线性表L中的第i个位置元素，并用e返回其值
ListDelete(&L,i,&e);

//返回线性表L的元素个数
ListLength(L);;

//销毁线性表
DestroyList(&L);

endADT

&符号，对参数修改的结果需要“带回来”

2.2 线性表的存储方式

6bo3fH

如上图，线性表的存储细分以下两种：

1.将所有数据一次存储在连续的整块屋里空间中，叫做顺序存储结构；

2.数据分散的存储在物理空间中，通过一根线保存着它们之间的逻辑关系，链式存储结构。

2.3 顺序表

2.3.1 顺序表的概念

　　顺序表不仅存在“一对一”的数据关系，对数据的物理存储结构也有要求。顺序表存储结构时，会提前申请一整块足够大小的物理空间，然后将数据依次存储起来，存储时做到数据元素之间不留一丝细缝。

优缺点：

优点	缺点
随机访问，既可以在O(1)的时间内找到第i个元素	插入和删除操作需要移动大量元素
无需为表示元素之间的逻辑关系而增加额外的存储空间	当线性表长度变化较大时，难以确定存储空间的容量
逻辑关系相邻，物理位置相邻	分配空间需按固定大小分配，利用不充分

2.3.2 顺序表的基本操作

可以运行的完整代码：附录-顺序表的基本操作

1.顺序表初始化

顺序表需要实时记录一下两项数据：

顺序表申请的存储容量；
顺序表的长度，也就是表中存储数据元素的个数；

1	提示：正常状态下，顺序表申请的存储容量要大于顺序表的长度

因此，需要自定义顺序表

//静态分配
#define MaxSize 10
typedef struct SqList{
    int data[MaxSize];//声明data数组，长度为10
    int length;//记录当前顺序表的长度
}SqList;

//动态分配
#define InitSize 10 //默认最大容量
typedef struct{
    ElemType *data;//指针
    int MaxSize;//最大容量
    int length;//当前长度
}SeqList;

初步建立一个顺序表，需要如下工作：

//静态分配
void InitList(SqList &L){
    for(int i=0;i<MaxSize;i++)
        L.data[i]=0;//将所有数据元素初始值为0
    L.length=0;//初始化顺序表长度为0
}


//动态分配
void InitList(SeqList &L){
    L.data=(int *)malloc(InitSize*sizeof(int));
    L.length=0;
    L.MaxSize=InitSize;
}
//增加动态数组的长度
void IncreaseSize(SeqList &L,int len){
    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);//释放原来内存
}

2.顺序表的插入元素

在线性表的第i个位置插入元素e

需要注意

如果插入位置==不合理==，或者线性表长度$\ge$数组长度，应抛出异常
从最后一个数向前遍历到第i个位置，分别将他们==向后==移动一个位置
将插入元素==填在i处==
表长==+1==

#define MaxSize 10
typedef struct {
    int data[MaxSize];
    int length;
} SqList;

//在L的i处插入元素e
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) {//将第i个元素及之后的元素后移
        L.data[j] = L.data[j - 1];
    }
    L.data[i - 1] = e;//在位置i处放入e
    L.length++;//长度加1
    return true;
}

时间复杂度分析：

$\begin{cases}最好情况：新元素插入到表尾不需要移动元素，i=n+1,循环0次，O(1)\\最坏情况：插入到表头，n个元素全部向后移动，i=1，循环n次；O(n)\\平均情况：插入到任意位置概率相同p=\frac{1}{n+1}，则循环次数=np+(n-1)p+……+1·p=\frac{n(n+1)}{2}=\frac{n}{2},O(\frac{n}{2})\end{cases} $

3.顺序表的删除元素

删除第i个位置的元素，==注意比如要删除第5个数，需要将访问的下标为4==

删除位置==不合理==，抛出异常
==取出==删除元素
从删除元素位置开始遍历到最后一个元素位置，分别将他们==向前==移动一个位置
表长==-1==

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

4. 顺序表的查找元素

查找元素可以使用多种查找算法，比如二分查找、插值查找算法。

//第i个元素
ElemType GetElem(SqList L, int i) {
    return L.data[i - 1];
}

//按值查找
int LocateElem(SqList L,int e){
    for (int i = 0; i < L.length; ++i)
        if(L.data[i]==e)
            return i+1;
    return false;
}

5.顺序表的更改元素

实现过程：

找到目标元素
直接修改元素的值

//更改函数
void listAmend(SqList &L, int e, int newElem) {
    int add = locateElem(L, e);
    if (add == -1) {
        printf("顺序表中没有找到目标元素\n");
        return;
    }
    L.data[add - 1] = newElem;
}

2.4 单链表

只能从头结点依次顺序的向后遍历

区别：

带头节点（L->next==NULL是空）
不带头节点（L==NULL是空）

详情代码

2.4.1 单链表的基本概念

适合频繁的==插入，删除，更新==元素

特点：

不要求大片连续空间，改变容量方便
不可随机存取，要耗费一定空间存放指针

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

LNode是强调一个节点；LinkList强调一个指针

1.单链表的初始化

//初始化,不带头节点
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;
}

2.单链表的建立

头插法：头插法构造单链表时一直往单链表的头部插入结点

尾插法：一直往单链表的尾部插入结点

3.单链表的插入

找到第i个结点前一个结点的另一种方法

while (p != NULL && j < i - 1) {
    p = p->next;
    j++;
}

if (p == NULL) {//i值不合法
    return false;
}

//单链表的插入，带头节点
bool ListInsert(LinkList &L, int i, ElemType e) {
    if (i < 1)
        return false;
    LNode *p;//指针p指向当前扫描到的节点
    int j;//p指向第几个节点

    p = L;//L指向头结点
    //找到第i个节点的前一个节点
    for(j = 1;j<i;j++){
        p=p->next;
        if(p==NULL)
            cout<<"插入位置无效"<<endl;
    }
    
    LNode *s = (LNode *) malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;//将节点连接到p之后
    return true;
}

// 单链表的插入，不带头节点
......
if (i == 1) {
    LNode *s = (LNode *) malloc(sizeof(LNode));
    s->data = e;
    s->next = L;
    L = 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;
}

4.单链表的删除

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

//单链表删除，带头节点
bool LinkListDelete(LinkList &L,int i,ElemType &e){
    if(i<1)
        return false;
    LNode *p;
    int j;
    p=L;
    
    if(p!=NULL){
        for(j=1;j<i;j++){
            p=p->next;
        }
    }
    
    if(p==NULL || p->next==NULL)
        return false;
/*
    while (p!=NULL && j<i-1){
        p=p->next;
        j++;
    }
    //i值不合法或者第i-1个节点就是最后一个节点
    if(p==NULL || p->next==NULL)
        return false;
*/
    LNode *q = p->next;//q指向被删除节点
    e = q->data;//e用于返回元素的值
    p->next=q->next;
    free(q);
    return true;
}

删除指定节点：

bool DeleteNode(LNode *p) {
    if (p == NULL)
        return false;
    LNode *q = p->next;

    p.data = p->next->data;
    p->next = q->next;
    free(q);
    return true;
}

5.单链表的查找

//找到第i个节点，按位查找
LNode *GetElem(LinkList L, int i) {
    if (i < 0)
        return false;
    LNode *p;
    int j = 0;
    p = L;
    while (p != NULL && j < 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->next;
    return p;
}

2.5 双链表

双链表结点中有两个指针prior和next，分别指向前驱结点和后继节点；判空只需要看==head->next和head->prior==的任意一个是否为head指针即可。

特点：

不可随机存取，按位查找和按值查找只能通过遍历方式实现O(n)。

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

1.双链表初始化

bool InitDLinkList(DLinkList &L) {
    L = (DNode *) malloc(sizeof(DNode));

    if (L == NULL)//内存不足，分配失败
        return false;

    L->next = NULL;
    L->prior = NULL;
    return true;
}

2.双链表插入

//后插操作，在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;
    p->next = s;
    s->prior = p;
    return true;
}

2.5.3 双链表删除

//删除p节点的后继节点
bool DeleteNextDNode(DNode *p){
    if(p==NULL)
        return false;
    DNode *q = p->next;
    if(q==NULL)//p没有后继节点
        return false;
    p->next=q->next;
    if(q->next!=NULL)//如果q不是最后一个节点
        q->next->prior=p;//修改q的前驱
    free(q);
    return true;
}

2.5.4 双链表遍历

按位查找和按值查找只能通过遍历方式实现O(n)。

2.6 循环链表

2.6.1 循环单链表

与单链表的区别在：最后一个结点的指针不是NULL而是改为指向头结点，形成环，判空条件是：==头指针结点的指针是否等于头指针==

2.6.2 循环双链表

头结点的prior指针还要指向表尾结点

2.7 静态链表

这里“指针”表示的是：下一个元素在数组中的位置

初始化：

typedef struct {
    ElemType data;
    int next;
} SLinkList[MaxSize];

2.8 广义表

2.8.1 基本概念

简称表，它是线性表的推广。一个广义表是n(n>=0)个元素的一个序列，$a0,a_1,a_2,…,a{n-1}$若n=0是称为空表。其中没一个$a_i$或者是原子，或者是广义表。

通常记作：$LS=(a_1,a_2,…,a_n)$

其中：LS是表名，n表示表的长度，每个$a_i$是表的元素

表头：若LS非空，则其第一个元素$a_1$就是表头

记作$head(LS)=a_1$。表头可以是原子，也可以是子表
表尾：除表头之外的其他元素组成的表。表尾不是最后一个元素，而是一个子表

记作$tail(LS)=(a_2,…,a_n)$

2.8.2 广义表的性质

长度：最外层所包含元素的个数；

如：$C=(a,(b,c))$是长度为2的广义表
深度：该广义表展开后所包含括号的重数

如：$A=(b,c)的深度为1，B(A,d)的深度为2，C=(f,B,h)的深度为3$原子的深度为0，空表的深度为1
广义表可以和其他广义表共享。递归标的深度是无穷值，长度是有限值

第三章栈和队列

3.1 栈的概念

　　栈就是一种只能从表的一端存储数据且遵循“先进后出”原则的线性存储结构。压栈（push），弹栈（pop）。

栈遵循先进后出，栈存储结构的实现有以下两种方式：

顺序栈
链栈

栈的基本操作

InitStack(&S);//初始化栈，构造空栈分配内存空间
DestroyStack(&S);//销毁栈，销毁并释放

Push(&S,x);//进栈
Pop(&S,&x);//出栈

GetTop(S,&x);//读栈顶元素

==n个不同元素进栈，出栈序列的个数为：$\frac{1}{n+1}C{^2_{2n}}=\frac{1}{n+1}\frac{(2n)!}{n!+n!}$==

例如：n=3，则个数为：$\frac{6×5×4}{4×3×2×1}=5$

3.2 顺序栈

特点：大小不可改变

3.2.1 顺序栈的定义

特点：给个各数据元素分配连续的存储空间

typedef struct{   
    ElemType data[maxsize];    //定义一个数组大小为maxsize的数组，用来存放栈中数据元素    
    int top;              //栈顶指针                 
}SqStack;				  //顺序栈定义

3.2.2 顺序栈的操作

判空s.top==-1

栈满s.top==maxSize-1，maxSize-1是栈满时栈顶元素在数组中的位置

上溢：栈满继续入栈；下溢：栈空继续出栈

1.初始化栈S.top=-1

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

//进栈
bool Push(SqStack &S,ElemType x){
    if(S.top==MaxSize-1)
        return false;
    S.top++;
    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--;
    return true;
}

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

2.初始化栈S.top=0

bool InitStack(SqStack &S) {
    S.top = 0;
}

bool Push(SqStack &S,ElemType x){
    if(S.top==MaxSize)
        return false;
    S.data[S.top]=x;
    S.top++;
    return true;
}

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

3.2.3 共享栈：解决栈大小不可改变

初始化：

typedef struct{
    ElemType data[MaxSize];
    int top0;
    int top1;
}ShStack;

void InitStack(ShStack &S){
    S.top0=-1;
    S.top1=MaxSize;
}

//栈满条件：top0+1==top1

以下是定义结构体实现：

点我查看详情代码

3.3 链栈

把栈顶放在单链表的表头，用链表来存储栈的数据结构称为链栈。

链栈节点定义如下：

typedef struct StackNode{
    ElemType data;
    struct StackNode *next;
}StackNode,*LinkStack;

3.3.1 链栈的操作

链栈也有四个元素，包括两个状态和两个操作

状态：

1）栈空：StakNode->next == NULL，即栈没有后继节点时，栈为空

2）栈满：如果存储空间无限大，没有这种情况。

操作：

进栈是头插法建立链表的插入方法，出栈就是单链表的删除操作

以上是链栈的插入操作

以上是链栈的删除操作

链栈初始化

void InitStack(LinkStack &S){
    //构造一个空栈S，栈顶指针置空
    S->next=NULL;
    return OK;
}

进栈

Status Push(LinkStack &S,SElemType e){
    //栈顶插入元素e
    p=new StackNode;    //创建新节点
    p->data=e;          //将新节点数据域置为e
    p->next=S;          //将新结点与头结点建立逻辑关系
    S=p;                //更新头结点的指向
    return OK;
}

出栈

Status Pop(LinkStack &S,SElemType &e){
    //删除S的栈顶元素，用e返回值
    if(S==NULL) 
        return ERROR;     //栈空
    e=S->data;            //将栈顶元素赋给e
    p=S;                  //用p临时保存栈顶元素空间，以备释放
    S=S->next;            //修改栈顶指针
    delete p;             //释放原栈顶元素的空间
    return OK;
}

取栈顶元素

SElemType GetTop(LinkStack S){
    if(S!=NULL)
        return S->data;
}

#include<stdio.h>
#include<stdlib.h>

typedef struct LinkedStackNode{
    int data;
    LinkedStackNode *next;
}LinkedStackNode,*LinkedStack;

//初始化栈
int InitLinkedStack(LinkedStack &L){
    L=(LinkedStackNode*)malloc(sizeof(LinkedStackNode));
    L->next=NULL;
    return 1;
}

//销毁栈
int DestroyList(LinkedStack &L){
    LinkedStack temp;
    while(L){
        temp=L->next;
        free(temp);
        L=temp;
    }
    return 1;
}

//判断栈空
int LinkedStackEmpty(LinkedStack L){
    if(!L->next){
        printf("LinkedStack is Empty\n");
        return 1;
    }
    else{
        printf("LinkedStack isn't Empty\n");
        return 0;
    }
}

//入栈
int Push(LinkedStack &L,int e){
    LinkedStack temp;
    temp=(LinkedStackNode*)malloc(sizeof(LinkedStackNode));//创建临时结点
    temp->data=e;//将e赋值给temp的数据域
    temp->next=L->next;//temp结点指向下一结点
    L->next=temp;//更改L结点的指向temp结点
    return 1;
}

//出栈
int Pop(LinkedStack &L,int &e){
    LinkedStack temp;
    temp=L->next;
    e=temp->data;
    L->next=temp->next;
    free(temp);
    return 1;
}

//获取栈顶元素
int GetElem(LinkedStack L,int &e){
    return e=L->next->data;
}

int main() {              //记几个测试代码，可随意修改
    int n,i,e;
    LinkedStackNode *top;
    InitLinkedStack(top);
    LinkedStackEmpty(top);
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        Push(top, i);
    }
    Pop(top,e);
    printf("%d\n",e);
    GetElem(top, e);
    printf("%d\n",e);
    DestroyList(top);
    return 0;
}

3.4 队列的基本概念

　　与栈不同的是，队列的两端都“开口”，要求数据只能,从一端进，从另一端出。

1234

1	通常，称进数据的一端叫做“队尾”，出数据的一端叫做“队头”，添加数据叫做入队，出队列叫做出队

队列遵循先进先出的原则，队列存储结构的实现有以下两种方式：

顺序队列：在顺序表的基础上实现队列的结构
链队列：在链表的基础上实现队列结构

InitQueue(&Q)://初始化队列
DestroyQueue(&Q)://销毁队列

EnQueue(&Q,x);//入队
DeQueue(&Q,&x);//出队

GetHead(Q,&x);//读队头元素

1.队列初始化

typedef struct {
    ElemType data[MaxSize];
    int front, rear;//队头指针和队尾指针
} SqQueue;

void InitQueue(SqQueue &Q){
    Q.rear=0;
    Q.front=0;
}

//如果队列为空则Q.front=Q.rear

2.入队

//入队
bool InsertQueue(SqQueue &Q, ElemType e) {
    if ((Q.rear + 1) % MaxSize == Q.front)
        return false;
    Q.rear = (Q.rear + 1) % MaxSize;
    Q.data[Q.rear] = e;
    return true;
}

4.出队

//出队
bool DeleteQueue(SqQueue &Q, ElemType &e) {
    if (Q.rear == Q.front)
        return false;
    Q.front = (Q.front + 1) % MaxSize;
    e = Q.data[Q.front];
    return true;
}

5.读取队头元素

//读取队头元素
bool GetHead(SqQueue &Q,ElemType &x){
    if(Q.rear==Q.front)
        return false;
    x=Q.data[Q.front];
    return true;
}

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

3.4.1 队列的顺序存储

　　为了满足顺序队列中数据从队尾进，队头出且先进先出的要求，我们还需要定义两个指针（front 和 rear）分别用于指向顺序队列中的队头元素和队尾元素。

由于顺序队列初始状态没有存储任何元素，因此 top 指针和 rear 指针重合，且由于顺序队列底层实现靠的是数组，因此 top 和 rear 实际上是两个变量，它的值分别是队头元素和队尾元素所在数组位置的下标。

用顺序表来存储队列元素的数据结构称为队列的顺序存储结构，定义如下：

typedef struct{
    int data[maxsize];	//定义数组
    int front;			//队首指针
    int rear;			//队尾指针
}LinkQueue;				//顺序队列定义

3.4.2 队列的链式存储结构

链式队列的结构定义

//节点结构
typedef struct LinkNode {
    ElemType data;
    LinkNode *next;
}LinkNode;
//队列的链表结构
typedef struct LinkQueue {
    LinkNode *front;
    LinkNode *rear;
}LinkQueue;

1.链队的初始化

//带头节点,判空是Q.front==Q.rear
void initQueue(LinkQueue &Q){
    //初始化front和rear都指向头结点
    Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));
    Q.front->next=NULL;
}

//不带头结点，判空Q.front==NULL
void InitQueue(LinkQueue &Q){
    //初始化front和rear都指向NULL
    Q.front=NULL;
    Q.rear=NULL;
}

2.入队（带头节点）

void EnQueue(LinkNode &Q,ElemType x){
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
    s.data=x;
    s.next=NULL;
    Q.rear->next=s;//新节点插入到rear节点之后
    Q.rear=s;//修改rear指针
}

3.入队（不带头节点）

void EnQueue(LinkNode &Q,ElemType 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;//新节点插入到rear节点后
        Q.rear=s;//修改rear指针
    }
}

4.出队（带头节点）

//带头节点
bool DeQueue(LinkQueue &Q, ElemType &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;
}

5.出队（不带头节点）

//删除节点，不带头节点
bool DeQueue(LinkQueue &Q, ElemType &x) {
    if (Q.front == NULL)
        return false;
    LinkNode *p = Q.front;
    x = p->data;
    Q.front = p->next;
    if (Q.rear == p) {
        Q.front = NULL;
        Q.rear = NULL;
    }
    free(p);
    return true;
}

3.4.3 双端队列

操作受限的线性表

3.5 栈和队列的应用

3.5.1 栈的括号匹配问题

依次扫描所有字符，遇到左括号入栈，遇到有括号弹栈并检查是否匹配。

匹配失败的情况：①左括号单身②右括号单身③左右括号不匹配

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 (SqStackEmpty(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.5.2 栈的表达式求值

1.三种表达式

如何运算？

前缀：右优先；后缀：左优先。

3.栈实现思路

后缀表达式计算方法：

①左往右扫描下一个元素，直到处理完所有操作数。

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

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

前缀表达式计算方法：

①右往左扫描下一个元素，直到处理完所有操作数。

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

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

中缀表达式转后缀表达式：

中缀表达式的实现：是以上两种的结合

3.6 队列的应用

3.6.1 用队列实现树的层次遍历

3.6.2 用队列实现图的广度优先遍历

3.7 特殊矩阵的压缩存储

3.7.1 数组

一维数组：

a[i]的存放地址=$LOC + i * sizeof(ElemType)$ ==i默认从0开始==

二维数组：b[M][N]

行优先：b[i][j]存储地址=$LOC + (iN+j)sizeof(ElemType)$

列优先：b[i][j]存储地址=$LOC + (i+jM)sizeof(ElemType)$

3.7.2 对称矩阵存储

存储策略一（行优先）：

只存主对角线+下三角区域

矩阵元素在数组中的下标k=$\begin{cases}\frac{i(i-1)}{2}+j-1, i\ge j\{\frac{j(j-1)}{2}+i-1},i\lt j\end{cases}$

3.7.3 三角矩阵的压缩存储

存储下三角和主对角线：

存储上三角和主对角线：

3.7.4 三对角矩阵

3.7.5 稀疏矩阵的压缩存储

三元组策略：

链式存储——十字链表法

第四章串

4.1 串的基本概念

字符串是由零个或多个字符组成的有限序列。

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

主串：包含子串的串。

4.2 串的基本操作

StrAssign(&T,chars);//赋值
StrCopy(&T,S);//复制串，由串S复制得到串T
StrEmpty(S);//判空，若S为空串，返回True，否则false
StrLength(S);//求串长
ClearString(&S);//清空操作
DestroyString(&S);//销毁串
Concat(&T,S1,S2);//串联接。用T返回S1和S2拼接的新串
SubString(&Sub,S,pos,len);//求子串。用Sub返回串S的第pos个字符起长度为len的子串。
Index(S,T);//定位操作。若主串S中存在与串T值相同的串，则返回它在主串S的第一次出现的位置

4.2.1 串的顺序存储

//静态数组实现
typedef struct SString{
    char ch[MAXLEN];
    int length;
}

//动态数组实现
typedef struct HString{
    char *ch;
    int length;
}

HString S;
S.ch=(char *)malloc(MAXLEN * sizeof(char));
S.length=0;

4.2.2 串的链式存储

typedef struct StringNode{
    char ch;//每个节点存1个字符
    StringNode *next;
}StringNode,*String;

typedef struct StringNode{
    char ch[4];//每个节点存多个个字符
    StringNode *next;
}StringNode,*String;

链式存储基本操作实现

求子串：

比较串：

求位置：

4.3 字符串的模式匹配

4.3.1 暴力循环

将主串中所有长度为m的子串(最多n-m+1个)依次与模式串进行对比，直到找到一个完全匹配的子串或所有子串不匹配。

typedef struct SString {
    char ch[MAXSIZE];
    int length;
} StringNode, *String;

int violent(SString S, SString T) {
    int i = j = 1;
    while (i <= S.length && j <= T.length) {
        if (S.ch[i] == T.ch[i]) {
            i++;
            j++;
        } else {
            i = i - j + 2;
            j = 1;
        }
    }
    if (j > T.length)
        return i - T.length;
    else
        return 0;
}

最坏时间复杂度：O(mn)

4.3.2 KMP算法

int KMP(SString S, SString T,int next[]) {
    int i = j = 1;
    while (i <= S.length && j <= T.length) {
        if (j=0||S.ch[i] == T.ch[i]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    if (j > T.length)
        return i - T.length;
    else
        return 0;
}

最坏情况：O(m+n)

求next数组：

next数组作用：当模式串的第j个字符失配时，从模式串的第next[j]个继续往后匹配

==任何模式串的next[1]=0;next[2]=1==

模式串T=ababaa

next[0]	next[1]	next[2]	next[3]	next[4]	next[5]	next[6]
	0	1	1	2	3	4

SmartSelect_20220911-171036_Samsung Notes

4.3.3 KMP优化

nextval数组：

next[1]直接写0

第五章树和二叉树

5.1 树

5.1.1 树的定义

　　树是n(n>=0)个结点的有限集，它或为空树(n=0)；或为非空树，对于非空树T：

（1）有且仅有一个称之为根的结点；

（2）除根节点意外的其余结点可分为m（m>0）个互不相交的有限集T₁，T₂，…，T_m，其中每一个集合本身又是一棵树，并且称为根的子树。

5.1.2 树的基本术语

如图5.1（b）：

　　（1）结点：数中的一个独立单元。包含一个数据元素及若干指向其子树的分支，如图的A、B、C、D等。

　　（2）结点的度：结点拥有的子树数。如，A的度是3，C的度是1，F的度是0。

　　（3）树的度：树内各结点度的最大值

　　（4）叶子：度为0的结点称为叶子或终端结点。比如，K、L、F、G、M、I、J都是树的叶子。

　　（5）非终端结点：度不为0的结点称为非终端结点或分支节点。除根结点之外，也叫内部节点。

　　（6）双亲和孩子：结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲。如，B的双亲为A，B的孩子有E和Ｆ。

　　（７）层次：结点的层次从根开始定义，根为第一层，根的孩子为第二层等等。

　　（8）树的深度：树中结点的最大层次称为树的深度或高度，上图树的深度为4。

常用性质：

①结点数=总度数+1

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

③度为m的树第i层至多有$m^{i-1}$个节点$(i\ge1)$

④高度为h的m叉树至多有$\frac{m^{h}-1}{m-1}$个结点

将③的每层相加，是等比数列求和

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

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

⑥具有n个结点的m叉树的最小高度为$\left\lceil{log_m(n(m-1)+1)}\right \rceil$——所有结点都有m个孩子

$\frac{m^{h-1}-1}{m-1}\lt n \le \frac{m^{h}-1}{m-1}\\ {m^{h-1}-1}\lt n(m-1) \le {m^{h}-1}\\ m^{h-1}\lt n(m-1)+1 \le m^{h}\\ 取对数：h-1<log_m{(n(m-1)+1)\le h}$

5.2 二叉树

5.2.1 二叉树的定义

==n个结点，组成二叉树的个数为：$\frac{1}{n+1}C{^n_{2n}}=\frac{1}{n+1}\frac{(2n)!}{n!+n!}$==

　　二叉树（Binary Tree）是n(n>=0)个结点所构成的集合，它或为空树(n=0)；或为非空树，对于非空树T：

（1）有且仅有一个称之为根的结点；

（2）除根结点之外的其余结点分为两个互不相交的子集T₁和T₂，分别称为T的左子树和右子树，且T₁和T₂本身又都是二叉树。

二叉树的基本特点

结点的度都<=2
有序树（子树有序，不能颠倒）

5.2.2 二叉树的性质

性质1 在二叉树的第i层上至多有2^i-1个节点（i>=1）。

性质2 深度为k的二叉树至多有2^k-1个节点（满二叉树）（k>=1）。

性质3 对任何一个二叉树T，如果度为0、1、2的结点个数分别为n₀、n₁、n₂，则n₀=n₂+1。

$假设树中结点总数为n，则\\ \begin{cases} n=n_0+n_1+n_2\\ n=n_1+2n_2+1 \end{cases}\\ 因此：n_0=n_2+1$

性质4 具有n个结点的完全二叉树的高度为：$\left \lfloor \log_2n\right \rfloor+1$

$\left \lfloor x\right \rfloor取不大于x的最大整数，\left \lceil x \right \rceil取不小于x的最小整数。$

性质5 如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到第[log₂n]+1层，每层从左到右),则对任一结点i（1<=i<=n),有：

（1）如果i＝1，则结点i无双亲，是二叉树的根；如果i>1，则其双亲是结点[i/2]。

（2）如果2i>n，则结点i无左孩子（结点i为叶子结点）；若2i==n，其左孩子是结点2i（i为最后一个非叶子结点）。

（3）如果2i＋1>n，则结点i无右孩子；若2i＋1==n ，其右孩子是结点2i＋1（i为最后一个非叶子结点）。

5.2.3 特殊的二叉树

（1）满二叉树：一个深度为h且有2^h-1个结点的二叉树。

特点：

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

②不存在度为1的节点

③按层序从1开始编号，节点i的左孩子为2i，右孩子为2i+1，父节点为i/2

（2）完全二叉树：高度为h的，有n个节点的二叉树，当且仅当其每个结点都与高度为h的满二叉树中编号从1至n的结点一一对应（且最后一层叶子不满，全部集中在左边）

特点：

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

②最多只有一个度为1的节点($n_0只能等于0或1$)

③按层序从1开始编号，节点i的左孩子为2i，右孩子为2i+1，父节点为i/2

④$i \le \frac{n}{2}$为分支节点，$i > \frac{n}{2}$为叶子结点

（3）二叉排序树：一颗二叉树或者是空二叉树，或者是如下性质的二叉树：

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

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

③左、右子树又各是一颗二叉排序树

（4）平衡二叉树：树上任一结点的左子树和右子树的高度只差不超过1

5.2.4 二叉树的存储结构

1 顺序存储结构

==顺序存储只适合完全二叉树==

struct TreeNode{
    ElemType value;
    bool isEmpty;
}

TreeNode t[MaxSize]：

定义一个长度为MaxSize的数组t，按照从上到下、从左到右的顺序依次存储完全二叉树的各个结点

2 链式存储结构

如图 1 所示，此为一棵普通的二叉树，若将其采用链式存储，则只需从树的根节点开始，将各个节点及其左右孩子使用链表存储即可。因此，图 1 对应的链式存储结构如图 2 所示：

由图 2 可知，采用链式存储二叉树时，其节点结构由 3 部分构成（如图 3 所示）：

指向左孩子节点的指针（Lchild）；
节点存储的数据（data）；
指向右孩子节点的指针（Rchild）；

表示该节点结构的 C 语言代码为：

typedef struct BiTNode{  
    TElemType data;//数据域   
    struct BiTNode *lchild,*rchild;//左右孩子指针    
    struct BiTNode *parent;//可以有可以没有
}BiTNode,*BiTree;

5.3 遍历二叉树

二叉树由3个基本单元组成：根结点、左子树、右子树。因此可以分为三个遍历部分。可以参考具体链接。

DLR——先序遍历，根左右
LDR——中序遍历，左根右
LRD——后序遍历，左右根

5.3.1 先序遍历

先序遍历：访问根节点，访问当前节点的左子树；若当前节点无左子树，则访问当前节点的右子树。O(h)

void PreOrder(BiTree T){
    if(T!=NULL){
        cout<<T->data;
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

5.3.2 中序遍历

中序遍历：访问当前节点的左子树；访问根节点；访问当前节点的右子树。

中序遍历的递归算法

void InOrder(BiTree T){
    if(T){
        InOrder(T->lchild);
        cout<<T->data;
        Inorder(T->rchild);
    }
}

中序遍历的非递归算法

①初始化一个空栈S，指针p指向根结点

②申请一个结点空间q，用来存放栈顶弹出的元素

③当p非空或者栈S非空时，循环执行以下操作：

如果p非空，则将p进栈，p指向该结点的左孩子；
如果p为空，则弹出栈顶元素并访问，将p指向该结点的右孩子。

void InOrder(BiTree T){
    InitStack(S);
    p=T;
    q=new BiTNode;
    while(p||!StackEmpty(S)){
        if(p){//p非空
            Push(S,p);//根指针进栈
            p=p->lchild;//根指针进栈，遍历左子树 
        }else{//p空
            Pop(S,q);//退栈
            cout<<q->data;//访问根结点
            p=q->rchild;//遍历右子树
        }
    }
}

5.3.3 后序遍历

后序遍历：从根节点出发，依次遍历各节点的左右子树，直到当前节点左右子树遍历完成后，才访问该节点元素。

5.3.4 层序遍历

层次遍历：从上往下一层一层遍历。

算法思想：

①初始化一个辅助队列

②根节点入队

③队列非空，则队头结点出队，访问该节点，并将其左右孩子插入队尾

④重复③直至队列为空

typedef struct BiTNode{
    char data;
    BiTNode *lchirld,*rchild;
};

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

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


void LevelOrder(BiTree T){
    LinkQueue Q;
    InitQueue(Q);//初始化辅助队列
    BiTree p;
    EnQueue(Q,T);//根节点入队
    while(!isEmpty(Q)){//队列不空则循环
        DeQueue(Q,p);//队头结点出队
        cout<<p->data;
        if(p->lchild!=NULL)
            EnQueue(Q,p->lchild);//左孩子入队
        if(p->rchild!=NULL)
            EnQueue(Q,p->rchild);//右孩子入队
    }
}

5.3.5 二叉树的遍历应用

由遍历序列构造二叉树

前序序列：ADBCE

中序序列：BDCAE

后序序列：EFAHCIGBD

中序序列：EAFDHCBGI

层序序列：DABEFCGHI

中序序列：EAFDHCBGI

先序遍历的顺序建立二叉链表

1.扫描序列，读入字符ch。

2.如果ch是一个“#”字符，则表明该二叉树为空树，即T为NULL；否则执行以下操作：

①申请一个节点空间T；

②将ch赋给T->data;

③递归创建T的左子树；

④递归创建T的右子树；

void CreatBiTree(BiTree &T){
    //按先序次序输入二叉树中的结点的值，创建二叉链表表示二叉树T
    cin>>ch;
    if(ch=='#')
        T=NULL; //递归结束，建立空树
    else{//递归创建二叉树
        T=new BiTNode;//生成根节点
        T->data=ch;//根结点数据域为ch
        CreateBiTree(T->lchild);//递归创建左子树
        CreateBiTree(T->rchild);//递归创建右子树
        
    }
}

复制二叉树

①若二叉树不空，则首先复制根结点（相当于先序遍历算法中访问根节点的语句）

②然后分别复制二叉树根结点的左子树和右子树（相当于先序遍历中递归遍历左子树和右子树的语句）

void Copy(BiTree T, BiTree &NewT){
    if(T==NULL){
        NewT=NULL;
        return;
    }
    else{
        NewT=new BiTNode;
        NewT->data=T->data;
        Copy(T->lchild,NewT->lchild);
        Copy(T->rchild,NewT->rchild);
    }
}

计算二叉树深度

如果是空树，递归结束，深度为0，否则

递归计算左子树的深度为m；

递归计算右子树的深度为n；

如果m>n，二叉树的深度为m+1，否则n+1。

int Depth(BiTree T)
{//计算二叉树T的深度
    if(T==NULL)
        return 0;//如果是空树，深度为0, 递归结束
    else{
        int m=Depth(T->lchild);//递归计算左子树的深度记为m
        int n=Depth(T->rchild);//递归计算右子树的深度记为n
        return m>n ? m+1 : n+1;//二叉树的深度为m与n的较大者加1
    }
}

统计二叉树中结点的个数

如果是空树，则结点个数为0,；否则，结点个数为左子树的结点个数加上右子树的结点个数再加上 1

int NodeCount(BiTree T){
    //统计二叉树T中结点的个数
    if (T==NULL) 
        return 0; //如果是空树，则结点个数为0, 递归结束
    else if(T->lchild==NULL&&T->rchild==NULL)
        return 1;
    else
        return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;//否则结点个数为左子树的结点个数＋右子树的结点个数+l
}

计算二叉树叶子结点的数

int LeadCount(BiTree T){
    if(T==NULL) 	//如果是空树返回0
        return 0;
    if (T->lchild == NULL && T->rchild == NULL)
        return 1; //如果是叶子结点返回1
    else return LeafCount(T->lchild) + LeafCount(T->rchild);
}

在n个结点的二叉链表中，有n+1个空指针域

二叉链表长这个样子：

5.4 线索二叉树

是为了解决找前驱和后继不方便：

==n个结点的二叉树有n+1个空链域==

遍历二叉树是以一定规则将二叉树中的结点排列成一个线性序列，得到二叉树中结点的先序序列、中序序列或后序序列。普通二叉树只能找到结点的左右孩子信息，而该结点的直接前驱和直接后继只能在遍历过程中获得。若将某种遍历序列某个结点的前驱和后继预存起来，则从第一个结点开始就能很快“顺藤摸瓜”而遍历整个树。

如何保存这类信息？

$两种解决方法=\begin{cases} 增加两个域：fwd和bwd;　　　使得结构的存储密度大大降低\\ \\ 利用空链域（n+1个空链域）　　　　　　　　　　 \end{cases}$

所以基于某种遍历规则：
1）若结点有左子树，则lchild指向其左孩子；
否则， lchild指向其直接前驱(即线索)；

2）若结点有右子树，则rchild指向其右孩子；
否则， rchild指向其直接后继(即线索) 。

为了避免混淆，增加两个标志域

其中：

$LTag=\begin{cases} 0　lchild域指示结点的左孩子　\\ 1　lchild域指示结点的前驱　　　　　　　　　　 \end{cases}$ $RTag=\begin{cases} 0　lchild域指示结点的左孩子　\\ 1　lchild域指示结点的后继　　　　　　　　　　 \end{cases}$

二叉树二叉线索类型定义如下：

typedef struct ThreadNode{
    ElemType data;
    struct BiThrNode *lchild,*rchild;
    int LTag,RTag;
}ThreadNode,*ThreadTree;

	中序线索化	先序线索化	后序线索化
找前驱	√	×	√
找后继	√	√	×

5.4.1 中序线索化

5.4.2 先序线索化

找前驱：根据遍历规则（NLR），结点只可能是根的后继

二叉链表变三叉链表，就可以找：

找后继：

5.5.3 后序线索化

找前驱：

找后继：根据结点遍历规则(LRN)，结点只能是前驱元素；

5.5 森林与树

5.5.1 树的存储结构

1.双亲表示法（顺序存储）：以一组连续空间存储树的结点，每个结点中保存指向双亲的“指针”。

根结点固定存储在0，-1表示没有双亲

双亲实现树定义：

#define MAX_TREE_SIZE 100   //最大结点个数
typedef struct PTNode{          //树结点定义
    ElemType data;                 
    int parent;                        
} PTNode;

typedef struct PTNode{          //树定义
    PTNode nodes[MAX_TREE_SIZE];                 
    int n;        //结点数                       
} PTree;

删除元素：

方案一：将p->parent直接改为-1，这样会导致有一条空数据，遍历查询的时候效率低

方案二：将最后一条数据移到该删除位

2.孩子表示法：

（1）多重链表法（两种）

（2）孩子链表法（顺序+链式）：将每个结点的孩子结点排列起来，看成一个线性表，且以单链表作存储结构，n个结点有n个孩子链表，n个头指针组成线性表。

typedef struct CTNode{
    int child;//孩子结点在数组中的位置
    CTNode *next;//下一个孩子
};

typedef struct CTBox{
    ElemType data;
    CTNode *firstChild;
};

typedef struct CTree{
    CTBox nodes[MAX_TREE_SIZE];
    int n,r;//结点数和根的位置
};

3.孩子兄弟表示法（链式存储）：每个节点除值域外，还包括两个指针，分别指向该节点的第一个孩子和下一个兄弟。

结点结构：

结构定义：

typedef char ElemType;

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

5.5.2 森林和二叉树的转换

1.树—->二叉树

方法（树的孩子兄弟表示法）：

①加线：树中所有相邻兄弟间加一连线；
②抹线：对树中的每个结点，只保留其与第一个孩子间的连线，删去它与其他孩子间连线；
③旋转：以树根为轴心，将整棵树顺时针旋转45度，使之结构层次分明。

　　任何一棵树和树对应的二叉树，其根结点的右子树必空。

示例：

特点：

左分支——-父子关系右分支—-兄弟关系
根没有兄弟，所以一棵树转换后的二叉树一定==只有左子树==

2.二叉树—->树

①若某结点的左孩子结点存在，将左孩子结点的右孩子结点、右孩子结点的右孩子结点……都作为该结点的孩子结点，将该结点与这些右孩子结点用线连接起来；

②删除原二叉树中所有结点与其右孩子结点的连线；

③整理（1）和（2）两步得到的树，使之结构层次分明。

3.森林—->二叉树

方法：

①将森林中每棵树转换成相应的二叉树；
②第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连起来后，此时，所得二叉树即是森林转换得到的。

示例：

4.二叉树—->森林

①先把每个结点与右孩子结点的连线删除，得到分离的二叉树；

②把分离后的每棵二叉树转换为树；

③整理第（2）步得到的树，使之规范，这样得到森林。

特点：根没有右孩子，则转换成的是树，否则转换成的是森林。

5.5.3 森林和树的遍历

1.树的遍历

先根遍历：若树不空，则先访问根结点，然后依次从左到右先根遍历根的各棵子树。与对应二叉树先序序列相同。
后根遍历：若树不空，则先依次从左到右后根遍历根的
各棵子树，然后访问根结点；与对应二叉树中序遍历相同。
层次遍历（用队列实现）：①若树非空，根节点入队；②队列非空，队头元素出队并访问，同时该元素的孩子依次入队；③重复②直到队列为空

2.森林的遍历

先序遍历森林：

若森林非空，则可按下述规则遍历：

①访问森林中第一棵树的根结点；

②先序遍历第一棵树的根结点的子树森林；

③先序遍历除去第一棵树之后剩余的树构成的森林。

中序遍历森林

若森林非空，则可按下述规则遍历：

①中序遍历森林中第一棵树的根结点的子树森林；

②访问第一棵树的根结点；

③中序遍历除去第一棵树之后剩余的树构成的森林。

5.6 哈夫曼树及其应用

5.6.1 哈夫曼树的基本概念

前缀码：在一个字符集中，任何一个字符的编码都不是另一个字符编码的前缀。

　　哈夫曼树又称最优树，是一类带权路径长度最短的树。

（1）路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。

（2）路径长度：路径上的分支数目称作路径长度。

（3）树的路径长度：从树根到每一结点的路径长度之和。

（4）权：赋予某个实体的一个量，是对实体的某个或某些属性的数值化描述。在数据结构中，实体有结点（元素）和边（关系）两大类，所以对应有结点权和边权。结点权或边权具体代表什么意义，由具体情况决定。如果在一棵树中的结点上带有权值，则对应的就有带权树等概念。

（5）结点的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积。

（6）树的带权路径长度：树中所有叶子结点的带权路径长度之和，通常记作$WPL=\sum_{k=1}^{n}{w_k}{l_k}$

（7）哈夫曼树：假设有m个权值{$w_1,w_2,···,w_m$}，可以构造一颗含有n个叶子结点的二叉树，每个叶子结点的权为$w_i$，则其中带权路径长度WPL最小的二叉树称作最优二叉树或哈夫曼树。

5.6.2 哈夫曼树的构造算法

1.哈夫曼树的构造过程

2.哈夫曼算法的实现

由于哈夫曼树中没有度为1的结点，则一颗有n个叶子结点的哈夫曼树共有2n-1个结点。

哈夫曼树的存储表示：

typedef struct{
    int weight;					//结点的权值
    int parent,lchild,rchild;	//结点的双亲、左孩子、右孩子
}*HuffmanTree;					//动态分配数组存储哈夫曼树

为了实现方便，数组0号单元不使用，从1号单元开始使用，所以数组大小为2n。叶子结点存储在前面部分1~n个位置，后面的n-1个位置存储其余非叶子结点。

构造哈夫曼树算法实现可以分为两部分：

①初始化：首先动态申请2n个单元；然后循环2n-1次，从1号单元开始，依次将1至2n-1所有单元中的双亲、左孩子、右孩子的下标都初始化为0,；最后循环n次，输入前n个单元中叶子结点的权值。

②创建树：循环n-1次，通过n01次的选择、删除与合并来创建哈夫曼树。选择是从当前森林中选择双亲为0且权值最小的两个树根节点s1和s2；删除是指将结点s1和s2的双亲改为非0；合并就是将s1和s2的权值和作为一个新结点的权值依次存入到数组的第n+1之后的单元中，同时记录这个节点做孩子的下标为s1，右孩子的下标为s2。

第六章图

6.1 图的定义和基本术语

6.1.1 图的定义

　　图由两个集合V(Vertex顶点集)和E(Edge边集)组成，记为G=(V,E)，其中V是顶点的有==穷非空==集合，E是V中顶点偶对的==有穷集合==，这些顶点偶对称为边。V(G)和E(G)通常分别表示图G的顶点集合和边集合。

　　无向图：每条边都没有方向

　　有向图：每条边都有方向

　　完全图：任意两点都有一条边相连

6.1.2 图的基本术语

无向图：度之和是2e

有向图：出度=入度=e

顶点的度：与该顶点相关联的边的数目，记为TD(v)。

　　在有向图中，顶点的度等于该顶点的入度与出度之和。

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

　　顶点v的出度是以v为始点的有向边的条数，记做OD(v)

问：当有向图仅有1个顶点的入度为0，其余顶点的入度均为1，此时是何结构？
答：是一棵树；一颗有向树。

路径：连续的边构成的顶点序列。

路径长度：路径上边或弧的数目/权值之和。

回路(环)：第一个顶点和最后一个顶点相同的路径。

简单路径：路径中各顶点均不重复出现的路径。

简单回路(简单环)：除路径起点和终点相同外，其余顶点均不重复出现的路径。

连通图（强连通图）：在无向图中，任意两个顶点都是连通的。在有向图中，任何一对顶点都是强连通的，则是强连通图。

	无向图	有向图
连通图（强连通图）	至少n-1条边	至少n条边
非连通图	最多$C{^n_{n-1}}$条边

连通分量：无向图G 的极大连通子图称为G的连通分量。极大连通子图意思是：该子图是 G 连通子图，将G 的任何不在该子图中的顶点加入，子图不再连通。

强连通分量：有向图G 的极大强连通子图称为G的强连通分量。极大强连通子图意思是：该子图是G的强连通子图，将D的任何不在该子图中的顶点加入，子图不再是强连通的。

子图：设有两个图G=（V，{E}）、G1=（V1，{E1}），若V1 V，E1 E，则称 G1是G的子图。例:(b)、(c) 是 (a) 的子图

极小连通子图：该子图是G 的连通子图，在该子图中删除任何一条边，子图不再连通。（n-1条边）

生成树：包含无向图G 所有顶点的极小连通子图。

n个顶点的树，必有n-1条边

生成森林：对非连通图，各个连通分量的生成树构成的集合。

6.2 图的存储结构

　　图没有顺序存储结构，但可以借助二维数组来表示元素之间的关系，即邻接矩阵表示法。另一方面，图的链式存储有==邻接表==、==十字链表==和==邻接多重表==。

6.2.1 邻接矩阵法

以顶点做表格，两个顶点之间有连接记为1，没有记为0

数组实现，因为空间复杂度高，适合存储稠密图。

顺序表（邻接矩阵）表示法

①建立一个顶点表（记录各顶点信息）和一个邻接矩阵（表示各顶点之间关系）

②结点数为n的图G=(V,E)的邻接矩阵A是n×n的。将G的顶点编号为$v_1,v_2,…,v_n$，则

$A.Edge[i][j]=\begin{cases}1,　　如果　<v_i,v_j>或者(v_i,v_j)是E(G)中的边\\ 0,　　反之 \end{cases}$

无向图的邻接矩阵表示法

特点1：无向图的邻接矩阵是对称的；

特点2：顶点i 的度＝第 i 行 (列) 中1 的个数；$如：D(v_3)=3$

特点3：完全图的邻接矩阵中，对角元素为0，其余为1。

有向图的邻接矩阵表示法

注意：在有向图的邻接矩阵中，

　　　第i行含义：以结点$v_i$为尾的弧（即出度边）；

　　　第i列含义：以结点$v_i$为头的弧（即入度边）。

特点1：有向图的邻接矩阵可能是不对称的。

特点2：顶点的出度=第i行元素之和

　　　　顶点的入度=第i列元素之和

　　　　顶点的度=第i行元素之和+第i列元素之和

邻接矩阵的性质：

1.==邻接矩阵法求顶点的度/出度/入度的时间复杂度是$O(|V|)$==

2.设图G的邻接矩阵A，则$A^n$的元素$A^n[i][j]$意思是由顶点i到顶点j的长度为n的路径的数目

网（有权图）的邻接矩阵表示法

定义为：

$N.Edge[i][j]=\begin{cases} W_{ij}　　<v_i,v_j>或(v_i,v_j){\in}V_R\\ \infty　　　无边（弧） \end{cases}$

邻接矩阵的存储表示

#define MaxVertexNum 100//顶点最大数
#define INFINITY //最大的int值，表示无穷大
typedef char VertexType;
typedef int EdgeType;
typedef struct{
    VertexType Vex[MaxVertexNum];//顶点表
    EdgeType Edge[MaxVertexNum][MaxVertexNum];//邻接矩阵，边表
    int vexnum,arcnum;//图的当前顶点数和边数
}MGragp;

算法：采用邻接矩阵表示法创建无向网

算法步骤：

①输入总顶点数和总边数

②依次输入店的信息存入顶点表中

③初始化邻接矩阵，使每个权值初始化为极大值。

④构造邻接矩阵。依次输入每条边依附的顶点和其权值，确定两个顶点在图中的位置之后，使相应边赋予相应的权值，同时使其对称边赋予相同的权值。

Status CreateUDN(AMGraph &G){
    //采用邻接矩阵表示法，创建无向网G
    cin>>G.vexnum>>G.arcnum;//输入总顶点数，总边数
    for(i=0;i<G.vexnum;i++)//依次输入点的信息
        cin>>G.vexs[i];
    for(i=0;i<G.vexnum;i++)//初始化邻接矩阵，边的权值均值为极大值MaxInt
        for(j=0;j<G>vexnum;j++)
            G.arcs[i][j]=MaxInt;//构造邻接矩阵
    for(k=0;k<g.arcnum;k++){
        cin>>v1>>v2>>w;//输入一条边依附的顶点及权值
        i=LocateVex(G,v1);j=LocateVex(G,v2);//确定v1和v2在G中的位置，即顶点数组的下标
        G.arcs[i][j]=w;//边<v1,v2>的权值为w
        G.arcs[j][i]=G.arcs[i][j];//置<v1,v2>的对称边<v2,v1>的权值为w
    }//for
    return OK;
}

算法分析

该算法的时间复杂度是$O(n^2)$。

6.2.2 邻接表法

顺序+链式存储，适合存储稀疏图

定义邻接表存储：

typedef struct ALGraph{
    AdjList vertices;//顶点
    int vexnum,arcnum;//边数和条数
};

定义存储顶点信息的结构体:

typedef struct VNode{
    VertexType data;
    ArcNode *first;
}VNode,AdjList[MaxVertexNum];

定义存储边信息的结构体：

typedef struct ArcNode{
    int adjvex;//边指向哪个节点
    ArcNode *next;//指向下一条弧的指针
};

邻接表和邻接矩阵对比

	邻接矩阵	邻接表
空间复杂度	$O(	V	^2)$	无向图$O(	V	+2	E	)$；有向图 $O(	V	^2)$
适用于	存储稠密图	存储稀疏图
表示方式	唯一	不唯一
计算度/入度/出度	遍历对应行/列	除了有向图的度和入度，其余很方便
找相邻的边	遍历对应行/列	找有向图的入边不方便，其余很方便

6.2.3 十字链表法和邻接多重表

1.十字链表法：只存储有向图

==按照绿色找出边，按照橙色找入边==

性能分析：

空间复杂度：$O(|V|+|E|)$

2.邻接多重表：只存储无向图

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

6.2.4 图的基本操作

1.判断图G是否存在或(x,y)

无向图/有向图：

邻接矩阵

只需要判断矩阵表中相应位是否等于1，需要O(1)的时间复杂度
邻接表

最好情况：目标结点为第一个连接的边，O(1)

最坏情况：遍历完结点所连接的E-1条边，O(E-1)

2.列出图G中与结点x邻接的边

有向图/无向图

邻接矩阵：

遍历某行或者某列，输出值为1的元素，O(V)
邻接表：

最好情况：所连边只有一个，O(1)

最坏情况：遍历完所连接的边，O(V)

3.在图G中插入顶点x

邻接矩阵：

在方阵后新加入一行一列，O(1)
邻接表：

在表末尾插入一个新元素，O(1)

4.在图G中删除顶点x

邻接矩阵：

将该行该列元素全置空，O(V)，【用一个bool型变量，判断结点是否为空】
邻接表：

最好情况：该结点并没有连边，O(1)

最坏情况：当前删除的顶点后边连接了尽可能多的边，这样导致该结点连接在了所有的边上，O(E)

5.若无向边(x,y)或者有向不存在，则向图G中添加该边

邻接矩阵：

只需要更改该结点的值为1，O(1)
邻接表：

需要在这两个结点的位置头插法或尾插法，如上图，O(1)

6.求图G中顶点x的第一个邻接点，若有则返回顶点号；若x没有邻接点或图中不存在x，则返回-1

邻接矩阵：

扫描该行直到第一个1，最好O(1)，最坏O(V)
邻接表

该结点链表中的第一个顶点，O(1)

7.假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1

邻接矩阵：

扫描该行的值直到第二个1，O(1)~O(V)
邻接表：

该结点链表中的第一个的下一个顶点，O(1)

6.3 图的遍历

6.3.1 深度优先搜索

对于一个连通图，深度优先搜索遍历的过程如下：

①从图中某个顶点v出发，访问v。

②找出刚访问过的顶点的第一个未被访问的邻接点，访问该顶点。以该顶点为新顶点，重复此步骤，直至刚访问的顶点没有被访问的邻接点为止。

③返回前一个访问过的且仍有未被访问的邻接点的顶点，找出该顶点的下一个未被访问的邻接点，访问该顶点。

④重复步骤②和③，直至图中所有顶点都被访问过，搜索结束。

访问顺序是：$v_1->v_2->v_4->v_8->v_5->v_3->v_6->v_7$

6.3.2 广度优先搜索

广度优先搜索遍历过程如下：

①从图中某个顶点v出发，访问v。

②依次访问v的各个未被访问过的邻接点。

③分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问。重复步骤③，直至图中所有已被访问的顶点的邻接点都被访问到。

图6.17访问顺序：$v_1->v_2->v_3->v_4->v_5->v_6->v_7->v_8$

bool visited[MAX_VERTEX_NUM];//初始都为false

//为了解决非连通图的BFS，调用BFS次数=连通分量数
void BFSTraverse(Graph G){
    for(int i=0;i<G.vexnum;i++)
        visited[i]=FALSE;//访问标记数组初始化
    InitQueue(Q);//初始化辅助队列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);//访问初始化顶点v
    visited[v]=TRUE;//对v做标记
    Equeue(Q,v);//v入队
    while(!isEmpty(Q)){//如果队列不为空
        DeQueue(Q,v);//v出队
        for(w=FirstNeighbor(G,v);w>=0;w=NextNeighBor(G,v,w)){
            if(!visited[w]){//如果w是v没被访问过的邻接顶点
                visit(w);//访问w
                visited[w]=TRUE;//将w做标记表示已访问过
                EnQueue(Q,w);//w入队
            }
        }
    }
}

6.4 图的应用

6.4.1 最小生成树

使边的权值之和最小的生成树

==连通图才有生成树，非连通图只有森林==

1.Prim算法

从某个顶点开始构建生成树；每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入。$O(v^2)$与顶点有关，适合边稠密图

邻接表存储的时间复杂度：O(n+e)

2.Kruskal算法

每次选择一条权值最小的边，使这条边的两头连通（已连通就不选），直到所有结点连通。$O(Elog_2E)$与边有关，适合边稀疏图

6.4.2 最短路径问题

$最短路径问题\begin{cases}单源最短路径\begin{cases}BFS算法（无权图）\\\\Djkstra算法（带权图、无权图）\end{cases}\\\\ 各顶点间的最短路径：Floyd算法（带权图、无权图）\end{cases}$

1.Djkstra算法

2.Floyd算法

求每一对顶点之间的最短路径

使用动态规划的思想，将问题的求解分为多个阶段

对于n个顶点的图G，求任意一对顶点$v_i$—>$v_j$之间的最短路径课分为如下几个阶段：

0：若允许在$v_0$中转，最短路径为？
1：若允许在$v_0、v_1$中转，最短路径为？
2：若允许在$v_0、v_1、v_2$中转，最短路径为？
···

n-1：若允许在$v0、v_1、v_2…v{n-1}$中转，最短路径为？

6.4.3 有向无环图

若一个有向图不存在环，就是有向无环图，简称DAG图

1.有向无环图来描述表达式

6.4.4 AOV 网

AOV网（Activity On Vertex NetWork，==用顶点表示活动==的网）：用DAG图表示一个工程。顶点表示活动，有向边$$表示活动$v_i$必须先于$v_j$活动

例子：各个课程为一个点，学了c语言才能学java，学了java才能学python，边是有向边

特性：

1先于2,2先于3，则1先于3
拓扑排序后的序列不唯一

6.4.5 拓扑排序

求顺序

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

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

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

一般步骤：

①从AOV网中选择入度为0的顶点

②删除该顶点与其他顶点的连线后，输出该顶点

③重复①和②直到当前的AOV网为空或当前网中不存在无前驱的顶点为止

代码实现：

采用邻接表的实现：

indegree[]：当前顶点入度

print[]：记录拓扑排序

#define MaxVertexNum 100//图中顶点数的最大值
typedef struct ArcNode{//边表结点
    int adjvex;//该弧所指向的顶点的位置
    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[i].firstarc;p;p=p->nextarc){
            //将所有i指向的顶点的入度减1，并且将入度减为0的顶点压入栈S中
            v=p->adjvex;
            if(!(--indegree[v]))
                Push(S,v);//入度为0，则入栈
        }
    }
    if(count<G.vexnum)
        return false;//排序失败，有向图有回路
    else
        return true;//排序成功
}

6.4.6 关键路径

关键路径：从原点到汇点的有向路径有多条，在所有路径中，具有最大路径长度的路径称为关键路径，该路径上的活动称为关键活动。是求最长活动路径

1.AOE网：

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

开始顶点（源点）：仅有一个入度为0

结束顶点（汇点）：仅有一个出度为0

性质：

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

2.基本概念

$1.事件v_k的最早发生时间ve(k)——决定了所有从v_k开始的活动能够开工的最早时间。\\ 2.活动a_i的最早开始时间e(i)——指该活动弧的起点所表示的事件的最早发生时间。\\ 3.事件v_k的最迟发生时间vl(k)——是指在不推迟整个工程完成的前提下，该事件最迟必须发生的时间。\\ 4.活动a_i的最迟开始时间l(i)——该活动弧的终点所表示事件最迟发生时间与该活动所需时间之差。\\ 5.活动a_i的时间余量d(i)=l(i)-e(i)，表示在不增加完成整个工程所需总时间的情况下，活动a_i可以拖延的时间，\\若一个活动的时间余量为0，则说明该活动必须如期完成，d(i)=0即l(i)=e(i)的活动a_i是关键活动。$

3.求关键路径的步骤

$拓扑序列为：v_1，v_3，v_2，v_5，v_4，v_6$

①求所有事件最早发生时间ve();

按拓扑排序序列，依次求各个顶点的ve(k)；

ve(源点)=0

$ve(k)=Max{ve(j)+Weight(v_j,v_k)}，v_j为v_k的任意前驱$

②求所有事件最迟发生时间vl();

③求所有活动的最早发生时间e();

④求所有活动的最迟发生时间l();$vl-weight(v_j,v_k)$

⑤求所有活动的时间余量d();

第七章查找

7.1 查找的基本概念

查找表:

由同一类型的数据元素（或记录）构成的集合
静态查找表：

查找的同时对查找表不做修改操作（如插入和删除）
动态查找表：

查找的同时对查找表具有修改操作
关键字

记录中某个数据项的值，可用来识别一个记录
主关键字：

唯一标识数据元素的值
次关键字：
可以标识若干个数据元素
平均查找长度（关键字的平均比较次数）

$ASL=\sum_{i=1}^{n}p_ic_i\\n：记录的个数\\ p_i：查找第i个记录的概率（通常认为$p_i$=1/n）\\ c_i：找到第i个记录所需的比较次数$

查找算法的评价指标：

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

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

7.2 线性表的查找

7.2.1 顺序查找

顺序查找适用于顺序结构，也适用于链式结构

数据元素类型的定义如下

typedef struct{
    ElemType *elem;
    int TableLen;
}SSTable;

算法步骤：

int Search_Seq(SSTable ST,ElemType key)
{
    int i=0;
    for(i=0;i<ST.TableLen && ST.elem[i].key!=key;++i)
        return i;
}

算法的时间复杂度是O(n)

最好情况：查找的元素就在表头，仅需比较一次，时间复杂度为O(1)

最坏情况：查找的元素在表尾（或不存在），需要比较n次，时间复杂度为O(n)

平均查找长度：$ASL=\frac{1}{n}\sum_{i=1}^{n}i=\frac{1+2+3+…+n}{n}=\frac{n+1}{2}$

7.2.2 折半查找

只适用于顺序结构

算法步骤：

①置查找区间初值，low为1，high为表长

②当low小于等于high时，循环执行以下操作

mid取值为low和high的中间值

将给定值key与中间位置记录的关键字进行比较，若相等则查找成功，返回中间位置mid；

若不想等则利用中间位置记录将表对分成前、后两个子表。如果key比中间位置记录的关键字小，则high取为mid-1，否则low取为mid+1。

③循环结束，说明查找区间为空，则查找失败，返回0。

int Search_Bin(SSTable ST,KeyType key){
    low=1;high=ST.length;
    while(low<=high){
        mid=(low+high)/2;
        if(key==ST.R[mid].key) 
            return mid;
        else if
            (key<ST.R[mid].key) high = mid-1;
        else 
            low = mid+1;
    }
    return 0;
}

时间复杂度是$O(log_2n)$

平均查找长度：$判断树层数*该层个数，之后累加：ASL=\sum{i=1}^{n}P_iC_i=\frac{1}{n}\sum{j=1}^{h}j·2^{j-1}=\frac{n+1}{n}log_2(n+1)-1$

当n较大时近似为：$ASL=log_2(n+1)-1$

7.2.3 分块查找

1.算法思想

索引块中保存每个分块的最大关键字和分块的存储区间

typedef struct{//索引表
    ElemType maxValue;
    int low,high;
}Index;

//顺序表存储实际元素
ElemType List[100];

2.算法过程：

①在索引表中确定待查记录的所属分块（可顺序，可折半）

②在块中顺序查找

3.查找效率分析

假设，长度为n的查找表被均匀的分为b块，每块s个元素[n=sb]

设索引查找和块内查找的平均查找长度分别为$L_1、L_s$，则分块查看的平均查找长度为$ASL=L_1+L_s$

用顺序查找查索引表，则

$L_1=\frac{1+2+...+b}{b}=\frac{b+1}{2}，L_s=\frac{1+2+...+s}{s}=\frac{s+1}{2}\\ 则ASL=\frac{b+1}{2}+\frac{s+1}{2}=\frac{s^2+2s+n}{2s},当s=\sqrt{n}时，ASL_{最小}=\sqrt{n}+1$

用折半查找查索引表，则

$L_1= \lceil log_2(b+1)\rceil,L_s=\frac{1+2+...+s}{s}=\frac{s+1}{2}\\ 则ASL=\lceil log_2(b+1)\rceil+\frac{s+1}{2}$

7.3 树表的查找

7.3.1 二叉排序树（BST）

二叉排序树或是空树，或是满足如下性质的二叉树：左子树结点值<根结点值<右子树结点值

(1)若其左子树非空，则左子树上所有结点的值均小于根结点的值；

(2)若其右子树非空，则右子树上所有结点的值均大于等于根结点的值；

(3)其左右子树本身又各是一棵二叉排序树

结点的数据域的类型定义

typedef Struct{
    KeyType key;
    IndoType otherindo;
}ElemType;
typedef struct BSTNode{
    ElemType data;
    struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;

1.二叉排序树的递归查找

①若二叉排序树为空，则查找失败，返回空指针。

②若二叉排序树非空，将给定值key与根结点的关键字T->data.key进行比较：

若key等于T->data.key，则查找成功，返回根节点地址

若key小于T->data.key，则递归查找左子树

若key大于T->data.key，则递归查找右子树

BSTree SearchBST(BSTree T,KeyType key){
    if((!T) || key==T->data.key)
        return T;
    else if(key<T->data.key)
        return SearchBST(T->lchild,key);
    else
        return SearchBST(T->rchild,key);
}

2.二叉排序树非递归查找

BSTNode *BST_Search(BSTree T,KeyType key){
    while(T!=NULL&&key!=T->key){
        if(key<T->key) T=T->lchild;
        else T=T->rchild;
    }
    return T;
}

3.二叉排序树的插入

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 if(k>T->key)
		return BST_Insert(T->rchild,k);
}

4.二叉排序树的删除

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

②若结点z只有一颗左子树或者右子树，直接将子树替代z

③若结点z有左右两颗子树，则令z的直接后继（或直接前驱）替代z，然后从二叉排序树中删去这个直接后继（或直接前驱），就转换为了①或②的情况

5.查找效率分析

查找成功：

最好情况：n个结点的二叉树最小高度为$\lfloor log_2n\rfloor+1$，平均查找长度=$O(log_2n)$
最坏情况：每个结点只有一个分支，树高h=结点数n，平均查找长度=$O(n)$

查找失败：

补齐空节点，然后计算

7.3.2 平衡二叉树

1.AVL树简介

AVL树的名字来源于它的发明作者G.M. Adelson-Velsky 和 E.M. Landis。AVL树是最先发明的自平衡二叉查找树（Self-Balancing Binary Search Tree,简称平衡二叉树）。

平衡二叉树定义(AVL)：它或者是一颗空树，或者具有以下性质的二叉排序树：==它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1==，且它的左子树和右子树都是一颗平衡二叉树。

平衡二叉树或者是空树，或者是具有如下特征的二叉排序树：

　1.左子树和右子树也是平衡二叉树

　2.每个结点的左子树和右子树高度差最多为1

图一中左边二叉树的节点45的左孩子46比45大，不满足二叉搜索树的条件，因此它也不是一棵平衡二叉树。

右边二叉树满足二叉搜索树的条件，同时它满足条件二，因此它是一棵平衡二叉树。

左边二叉树的节点45左子树高度2，右子树高度0，左右子树高度差为2-0=2，不满足条件二；

右边二叉树的节点均满足左右子树高度差至多为1，同时它满足二叉搜索树的要求，因此它是一棵平衡二叉树。

AVL树的查找、插入、删除操作在平均和最坏的情况下都是O（logn），这得益于它时刻维护着二叉树的平衡。如果我们需要查找的集合本身没有顺序，在频繁查找的同时，也经常的插入和删除，AVL树是不错的选择。不平衡的二叉查找树在查找时的效率是很低的，因此，AVL如何维护二叉树的平衡是我们的学习重点。

2.AVL树相关概念

平衡因子：将二叉树上节点的左子树高度减去右子树高度的值称为该节点的平衡因子BF(Balance Factor)。

在图二右边的AVL树上：

节点50的左子树高度为3，右子树高度为2，BF= 3-2 = 1；

节点45的左子树高度为2，右子树高度为1，BF= 2-1 = 1；

节点46的左子树高度为0，右子树高度为0，BF= 0-0 = 0；

节点65的左子树高度为0，右子树高度为1，BF= 0-1 = -1；

对于平衡二叉树，BF的取值范围为[-1,1]。如果发现某个节点的BF值不在此范围，则需要对树进行调整。
最小不平衡子树：距离插入节点最近的，且平衡因子的绝对值大于1的节点为根的子树.。

在图三中，左边二叉树的节点45的BF = 1，插入节点43后，节点45的BF = 2。节点45是距离插入点43最近的BF不在[-1,1]范围内的节点，因此以节点45为根的子树为最小不平衡子树。

3.AVL树的平衡调整

定义平衡二叉树结点结构

typedef struct Node{
    int key;
    struct Node *left;
    struct Node *right;
    int height;
}BTNode;

整个实现过程是通过在一棵平衡二叉树中依次插入元素(按照二叉排序树的方式)，若出现不平衡，则要根据新插入的结点与最低不平衡结点的位置关系进行相应的调整。分为LL型、RR型、LR型和RL型4种类型，各调整方法如下(下面用A表示最低不平衡结点)：

LL型调整：

由于在A的左孩子(L)的左子树(L)上插入新结点，使原来平衡二叉树变得不平衡，此时A的平衡因子由1增至2。下面图1是LL型的最简单形式。显然，按照大小关系，结点B应作为新的根结点，其余两个节点分别作为左右孩子节点才能平衡，A结点就好像是绕结点B顺时针旋转一样。

LL型调整的一般形式如下图2所示，表示在A的左孩子B的左子树BL(不一定为空)中插入结点(图中阴影部分所示)而导致不平衡( h 表示子树的深度)。这种情况调整如下：==①将A的左孩子B提升为新的根结点；②将原来的根结点A降为B的右孩子；③各子树按大小关系连接(BL和AR不变，BR调整为A的左子树)。==

代码实现：

BTNode *ll_rotate(BTNode *y)
{
    BTNode *x = y->left;
    y->left = x->right;
    x->right = y;   
 
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;
 
    return x;
}

RR型调整：

由于在A的右孩子(R)的右子树(R)上插入新结点，使原来平衡二叉树变得不平衡，此时A的平衡因子由-1变为-2。图3是RR型的最简单形式。显然，按照大小关系，结点B应作为新的根结点，其余两个节点分别作为左右孩子节点才能平衡，A结点就好像是绕结点B逆时针旋转一样。

RR型调整的一般形式如下图4所示，表示在A的右孩子B的右子树BR(不一定为空)中插入结点(图中阴影部分所示)而导致不平衡( h 表示子树的深度)。这种情况调整如下：

==将A的右孩子B提升为新的根结点；
将原来的根结点A降为B的左孩子
各子树按大小关系连接(AL和BR不变，BL调整为A的右子树)。==

代码实现：

BTNode *rr_rotate(struct Node *y)
{
    BTNode *x = y->right;
    y->right = x->left;
    x->left = y;
    
 
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;

    return x;
}

LR型调整

由于在A的左孩子(L)的右子树(R)上插入新结点，使原来平衡二叉树变得不平衡，此时A的平衡因子由1变为2。图5是LR型的最简单形式。显然，按照大小关系，结点C应作为新的根结点，其余两个节点分别作为左右孩子节点才能平衡。

LR型调整的一般形式如下图6所示，表示在A的左孩子B的右子树(根结点为C，不一定为空)中插入结点(图中两个阴影部分之一)而导致不平衡( h 表示子树的深度)。这种情况调整如下：==①将B的右孩子C提升为新的根结点；②将原来的根结点A降为C的右孩子；③各子树按大小关系连接(BL和AR不变，CL和CR分别调整为B的右子树和A的左子树)。==

代码实现：

BTNode* lr_rotate(BTNode* y)
{
    BTNode* x = y->left;
    y->left = rr_rotate(x);
    return ll_rotate(y);
}

RL型调整：

由于在A的右孩子(R)的左子树(L)上插入新结点，使原来平衡二叉树变得不平衡，此时A的平衡因子由-1变为-2。图7是RL型的最简单形式。显然，按照大小关系，结点C应作为新的根结点，其余两个节点分别作为左右孩子节点才能平衡。

RL型调整的一般形式如下图8所示，表示在A的右孩子B的左子树(根结点为C，不一定为空)中插入结点(图中两个阴影部分之一)而导致不平衡( h 表示子树的深度)。这种情况调整如下：==①将B的左孩子C提升为新的根结点；②将原来的根结点A降为C的左孩子；③各子树按大小关系连接(AL和BR不变，CL和CR分别调整为A的右子树和B的左子树)。==

代码实现：

BTNode* lr_rotate(BTNode* y)
{
    BTNode* x = y->left;
    y->left = rr_rotate(x);
    return ll_rotate(y);
}

插入和删除完整代码

#include<stdio.h>
#include<stdlib.h>

typedef struct Node
{
    int key;
    struct Node *left;
    struct Node *right;
    int height;
}BTNode;

int max(int a, int b);


int height(struct Node *N)
{
    if (N == NULL)
        return 0;
    return N->height;
}

int max(int a, int b)
{
    return (a > b) ? a : b;
}

BTNode* newNode(int key)
{
    struct Node* node = (BTNode*)malloc(sizeof(struct Node));
    node->key = key;
    node->left = NULL;
    node->right = NULL;
    node->height = 1;
    return(node);
}

BTNode* ll_rotate(BTNode* y)
{
    BTNode *x = y->left;
    y->left = x->right;
    x->right = y;

    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;

    return x;
}

BTNode* rr_rotate(BTNode* y)
{
    BTNode *x = y->right;
    y->right = x->left;
    x->left = y;

    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;

    return x;
}

int getBalance(BTNode* N)
{
    if (N == NULL)
        return 0;
    return height(N->left) - height(N->right);
}

//插入
BTNode* insert(BTNode* node, int key)
{

    if (node == NULL)
        return newNode(key);

    if (key < node->key)
        node->left = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);
    else
        return node;

    node->height = 1 + max(height(node->left), height(node->right));


    int balance = getBalance(node);



    if (balance > 1 && key < node->left->key) //LL型
        return ll_rotate(node);


    if (balance < -1 && key > node->right->key)     //RR型
        return rr_rotate(node);


    if (balance > 1 && key > node->left->key)     //LR型
    {
        node->left = rr_rotate(node->left);
        return ll_rotate(node);
    }

    if (balance < -1 && key < node->right->key)     //RL型
    {
        node->right = ll_rotate(node->right);
        return rr_rotate(node);
    }

    return node;
}


BTNode * minValueNode(BTNode* node)
{
    BTNode* current = node;

    while (current->left != NULL)
        current = current->left;

    return current;
}

//删除
BTNode* deleteNode(BTNode* root, int key)
{

    if (root == NULL)
        return root;

    if (key < root->key)
        root->left = deleteNode(root->left, key);

    else if (key > root->key)
        root->right = deleteNode(root->right, key);

    else
    {
        if ((root->left == NULL) || (root->right == NULL))
        {
            BTNode* temp = root->left ? root->left : root->right;

            if (temp == NULL)
            {
                temp = root;
                root = NULL;
            }
            else
                *root = *temp;
            free(temp);
        }
        else
        {
            BTNode* temp = minValueNode(root->right);

            root->key = temp->key;

            root->right = deleteNode(root->right, temp->key);
        }
    }


    if (root == NULL)
        return root;

    root->height = 1 + max(height(root->left), height(root->right));

    int balance = getBalance(root);


    if (balance > 1 && getBalance(root->left) >= 0) //LL型
        return ll_rotate(root);


    if (balance > 1 && getBalance(root->left) < 0) //LR型
    {
        root->left = rr_rotate(root->left);
        return ll_rotate(root);
    }

    if (balance < -1 && getBalance(root->right) <= 0) //RR型
        return rr_rotate(root);

    if (balance < -1 && getBalance(root->right) > 0)  //Rl型
    {
        root->right = ll_rotate(root->right);
        return rr_rotate(root);
    }

    return root;
}


void preOrder(struct Node *root)
{
    if (root != NULL)
    {
        printf("%d ", root->key);
        preOrder(root->left);
        preOrder(root->right);
    }
}

int main()
{
    BTNode *root = NULL;

    root = insert(root, 9);
    root = insert(root, 5);
    root = insert(root, 10);
    root = insert(root, 0);
    root = insert(root, 6);
    root = insert(root, 11);
    root = insert(root, -1);
    root = insert(root, 1);
    root = insert(root, 2);
    printf("前序遍历：\n");
    preOrder(root);

    /* The constructed AVL Tree would be
                     9
                    /  \
                   1    10
                 /  \     \
                0    5     11
               /    /  \
              -1   2    6
    */

    root = deleteNode(root, 10);
    /* The AVL Tree after deletion of 10
                       1
                     /   \
                    0     9
                  /     /  \
                -1     5     11
                     /  \
                    2    6
    */
    printf("\n");
    printf("前序遍历：\n");
    preOrder(root);
    return 0;
}

7.3.3 B树

1.基本概念

若每个结点内的关键字太少，导致树变高，要查更多层结点，导致效率低。

m叉查找树中，规定除了根结点外，任何结点至少有$\lceil\frac{m}{2}\rceil$个分叉，即至少含有$\lceil\frac{m}{2}\rceil-1$个关键字
m叉查找树中，尽量保证所有子树高度相同

B树，又称为多路平衡查找树，B树中所有结点的孩子个数的最大值称为B树的阶，通常用m表示。一颗m阶B树或为空树，或为满足如下特性的m叉树：

①树中每个结点至多有m颗子树，即至多含有m-1个关键字

②若根结点不是终端结点，则至少有两颗子树

③m叉查找树中，规定除了根结点外，任何结点至少有$\lceil\frac{m}{2}\rceil$个分叉，即至少含有$\lceil\frac{m}{2}\rceil-1$个关键字

④所有的叶子结点都出现同一层上，并且不带信息

⑤所有非叶结点的结果如下：

$|　n　|　P_0　|　K_1　|　P_1　|　K_2　|　P_2　|　…　|　K_n　|　P_n　|$

其中，$K_i(i=1,2,3,…,n)$为结点的关键字，且满足$K_1<K_2<…<K_n$；$P_i(i=0,1,…,n)$为指向子树根结点的指针，且指针$P_i-1$所指子树中所有结点的关键字均小于$K_i$，$P_i$所指子树中所有结点的关键字均大于$K_i$，$n(\lceil\frac{m}{2}\rceil-1) \le n \le m-1$，为节点中关键字的个数。

2.B树的高度

含n个关键字的m叉B树，高度$\textcolor{red}{ logm(n+1) \le h \le log{\lceil\frac{m}{2}\rceil}\frac{n+1}{2}+1}$

B树的高度一般不包括失败节点（叶子结点）

问题1：含n个关键字的m阶B树，最小高度，最大高度？

$最小高度——让每个结点尽可能的填满关键字，有m-1个关键字，m个分叉，则有\\ n \le (m-1)(1+m+m^2+...+m^{h-1})=m^h-1，因此h \ge log_m(n+1)\\\\ 最大高度——让各层的分叉尽可能的少，即根结点只有2个分叉，其他节点只有\lceil\frac{m}{2}\rceil个分叉;\\各层结点至少有:第一层1、第二层2、第三层2\lceil\frac{m}{2}\rceil...第h层2(\lceil\frac{m}{2}\rceil)^{h-2};\\ 第h+1层共有叶子结点2(\lceil\frac{m}{2}\rceil)^{h-1}个\\ \textcolor{red}{n个关键字的B树必有n+1个叶子结点}，则n+1 \ge \lceil\frac{m}{2}\rceil)^{h-1}，即h \le log_{\lceil\frac{m}{2}\rceil}\frac{n+1}{2}+1$

问题2：含n个关键字的m叉B树，最小高度、最大高度？

$最大高度——让每个结点包含的关键字、分叉尽可能地少。记k=\lceil\frac{m}{2}\rceil$

3.B树的插入

4.B树的删除

删除叶子结点时，兄弟左移
删除根结点，要找到直接前驱或直接后继替换他
借左右兄弟
兄弟不够借，就合并父节点，如果父节点关键字数量小于，可能要继续合并

7.3.4 B+树

一颗m阶的B+树，满足下列条件：

①每个分支节点最多有m棵子树

②非叶根结点至少有两颗子树，其他每个分支结点至少有$\lceil\frac{m}{2}\rceil$棵子树

③结点的子树个数与关键字个数相等

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

1.B+树的查找

从上往下查找
指针p顺序查找

2.B树和B+树的区别

	m阶B树	m阶B+树
关键字与分叉	结点中n个关键字对应n+1棵子树	结点中n个关键字对应n个子树
	根结点关键字树$n \in [1,m-1]$；其他节点关键字数$n \in [\lceil\frac{m}{2}\rceil-1,m-1]$	根结点的关键字数$n \in [1,m]$；其他结点的关键字数$n \in [\lceil\frac{m}{2}\rceil,m]$
	各结点中的关键字不重复	叶结点包含全部关键字，非叶结点中出现过的关键字也会出现在叶结点中
	结点中包含了关键字对应的记录的存储地址	叶结点包含信息，非叶结点仅有索引作用
查找方式	不支持顺序查找。查找成功时，可能停在任何一层结点，查找速度“不稳定”	支持顺序查找。查找成功或失败都会到达最下一层结点，查找速度“稳定”

相同点：除根节点意外，最少有$\lceil\frac{m}{2}\rceil$个子树；任一结点的子树都一样高

7.4 散列查找

7.4.1 散列表基本概念

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

若不同的关键字通过散列函数映射到同一个值，则他们称为同义词

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

解决冲突的方法：

拉链法：把所有同义词存储在一个链表中

1.查找效率

==装填因子α=表中记录数/散列表长度==：装填因子直接影响散列表的查找效率

7.4.2 常见的散列函数（为了使冲突减少）

1.除留余数法——H(key)=key%p

散列表表长为m，去一个不大于m但最接近或等于m的质数p（除了1和此数自身外不能被其他自然数整除的数）

2.直接定址法——H(key)=key或H(key)=a*key+b

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

3.数字分析法——选取数码分布较为均匀的若干位作为散列地址

设关键字是r进制数，而r个数码在各位上出现的频率一定不相同，可能在某些位上分布均匀一些，每种数码出现的机会均等；而在某些位上分布不均匀，只有某几种数码经常出现，此时可选取数码分布较为均匀的若干位作为散列地址。这种方法适合已知的关键字集合，若更换了关键字，则需要重新构造新的散列函数。

4.平均取中法——取关键字的平方值的中间几位作为散列地址

具体取多少位要视情况而定。这种方法得到的散列地址与关键字的每位都有关系，因此是的散列地址分布比较均匀，适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数

5.开放定址法——可存放新表项的空闲地址即向它的同义词表项开放，又向它的非同义词表项开放。其递推公式：

$H_i=(H(key)+d_i)\%m\\ i=0,1,2,...,k(k \le m-1)，m表示散列表表长；d_i为增量序列；i可理解为第i次发生冲突$

①线性探测法——$d_i=0,1,2,3,…,m-1$;即发生冲突时，每次往后探测相邻的下一个单元是否为空。

这里，空位置的比较也算作一次，删除元素的时候，需要删除标记（逻辑删除）

②平方探测法：当$d_i=0^2,1^2,-1^2,2^2,-2^2,…k^2,-k^2$时，称为平方探测法$k \le \frac{m}{2}$

==散列表长度m必须是一个可以表示成4j+3的素数，才能探测到所有位置==

③伪随机序列法：$d_i$是某个伪随机序列

6.再散列法：除了原始的散列函数H(key)之外，多准备几个散列函数，当散列函数冲突时，用下一个散列函数计算一个新地址，直到不冲突为止：

$H_i=RH_i(Key)　　　　i=1,2,3,4,...,k$

第八章排序

以下算法都会用到的类型定义

#define MAXSIZE 20
typedef int KeyType;
typedef struct{
    KeyType key;					//关键字项
    InfoType otherinfo;				//其他数据项
}RedType;							//记录类型
typedef struct{
    RedType r[MAXSIZE+1];			//r[0]闲置或用做哨兵单元
    int length;
}SqList;

所有排序算法比较：

8.1 插入排序

8.1.1 直接插入方法排序

基本操作是将一条记录插入到已排好序的有序表中，从而得到一个新的、记录数量增1的有序表。

#include "iostream"
using namespace std;

void swap(int &a, int &b) {
    int t = a;
    a = b;
    b = t;
}

int main() {
    int a[] = {4, 8, 40, 28, 13, 14, 22, 32, 40, 21, 48, 24, 47, 17, 37, 18};
    int n = (int) sizeof(a) / a[0];

    int i, j, t;
    for (i = 1; i < n; ++i) {
        if (a[i] < a[i - 1]) {
            t = a[i];
            for (j = i - 1; j > -1 && t < a[j]; j--)
                a[j + 1] = a[j];
            a[j+1] = t;
        }
    }

    for (int k = 0; k < n; ++k) {
        cout << a[k] << " ";
    }
}

8.1.2 折半插入排序

8.1.3 希尔排序

1.基本概念

希尔排序(Shell Sort)是插入排序的一种，它是针对直接插入排序算法的改进。

希尔排序又称缩小增量排序，因 DL.Shell 于 1959 年提出而得名。

它通过比较相距一定间隔的元素来进行，各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。

2.适用说明

希尔排序时间复杂度是$O(n^{\frac{3}{2}})$，空间复杂度是$O(1)$，==只能用于顺序结构，不适用于链式结构==

3.过程演示

希尔排序目的为了加快速度改进了插入排序，交换不相邻的元素对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。

我们来看下希尔排序的基本步骤，在此我们选择增量$gap=\frac{length}{2}$，缩小增量继续以$gap=\frac{gap}{2}$的方式，这种增量选择我们可以用一个序列来表示，{$\frac{n}{2},\frac{\frac{n}{2}}{2},…,1$}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。

如图所示：

（1）初始增量第一趟$gap=\frac{length}{2}$

（2）第二趟，增量缩小为2

（3）第三趟，增量缩小为1，得到最终结果

4.算法伪码：

void ShellInsert(SqlList &L, int dk){
    //对顺序表L做一趟增量是dk的希尔排序
    for(i=dk+1;i<=L.length;++i)
        if(L.r[i].key<L.r[i-dk].key){
            L.r[0]=L.r[i];
            for(j=i-dk;j>0 && L.r[0].key<L.r[j].key;j-=dk)		//记录后移，直到找到插入位置
                L.r[j+dk]=L.r[j];								//将r[0]即原r[i]，插入到正确位置
            L.r[j+dk]=L.r[0];
        }
}

void ShellSort(SqList &L,int dt[],int t){
    //按增量序列dt[0...t-1]对顺序表L作希尔排序
    for(k=0;k<t;++k)
        ShellInsert(L,dt[k]);
}

void ShellSort(int data[], int len) {
    int i, j, temp, gap;
    for (gap = len / 2; gap > 0; gap /= 2) {
        for (i = gap; i < len; i++) {
            if (data[i] < data[i - gap]) {
                temp = data[i];
                for (j = i - gap; j > -1 && data[j] > temp; j -= gap) {
                    data[j + gap] = data[j];
                }
                data[j + gap] = temp;
            }
        }
    }
}

8.2 交换排序

8.2.1 冒泡排序

1.基本概念

从前到后或者从后到前依次对比相邻两个数，如果逆序就交换。

特点：==稳定，适用于链表==

2.过程演示

原始数据：
3, 2, 7, 6, 8
第1次循环：(最大的跑到最右边。)
2, 3, 7, 6, 8 （3和2比较，2 < 3，所以2和3交换位置）
2, 3, 7, 6, 8 （虽然不需要交换位置：但是3和7还是需要比较一次。）
2, 3, 6, 7, 8 （7和6交换位置）
2, 3, 6, 7, 8 （虽然不需要交换位置：但是3和7还是需要比较一次。）

经过第1次循环，此时剩下参与比较的数据：2, 3, 6, 7
第2次循环：
2, 3, 6, 7 (2和3比较，不需要交换位置)
2, 3, 6, 7 （3和6比较，不需要交换位置）
2, 3, 6, 7 (6和7比较，不需要交换位置)

经过第2次循环，此时剩下参与比较的数据：2, 3, 6
第3次循环：
2, 3, 6 (2和3比较，不需要交换位置)
2, 3, 6 （3和6比较，不需要交换位置）

经过第3次循环，此时剩下参与比较的数据：2, 3
第4次循环：
2, 3 (2和3比较，不需要交换位置)

3.算法代码

#include "iostream"

void swap(int &a, int &b) {
    int t = a;
    a = b;
    b = t;
}

void BubleSort(int *data, int len) {
    for (int i = 0; i < len - 1; ++i) {
        //是否进行交换的标志
        bool flag = false;

        for (int j = len - 1; j > i; j--) {
            if (data[j] < data[j - 1]) {
                swap(data[j], data[j - 1]);
                flag = true;
            }
        }
        //本趟遍历后没有发生交换，说明表已经有序。
        if (flag == false)
            return;
    }
}

int main() {
    int a[8] = {38, 49, 65, 97, 76, 13, 27, 49};
    int size = sizeof(a) / sizeof(a[0]);
    BubleSort(a, size);

    for (int i = 0; i < size; i++) {
        printf("%d\t", a[i]);
    }
    return 0;
}

4.效率分析

最好情况：原本有序，$O(n)$

最坏情况：逆序，$O(n^2)$

8.2.2 快速排序

1.基本概念

算法思想：在待排序表中任取一个元素pivot作为主元，将待排序表划分为两部分，使左边部分元素都小于主元，右边部分元素都大于等于主元，最终插入pivot，这是一次划分。之后重复递归两个子部分，直到每部分只有一个元素或空。

特点：==不稳定==

2.过程演示

3.算法代码

#include "iostream"

int Partition(int *data, int low, int high) {
    int pivot = data[low];//定义第一个元素为主元

    while (low < high) {//如果low<high
        //右指针想左扫描，如果>=主元就跳过，否则赋值给data[low]
        while (low < high && data[high] >= pivot)
            --high;
        if (low < high)
            data[low++] = data[high];
        //左指针右扫描，如果<=主元就跳过，否则赋值给data[high]
        while (low < high && data[low] <= pivot)
            ++low;
        if (low < high)
            data[high--] = data[low];
    }
    //将主元放在最终位置
    data[low] = pivot;
    return low;//返回存放主元的下标
}

void QuickSort(int *data, int low, int high) {
    if (low < high) {
        int pos = Partition(data, low, high);
        QuickSort(data, low, pos - 1);
        QuickSort(data, pos + 1, high);
    }
}

int main() {
    int a[10] = {38, 49, 65, 97, 76, 13, 27, 49, 12, 13};
    int size = sizeof(a) / sizeof(a[0]);
    QuickSort(a, 0, size - 1);

    for (int i = 0; i < 10; i++) {
        printf("%d\t", a[i]);
    }
    return 0;
}

5.算法效率分析

最好情况是：每一次主元将待排序序列划分为均匀的两部分。

最坏的情况，每次主元划分为不均匀的部分。（原本有序，或者逆序）

优化：①选头、中、尾三个位置的元素，去中间值为主元。②随机选一个元素作为主元。

8.3 选择排序

8.3.1 简单选择排序

1.基本概念

算法思想：每一趟在待排序选择关键字最小的元素加入到有序序列。

特点：不稳定，既可以顺序表，也可以链表

2.过程演示

选择排序比冒泡排序的效率高

高在交换位置的次数上。

循环一次，然后找出参加比较的这堆数据中最小的，拿着这个最小的值和
最前面的数据”交换位置”

参与比较的数据：3 1 6 2 5 这一堆数据最左边下标为0
第1次循环之后的结果是：
1 3 6 2 5

参与比较的数据：3 6 2 5 这一堆数据最左边下标为1
第2次循环之后的结果是：
2 6 3 5

参与比较的数据：6 3 5 这一堆数据最左边下标为2
第3次循环之后的结果是：
6 5

参与比较的数据：6 5 这一堆数据最左边下标为3
第4次循环之后的结果是：
5 6

注意：5条数据，循环4次

3.算法代码

void SelectSort(int data[], int len) {
    int t = 0;
    for (int i = 0; i < len - 1; ++i) {//一共进行n-1趟
        int min = i;//记录最小元素位置

        for (int j = i + 1; j < len; ++j) { //在i..n-1中选择最小元素
            if (data[j] < data[min])
                min = j;//更新最小元素位置
        }
        if (i != min) {
            swap(data[i],data[min]);
        }
    }
}

4.效率分析

时间复杂度为：$O(n^2)$

8.3.2 树形选择排序

8.3.3 堆排序

1.基本概念

大根堆：根>=左右孩子

小根堆：根<=左右孩子

根为i，则左孩子是2i，右孩子是2i+1，父节点为i/2，i从1开始

算法思想：把所有非终端节点都检查一遍，看是否满足大根堆要求，如果不满足进行调整（将当前节点与更大的孩子互换

）。

特点：不稳定

2.过程演示

3.算法代码

//1.建立大根堆
void BuildMaxHeap(int A[], int len) {
    for (int i = len >> 1; i > 0; --i) {//从后往前调整所有非终端节点
        HeadAdjust(A, i, len);
    }
}

//2.调整大根堆
void HeadAdjust(int *A, int k, int len) {
    A[0] = A[k];//A[0]暂存子树的根节点
    //沿key较大的子节点向下筛选
    for (int i = 2 * k; i <= len; i *= 2) {
        //对比左右孩子，取更大的孩子
        if (i < len && A[i] < A[i + 1])
            i++;
        //如果根节点比孩子更大，就退出；否则更新
        if (A[0] >= A[i])
            break;
        else {
            A[k] = A[i];
            k = i;
        }
    }
    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);//把剩余待排序元素整理成堆。
    }
}

void swap(int &a, int &b) {
    int t = a;
    a = b;
    b = t;
}

int main() {
    int a[8] = {38, 49, 65, 97, 76, 13, 27, 49};
    int size = sizeof(a) / sizeof(a[0]);
    HeapSort(a, size);

    for (int i = 0; i < 8; i++) {
        printf("%d\t", a[i]);
    }
    return 0;
}

4.效率分析

5.堆的插入删除

插入：对于小根堆，新元素放到表尾，与父节点对比，若新元素比父节点更小，则将二者互换。新元素就这么一路上升，知道无法上升为止。

删除：被删除元素用堆低元素代替，然后让钙元素不断下坠，直到无法下坠。

8.4 归并排序

1.基本概念

算法思路：把两个或多个有序的子序列合并为一个

特点：稳定

2.过程分析

3.算法代码

void MergeSort(int *a, int begin, int end) {
    if (begin < end) {
        int mid = (begin + end) >> 1;

        MergeSort(a, begin, mid);
        MergeSort(a, mid + 1, end);
        Merge(a, begin, mid, end);
    }
}

void Merge(int *a, int begin, int mid, int end) {

    int helper[10];
    for (int i = 0; i < 10; ++i) {
        helper[i]=a[i];
    }

    int left = begin;//左部分开始指针
    int right = mid + 1;//右部分开始指针
    int current = begin;//索引下标

    while (left <= mid && right <= end) {
        if (helper[left] <= helper[right]) {
            a[current++] = helper[left++];
        } else {
            a[current++] = helper[right++];
        }
    }

    //右指针比对完了，但是左边还没有放入
    while (left <= mid) {
        a[current++] = helper[left++];
    }
}

4.效率分析

时间复杂度：$O(nlogn)$，空间复杂度$O(n)$

8.5 基数排序

1.基本概念

特点：链式存储，稳定

2.过程分析

以个位分配：

以十位分配：

以百位分配：

3.算法代码

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

typedef struct{//链式队列
    LinkNode *front,*rear;//队列得列头和队尾指针
}LinkQueue;

4.效率分析

5.基数排序的应用

基数排序擅长解决：

数据元素的关键字可以方便的拆分为d组，且d较小
每组关键字的取值范围不大，即r较小
数据元素个数n较大

8.6 外部排序

1.基本概念

外部排序原理：数据元素太多，无法一次全部读入内存进行排序。

2.过程分析

3.算法代码

4.效率分析

如何优化？

可以看到，影响时间速率的是归并的趟数。上面使用的是2路归并，可以进行多路归并来缩减时间，如果采用4路归并，读写磁盘次数=32+32*2=96

重要结论：采用多路归并可以减少归并趟数，从而减少磁盘IO次数

==$对r个初始归并段，做k路归并，则归并树可用k叉树表示，若树高为h，则归并趟数S=h-1=\left \lceil{log_kr} \right \rceil$==

8.6.1 败者树

1.基本概念

可以看做一颗完全二叉树（多了一颗头头）。k个叶节点分别是当前参加比较的元素，非叶子结点迎来记忆左右子树的失败者，而让胜利者网上继续比较，一直到根节点。

2.败者树在多路归并的应用

叶子结点相比较，选出最小的，只不过，存储的不是元素，而是这个元素来自哪个归并段。

8.6.2 置换-选择排序

算法步骤

1）从FI输入w个记录到工作区WA。

2）从WA中选出其中关键字取最小值，记录为MINIMAX。

3）将MINIMAX记录输出到FO中去。

4）若FI不为空，则从FI输入下一个记录到WA中。

5）从WA中所有关键字比MINIMAX记录的关键字大的记录中选出最小关键字记录，作为MINIMAX记录。

6）重复3-5，直到WA中选不出新的MINIMAX记录为止，由此得到一个初始归并段，输出一个归并段的结束标志到FO中去。

7）重复2-6，直到WA为空。

8.6.3 最佳归并树

重要结论：

$归并过冲中的磁盘I/O次数=归并树WPL*2$

构造哈夫曼树优化：

对于三路以上需要添加虚段：

附录

小知识：函数参数是否带“&”的区别

#include <iostream>
using namespace std;

void test1(int x) {
    x = 1024;
    cout << "在函数中的x = " << x << endl;
}

void test2(int &x) {
    x = 1024;
    cout << "在函数中的x = " << x << endl;
}

int main() {
    int x = 666;
    cout << "未经过函数的x = " << x << endl;
    test1(x);
    cout << "经过函数的x = " << x << endl;
    cout << "------------------" << endl;
    cout << "未经过函数的x = " << x << endl;
    test2(x);
    cout << "经过函数的x = " << x << endl;
}

输出结果如下：

未经过函数的x = 666
在函数中的x = 1024
经过函数的x = 666
------------------
未经过函数的x = 666
在函数中的x = 1024
经过函数的x = 1024

可以看到添加“&”之后，x的值从666修改为了1024。

实际上，主函数中定义的x和test函数中的参数x并不是同一个，在虚拟内存中，他们的地址是不同的。而&叫做引用符，它可以引用主函数中x的地址，这样就可以对主函数中的x进行修改。所以函数需要修改原变量时，需要给该参数添加&。

各个数据类型的定义结构体

QQ截图20220919102243

1 顺序表的基本操作

点击我回到原位置

#include <stdio.h>
#include <stdlib.h>

#define Size 5
typedef struct {
    int *data; //定义一个名为data的长度不确定的数组，也叫“动态数组”
    int length; //记录当前顺序表的长度
    int size; //记录顺序表的存储容量
} SqList;

//创建顺序表
void initList(SqList &L) {
    //构造一个空的顺序表，动态申请存储空间
    L.data = (int *) malloc(Size * sizeof(int));
    //如果申请失败，作出提示并直接退出程序
    if (L.data == NULL) {
        printf("初始化失败");
        exit(0);
    }
    //空表的长度初始化为0
    L.length = 0;
    //空表的初始存储空间为Size
    L.size = Size;
}

//插入函数，其中，e为插入的元素，i为插入到顺序表的位置
void listInsert(SqList &L, int i, int e) {
    //如果插入元素位置比整张表的长度+1还大（如果相等，是尾随的情况），或者插入的位置本身不存在，程序作为提示并自动退出
    if (i > L.length + 1 || i < 1) {
        printf("插入位置有问题\n");
        return;
    }
    //做插入操作时，首先需要看顺序表是否有多余的存储空间提供给插入的元素，如果没有，需要申请
    if (L.length == L.size) {
        L.data = (int *) realloc(L.data, (L.size + 1) * sizeof(int));
        if (L.data == NULL) {
            printf("存储分配失败\n");
            return;
        }
        L.size += 1;
    }
    //插入操作，需要将自插入位置之后的所有元素全部后移一位
    for (int j = L.length; j >= i; j--) {
        L.data[j] = L.data[j - 1];
    }
    //后移完成后，直接插入元素
    L.data[i - 1] = e;
    L.length++;
}

//删除函数
void listDelete(SqList &L, int i) {
    if (i > L.length || i < 1) {
        printf("被删除元素的位置有误\n");
        return;
    }
    //删除操作
    for (int j = i; j < L.length; j++) {
        L.data[j - 1] = L.data[j];
    }
    L.length--;
}

//查找函数
int locateElem(SqList L, int e) {
    int i;
    for (i = 0; i < L.length; i++) {
        if (L.data[i] == e) {
            return i + 1;
        }
    }
    return -1;
}

//更改函数
void listAmend(SqList &L, int e, int newElem) {
    int add = locateElem(L, e);
    if (add == -1) {
        printf("顺序表中没有找到目标元素\n");
        return;
    }
    L.data[add - 1] = newElem;
}

//输出顺序表中的元素
void showList(SqList L) {
    int i;
    for (i = 0; i < L.length; i++) {
        printf("%d ", L.data[i]);
    }
    printf("\n");
}

int main() {
    int i, add;
    SqList sl = {NULL, 0, 0};
    initList(sl);
    for (i = 1; i <= Size; i++) {
        sl.data[i - 1] = i;
        sl.length++;
    }
    printf("原顺序表：\n");
    showList(sl);
    printf("删除元素2:\n");
    listDelete(sl, 2);
    showList(sl);
    printf("在第2的位置插入元素5:\n");
    listInsert(sl, 2, 5);
    showList(sl);
    printf("查找元素3的位置:\n");
    add = locateElem(sl, 3);
    printf("%d\n", add);
    printf("将元素3改为6:\n");
    listAmend(sl, 3, 6);
    showList(sl);
    return 0;
}

2 链表的基本操作

2.1 单链表的基本操作

点我回到原来位置

#include <malloc.h>
#include "iostream"

using namespace std;

/**
 * 定义结点类型结构体，有一个data域和一个next域
 */
typedef struct LNode {
    int data;
    struct LNode *next;
} LNode, *LinkList;

/**
 * 初始化，生成带有头结点的单链表
 * @param L 引用类型，头指针
 */
void InitLinkList(LinkList &L) {
    L = (LinkList) malloc(sizeof(LNode));
    if (L) {   //内存分配成功
        L->next = NULL;
    }
}

/**
 * 头插法建立单链表
 * @param L 引用类型的头指针
 * @param n 表示需要插入的元素个数
 */
void HeadInsert_LinkList(LinkList &L, int n) {
    LNode *s;   //辅助指针s，用于指向新申请的结点空间，并将输入的数据存入s->data
    for (int i = 1; i <= n; ++i) {
        s = (LNode *) malloc(sizeof(LNode));  //申请新结点空间
        if (s)  //内存分配成功
        {
            scanf("%d", &s->data);  //输入需要插入的值
            /**
             * 头插法的关键步骤：
             */
            s->next = L->next;  //让s的next已知的L的next（最开始为NULL）
            L->next = s;        //再让头指针L的next指向新插入的结点s
        }

    }
}

/**
 * 尾插法建立单链表
 * @param L 引用类型的头指针
 * @param n 需要插入的元素的个数
 */
void RailInsert_LinkList(LinkList &L, int n) {
    LNode *s, *r;  //s用于指向新申请的节点空间，r用于始终指向尾结点
    r = L;   //r初始指向头结点
    for (int i = 1; i <= n; ++i) {
        s = (LNode *) malloc(sizeof(LNode));
        if (s) {
            scanf("%d", &s->data);
            /**
             * 尾插法的关键步骤
             */
            r->next = s;  //直接让r的next指向新结点s
            r = s;        //再让r重新指向当前的尾结点
        }

    }
    r->next = NULL;   //最后，将r的next置空
}

/**
 * 在单链表中插入一个元素
 * @param L        单链表的头指针，代表单链表，使用引用型
 * @param location 在第location个位置插入
 * @param elem     插入的元素值
 */
int InsertElem_LinkList(LinkList &L, int location, int elem) {
    LNode *p, *s;  //p用于遍历单链表，s用于指向新生成的结点空间，并存储插入的数据
    p = L;  //p初始指向头结点
    int j = 1;  //计数，帮助找到要插入的第i个位置

/*    while (p != NULL && j < location) {
        p = p->next;
        ++j;
    }

    if (!p || j > location)  //插入的位置小于1或者大于表长+1
    {
        return 0;
    }*/
    if (p != NULL) {
        for (j = 1; j < location; j++) {
            p = p->next;
        }
    } else {
        return -1;
    }


    s = (LNode *) malloc(sizeof(LNode));
    if (s) {
        s->data = elem;
    }

    if (s) {
        /*
        插入的关键步骤：顺序不能颠倒
         */
        s->next = p->next;  //先把第i-1个位置的next给到s的next
        p->next = s;        //再把s给到第i-1个位置的next，即给到第i个位置
    }
    return 1;
}

/**
 * 按顺序输出单链表中元素的值
 * @param L 单链表的头指针
 */
void Print_LinkList(LinkList L) {
    LNode *p = L->next;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

/**
 * 主函数
 * @return 1，结束
 */
int main() {
    LinkList L;
    InitLinkList(L);

    int n;

/*    // 头插法建立单链表
    printf("请输入元素个数：");
    fflush(stdout);
    scanf("%d", &n);
    HeadInsert_LinkList(L, n);
    printf("链表为：");
    Print_LinkList(L);
*/
    // 尾插法建立单链表
    printf("请输入元素个数：");
    fflush(stdout);
    scanf("%d", &n);
    RailInsert_LinkList(L, n);
    printf("链表为：");
    Print_LinkList(L);

    // 插入元素
    int i, elem;
    printf("请输入要插入的位置和元素值：");
    fflush(stdout);
    scanf("%d %d", &i, &elem);
    InsertElem_LinkList(L, i, elem);
    printf("添加数据%d后的链表：", elem);
    Print_LinkList(L);

    return 0;
}

3 栈的基本操作

#include<stdio.h>
#include<iostream>

#define MAXSIZE 5
#define ElemType int

typedef struct//定义一个栈
{
    ElemType *base;
    ElemType *top;
    int stacksize;
} SqStack;

bool InintStak(SqStack &s)//初始化一个顺序栈
{
    s.base = new ElemType[MAXSIZE];//给栈一个分配一个数组，这个栈的基地址为数组首地址
    if (!s.base)
        return false;//栈不存在基地址，没有分配成功
    s.top = s.base;//分配成功，top=base，栈S为空表
    s.stacksize = MAXSIZE;//栈的最大空间就是数组元素个数，数组几个数，栈就几个元素
    return true;
}

bool CreateStack(SqStack &s)//创建一个
{
    int m, n;//n为输入元素的值
    printf("输入元素：");
    for (int m = 0; m < MAXSIZE; m++) {
        fflush(stdout);
        scanf("%d", &n);
        if (n == -1) return false;
        *s.top = n;//*S.top的值是n
        s.top++;//头节点往上移
    }
    return true;
}

bool pushStack(SqStack &s, ElemType e)//将值e入栈
{
    if (s.top - s.base == 0) return false;
    *s.top++ = e;
    return true;
}

bool PopStack(SqStack &s, ElemType &e)//出栈
{
    if (s.top == s.base) return false;
    e = *--s.top;
    return true;
}

void GetlengthStack(SqStack s, ElemType &a)//获取栈的长度
{
    if (s.top - s.base == 0) {
        printf("空栈");
    } else {
        a = s.top - s.base;
        printf("栈长为:%d", a);
    }
}

bool DisplayStack(SqStack s)//打印栈的内容,读栈
{
    ElemType *i;
    i = s.top;//采用后进先出规则
    if (s.top == s.base) return false;
    while (i > s.base)//后进先出，从top指针的元素开始出栈
    {
        i--;
        printf("%d ", *i);
    }
    printf("\n");
    return true;
}

int main() {
    int e, a, b;
    SqStack S;
    InintStak(S);
    printf("创建一个顺序栈\n");
    CreateStack(S);
    printf("打印这个顺序栈：");
    DisplayStack(S);
    printf("进行入栈操作\n");
    printf("你要入栈的数是：");
    fflush(stdout);
    scanf("%d", &b);
    pushStack(S, b);
    printf("入栈后，这时的顺序栈为：");
    DisplayStack(S);
    printf("进行出栈操作\n");
    PopStack(S, e);
    printf("出栈后，这时的顺序栈为：");
    DisplayStack(S);
    printf("此时顺序栈的长度为：");
    GetlengthStack(S, a);
}

4 共享栈的基本操作

点我回到原来位置

typedef struct{
    int elem[maxSize];
    int top[2];//top[0]是s0的栈顶，top[1]是s1的栈顶
}ShStack;

//初始化栈
void initShStack(ShStack &sh){
    sh.top[0]=-1;
    sh.top[1]=max
}

//入栈
int push(ShStack &sh, int stNo, int x){
    if(sh.top[0] + 1 < sh.top[1]){//栈不满
        if(stNo==0){//元素入s0
            ++sh.top[0];
            sh.elem[sh.top[0]]=x;
            return 1;
        }else if(stNo==1){//元素入s1
            --sh.top[1];
            sh.elem[sh.top[1]]=x;
            return 1;
        }
        else return -1;//栈编号误，返回-1
    }
    else return 0;//栈满后元素不能入栈，返回0
}

//出栈
int pop(ShStack &sh, int stNo, int &x){
    if(stNo==0){//元素出s0
        if(sh.top[0] != -1){//s0不是空栈
            sh.elem[sh.top[0]]=x;
            --sh.top[0];
            return 1;
        }
        else return 0;//s0空栈，出栈失败
    }else if(stNo==1){//元素出s1
        if(sh.top[1] != maxSize){
            sh.elem[sh.top[1]]=x;
            ++sh.top[1];
            return 1;
        }
        else return 0;//s1空，初战失败
    }
    else return -1;//栈编号误，返回-1
}

第一章 绪论

1.1 数据结构的基本概念

1.2 算法的基本概念

1.2.1 时间复杂度

1.2.2 空间复杂度

第二章 线性表

顺序表和链表对比

2.1 线性表的基本概念

2.1.1 数学定义

2.1.2 线性表的操作

2.2 线性表的存储方式

2.3 顺序表

2.3.1 顺序表的概念

2.3.2 顺序表的基本操作

2.4 单链表

2.4.1 单链表的基本概念

2.5 双链表

2.6 循环链表

2.6.1 循环单链表

2.6.2 循环双链表

2.7 静态链表

2.8 广义表

2.8.1 基本概念

2.8.2 广义表的性质

第三章 栈和队列

3.1 栈的概念

3.2 顺序栈

3.2.1 顺序栈的定义

3.2.2 顺序栈的操作

3.2.3 共享栈：解决栈大小不可改变

3.3 链栈

3.3.1 链栈的操作

3.4 队列的基本概念

3.4.1 队列的顺序存储

3.4.2 队列的链式存储结构

3.4.3 双端队列

3.5 栈和队列的应用

3.5.1 栈的括号匹配问题

3.5.2 栈的表达式求值

3.6 队列的应用

3.6.1 用队列实现树的层次遍历

3.6.2 用队列实现图的广度优先遍历

3.7 特殊矩阵的压缩存储

3.7.1 数组

3.7.2 对称矩阵存储

3.7.3 三角矩阵的压缩存储

3.7.4 三对角矩阵

3.7.5 稀疏矩阵的压缩存储

第四章 串

4.1 串的基本概念

4.2 串的基本操作

4.2.1 串的顺序存储

4.2.2 串的链式存储

4.3 字符串的模式匹配

4.3.1 暴力循环

4.3.2 KMP算法

4.3.3 KMP优化

第五章 树和二叉树

5.1 树

5.1.1 树的定义

5.1.2 树的基本术语

5.2 二叉树

5.2.1 二叉树的定义

5.2.2 二叉树的性质

5.2.3 特殊的二叉树

5.2.4 二叉树的存储结构

5.3 遍历二叉树

5.3.1 先序遍历

5.3.2 中序遍历

5.3.3 后序遍历

5.3.4 层序遍历

5.3.5 二叉树的遍历应用

5.4 线索二叉树

5.4.1 中序线索化

5.4.2 先序线索化

5.5.3 后序线索化

5.5 森林与树

5.5.1 树的存储结构

5.5.2 森林和二叉树的转换

5.5.3 森林和树的遍历

第一章绪论

第二章线性表

第三章栈和队列

第四章串

第五章树和二叉树

第六章图

第七章查找

第八章排序