数据结构¶

树¶

树的定义和基本术语¶

树的基本概念

空树：结点数为0的树

非空树的特性：

有且仅有一个根节点

没有后继的称为叶子结点

有后继的称为分支结点

除了根节点，任何结点都有且仅有一个前驱

每个结点可以有0或多个后继

结点之间的关系描述

祖先结点：结点向上到根节点所经过的所有结点

子孙结点：结点的后继以及他们的所有后继

父节点（双亲结点）：结点的直接前驱

孩子结点：结点的所有直接的后继

兄弟结点：相同父节点的其他结点

堂兄弟结点：非兄弟结点的同一层级的结点

两节点之间的路径：从上往下连接两个点的边的路径

路径长度：经过几条边

结点、树的属性描述

结点的层次（深度）：从上往下数第几层（根节点是第一层）

结点的高度：从下往上数第几层

树的高度：总归有多少层

结点的度：有几个分支

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

有序树，无序树

有序树：逻辑上树中结点的各子树从左往右有逻辑顺序，不能互换

无序树：逻辑上树中结点的各子树从左往右无逻辑顺序，可以互换

森林

概念：m棵互不相交的树的集合；m可为0，称为空森林

树的性质¶

1.结点数=总度数+1

2.度为m的数和m叉树区别

度为m的树：至少有一个结点度为m；一定是非空树，至少有m+1个结点

m叉树：允许所有结点的度数<m；可以是空树，称为m叉空树

3.度为m的树（或m叉树）第i层最多有m^(i-1)^个结点

4.高度为h的m叉树最多有(m^h^-1)/(m-1)个结点（由3等比数列求和得到）

5.高度为h的m叉树最少有h个结点

6.高度为h，度为m的树最少有h+m-1个结点

7.有n个结点的m叉树最小高度为log~m~(n*(m-1)+1)向上取整

二叉树的定义和基本性质¶

二叉树：

特点：1.每个结点最多有两个子树 2.左右子树不能颠倒（有序树）

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

特点：

只有最后一层有叶子结点

没有度为1的结点

==按层序从1开始编号，结点i的左孩子为2i，右孩子为2i+1，父节点为i/2的向下取整（如果有的话）==

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

特点：

只有最后两层会有叶子结点

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

==按层序从1开始编号，结点i的左孩子为2i，右孩子为2i+1，父节点为i/2的向下取整（如果有的话）==

i<=n/2向下取整为分支结点，i>n/2向下取整为叶子结点

二叉排序树：所有结点的左子树的关键字小于根结点的关键字，所有结点的右子树的关键字大于该结点的关键字

用于元素排序，搜索

平衡二叉树：所有结点的左子树和右子树的高度差小于1

平衡的二叉排序树能提高搜索效率

二叉树的性质¶

二叉树：

1.度为0的结点个数n~0~=度为2的结点个数n~2~+1（推导：n=n~0~+n~1~+n~2~【所有结点总数】 n=n~1~+2n~2~+1【树的结点总数=总度数+1】两式相减）

2.二叉树第i层最多有2^(i-1)^个结点

3.高度为h的二叉树最多有2^h^-1个结点

完全二叉树：

1.具有n个结点的完全二叉树高度为log~2~(n+1)向上取整或 log~2~n向下取整+1

推导：2^h-1^-1<n<=2^h^-1 或 2^h-1^<=n<2^h^

第i个结点所在层次为log~2~(i+1)向上取整或 log~2~i向下取整+1

2.对于完全二叉树，已知结点数n可以推出度为0，1，2的结点数为多少：n~1~=0或1；n~0~=n~2~+1（n~0~+n~2~必为奇数）

若n=2k为偶数，n~1~=1，n~0~=k，n~2~=k-1

若n=2k-1为奇数，n~1~=0，n~0~=k，n~2~=k-1

二叉树存储结构¶

顺序存储

#define MaxSize 100
struct TreeNode{
    ElemType value;//结点元素数据
    bool isEmpty;//记录结点是否为空
};
TreeNode t[MaxSize];//用数组存储树

必须要对应完全二叉树来进行操作：

i的左孩子——2i i的右孩子——2i+1 i的父节点——i/2向下取整

i所在层次——第i个结点所在层次为log~2~(i+1)向上取整或 log~2~i向下取整+1

是否有左孩子——2i<=n? 是否有右孩子——2i+1<=n?

是否是分支结点/叶子结点？——i>n/2向下取整？

如果不是完全二叉树，需要将号码对应完全二叉树再进行操作

i的左孩子——2i i的右孩子——2i+1 i的父节点——i/2向下取整

判断是否有左右孩子——使用isEmpty字段判断

二叉链表

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

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

//构造二叉链表
BiTree root=NULL;

//插入根节点
root=(BiTree)malloc(sizeof(BiTNode));
//省略具体化数据

//插入结点
BiTree* p=(BiTree*)malloc(sizeof(BiTNode));
//省略具体化数据

二叉链表不方便找到父节点，只能从根节点往下找父节点

因此增加指向父节点的指针变成三叉链表从而便于寻找父节点

二叉树先中后序遍历¶

先序：根左右

中序：左根右

后序：左右根

代码实现：

递归

void preOrder(BiTree T){//以先序为例
    if(T!=NULL){
        visit(T);//访问根节点
        preOrder(T->lchild);//递归遍历左子树
        preOrder(T->lchild);//递归遍历右子树
    }
}

空间复杂度：O(h)

函数调用栈：每一次递归调用函数时，先记录当前运行到第几行代码，再将递归调用的函数放入栈中运行

==非递归==

void preOrder(BiTree *BT){//先序
    if(BT==NULL)
        return;
    BiTree *p=BT;
    stack<BiTree*>st;//C中可以用数组作为栈，设置top指向索引
    while(p!=NULL||!st.empty()){//top>0
        while(p!=NULL){
            st.push(p);
            visit(p);
            p=p->lchild;
        }
        if(!st.empty()){
            p=st.top();
            st.pop();
            p=p->rchild;
        }
    }
}

void inOrder(BiTree *BT){//中序
    if(BT==NULL)
        return;
    BiTree *p=BT;
    stack<BiTree*>st;
    while(p!=NULL||!st.empty()){
        while(p!=NULL){
            st.push(p);
            p=p->lchild;
        }
        if(!st.empty()){
            p=st.top();
            visit(p);
            st.pop();
            p=p->rchild;
        }
    }

void postOrder(BiTree *BT){//后序
    if(BT==NULL)
        return;
    BiTree *p=BT;
    stack<BiTree*>st;
    BiTree *flag=NULL;
    while(p!=NULL||!st.empty()){
        if(p!=NULL){
            st.push(p);
            p=p->lchild;
        }
        else{
            p=st.top();
            if(p->rchild!=NULL&&flag!=p->rchild){
                p=p->rchild;
            }
            else{
                visit(p);
                st.pop();
                flag=p;
                p=NULL;
            }
        }
    }

二叉树层序遍历¶

1.初始化一个队列

2.根节点入队

3.让队头元素出队，访问该结点，并将该节点的左右孩字按顺序入队

4.循环3直至队列为空

void levelOrder(BiTree* BT)
{
    queue<BiTree*>q;//存放指针
    BiTree *p=BT;
    q.push(p);
    while(!q.empty){
        q.pop();
        visit(p);
        if(p->lchild!=NULL){
            q.push(p->lchild);
        }
        if(p->rchild!=NULL){
            q.push(p->rchild);
        }
    }
}

由遍历序列推出二叉树形态¶

若只给一棵二叉树的前，中，后，层序遍历的其中一种结果。则不能确定一棵唯一的二叉树

能够由遍历序列推出二叉树形态的组合：

1.前序+中序

2.后序+中序

3.层序+中序

找到树的根节点，从而划分左右子树，再找到子树的根节点，直至推出结果

线索二叉树¶

普通二叉树存在的问题：

不能从任一结点开始进行遍历，因为没有办法直接找到该结点的前驱或者后继

不使用线索二叉树寻找p结点前驱后继的方法：设置两个指针q和pre，q记录当前访问结点，pre记录上一个访问的结点；从头开始遍历，当p==q时pre为p的前驱，当p==pre时q为p的后继

线索二叉树：将二叉树的左空链域指向该结点的前驱，右空链域指向该结点的后继

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

分为：先，中，后序线索二叉树

typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode *lchild,*rchild;
    int ltag,rtag;
}ThreadNode,*TreadTree;

二叉树线索化¶

void createPreThread(ThreadNode *T)
{
    TreadNode *pre=NULL;//记录当前访问节点的前驱
    if(T!=NULL)
    {
        preThread(T,&pre);
    }
    if(pre->rchild==NULL)//最后一个结点的后继设为NULL，三种线索化时都添加一下
    {
        pre->rtag=1;
    }
}
void preThread(ThreadNode *p,ThreadNode &*pre)
{
    if(p!=NULL)
    {
        if(p->lchild==NULL)
        {
            p->lchild=pre;
            p->ltag=1;
        }
        if(pre!=NULL&&pre->rchild==NULL)//防止第一个结点开始线索化时pre还没有指向任何一个结点时出错
        {
            pre->rchild=p;
            pre->rtag=1;
        }
        pre=p;
        if(p->ltag==0)
        {
            preThread(p->lchild,&pre);//防止父节点线索化后访问左孩子时已经指向父节点的前驱导致的循环问题
        }
        preThread(p->rchild,&pre);
    }
}

void createInThread(ThreadNode *T)
{
    TreadNode *pre=NULL;//记录当前访问节点的前驱
    if(T!=NULL)
    {
        InThread(T,&pre);
        if(pre->rchild==NULL)//最后一个结点的后继设为NULL，三种线索化时都添加一下
        {
            pre->rtag=1;
        }
    }
}
void InThread(ThreadNode *p,ThreadNode &*pre)
{
    if(p!=NULL)
    {
        InThread(p->lchild,&pre);
        if(p->lchild==NULL)
        {
            p->lchild=pre;
            p->ltag=1;
        }
        if(pre!=NULL&&pre->rchild==NULL)//防止第一个结点开始线索化时pre还没有指向任何一个结点时出错
        {
            pre->rchild=p;
            pre->rtag=1;
        }
        pre=p;//访问完该节点后向后遍历
        InThread(p->rchild,&pre);
    }
}

void createInThread(ThreadNode *T)
{
    TreadNode *pre=NULL;//记录当前访问节点的前驱
    if(T!=NULL)
    {
        postThread(T,&pre);
        if(pre->rchild==NULL)//最后一个结点的后继设为NULL，三种线索化时都添加一下
        {
            pre->rtag=1;
        }
    }
}
void postThread(ThreadNode *p,ThreadNode &*pre)
{
    if(p!=NULL)
    {
        postThread(p->lchild,&pre);
        postThread(p->rchild,&pre);
        if(p->lchild==NULL)
        {
            p->lchild=pre;
            p->ltag=1;
        }
        if(pre!=NULL&&pre->rchild==NULL)//防止第一个结点开始线索化时pre还没有指向任何一个结点时出错
        {
            pre->rchild=p;
            pre->rtag=1;
        }
        pre=p;//访问完该节点后向后遍历
    }
}

线索二叉树中找前/后驱¶

中序线索二叉树

中序后继：

1.若p->rtag==1，则next=p->rchild;

2.若p->rtag==0,则中序后继为右子树最左下角的结点

中序线索二叉树遍历代码：

void InOrder(ThreadNode *T)//中序遍历线索化二叉树
{
    for(ThreadNode *p=FirstNode(T);p!=NULL;p=NextNode(p))
    {
        visit(p);
    }
}


ThreadNode *FirstNode(ThreadNode *p)//找到最左下脚的结点
{
    while(p->ltag==0)
    {
        p=p->lchild;
    }
    return p;
}

ThreadNode *NextNode(ThreadNode *p)
{
    if(p->rtag==0)
    {
        return FirstNode(p->rchild);
    }
    else
    {
        return p->rchild;
    }
}

中序前驱：

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

2.若p->ltag==0，则pre=p->lchild的最右下角的结点

中序线索二叉树逆向遍历：

void RevInOrder(ThreadNode *T)//逆中序遍历线索化二叉树
{
    for(ThreadNode *p=LastNode(T);p!=NULL;p=PreNode(p))
    {
        visit(p);
    }
}


ThreadNode *LastNode(ThreadNode *p)//找到最右下脚的结点
{
    while(p->rtag==0)
    {
        p=p->rchild;
    }
    return p;
}

ThreadNode *PreNode(ThreadNode *p)
{
    if(p->ltag==0)
    {
        return LastNode(p->lchild);
    }
    else
    {
        return p->lchild;
    }
}

先序线索二叉树：

先序后继：

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

2.若p->rtag==0,则若有左孩子，则后继就是左孩子的第一个结点；若没有左孩子只有右孩子，则后继就是右孩子的第一个结点

void PreOrder(ThreadNode *T)//先序遍历线索化二叉树
{
    for(ThreadNode *p=T;p!=NULL;p=NextNode(p))
    {
        visit(p);
    }
}

ThreadNode *NextNode(ThreadNode *p)
{
    if(p->rtag==1)
    {
        return p->rchild;
    }
    else
    {
       if(p->lchild!=NULL)
       {
           return p->lchild;
       }
        else
        {
            return p->rchild;
        }
    }
}

先序后继：

1.若p->ltag==1,则pre=p->lchild

2.若p->ltag==0,则只有通过三叉链表（能够找到父节点）才能找到前驱

i.若p为左孩子或p为右孩子且左孩子为空，则pre为父节点

ii.若p为右孩子且父节点存在左孩子，则前驱为左孩子最后被访问的节点

iii.若p没有父节点，则为根节点，没有前驱

void RevPreOrder(ThreadNode *T)//逆先序遍历线索化二叉树（必须使用三叉链表）
{
    for(ThreadNode *p=LastNode(T);p!=NULL;p=PreNode(p))
    {
        visit(p);
    }
}


ThreadNode *LastNode(ThreadNode *p)//找到最后一个访问的结点
{
    while(p->rtag==0||p->ltag==0)
    {
        if(p->rtag==0)
        {
            p=p->rchild;
        }
        else if(p->ltag==0)
        {
            p=p->lchild;
        }
    }
    return p;
}

ThreadNode *PreNode(ThreadNode *p)
{
    if(p->ltag==1)
    {
        return p->lchild;
    }
    else
    {
        if(p=p->parent->lchild||p=p->parent->rchild&&p->parent->lchild==NULL)//若p为左孩子或p为右孩子且左孩子为空，则pre为父节点
        {
            return p->parent;
        }
        else if(p=p->parent->rchild&&p->parent->lchild!=NULL)
        {
            return LastNode(p->parent->lchild);
        }
        else
        {
            return NULL;
        }
    }
}

后序线索二叉树

后序前驱：

1.若p->ltag==1,则pre=p->lchild

2.若p->ltag==0,则若既有左孩子又有右孩子，则前驱为右孩子的第一个结点；若只有左孩子，则前驱为左孩子的第一个结点

void RevPostOrder(ThreadNode *T)//逆后序遍历线索化二叉树
{
    for(ThreadNode *p=T;p!=NULL;p=PreNode(p))
    {
        visit(p);
    }
}

ThreadNode *PreNode(ThreadNode *p)
{
    if(p->ltag==1)
    {
        return p->lchild;
    }
    else
    {
        if(rtag==0)
        {
            p=p->rchild;
        }
        else
        {
            p=p->lchild;
        }
    }
}

后序后继：

1.若p->ltag==1,则pre=p->lchild

2.若p->ltag==0,则只有通过三叉链表（能够找到父节点）才能找到后继

i.若p为右孩子或p为左孩子且右孩子为空，则next为父节点

ii.若p为左孩子且父节点存在右孩子，则后继为右孩子最后被访问的节点

iii.若p没有父节点，则为根节点，没有后继

void PostOrder(ThreadNode *T)//后序遍历线索化二叉树（必须使用三叉链表）
{
    for(ThreadNode *p=FirstNode(T);p!=NULL;p=PreNode(p))
    {
        visit(p);
    }
}


ThreadNode *FirstNode(ThreadNode *p)//找到最后一个访问的结点
{
    while(p->rtag==0||p->ltag==0)
    {
        if(p->ltag==0)
        {
            p=p->lchild;
        }
        else if(p->rtag==0)
        {
            p=p->rchild;
        }
    }
    return p;
}

ThreadNode *PreNode(ThreadNode *p)
{
    if(p->ltag==1)
    {
        return p->lchild;
    }
    else
    {
        if(p=p->parent->rchild||p=p->parent->lchild&&p->parent->rchild==NULL)//
        {
            return p->parent;
        }
        else if(p=p->parent->lchild&&p->parent->rchild!=NULL)
        {
            return FirstNode(p->parent->rchild);
        }
        else
        {
            return NULL;
        }
    }
}

树的存储结构¶

双亲表示法（顺序存储）：每个结点包含记录以及双亲的下标

struct PTNode//树的结点的数据结构
{
    Elemtype data;
    int parent;
};
struct PTree//树的数据结构
{
    PTNode nodes[Max_Tree_Size];
    int n;
}；

添加元素：直接在末尾添加

删除元素：用末尾的记录替代被删除的记录；若删除的不是叶子结点，则需要把所有的孩子都删除了

优点：找父节点方便缺点：找孩子不方便

孩子表示法（顺序+链式）：顺序存储各结点，链式存储孩子，每个结点保存指向第一个孩子的指针

struct CTNode//孩子结点的数据结构
{
    int child;
    struct CTNode *next;
}
struct CTBox//树的结点的数据结构
{
    Elemtype data;
    struct CTNode *firstchild;
};
struct CTree//树的数据结构
{
    CTBox nodes[Max_Tree_Size];
    int n,r;//结点数和根的位置
};

优点：找孩子节点方便缺点：找父节点不方便

孩子兄弟表示法（链式）：将树转化为二叉树存储

typedef struct CSNode
{
    Elemtype data;
    CSNode *firstchild,*nextsibling;//左孩子指向第一个孩子结点，右孩子指向兄弟结点
};

树和二叉树的转换：左孩子指向第一个孩子结点，右孩子指向兄弟结点（见孩子兄弟法）

森林和二叉树的相互转化：

森林->二叉树：先将每个树转化为二叉树，再将根节点连起来

反之亦然

树和森林的遍历¶

树的先根遍历：先访问根节点。再依次对每个子树先根遍历

树的先根遍历的序列和对应转化的二叉树的先序遍历序列相同

树的后根遍历：先对子树进行后根遍历，最后再访问根节点

树的后根遍历的序列和对应转化的二叉树的中序遍历序列相同

以上两种也可以被称为深度优先遍历

树的层次遍历（用队列实现）：

1.根节点入队

2.若队列非空，则队头元素出队，并让其孩子都依次入队

3.循环2直至队列为空

也可以称为对树的广度优先遍历

森林的先序遍历：

1.访问第一棵树的根节点

2.先序遍历第一棵树中根节点的子树森林

3，先序遍历第一棵树以外剩余数构成的森林

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

森林的先序遍历序列等于对应转化的二叉树的先序遍历序列

森林的中序遍历：效果等同于依次对各个树进行后根遍历

森林的中序遍历序列等于对应转化的二叉树的中序遍历序列

==二叉搜索树（BST）==¶

又称二叉排序树，左子树结点值<根结点值<右子树结点值

进行中序遍历可以得到一个递增的有序序列

二叉排序树查找：

非递归：空间复杂度O（1）

BSTNode *BST_Search(BSTree T,int key)
{
    while(T!=NULL&&T->key!=key)
    {
        if(T->key<key)//要查找的值大于该结点的值
        {
            T=T->rchild;//往右子树找
        }
        else
        {
            T=T->lchild;//往左子树找
        }
    }
    return T;
}

递归：空间复杂度O（h）

BSTNode *BST_Search(BSTree T,int key)
{
    if(T==NULL)//查找失败，单独if
    {
        return NULL;
    }
    if(T->key==key)//查找成功
    {
        return T;
    }
    else if(T->key<key)//要查找的值大于该结点的值
    {
        BST_Search(T->rchild,key);//递归往右子树找
    }
    else
    {
        BST_Search(T->lchild,key);//递归往左子树找
    }
}

二叉排序树的插入：

递归：空间复杂度O（h）

int BST_Insert(BSTree &T,int k)
{
    if(T==NULL)//结点为空，插入新结点
    {
        T=malloc(sizeof(BSTNode));
        T->key=k;
        T->lchild=T->rchild=NULL;
        return 1;//插入成功返回1
    }
    else if(k==T->key)//有相同关键字，查找失败
    {
        return 0;
    }
    else if(k<T->key)//要查找的值小于该结点的值
    {
        BST_Insert(T->lchild,k);//递归的插入到左子树
    }
    else
    {
        BST_Insert(T->rchild,k);//递归的插入到右子树
    }
}

非递归：空间复杂度O（1）

int BST_Insert(BSTree &T,int k)
{
    while(T!=NULL)
    {
        if(T->key==k)//有相同关键字，查找失败
        {
            return 0;
        }
        else if(k<T->key)//要查找的值小于该结点的值
        {
            T=T->lchild;//往左子树插入
        }
        else 
        {
            T=T->rchild;
        }
    }
    T=malloc(sizeof(BSTNode));
    T->key=k;
    T->lchild=T->rchild=NULL;
    return 1;//插入成功返回1
}

二叉排序树的构造：

void Create_BST(BSTree &T,int str[],int n)
{
    T=NULL;
    int i=0;
    while(i<n)
    {
        BST_Insert(T,str[i]);
        i++;
    }
}

序列不同构造的二叉树形状也不同

二叉排序树删除：

1.若删除叶子结点，则直接删去即可

2.若删除的结点只有左子树或只有右子树，则用左子树或右子树替代原来的位置

3.若删除的结点既有左子树也有右子树，则可以用该结点的直接前驱或后继来代替该节点的位置；

直接前驱：左子树最右下角的结点 while(p!=NULL) p=p->rhchild;

直接后继：右子树最左下角的结点 while(p!=NULL) p=p->lhchild;

查找效率分析：

取决于树高，最好O（logn），最坏O（n）

平衡二叉树（AVL）¶

树上任一结点的左子树和右子树的高度之差不超过1

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

平衡二叉树的插入

调整对象：最小不平衡子树

最小不平衡子树：从插入点网上找第一个不平衡的结点（平衡因子不等于1,0,-1）为根的子树

调整最小不平衡子树：（A为最小不平衡子树）

1.A结点的左孩子的左子树中插入导致不平衡

解决方案：右旋最小不平衡子树：以A的左孩子作为根节点，A变为新的根节点的右孩子，并将新节点原来的右孩子变成A的左孩子

代码：

//与下图对应
f->lchild=p->rchild;
p->rchild=f;
gf->lchild/rchild=p;

2.A结点的右孩子的右子树中插入导致不平衡

解决方案：左旋最小不平衡子树：以A的右孩子作为根节点，A变为新的根节点的左孩子，并将新节点原来的左孩子变成A的右孩子

代码：

//与下图对应
f->rchild=p->lchild;
p->lchild=f;
gf->lchild/rchild=p;

3.A结点的左孩子的右子树中插入导致不平衡

解决方案：先将A的左孩子的进行左旋，再将整棵子树右旋

4.A结点的右孩子的左子树中插入导致不平衡

解决方案：先将A的右孩子的进行右旋，再将整棵子树左旋

==查找效率分析：时间复杂度：O（log~2~n）==

哈夫曼树¶

带权路径长度：从树的根节点到该系欸但的路径长度与该系欸点上权值的乘积

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

哈夫曼树：也称为最优二叉树。即还有n个带权叶节点的二叉树中，带权路径长度最小的二叉树

哈夫曼树的构造：

1.选择权值最小的两个结点变成一棵树，树的根节点的权值为两个结点之和，并将这棵树看作一个新的结点

2.重复1的操作，直到只剩下一棵树

应用：哈夫曼编码

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

可变长度编码：允许不同字符长度不同；若没有一个字符的编码是另一个字符的编码的前缀，则称为前缀编码

哈夫曼编码：每个字符作为叶子结点，将各个字符出现的频度作为结点的权值，构造哈夫曼树

图¶

图的基本概念¶

注意：线性表，树都可以为空，图的顶点集一定不能为空（边集可以为空）

无向图和有向图

无向图：由无向边组成（简称边）

有向图：由有向边组成（也成为弧），没有箭头一端被称为弧尾，有箭头一端被称为弧头

简单图和多重图

简单图：不存在重复的边；不存在顶点到自身的边

多重图：存在重复的边；存在顶点到自身的边

顶点的度，入度，出度

对于无向图：顶点的度为依附于该顶点边的条数

无向图全部顶点的度的和等于边数乘以2

对于有向图：顶点的入度为该顶点有向边的终点个数

顶点的出度为该顶点有向边的起点个数

顶点的度为入度加出度之和

有向图全部顶点的入度之和等于出度之和等于边的数量

顶点-顶点的关系描述

路径：一个顶点到另一个顶点的顶点序列

回路（环）：第一个顶点和最后一个顶点相同的路径

简单路径：路径中没有重复出现的点

简单回路：除了第一个点和最后一个点没有重复出现的点

路径长度：路径上边的数目

点到点的距离：两个顶点间的最短路劲长度

无向图中，若两点之间有路径存在，则称为连通的

有向图中，若两顶点间来回都有路径，则称为强连通的

连通图，强连通图

连通图：无向图中任意两个顶点都连通

连通图至少有n-1条边；非连通图最多有C^2^~n-1~

强连通图：有向图中任意一对顶点是强连通的

强连通图至少有n条边（形成回路）

子图

图的顶点集和边集都是原图的子集，称为子图

生成子图：子图包含原图的所有顶点

连通分量

无向图中的极大连通子图（包含尽可能多的顶点和边）称为连通分量

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

生成树

连通图的生成树是包含图中全部顶点的极小连通子图（边尽可能少）

若原图顶点数为n，则他的生成树含有n-1个遍；砍去一个边则会变成非连通图；若加上一边则会形成一个回路

生成森林

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

边的权，带权图/网

边的权：每条边上带有含义的数值

带权图/网：边上带有权值的图叫带权图，又叫网

带权路径长度：一条路径上所有边的权值之和

几种特殊形态的图

无向完全图：无向图中任意两个顶点间都存在边，共有C^2^~n~条边

有向完全图：有向图中任意两个顶点之间存在方向相反的两条弧，共有2C^2^~n~条边

稀疏图：边很少的图

稠密图：边很多的图

树：不存在回路且连通的无向图（n个顶点的树，必有n-1条边）

有向树：一个顶点的入度为0，其余顶点的入度都为1的图，称为有向树

n个顶点的图，若边数>n-1，则一定有回路

图的存储¶

邻接矩阵法

typedef struct //邻接矩阵的数据结构
{
    char Vex[MaxVertexNum];//顶点表，存放顶点数据
    int Edge[MaxVertexNum][MaxVertexNum];//邻接矩阵,边表
    int vexnum,arcnum;//图当前顶点数和边数
}MGraph;

求顶点的度，入度，出度：

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

有向图：第i个结点的入度=第i行非零元素的个数

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

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

邻接矩阵法求顶点入度，出度，度的时间复杂度为O（|V|）（|V|代表顶点个数）

邻接矩阵的性能分析

空间复杂度：O（V^2^）只和顶点数有关，和实际边数无关

只适合存储稠密图

无向图的邻接矩阵是对称矩阵，可以压缩存储（只存上三角/下三角区）

邻接矩阵的性质

设图的邻接矩阵为A，则A^n^的元素A^n^i j等于有顶点i到顶尖j的长度为n的路径数目

邻接表法

typedef struct VNode
{
    VertexType data;//顶点信息
    ArcNode *first;//指向第一条边/弧
}Vnode,AdjList[MaxVertexNum];

typedef struct
{
    AdjList vertices;//结点数组
    int vexnum,arcnum;//结点数，边数
}ALGraph;

typedef struct ArcNode
{
    int adjvex;//边指向哪个结点
    struct ArcNode *next;//指向下一条弧的指针
    //InfoTypr info;//边权值
}ArcNode;

空间复杂度：

无向图：O（|V|+2|E|）

有向图：O（|V|+|E|）

邻接表求度，入度，出度，与顶点相连的边：

无向图：遍历该顶点的边链表

有向图：

出度，从顶点出发的边：遍历该顶点的边链表

入度，到达顶点的边：遍历整个邻接表，找到便链表中指向该结点的边

邻接表便是方式并不是唯一的

十字链表（只适用于有向图）

空间复杂度：O（|V|+|E|）

找出边：沿着绿线寻找找入边：沿着橘线寻找

邻接多重表（只适用于无向图）

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

图的基本操作¶

Adjacent(G,x,y)：判读图G是否存在边或（x，y）

邻接矩阵：直接找到对应位置，判断为0或1；时间复杂度：O（1）

邻接表：遍历一个顶点的所有边表；时间复杂度：O（1）~O（|V|）

有向无向图表现相当

Neighbor（G，x）：列出图G中与顶点x邻接的边

邻接矩阵：遍历该顶点那行或那列，找到值唯一的对应的边；时间复杂度：O（|V|）

邻接表：遍历该顶点的边表；时间复杂度：O（1）~O（|V|）

有向图：出边：遍历该顶点的边表；入边：遍历整个表的边表时间复杂度：O（|E|）

InsertVertex（G，x）：在图G中插入顶点x

邻接矩阵：顶点表新增，邻接矩阵增加一行一列

邻接表：顶点表增加一个

有向无向图表现相当

DeleteVertex（G，x）：在图G中删除顶点x

邻接矩阵：将对应行和列全部改成0，并在顶点表中添加bool判定已经被删除

邻接表：无向图：删除对应顶点后面所有的边，并找到这些边所指向的顶点，将其边表中的指向删除顶点的边删除

有向图：删除出边：直接删除该顶点的边表删除入边：遍历整个表

AddEdge（G，x，y）：若边不存在，则向图G中添加该边

邻接矩阵：找到对应行列改成1

邻接表：找到对应顶点头插或尾插顶点

有向无向图表现相当

FirstNeighbor（G，x）：求图G中顶点x的第一个邻接点，返回顶点号，若没有则返回-1

邻接矩阵：找到对应行或列的第一个1元素

邻接表：无向图：找到对应点的边表的第一个

有向图：出边：找到对应点的边表的第一个

入边：遍历整个边表找到第一个

NextNeighbor（G，x，y）：求图G中x顶点中，除y以外的下一个邻接顶点，若没有则返回-1

邻接矩阵：找到对应行或列的第二个1元素

邻接表：找到对应边表的第二个

图的广度优先遍历算法（BFS）¶

1.从顶点开始访问，并访问后将标志数组中该点的标记改为已访问，最后顶点入队

2.让队列的队头出队，并访问所有该结点的邻接顶点，标记为已访问，并入队

3.循环2直至队列为空，此时BFS完成

4.遍历标记数组，判断是否还有结点没有访问，若有则重复123，若没有则结束（防止是非连通图没有全部被访问到）

代码：

vector<bool> visited(MaxVertexNum,false);//标志数组，判断是否已经访问过,全部初始化为false

void BFSTraverse(Graph G)
{
    queue<int> Q;//辅助队列
    for(vector<bool>::iterator it=Q.begin();it!=Q.end();it++)//遍历标记数组
    {
        if(*it==false)
        {
            BFS(G,*it);
        }
    }
}

void BFS(Graph G,int v)//v为顶点
{
    visit(v);//访问顶点
    visited[v]=true;
    Q.push(v);//入队
    while(!isEmpty(Q))//当队伍非空时
    {
        Q.pop();//队头元素出队
        for(int w=FirstNeighbor(G,q.front);w!=-1;w=NextNeighbor(G,q.front,w))//遍历所有邻接点
        {
            if(!visited[w])//访问没有被访问过的结点
            {
                visit[w];
                visited[w]=true;
                Q.push(w);//入队
            }
        }
    }
}

遍历序列：邻接矩阵：唯一邻接表：不唯一

时间复杂度分析：

邻接矩阵存储：O（|V|^2^）邻接表：O（|V|+|E|）

广度优先生成树

根据广度优先遍历的顺序构成的树

邻接矩阵的广度优先生成树唯一邻接表的广度优先生成树不唯一

广度优先生成森林

非连通图根据广度优先遍历的顺序构成的森林

图的深度优先遍历（DFS）¶

类似于树的先序遍历，递归的往下访问直到没有没访问过的邻接点

代码：

vector<bool> visited(MaxVertexNum,false);//标志数组，判断是否已经访问过,全部初始化为false

void DFSTraverse(Graph G)
{
    for(v=1;v<=G.vexnum;v++)//遍历所有顶点，检查是否还有顶点没有访问（防止非连通图）
    {
        if(!visited[v])
        {
            DFS(G,v);
        }
    }
}

void DFS(Graph G,int v)
{
    visit(v);
    visited[v]=true;
    for(int w=FirstNeighbor(G,v);w!=-1;w=NextNeighbor(G,v,w))
    {
        if(!visited[w])
        {
            DFS(G,w);//递归的访问邻接点
        }
    }
}

遍历序列：邻接矩阵：唯一邻接表：不唯一

复杂度分析：

空间复杂度：最好：O（1）最坏：O（|V|）

时间复杂度：邻接矩阵存储：O（|V|^2^）邻接表：O（|V|+|E|）

深度优先生成树

根据深度优先遍历顺序得到的树

深度优先生成森林

非连通图根据深度优先遍历顺序得到的森林

最小生成树¶

生成树

连通图的生成树是包含图中全部顶点的极小连通子图（边尽可能少）

若原图顶点数为n，则他的生成树含有n-1个边；砍去一个边则会变成非连通图；若加上一边则会形成一个回路

最小生成树

对于带权连通无向图，若一生成树边的权值之和最小，则称为最小生成树

最小生成树可能有多个，但边的权值之和总是最小的且唯一的

若连通图本身就是一棵树，则最小生成树就是其本身

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

求最小生成树（MST）

==Prim算法==¶

从某一顶点开始，每次将代价最小的新顶点纳入生成树，直到所有顶点都被纳入

时间复杂度：O（|V|^2^） 适合边稠密图（E大）

算法实现：

1.设置两个数组，一个bool数组记录顶点是否被纳入生成树，一个int数组记录当前生成树到每个顶点代价最小的权值，若不能直接连到另一个顶点，则设置值为∞

2.选择一个顶点开始，设置已经纳入生成树，并遍历最小权值数组，将距离最短的结点纳入生成树

3.遍历一边最小权值数组，按照新的生成树修改最小权值数组

4.重复23，直至结束

==Kruskal算法==¶

每次选择一条权值最小的边，使这条边两头连通，若已连通则不选，直至所有结点连通

时间复杂度：O（|E|log~2~|E|） 适合边稀疏图（E小）

算法实现：

1.设置一个数组，每个元素包含各边的权值，以及这条边两头的顶点是谁，并按照权值递增排列

2.找到权值最小的边，并判断两头的顶点是否是连通的（并查集），若不连通则使其连通，若已连通则寻找下一个

3.重复2直到所有顶点都连通

最短路径问题¶

单源最短路径：BFS算法（无权图），Dijkstra算法（带权图，无权图）

各顶点间的最短路径：Floyd算法（带权图，无权图）

BFS算法（无权图）¶

在BFS的基础上增加两个数组，一个记录起始点到该点的最短路径，另一个记录该点的直接前驱是哪个结点

在BFS访问新结点的时候，记录该点到起始点的距离，以及他的前驱结点

最后通过两个数组可以判断最短路径以及路径的顺序

void BFS_Min_Distance(Graph G,int v)//v为起始点
{
    for(int i=0;i<G.vertexnum;i++)//初始化两个数组
    {
        d[i]=∞;//到起始点的最短距离
        path[i]=-1;//记录结点的直接前驱
    }
    visit(v);//访问顶点
    visited[v]=true;
    d[v]=0;
    Q.push(v);//入队
    while(!isEmpty(Q))//当队伍非空时
    {
        Q.pop();//队头元素出队
        for(int w=FirstNeighbor(G,q.front);w!=-1;w=NextNeighbor(G,q.front,w))//遍历所有邻接点
        {
            if(!visited[w])//访问没有被访问过的结点
            {
                d[w]=d[q.front]+1;
                path[w]=q.front;
                visit[w];
                visited[w]=true;
                Q.push(w);//入队
            }
        }
    }
}

时间复杂度：邻接矩阵存储：O（|V|^2^）邻接表：O（|V|+|E|）

Dijkstra算法（带权图，无权图）¶

设置三个数组，数组1记录各顶点是否已找到最短路径，数组2记录最短路径的长度，数组三记录路径上的前驱

1.从出发点开始，遍历记录到每个顶点的最短距离，并修改直接前驱

2.将目前还没有考虑的&&最短距离中最短的对应的顶点设为已找到最短路径，并遍历这个顶点到邻接点的边的权值，更新最短路径的值和前驱

3.重复2的操作，直至所有的顶点都找到最短路径

时间复杂度：O（|V|^2^）

Dijkstra算法不适合有负权值的带权图！

Floyd算法（带权图，无权图）¶

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

设置两个矩阵，矩阵1记录当前情况下各顶点间最短路径，矩阵2记录两个顶点间的中转点

1.假设没有中转点时，遍历记录各顶点间的最短路径，并让中转点为-1

2.假设V0为中转点，通过下式判断是否存在更近的路径并更新，记录此时两点之间的中转点

（i，j分别表示行列，k表示新增的中转点序号）

3.假设V0，V1为中转点，重复2的操作

4.再增加一个中转点然后重复2的操作，直至所有点都能够称为中转点

for(int k=0;k<G.vexnum;k++)//新增中转点
{
    for(int i=0;i<G.vexnum;i++)
    {
        for(int j;j<G.vexnum;j++)
        {
            if(A[i][j]>A[i][k]+A[k][j])//判断通过新的中转点最短路径是否变小
            {
                A[i][j]=A[i][k]+A[k][j];//修改最短路径
                path[i][j]=k;//修改中转点
            }
        }
    }
}

时间复杂度：O（|V|^3^）

空间复杂度：O（|V|^2^）

寻找最短路径：

Floyd算法可以解决负权值带权图，但不能解决带负权回路的图！

有向无环图（DAG）¶

若一个有向图中没有环路，称为有向无环图

有向无环图的描述表达式

拓扑排序¶

找到做事情的顺序

==AOV网：用顶点表示活动的网，一定是有向无环图==

拓扑排序的实现：

1.找到一个没有前驱的结点并输出

2.删除网中该节点以及该结点为起点的所有有向边

3.重复1和2直到AOV网空或不存在没有前驱结点的点为止

拓扑排序的序列可能有多个

//设置两个数组，indegree[]用于记录该点前驱还有几个，print[]用于记录拓扑排序后的顺序
bool TopologicalSort(Graph G)//基于邻接表实现
{
    InitStack(S);//初始化栈，存储入度为0的结点
    for(int i=0;i<G.vexnum;i++)//将所有一开始入度为0的结点入栈
    {
        if(indegree[i]==0)
        {
            S.push(i);
        }
    }
    int count=0;//计数已经排序几个，用于之后判断拓扑排序是否成功
    while(!S.Empty)
    {
        S.pop();//栈顶出栈
        print[count++]=i;//放入拓扑排序后的序列中
        for(p=G.vertex[i].firstarc;p!=NULL;p=p->nextarc)//遍历邻接表顶点后的所有边结点
        {
            int v=p->adjvex;//v=邻接表的边结点所指向的结点
            if(--indegree[v]==0)//判断结点前驱数量-1后前驱是否为0
            {
                s.push(v);//前驱为0的结点入栈
            }
        }
    }//while
    if(count<G.vexnum)
    {
        return false;//放入拓扑排序的结点数<总结点数，说明存在回路，拓扑排序失败
    }
    else
    {
        return true;//成功
    }
}

时间复杂度：邻接矩阵O（|V|^2^）邻接表O（|V|+|E|）

逆拓扑排序

与拓扑排序相反，从出度为0的结点开始，获得一个倒着完成事情的顺序

可以使用DFS实现逆拓扑排序：在结点被访问且没有邻接点时输出

vector<bool> visited(MaxVertexNum,false);//标志数组，判断是否已经访问过,全部初始化为false

void DFSTraverse(Graph G)
{
    for(v=1;v<=G.vexnum;v++)//遍历所有顶点，检查是否还有顶点没有访问（防止非连通图）
    {
        if(!visited[v])
        {
            DFS(G,v);
        }
    }
}

void DFS(Graph G,int v)
{
    visited[v]=true;
    for(int w=FirstNeighbor(G,v);w!=-1;w=NextNeighbor(G,v,w))
    {
        if(!visited[w])
        {
            DFS(G,w);//递归的访问邻接点
        }
    }
    print(v);//输出顶点
}

查找¶

顺序查找¶

从头到尾一个个找

算法：

vector<int>v;
for(int i=0;i<v.size()&&v[i]!=key;i++)
return i==v.size? -1:i;

查找效率：

ASL（平均查找长度）：（查找长度*查找次数）的总和

ASL~成功~=（n+1）/2

ASL~失败~=n+1

==所以顺序查找得时间复杂度为O（n）==

优化算法（仅对于有序表）

当查找的序列有序时，以递增为例，只需要查找到第一个大于要查找的数，之后的就没必要继续对比之后的数了

由此我们可以得到一棵查找判定树：

ASL~失败~=n/2+n/(n+1)

优化算法2（已知各个元素被查概率大小不同）

将被查概率大的放在前面，从而增加查找效率

折半查找（二分查找）¶

仅适用于==有序==的==顺序表==（顺序表拥有随机访问的特性，链表不能用二分查找）

1.定义low high两个变量指向数组的第一个数和最后一个数

2.mid=(low+high)/2向下取整，判断mid所指向的值是否等于要查找的值；若等于则找到，结束；若所要查找的值大于mid所指向的值，则令low=mid+1；若所要查找的值小于mid所指向的值，则令high=mid-1；

3.重复执行2直至找到需要的值或者low>high;若low>high了则查找失败

vector<int>v;
int low,high,mid;
low=0;high=v.size()-1;
while(low<=high)
{
    mid=(low+high)/2;
    if(key==v[mid])
        return;
    else if(key>v[mid])
        low=mid+1;
    else if(key<v[mid])
        high=mid-1;
}
return -1;

折半查找判定树

对于mid=(low+high)/2向下取整的情况，对于任何一个结点，右子树的结点数-左子树的结点数=0或1

折半查找判定树一定是平衡二叉树

元素个数为n时树高h=log~2~（n+1）向上取整

==由折半查找判定树得折半查找得时间复杂度为O（log~2~n）==

分块查找（索引顺序查找）¶

将待查找得序列按照范围进行分块，并用一个新的索引表记录每个分块的最大关键字和分块的索引区间

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

算法：

1.在索引表内确定需要查找的元素所属于的分块（可顺序，可折半）

2.在块内顺序查找

用折半查找查索引

若索引表不包含需要查找的元素（如下图），则折半查找最终一定停在low>high，要在low对应的分块内查找

若low超出索引表范围，则查找直接失败

顺序查找索引表时，ASL~最小~=n^1/2^+1,当且仅当s=b=n^1/2^时

折半查找索引表时，ASL=log~2~（b+1）向上取整+(s+1)/2

（s为每块的元素个数，b为索引表元素的个数）

B树¶

m阶B树的核心特征：

1.除根节点外，每个结点至少有m/2向上取整个子树，即至少有m/2向上取整-1个关键字（尽可能让数满，不要太高）

2.对任意结点，其所有子树高度相同（尽可能让树平衡）

3.关键字的值的规则和二叉排序树相同

含有n个关键字的m叉B树，其高度的范围是[log~m~(n+1),log~m/2向上取整~(n+1)/2+1]

B树的插入

新元素通过查找来判断插入位置，插入的位置一定是终端结点；在插入后，若导致结点的关键字超过上限（超过m-1），则从中间位置（m/2的向上取整）将关键字分为两部分，左边部分放在原结点中，右边部分放到新结点中，中间位置的元素放到原结点的父节点中；若此操作导致父节点也满了，则重复前面的操作直到根节点或父节点没有满的情况

B树的删除

若对终端结点删除：

若删除后结点元素个数符合要求（即>=2），则直接删去即可

若删除后结点元素个数不符合要求（即<2），则：

若右（或左）兄弟结点元素数量>2，则将右侧（或左侧）的最小值（最大值）替换这个两个结点父节点元素，并将父节点元素填补到删除的结点处

若左右结点元素数量都<=2，则将结点和其右（或左）兄弟结点合并为一个，并将父节点的元素也合并进去；若父节点因为合并元素数量<2了，则重复前面合并的操作，直到根节点或所有父节点都符合B树要求

若对非终端结点删除：

可以找到该元素的直接前驱或直接后继来填补该位置，从而转化为删除终端结点（直接前驱或直接后继）的操作

直接前驱：该结点左子树的最右下角的元素

直接后继：该节点右子树的最左下角的元素

B+树¶

B树与B+树的区别

1.B+树：结点中n个关键字对应n棵子树 B树：结点中n个关键字对应n+1个子树

2.m阶B+树：根节点关键字个数：[1,m]；其他结点关键字：[m/2向上取整,m]

m阶B树：根节点关键字个数：[1,m-1]；其他结点关键字：[m/2向上取整-1,m-1]

3.B+树：叶子结点包含全部关键字，非叶子结点中出现的关键字叶子结点中也会出现

B树：各结点中关键字不会重复

4.B+树：叶子结点包含信息，非叶子结点仅起索引作用，含有对应子树最大关键值和指向子树的指针，没有关键字对应记录的存储地址

B树：结点中包含了关键字的对应记录的储存地址

B+树的优点：

当B+树的每个结点都代表磁盘块时，相同情况下一个结点所存放的信息就比B树更多（因为B树每个结点还要存放对应记录的地址），因此树会更矮，读磁盘的次数会更少，效率更高

散列函数¶

又称哈希表，特点是数据元素的关键字和储存地址直接相关

通过散列函数（哈希函数）建立关键字和地址的联系 Address=H（key）

不同的关键字根据散列函数映射到同一个地址值，则称他们为同义词，这种情况叫冲突

上图运用了拉链法解决冲突——把所有同义词存储在一个链表中

对上图：

ASL~成功~=（16+2*4+3*1+4*1）/12=1.75

ASL~失败~=（0+4+0+2+0+0+2+1+0+0+2+1+0）/13=0.92

装填因子：表中记录的个数/散列表长度

装填因子的大小直接影响散列表的查找效率

减少冲突能够有效提高提高散列查找的效率

通过设计散列函数来减少冲突

1.除留余数法：H（key）=key%p p是不大于散列表长但最接近或等于表长的素数（如散列表长14，p取13）

原理：素数取模，分布更均匀，冲突更少

2.直接定值法：H（key）=key或H（key）=a*key+b

适合关键字分布基本连续的情况

3.数字分析法：选取数码分布较为均匀的若干位作为散列地址（如手机号前面几位格式较为固定，最后四位数码分布较为均匀，可以直接以后四位作为散列地址）

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

原理：这种方法得到的散列地址和关键字的每一位都有关系，因此更加平均

散列查找是典型的以空间换时间的算法，若设计够合理，则散列表越长，冲突越少

冲突时的处理方式

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

2.开放定址法：将表中的空闲地址向其非同义词开放，其数学递推公式为：

H~i~=(H(key)+d~i~)%m （m散列表长，d~i~增量序列，i可理解为第i次发生冲突）

d~i~的设计方法：

i.线性探测法：d~i~=0，1，2，……，m-1；即发生冲突时探测后一个位置是否为空

线性探测法设计的哈希表查找方法：

1.根据哈希函数找到对应的位置

2.对比关键字，如果相同则找到；如果不相同，则向后移一位

3.重复2，直至找到；若对比的位置为空，说明查找失败（空位置的判断也算作一次判断）

线性探测法很容易造成同义词和非同义词聚集，严重影响查找效率

ii.平方探测法：d~i~=0^2^,1^2^,-1^2^,2^2^,-2^2^,……k^2^,-k^2^ (k<=m/2)

比起线性探测法更不易产生聚集问题

平方探测法设计的哈希表查找方法：根据公式H~i~=(H(key)+d~i~)%m找到下一个元素的位置并进行比较

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

iii.伪随机序列法：d~i~是一个伪随机的序列，如d~i~=0，5，17，23，11，……

使用开放定址法设计的哈希表删除元素不能直接删除，否则会导致存在的元素无法被找到

需要进行逻辑删除，即保留元素的同时使用bool值标记该元素已被删除，从而防止上述问题发生

3.再散列法：除了原始散列函数，再准备几个散列函数；当发生冲突时，用下一个散列函数计算新地址，直到不冲突为止

公式：H~i~=RH~i~(Key) i=1，2，3，……，k

排序¶

插入排序¶

以递增为例：

1.从第二个数开始，取出这个数放入临时变量

2.设置一个指针指向这个数前面一个数，并对两数进行比较，若前面的数比这个数大则前面的数向后移一位，指针向前移动一位，继续比较，直至指针指向的数<=这个数

3.将这个数放入指针后一位的空位置中

在这里插入图片描述

代码：

void InsertSort(vector<int> v)
{
    for(int i=1;i<=v.size();i++)//从第二个元素开始，依次往后判断是否需要插入排序
    {
        int temp=v[i];
        for(int pos=i-1;pos>=0&&v[pos]>v[i];pos--)//判断需要插入的元素前是否存在比该元素大的元素
        {
            v[pos+1]=v[pos];//向后移位
        }
        v[pos+1]=temp;
    }
}

==效率分析：==

==空间复杂度：O（1）==

==时间复杂度：==

==最好：O（n）==

==最坏：O（n^2^）==

==平均：O（n^2^）==

==稳定性：稳定==

优化：折半插入排序

先用折半查找找到应该插入元素的位置，再范围内元素移动

以递增为例：

1.先对需要排序的数前面已经排好序的序列使用二分查找，运行至low>high的情况（无论是否出现相同的数）

2.将[low,i-1]的数向后移动，再将需要排序的数放入空位中

代码：

void InsertSort(vector<int> v)
{
    for(int i=1;i<=v.size();i++)//从第二个元素开始，依次往后判断是否需要插入排序
    {
        int temp=v[i];
        int low=0,high=i-1
        while(low<=high)//对需要插入元素前的序列进行二分查找，一直运行到low>high的位置
        {
            int mid=(low+high)/2;
            if(temp>=v[mid])
            {
                low=mid+1;
            }
            else if(temp<v[mid])
            {
                high=mid-1
            }
        }
        for(int j=i-1;j>=low;j--)//将low到i-1区间的元素向后挪
        {
            v[j+1]=v[j];
        }
        v[low]=temp;//将需要插入排序的元素放入空位
    }
}

时间复杂度依旧为O（n^2^）

链表进行插入排序

不需要移动，只需要修改指针，时间复杂度依旧是O（n^2^）

希尔排序¶

先将待排序的序列分成若干个子序列，子序列为i,i+d,i+2d，……，i+kd，对各子表进行直接插入排序；再逐步缩小增量d，重复前面步骤，直至d=1；

只适用与顺序表，不适用于链表（需要支持随机访问）

在这里插入图片描述

希尔本人建议，每次增量d缩小一半

void ShellSort(vector<int> v)//以递增为例
{
    int temp=0;
    int d;
    for(d=(v.size()-1)/2;d>=1;d/=2)//增量递减
    {
        for(int i=d;i<v.size();i++)//每一趟中逐个元素判断是否要调整位置
        {
            int j=i-d;
            int temp=v[i];
            while(j>=0&&temp<v[j])//对比子序列中在前一个元素之前是否还有比该元素大的元素
            {
                v[j+d]=v[j];//在子序列中向后移位
                j-=d;
            }
            v[j+d]=temp;//将该元素复制到移动后的空位
        }
    }
}

算法性能分析：

==空间复杂度：O（1）==

==时间复杂度：==

==最好：O（n）==

==最坏：O（n^2^）==

==平均：O（n^1.3^）==

==稳定性：不稳定==

冒泡排序¶

从后往前（或从前往后）两两比较相邻元素的值，若顺序错误则调换，一趟以后重复前面的操作到已经排好序的序列前，直至全部排好

void BubbleSort(vector<int> v)//以递增，从头开始冒泡的为例
{
    for(int i=0;i<v.size()-1;i++)//总共进行几趟冒泡排序
    {
        bool flag=false;//一趟冒泡排序中是否发生交换的标志位
        for(int j=0;j<v.size()-1-i;j++)//每次冒泡排序从头到尾部已排好的序列前
        {
            int temp;
            if(v[j]>v[j+1])
            {
                temp=v[j];v[j]=v[j+1];v[j+1]=temp;
                flag=true;
            }
        }
        if(flag==false)//如果一趟冒泡排序一次都没有交换，则说明已经有序，直接退出
        {
            return;
        }
    }
}

链表顺序表都能用

在这里插入图片描述

算法性能分析：

==空间复杂度：O（1）==

==时间复杂度：==

==最好：O（n）==

==最坏：O（n^2^）==

==平均：O（n^2^）==

==稳定性：稳定==

快速排序¶

以递增为例：在待排序列中选择一个元素作为基准（被称为枢轴，通常取首元素），通过low和high两个指针遍历剩下的序列，将小于基准的元素放到左侧，大于基准的元素放到右侧；一次划分结束后以基准分开的左右两侧再次重复之前的算法（递归），直至所有元素都被排序

算法:

void QuickSort(vector<int> v,int low,int high)
{
    if(low<high)//如果low=high说明已经全部排序结束，不需要再排序
    {
        int pivotpos=Partition(v,low,high);//接受快速排序分区间后基准的位置
        QuickSort(low,pivotpos-1);//递归快速排序基准左侧序列
        QuickSort(pivotpos+1,high);//递归快速排序基准右侧序列
    }
}

int Partition(vector<int> v,int low,int high)
{
    int pivot=v[low];//取序列第一个作为基准
    while(low<high)//如果low=high说明已经全部排序结束，不需要再排序
    {
        while(v[high]>pivot&&low<high)//从high开始寻找比基准小的数；如果low=high说明已经全部排序结束，不需要再排序
        {
            high--;
        }
        v[low]=v[high];//移到左边
        while(v[low]<pivot&&low<high)//从low开始寻找比基准大的数；如果low=high说明已经全部排序结束，不需要再排序
        {
            low++;
        }
        v[high]=v[low];//移到右边
    }
    v[low]=pivot;//全部分完，此时low=high，将基准放到空位
    return low;//返回基准位置
}

非递归：(2条消息) 排序 - 快速排序（非递归实现）C++_快速排序的非递归实现c++_biaogexf的博客-CSDN博客

算法性能分析：

快速排序可以转化称为二叉树，二叉树的层数就是递归调用的层数

==空间复杂度：==

==由O（递归层数）&n个结点的二叉树最小高度=log~2~n向下取整+1，最大高度n，得：==

==最好：O（log~2~n）==

==最坏：O（n）==

==时间复杂度：==

==由O（n*递归层数）&n个结点的二叉树最小高度=log~2~n向下取整+1，最大高度n，得：==

==最好：O（nlog~2~n）每一次划分左右元素数量都很平均，递归深度最小，算法效率最高==

==最坏：O（n^2^）原本是正序或逆序的==

==平均：O（nlog~2~n）==

==稳定性：不稳定==

快速排序算法优化思路

1.选头，中，尾三个位置的元素，取他们中中间的值作为基准

2.随机选一个元素作为基准

选择排序¶

简单选择排序¶

以递增为例：遍历找到序列中最小值，与第一个元素互换；再从未排元素中选出最小的放到已排元素后，一直重复，直到未排的只有最后一个，此时已经全部排完，算法结束

链表顺序表都适用

在这里插入图片描述

代码：

void SelectionSort(vector<int> v)//以递增为例
{
    for(int i=0;i<v.size()-1;i++)
    {
        int min=i;
        for(int j=i+1;j<=v.size()-1;j++)
        {
            if(min>v[j])
            {
                min=j;
            }
        }
        if(min!=i)
        {
          int temp=v[i];v[i]=v[min];v[min]=temp;   
        }
    }
}

算法性能分析：

==空间复杂度：O（1）==

==时间复杂度：O（n^2^）==

==稳定性：不稳定==

堆排序¶

什么是堆？

完全二叉树按照顺序存储的方式去存储，并且这棵树根节点的值一定>=（或<=）左，右结点的值

分为大根堆（>=）和小根堆（<=）

基于大根堆堆排序得到递增，基于小根堆堆排序得到递减

建立大根堆

从最小的分支结点开始，依次检查是否是大根堆，若不是，则将左右孩子最大的与其互换，并检查元素下沉后是否依旧符合大根堆的要求；若是，则无需改变；直至整棵树变成大根堆

基于大根堆进行排序：

将大根堆的第一个元素与最后一个元素互换，并将最后一个位置的结点排除不操作（已经排好序），对剩下的元素重新调整为大根堆，再将第一个元素和倒数第二个元素互换，如此循环直至排序结束

代码：

void HeapSort(vector<int> v)//堆排序主代码
{
    BuildMaxHeap(v);//建立大根堆
    for(int i=v.size()-1,i>0;i--)//从最后一个开始作为已经排好序的位置
    {
        swap(v[1],v[i]);//将最大的交换到最后的位置
        HeadAdjust(v,0,i-1);//重新调整成为大根堆，注意将后面已经排好序的部分剔除不要参加重新排序
    }
}

void BuildMaxHeap(vector<int> v)//建立大根堆
{
    for(int i=v.size()/2;i>0;i--)//依次从下往上检查分支结点
    {
        HeadAdjust(v,i,v.size());//对分支结点逐个调整为大根堆
    }
}

void HeadAdjust(vector<int> v,int n,int len)
{
    int temp=v[n];//存放需要调整为大根堆的树的根节点
    for(int j=2*n;j<=len;j*=2)//可能存在小的元素下沉后下面原来调整为大根堆的子树不再是大根堆，因此要向下逐层检查调整
    {
        if(v[j]<v[j+1]&&j<len)//标记左右孩子较大的那个
        {
            j++;
        }
        if(temp<v[j])
        {
            v[n]=v[j];//将下沉的结点值记录
            n=j;//修改下沉后节点的位置
        }
    }
    v[n]=temp;//将下沉的位置赋下沉的值
}

算法性能分析：

==空间复杂度：O（1）==

==时间复杂度：==

==建堆：O（n）==

==排序：O（nlogn）==

==总时间复杂度：O（nlogn）==

==稳定性：不稳定==

堆的插入

将要插入的元素放在最末尾，然后不断的与父结点比较进行上升，直到无法上升为止

堆的删除

将删除的空位用最后一个元素替代，然后对这个元素进行下沉，直至无法下沉

归并排序¶

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

从两个有序序列第一个元素开始比较，将较小的元素放到排好序的数组中，并指针后移比较下一个，直至全部比较完

k路归并：k个有序序列合并为一个有序序列

算法步骤：

1.设置两个指针low和high，指向第一个和最后一个元素，并通过mid=（low+high）/2从中间分开

2.对左半部分递归进行归并排序，即重复1

3.对右半部分递归进行排序，即重复1

4.将左右两个子序列合并为一个

代码：

void MergeSort(vector<int> v,int low,int high)//以递增为例
{
    if(low<high)
    {
       int mid=(low+high)/2; 
        MergeSort(v,low,mid);//递归的归并左半部分
        MergeSort(v,mid+1,high);//递归的归并右半部分
        Merge(v,low,mid,high);//对划分好的两个序列进行二路归并排序
    }
}

vector<int> v1;//辅助数组

void Merge(vector<int> v,int low,int mid,int high)
{
    v1=v;
    for(int i=low,int j=mid+1,int k=low;i<=mid&&j<=high;k++)//比较左右子序列
    {
        if(v1[i]<=v1[j])//当两数相等时取前面一个，保证稳定性
        {
            v[k]=v1[i];
            i++;
        }
        else
        {
            v[k]=v1[j];
            j++;
        }
        k++
    }
    //对剩余的还没有归并部分直接加入到已排序序列的末端
    while(i<=mid)
    {
        v[k]=v1[i];
        i++;k++;
    }
    while(j<=high)
    {
        v[k]=v1[j];
        j++;k++;
    }
}

算法性能分析：

==空间复杂度：O（n），来源于辅助数组==

==时间复杂度：O（nlog~2~n）==

==稳定性：稳定==

基数排序¶

将一个数字拆分成个/十/百位，从个位开始（最低位关键字）排入对应数字的队列，在从大到小出队，反复执行直到三位都如此执行过后，排序结束

官方定义：

假设长度为n的线性表中每个结点a~j~的关键字由d元组组成，其中每个元组中的数都属于[0,r-1]，r成为基数

基数排序通常基于链式结构存储

在这里插入图片描述

算法性能分析：

==空间复杂度：O（r）==

==时间复杂度：O（d（n+r））其中r代表辅助队列数量，d代表需要几趟排序==

==稳定性：稳定==

基数排序擅长解决的问题：

1.数据元素的关键字可以方便的拆分为d组，且d较小

2.每个关键字取值范围不大，即r较小

3.数据元素n较大

应用的例子：万名学生按照生日年月日给他们年龄排序

外部排序（以递增为例）¶

外存内存的数据交换

操作系统以块为单位管理磁盘存储空间，数据从磁盘读入内存中开辟的缓冲区后才能修改，修改完还需要写回磁盘

外部排序原理

使用归并排序的方法，至少需要内存中三块和磁盘块大小一致的缓冲区进行排序

第一步：构造初始归并段

由于归并排序要求各子序列有序，因此首先两块两块的读入内容进行内部排序得到一个有序的归并段

第二步：进行归并排序

对两个归并段进行归并排序：

1.首先取出两个归并段的第一个块磁盘块

2.分别从头比较大小，输出最小值放入输出缓冲区

3.若输出缓冲区满了以后读回磁盘

注意：从输出缓冲区读回磁盘时是开辟了新的空间存储，原有的空间将归还给磁盘

4.若输入缓冲区的内容都被输出了以后就将对应归并段的下一块磁盘块的内容读入

5.循环直至排序结束

第三步：多趟归并

将上一次归并的结果视作新的归并段，重复第二步归并排序的操作，直至排序结束

时间开销：

外部排序时间开销=读写外存的时间+内部排序（构造初始归并段）所需时间+内部归并所需时间

读写外存时间长，占大部分时间，因此可以减少读写趟数优化算法

优化：多路归并

即增加输入缓冲区的数量，从而增加一次归并读入的归并段数量，整体思路和之前一样（两个输入缓冲区——二路归并；四个输入缓冲区——四路归并）

==采用多路归并可以减少归并趟数，从而减少磁盘读写次数==

对r个初始归并段做k路归并，则归并树可以用k叉树表示，若树高为h，则归并趟数h-1=log~k~r向上取整

所以k越大，r越小，归并趟数越少，磁盘读写次数越少

推导：k叉树第h层最多有k^(h-1)^个结点，则r<=k^(h-1)^,（h-1）最小=log~r~k向上取整

多路归并的负面影响：

1.k路归并需要开辟k+1个缓冲区，内存开销大

2.k路归并需要对比关键字k-1次，内部归并时间增加（可以用败者树减少关键字对比次数）

因此k也不能无限大

优化：减少归并段数量(r)

内存中处理初始归并段的输入缓冲区就越大，归并段长度就越长，归并段数量越少

N个记录（数据元素），内存工作区可以容纳N个记录，则初始归并段数量r=N/L（可以用置换选择排序进一步减少初始归并段数量）

k路平衡归并

1.最多只能由k个段归并为一个

2.每趟归并中，若有m个归并段参与归并，则经过这一趟处理得到M/k向上取整

四路平衡归并

四路归并

败者树¶

败者树的构造

可视为一颗完全二叉树，在完全二叉树的根节点上再加一个节点，k个叶子结点分别是参与比较的元素，非叶子结点存放“失败者”，让“胜者”往上进行比较，一直到最上面的根节点

败者树的使用

基于已经构建好的败者树，选出新的胜者就不需要全部重新比一次，可以减少比较次数

败者树在多路归并的应用

1.用每一个归并段作为败者树的叶子结点

2.进行两两比较将失败者所在的归并段索引记录在节点中

3.重复2直到比较出结果，并将结果所在的归并段的索引记录在最上面的结点

4.从结果所在的归并段中取出下一个需要进行比较的值

5.从新的值所在子树开始比较，直至新的结果出现，将结果所在的归并段的索引记录在最上面的结点

6.重复4直到全部比较完

构建完败者树后，选出最小元素只需要进行log~2~k向上取整次比较，远小于原来的k-1次比较（推导：二叉树第k层最多2^(k-1)^个结点）

败者树的程序实现思路

int ls[k]//k路归并的败者树，0号结点记录“胜者”，其他结点记录“败者”

置换—选择排序¶

原办法构造初始归并段的局限性

用于内部排序的内存工作区能够容纳L个记录（数据元素），则每个初始归并段也只能包含L个记录；若文件总归有n个记录，则初始归并段数量r=n/L

使用置换—选择排序，可以让每个初始归并段的长度超越内存工作区的大小限制

置换选择排序

1.从磁盘中读入记录到内存工作区填满

2.取出最小的记录输出，并记录下他的值存放到名为MINMAX的变量中，最后输入下一个记录

3.重复第二步，若要输出的记录小于MINMAX的值，则暂时不输出，将下一个大于MINMAX的内存工作区的最小值输出，直至内存工作区的所有值都小于MINMAX

4.将之前输出的所有记录作为一个归并段，并重新执行2，3步，直至所有记录都被输出，得到全部初始归并段

最佳归并树¶

由于置换—选择排序所产生的归并段长度不同，对于一趟k路归并需要读写磁盘的次数，可以抽象为将每个归并段需要磁盘读入/写入次数（即一个归并段的磁盘块数量）作为权值的k叉树的带权路径长度（WPL）的两倍

因此存在一棵最佳归并树使得带权路径长度最小，即磁盘读写次数最少（如二路归并的最佳归并树是二叉哈夫曼树）

注意：k路归并的最佳归并树一定是严格的k叉树，即只有度为k和度为0的结点

构造k路归并的最佳归并树

1.判断初始归并段数量能否构成严格的k叉归并树，判断依据：（初始归并段数量-1）%（k-1）=u是否等于0，若等于0转3，否则转2

2.在初始归并段的基础上补充（k-1）-u个长度为0的虚归并段

3.将所有归并段（包括虚归并段）作为叶子结点构造k叉哈夫曼树，得到最佳归并树

最小磁盘读写速度=最佳归并树的WPL*2