数据结构算法总结-自用

数据结构算法整理

By 舜桀BB

循环双链表的存储结构

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

//初始化空的循环双链表
bool InitDLinkList(DLinklist &L){
    L = (DNode *) malloc(sizeof(DNode));     //分配一个头结点
    if(L==NULL)     //内存不足，分配失败
        return false;
    L->prior = L;    //头结点的prior指向头结点
    L->next = L;     //头结点的next指向头结点
    return false;
}

//判断循环双链表是否为空
bool Empty(DLinklist L){
    if(L->next==L)
        return true;
    else
        return false;
}

//判断结点p是否为循环单链表的表尾结点
bool isTail(DLinklist L, DNode *p){
    if(p->next==L)
        return true;
    else
        return false;
}

//在p结点之后插入s结点
void InsertNextDNode(DNode *p, DNode *s){
    s->next=p->next;  //s的下一个结点为当前p的下一个结点，即把s插到p后面
    p->next->prior=s; //将第三个结点的头接到s
    s->prior=p;       //将s的头接到p
    p->next=s;        //将p的尾接到s
}

//在带头结点的双向循环链表L中第i个位置之前插入元素e
//i的合法值为1=<i=<表长+1
bool InsertBeforeI(DLinklist &L, int i,Elemtype e){
    if(!(p=GetElem(L,i))) //GetElem(L,i):获取表中第i个位置的元素的值
        return false;//插入位置不合法
    if(!(s=(DLinklist)malloc(sizeof(DNode))))
        return false;//内存空间不足，无法创建新结点
    s->data=e;
    s->prior=p->prior;
    p->prior->next=s;
    s->next=p;
    p->prior=s;
    return true;
}

//删除p的后继节点q
void deleteNextDNode(DNode *p, DNode *q){
    p->next=q->next;  //将p的尾接到q的下一个结点
    q->next->prior=p; //将q的下一个结点的头接到p
    free(q);
}

//删除带头结点的双向循环链表L中第i个元素
//i的合法值为1=<i=<表长
bool DeleteElemI(DLinklist &L, int i){
    if(!(p=GetElem(L,i)))
        return false;
    p->prior->next=p->next;
    p->next->prior=p->prior;
    free(p);
    return true;
}

栈、队列和数组

栈

队列

//队列是一种操作受限的线性表，只允许在表的一端插入，在表的另一端删除（先进先出）
//队列常见基本操作
//InitQueue(&Q):初始化队列，构造一个空队列Q
//QueueEmpty(Q):判队列空，若队列为空则返回true，否则返回false
//EnQueue(&Q,x):入队，若队列Q未满，将x加入，使其成为新的队尾
//DeQueue(&Q,&x):出队，若队列Q非空，删除队头元素，并用x返回
//GetHead(Q,&x):读队头元素，若队列Q非空，则将队头元素赋值给x

//队列的顺序存储
//分配一块连续的存储单元存放队列中的元素，并附设两个指针：队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置
//循环队列：把存储队列元素的表从逻辑上视为一个环
//当队首指针Q.front=MaxSize-1后，再前进一个位置就自动到0，通过除数取余运算%实现
//初始时：Q.front=Q.rear=0
//队首指针进1：Q.front=(Q.front+1)%MaxSize
//队尾指针进1：Q.rear=(Q.rear+1)%MaxSize
//队列长度：(Q.rear+MaxSize-Q.front)%MaxSize
//出队入队时：指针都按顺时针方向进1
//判断队空队满：牺牲一个单元来区分队空队满，入队时少用一个队列单元
//队头指针在队尾指针的下一位置为队满的标志
//队满条件：(Q.rear+1)%MaxSize==Q.front
//队空条件：Q.front==Q.rear
//队列中元素的个数：(Q.rear+MaxSize-Q.front)%MaxSize

//循环队列的操作
#define MaxSize 50      //定义队列中元素的最大个数
typedef struct{
    ElemType data[MaxSize];   //存放队列元素
    int front,rear;           //队头指针和队尾指针
}SqQueue;
//初始化
void InitQueue(SqQueue &Q){
    Q.rear=Q.front=0;       //初始化队首队尾指/
}
//判队空
bool isEmpty(SqQueue Q){
    if(Q.rear=Q.front) return true;  //队空条件
    else return false;
}
//入队
bool EnQueue(SqQueue &Q,ElemType x){
    if((Q.rear+1)%MaxSize==Q.front) return false;  //队满则报错
    Q.data[Q.rear]=x;
    Q.rear=(Q.rear+1)%MaxSize;     //队尾指针加一取模
    return true;
}
//出队
bool DeQueue(SqQueue &Q,ElemType &x){
    if(Q.rear==Q.front) return false;   //队空则报错
    x=Q.data[Q.front];
    Q.front=(Q.front+1)%MaxSize;   //队头指针加一取模
    return true;
}

数组

树与二叉树

树

//树中的结点数=所有结点的度数之和+1=分支数+1
//n个结点的树中由n-1条边
//度为m的树中第i层至多有m^(i-1)个结点
//高度为h的m叉树至多有(m^h-1)/(m-1)个结点
//具有n个结点的m叉树的最小高度为⌈logm(n(m-1)+1)⌉ 

特殊的二叉树

//满二叉树
//高度为h，含有2^h-1个结点的二叉树

//完全二叉树
//高度为h、有n个结点的二叉树，且每个结点都与高度为h的满二叉树中编号为1-n的结点一一对应。
//对于完全二叉树，若i<=⌊n/2⌋,则结点i为分支结点，否则为叶节点
//若有度为1的结点，则只有可能有一个，且该结点有左孩子无右孩子
//若n为奇数，则每个分支结点都有左右孩子，
//若n为偶数，则编号最大的分支结点（编号为n/2）只有左孩子，无右孩子，其余分支结点左右孩子都有

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

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

二叉树的性质

//二叉树
//非空二叉树上的叶结点数等于度为2的结点数加1，即n0=n2+1
//非空二叉树上第k层上至多2^(k-1)个结点
//高度为h的二叉树至多有2^h-1个结点

//完全二叉树
//具有n个结点的完全二叉树的高度h为⌈log2(n+1)⌉或⌊log2n⌋+1
//对于完全二叉树，可以由结点数推出度为0、1和2的结点个数n0、n1、n2（突破口：完全二叉树最多只有会有一个度为1的结点；n0=n2+1，所以n0+n2为奇数，若结点数为偶数，则n1=1；若结点数为奇数，则n1=0）

//二叉树的链式存储结构
// |lchid|data|rchild|
typedef struct BiNode{
    ElemType data;                    //数据域
    struct BiNode *lchild,*rchild;    //左右孩子指针
}BiTNode,*BiTree;
//在含有n个结点的二叉链表中，含有n+1个空链域

二叉树的遍历

//二叉树的遍历是指按某条搜索路径访问树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次

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

//三种遍历算法中，遍历递归左右子树的顺序都是固定的，只是访问根结点的顺序不同。
//不管采用哪种遍历算法，每个结点都访问一次且仅访问一次，所以时间复杂度为O(n)
//在递归遍历中，递归工作栈的栈深恰好为树的深度，所以在最坏情况下，二叉树是由n个结点且深度为n的单支树，遍历算法的空间复杂度为O(n)

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

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

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

//中序遍历非递归算法
//1.沿着根的左孩子，依次入栈，直到左孩子为空，说明已找到可以输出的结点
//2.栈顶元素出栈并访问：若其右孩子为空，继续执行2，若其右孩子不为空，将右子树执行1
void InOrder2(BiTree T){
    InitStack(S);           //初始化栈S
    BiTree p = T;           //p是遍历指针
    while(p||!IsEmpty(S)){  //栈不为空或p不空时循环
        if(p){              //一路向左
            Push(S,p);      //当前结点入栈
            p=p->lchild;    //左孩子不空，一直向左走
        }
        else{               //出栈，并转向出栈结点的右子树
            Pop(S,p);       //栈顶元素出栈
            visit(p);       //访问出栈结点
            p=p->rchild;    //向右子树走，p赋值为当前结点的右孩子
        }
    }
}

//先序遍历非递归算法
//1.访问该结点，沿着根的左孩子，依次入栈，直到左孩子为空，说明已找到可以输出的结点
//2.栈顶元素出栈：若其右孩子为空，继续执行2，若其右孩子不为空，将右子树执行1
void PreOrder2(BiTree T){
    InitStack(S);           //初始化栈S
    BiTree p = T;           //p是遍历指针
    while(p||!IsEmpty(S)){  //栈不为空或p不空时循环
        if(p){              //一路向左
            visit(p);       //访问结点
            Push(S,p);      //当前结点入栈
            p=p->lchild;    //左孩子不空，一直向左走
        }
        else{               //出栈，并转向出栈结点的右子树
            Pop(S,p);       //栈顶元素出栈
            p=p->rchild;    //向右子树走，p赋值为当前结点的右孩子
        }
    }
}

//二叉树的层次遍历算法
//进行层次遍历需要借助一个队列。
//首先将二叉树根结点入队，然后出队，访问出队结点
//若它有左子树，则将左子树根结点入队；若它有右子树，则将右子树根结点入队。
//完成入队后出队，访问出队结点
//如此反复，直到队列为空
void LevelOrder(BiTree T){
    InitQueue(Q);                  //初始化辅助队列
    BiTree p;                      
    EnQueue(Q,T);                  //将根结点入队
    while(!isEmpty(Q)){            //队列不为空则循环
        DeQueue(Q,p);              //队头结点出队
        visit(p);                  //访问队头结点
        if(p->lchild!=NULL)
            EnQueue(Q,p->lchild);  //左子树不为空，则左子树根结点入队
        if(p->rchild!=NULL)
            EnQueue(Q,p->rchild);  //右子树不为空，则右子树根结点入队
    }
}

//由遍历构造二叉树
//先序+中序 后序+中序 层序+中序

二叉树常见应用

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


//求二叉树带权路径长度
//二叉树带权路径长度为每个叶结点的深度与权值之积的总和，可以使用先序遍历或者层次遍历解决问题
//先序遍历思想：
//用一个static变量记录wpl，把每个结点的深度作为递归函数的一个参数传递
//若该结点为叶结点，则变量wpl加上该结点的深度与权值之和
//若该结点为非叶结点，则左子树不为空，对左子树调用递归算法，右子树不为空，对右子树调用递归算法，深度参数均为本结点的深度参数加1
//最后返回计算出的wpl即可

//二叉树结点的数据结构定义如下
typedef struct BiTNode{
    int weight;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

int WPL(BiTree root){
    return wpl_PreOrder(root,0);
}

int wpl_PreOrder(BiTree root,int deep){
    static int wpl=0;      //定义变量存储wpl
    if(root->lchild==NULL&&root->rchild==NULL)    //若为叶结点，则累积wpl
        return wpl+=deep*root->weight;
    if(root->lchild!=NULL)                        //若左子树不为空，则对左子树递归遍历
        wpl_PreOrder(root->lchild,deep+1);
    if(root->rchild!=NULL)                        //若右子树不为空，则对右子树递归遍历
        wpl_PreOrder(root->rchild,deep+1);
    return wpl;
}

//判定给定二叉树是否为完全二叉树
//根据完全二叉树定义，具有n个结点的完全二叉树与满二叉树中编号从1-n的结点一一对应
//算法思想：采用层次遍历算法，将所有结点加入队列（包括空结点）。遇到空结点时，查看其后是否有非空结点。若有，则二叉树不是完全二叉树。
bool IsComplete(BiTree T){
    InitQueue(Q);
    if(!T)
        return 1;      //空树为满二叉树
    EnQueue(Q,T);
    while(!IsEmpty(Q)){
        DeQueue(Q,p);
        if(p){                       //p不为空结点
            EnQueue(Q,p->lchild);    //将结点左子树加入队列（可能是空结点）
            EnQueue(Q,p->rchild);    //将结点右子树加入队列（可能是空结点）
        }
        else                         //结点为空结点
            while(!IsEmpty(Q)){      //遇到空结点，就将队列中的元素全部输出，看是否有非空结点
                DeQueue(Q,p);
                if(p)                //有非空结点，说明不是完全二叉树
                    return 0;
            }
    }
    return 1;
}

//采用递归算法实现交换二叉树左右子树
//首先交换b结点的左孩子的左右子树，然后交换b结点的右孩子的左右子树，最后交换b结点的左右子树，当结点为空时递归结束（后序遍历的思想）
void swap(BiTree b){
    if(b){
        swap(b->lchild);     //递归交换左子树
        swap(b->rchild);     //递归交换右子树
        temp=b->lchild;      //交换左右孩子结点
        b->lchild=b->rchild;
        b->rchild=temp;
    }
}

//孩子兄弟表示法，求叶子节点个数之和
//当森林以孩子兄弟表示法存储时，若结点没有孩子（fch=NULL），则它必是叶子结点。
//总的叶子结点个数是孩子子树(fch)上的叶子数和兄弟子树(nsib)上的叶结点数之和
typedef struct node{
    ElemType data;    //数据域
    struct node *fch,*nsib;    //孩子与兄弟域 
}*Tree;
int Leaves(Tree t){                 //计算以孩子兄弟表示法存储的森林的叶子数
    if(t==NULL)                     //树空返回0
        return 0; 
    if(t->fch==NULL)                //若结点无孩子，则该结点必是叶子
        return 1+Leaves(t->nsib);   //返回叶结点和其兄弟子树中的叶结点数
    else                            //若结点有孩子，则返回孩子子树和兄弟子树中叶子结点个数
        return Leaves(t->fch)+Leaves(t->nsib);
}

线索二叉树

//传统的二叉链表存储仅能体现一种父子关系，不能直接得到结点在遍历中的前驱或后继
//在含n个结点的二叉树中，有n+1个空指针，可以利用这些空指针存放指向其前驱或者后驱的指针
//引入线索二叉树就是为了加快查找结点前驱和后继的速度

//规定：若无左子树，令lchild指向其前驱结点；若无右子树，令rchild指向其后继结点
//线索二叉树的结点结构：|lchild|ltag|data|rtag|rchild|
//ltag=0,lchild域指示结点的左孩子；ltag=1,lchild域指示结点的前驱
//rtag=0,rchild域指示结点的右孩子；rtag=1,rchild域指示结点的后继

//线索化的实质就是遍历一次二叉树
//pre指向刚刚访问过的结点，p指向正在访问的结点，即pre指向p的前驱
//中序遍历过程中，检查p的左指针是否为空，若为空则将它指向pre；检查pre的右指针是否为空，若为空则将它指向p

//线索二叉树结点
typedef struct ThreadNode{
    ElemType data;                      //数据元素
    struct ThreadNode *lchild,*rchild;  //左、右孩子指针
    int ltag,rtag;                      //左、右线索标志
}ThreadNode,*ThreadTree;

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

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

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

void visit(ThreadNode *q){
    if(q->lchild==NULL){ //左子树为空，建立前驱线索
        q->lchild=pre;
        q->ltag=1;
    }
    if(pre!=NULL&&pre->rchild==NULL){
        pre->rchild=q;   //建立前驱结点的后继线索
        pre->rtag=1;
    }
    pre=q;               //标记当前结点成为刚刚访问过的结点
}


//在线索二叉树中找前驱后继
//若ltag/rtag=0

//中序线索二叉树（左根右）
//后继：p的右子树最左下结点；
//前驱：p的左子树最右下结点

//先序线索二叉树（根左右）
//后继
//1.若p有左孩子，则先序后继为其左孩子
//2.若p没有左孩子，则先序后继为其右孩子
//前驱：
//1.若有父结点，且p为左孩子，则前驱为父结点
//2.若有父结点，且p为右孩子，其左兄弟为空，则前驱为父结点
//3.若有父结点，且p为右孩子，其左兄弟非空，则前驱为其左兄弟子树的最后一个被先序遍历的结点
//4.若p为根结点，则p没有先序前驱

//后序线索二叉树（左右根）
//后继
//1.若p有父结点，且p为右孩子，则其后继为父结点
//2.若p有父结点，且p为左孩子，其右兄弟为空，则其后继为父结点
//3.若p有父结点，且p为左孩子，其右兄弟非空，则其后继为其右兄弟子树中第一个被后序遍历的结点
//4.若p为根结点，则p没有后序后继
//前驱
//1.若p有右孩子，则其前驱为右孩子
//2.若p没有右孩子，则其前驱为左孩子

树的存储结构

//双亲表示法
//顺序存储结点数据，结点中保存父结点在数组中的下标
//利用了每个结点（根结点除外）只有唯一双亲的性质，找父结点很方便，但是求结点的孩子时则需要遍历整个结构

//孩子表示法
//顺序存储结点数据，结点中保存孩子链表头指针（顺序存储+链式存储）
//寻找子女方便，但是寻找双亲需要遍历n个结点中孩子链表指针域所指向的n个孩子链表

//孩子兄弟表示法（二叉树表示法）
//用二叉链表存储树--左孩子右兄弟
//每个结点包括三部分：结点值，指向结点第一个孩子结点的指针，以及指向结点下一个兄弟结点的指针（沿此域可以找到结点的所有兄弟结点）
//方便实现树转换为二叉树，易于查找结点的孩子

树、森林和二叉树的相互转换

//树转换为二叉树
//左孩子右兄弟
//由于根结点没有兄弟，所以对应二叉树没有右子树

//森林转换为二叉树
//先将森林中的每棵树转换为二叉树（左孩子右兄弟），把第二棵树根视为第一棵树的右兄弟

//二叉树转换为森林
//二叉树的根和其右子树为第一棵树的二叉树形式，将根的右链断开，以此类推直到最后只剩一棵没有右子树的二叉树为止，再将每棵二叉树转换为树，即得到森林

树和森林的遍历

树	森林	二叉树
先根遍历	先序遍历	先序遍历
后根遍历	中序遍历	中序遍历

哈夫曼树和哈夫曼编码

//树的带权路径长度(WPL)=树中所有叶子结点的带权路径长度之和
//哈夫曼树（最优二叉树）：在含有给定的n个带权叶结点的二叉树中，WPL最小的二叉树
//构造哈夫曼树：每次选两个根结点权值最小的树合并，并将二者权值之和作为新的根结点的权值
//哈夫曼树不唯一，但WPL必然都是最小值
//每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大
//构建过程中共新建了n-1个结点，哈夫曼树结点总数为2n-1
//哈夫曼树不存在度为1的结点（每次构造都选择两棵树作为新结点的孩子）

//哈夫曼编码
//将每个出现的字符当作一个独立结点，其权值为出现的频数，构造对应的哈夫曼树
//所有的字符结点都会出现在叶结点
//边标记0表示转向左孩子，边标记1表示转向右孩子

图算法

图的存储

邻接矩阵法

//图的邻接矩阵存储结构定义
#define MaxVertexNum 100               //顶点数目的最大值
typedef char VertexType;               //顶点的数据类型
typedef int EdgeType;                  //带权图中边上权值的数据类型
typedef struct{
    VertextType Vex[MaxVertexNum];     //顶点表
    EdgeType Edge[MaxVertexNum][MaxVertexNum];  //邻接矩阵，边表
    int vexnum,arcnum;                 //图的当前顶点数和弧数
}MGraph;
//当邻接矩阵的元素仅表示相应边是否存在时，EdgeType可采用0和1的枚举类型
//无向图的邻接矩阵是对称矩阵，对规模特大的邻接矩阵可采用压缩存储
//邻接矩阵表示法的空间复杂度为O(n^2)，其中n为图的顶点数|V|
//对于无向图，邻接矩阵的第i行（或第i列）的非零元素的个数正好是顶点i的度TD(vi)
//对于有向图，邻接矩阵的第i行的非零元素的个数正好是顶点i的出度OD(vi)，第i列的非零元素个数正好是顶点i的入度ID(vi)
//邻接矩阵存储法容易确定任意两个顶点之间是否有边相连，但是确定多少条边必须按行、按列对各个元素进行检测，所花费时间代价很大
//稠密图适合邻接矩阵的存储表示

邻接表法

//邻接表结合了顺序存储和链式存储方法，减少了空间的浪费
//邻接表是指对每个顶点建立一个单链表，单链表中的结点表示依附于该顶点的边（对于有向图则是以该顶点为尾的弧），这个单链表称为该顶点的边表（对于有向图称为出边表）
//边表的头指针和顶点的数据信息采用顺序存储，称为顶点表
//邻接表中存在两种结点：顶点表结点和边表结点
//顶点表结点由顶点域(data)和指向第一条邻接表的指针(firstarc)构成
//边表结点由邻接点域(adjvex)和指向下一条邻接边的指针域(nextarc)构成
//图的邻接表存储结构定义
#define MaxVertexNum 100               //顶点数目的最大值
typedef struct ArcNode{                //边表结点
    int adjvex;                        //该弧所指向的顶点位置
    struct ArcNode *next;              //指向下一条弧的指针
    //InfoType info;                   //网的边权值
}ArcNode;
typedef struct VNode{                  //顶点表结点
    VertextType data;                  //顶点信息
    ArcNode *first;                    //指向第一条依附于该顶点的弧的指针
}VNode,AdjList[MaxVertexNum];
typedef struct{
    AdjList vertices;                  //邻接表
    int vexnum,arcnum;                 //图的顶点数和弧数
}ALGraph;                              //ALGraph是以邻接表存储的图类型
//对于无向图，邻接表所需存储空间为O(|V|+2|E|)
//对于有向图，邻接表所需存储空间为O(|V|+|E|)
//前者的倍数2是由于在无向图中，每条边在邻接表中出现了两次
//对于稀疏图，采用邻接表将大大节省存储空间
//在邻接表中很容易找到给定一个顶点的所有邻边，因为只需要读取邻接表，而在邻接矩阵中则需要扫描一行，花费的时间为O(n)。
//确定给定两个顶点是否存在边，在邻接矩阵中可以立刻查到，在邻接表中则需要在相应结点对应的边表中查找另一个结点，效率较低
//在有向图的邻接表表示中，求一个给定点的出度只需计算其邻接表中的结点个数；但求入度就要遍历全部的邻接表（可采用逆邻接表的存储方式加速求解入度）
//图的邻接表不唯一

图的基本操作

//Adjacent(G,x,y)          //判断图G是否存在边<x,y>
//Neighbors(G,X)           //列出图G中与结点x邻接的边
//InsertVertex(G.x)        //在图G中插入顶点x
//DeleteVertex(G,x)        //从图G中删除顶点x
//AddEdge(G,x,y)           //若无向边(x,y)或有向边<x,y>不存在，则向图G中添加该边
//RemoveEdge(G,x,y)        //若无向边(x,y)或有向边<x,y>存在，则从图G中删除该边
//FirstNeighbor(G,x)       //求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或者图中不存在x则返回-1
//NextNeighbor(G,x,y)      //假设图G中顶点y是顶点x的一个邻接点，返回除y外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1
//Get_edge_value(G,x,y)    //获取图G中边(x,y)或<x,y>对应的权值
//Set_edge_value(G,x,y,v)  //设置图G中边(x,y)或<x,y>对应的权值为v

广度优先搜索-BFS

bool visited[MAX_VERTEX_NUM];   //访问标记数组
void BFSTraverse(Graph G){      //对图G进行广度优先遍历
    for(i=0;i<G.vexnum;++i)
        visited[i]=FALSE;       //访问标记数组初始化
    InitQueue(Q);               //初始化辅助队列Q
    for(i=0;i<G.vexnum;++1){    //从0号顶点开始遍历
        if(!visited[i]){        //对每个连通分量调用一次BFS
            visit(i);           //访问初始顶点i
            visited[i]=TRUE;    //对i做已访问标记
            Enqueue(Q,i);       //顶点i入队列
            while(!isEmpty(Q)){
                DeQueue(Q,i);   //顶点i出队列
                //检测i所有的邻接点
                for(w=FirstNeighbor(G,i);w>=0;w=NextNeighbor(G,i,w))
                    if(!visited[w]){  //w为i的尚未被访问的邻接顶点
                        visit(w);     //访问顶点w
                        visited[w]=TRUE; //对w做已访问标记
                        EnQueue(Q,w);    //顶点w入队列
                    }
            }
        }
    }
    
}

BFS求解单源最短路径问题

//求顶点u到其他顶点的最短路径
//使用BFS可以求解非带权图的单源最短路径问题，因为广度优先搜索总是按照距离由近到远来遍历图中的每一个顶点
//BFS需要一个辅助队列Q，n个顶点均需入队一次，在最坏情况下，空间复杂度为O(|V|)
//采用邻接表存储方式时，每个顶点均需搜索一次（或入队一次），故时间复杂度为O(|V|)，在搜索任意一个顶点的邻接点时，每条边至少访问一次，故时间复杂度为O(|E|)，算法总的时间复杂度为O(|V|+|E|)
//采用邻接矩阵存储方式时，查找每个顶点的邻接点所需时间为O(|V|)，故算法总的时间复杂度为O(|V|^2)
void BFS_MIN_Distance(Graph G,int u){
    //d[i]表示从u到i结点的最短路径
    for(i=0;i<G.vexnum;++1){
        d[i]=∞;       //初始化路径长度
        path[i]=-1;   //最短路径从哪个顶点d过来
    }
    d[u]=0;
    visited[u]=TRUE;
    EnQueue(Q,u);
    while(!isEmpty(Q)){          //BFS算法主过程
        DeQueue(Q,u);            //队头元素u出队
        for(w=FirstNeighbor(G,u);w>=0;w=NextNeighbor(G,u,w))
            if(!visited[w]){     //w为u尚未访问的邻接顶点
                d[w]=d[u]+1;     //路径长度加1
                path[w]=u;       //最短路径应从u到w
                visited[w]=TRUE; //设已访问标记
                EnQueue(Q,w);    //顶点w入队
            }
    }
}

深度优先搜索-DFS

//DFS算法是一个递归算法，需要借助一个递归工作栈，故其空间复杂度为O(|V|)
//遍历图的过程实质上是对每个顶点查找其邻接点的过程，其耗费时间取决于所用的存储结构
//以邻接矩阵表示时，查找每个顶点的邻接点所需的时间为O(|V|)，故总的时间复杂度为O(|V|^2)
//以邻接表表示时，查找所有顶点的邻接点所需的时间为O(|E|)，访问顶点所需的时间为O(|V|),总的时间复杂度为O(|V|+|E|)
bool visited[MAX_VERTEX_NUM];     //访问标记数组
void DFSTraverse(Graph G){        //对图G进行深度优先遍历
    for(v=0;v<G.vexnum;++v)
        visited[v]=FALSE;         //初始化已访问标记数组
    for(v=0;v<G.vexnum;++v)
        if(!visited[v])
            DFS(G,v);
}
void DFS(Graph G,int v){          //从顶点v出发，深度优先遍历图G
    visit(v);                     //访问顶点v
    visited[v]=TRUE;              //设已访问标记
    for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
        if(!visited[w]){          //w为v的尚未访问的邻接顶点
            DFS(G,w);
        }
}

//图的遍历算法可以用来判断图的连通性。
//对于无向图，调用BFS(G,i)或DFS(G,i)的次数等于该图的连通分量；对于有向图并非如此。

排序算法

插入排序

直接插入排序

//插入排序
//算法思想：每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中，直到全部记录插入完成
//直接插入排序
//空间复杂度：O(1)
//时间复杂度：主要来自于对比关键字、移动元素。若有n个元素，则需要n-1趟处理
//最好时间复杂度（全部有序）：O(n)
//共n-1趟处理，每一趟只需要对比关键字一次，不用移动元素
//最坏时间复杂度（全部逆序）：O(n^2)
//共n-1趟处理，每一趟需要对比关键字i+1次，移动元素i+2次
//平均时间复杂度：O(n^2)
//算法稳定性：稳定
void InsertSort(int A[],int n){
    int i,j,temp;
    for(i=1;i<n;i++)            //将各元素插入已排好序的序列中
        if(A[i]<A[i-1]){        //若A[i]关键字小于前驱
            temp=A[i];          //用temp暂存A[i]
            for(j=i-1;j>=0 && A[j]>temp;--j)    //检查所有前面已排好序的元素
                A[j+1]=A[j];    //所有大于temp的元素都向后挪位
            A[j+1]=temp;        //复制到插入位置
        }
}

折半插入排序

//优化--折半插入排序
//算法思想：先用折半查找找到应该插入的位置，再移动元素
//当low>high时折半查找停止，应将[low,i-1]内的元素全部右移，并将A[0]复制到low所指位置
//当A[mid]==A[0]时，为了保证算法稳定性，应继续在mid所指位置右边寻找插入位置
//比起直接插入排序，比较关键字的次数减少了，但是移动元素的次数没变，整体来看时间复杂度依然是O(n^2)
void InsertSort(int A[],int n){
    int i,j,low,high,mid;
    for(i=2;i<=n;i++){       //依次将A[2]-A[n]插入前面的已排序序列
        A[0]=A[i];           //将A[i]暂存到A[0]
        low=1;               //设置折半查找的范围
        high=i-1;
        while(low<=high){    //折半查找（默认递增有序）
            mid=(low+high)/2;//取中间点
            if(A[mid]>A[0])  //查找左半子表
                high=mid-1;  
            else             //查找右半子表
                low=mid+1;
        }
        for(j=i-1;j>=high;--j)
            A[j+1]=A[j];     //统一后移元素，空出插入位置
        A[high+1]=A[0];      //插入操作
    }
}

希尔排序

//希尔排序
//算法思想：先将待排序表分割成若干形如L[i,i+d,i+2d,...,i+kd]的特殊子表；对每个子表分别进行直接插入排序。缩小增量d，重复上述过程，直到d=1为止。
//空间复杂度：O(1)
//时间复杂度：优于直接插入排序
//稳定性：不稳定
//适用性：仅可用于顺序表
void ShellSort(int A[],int n){
    int d,i,j;
    //A[0]只是暂存单元，当j<=0时，插入位置已到
    for(d=n/2;d>=1;d=d/2)     //步长变化
        for(i=d+1;i<=n;++i)
            if(A[i]<A[i-d]){  //需要将A[i]插入有序增量子表
                A[0]=A[i];    //暂存在A[0]
                for(j=i-d;j>0&&A[0]<A[j];j-=d)
                    A[j+d]=A[j];  //记录后移，查找要插入的位置
                A[j+d]=A[0];      //插入
            }
}

交换排序

冒泡排序

//冒泡排序
//算法思想：从后往前（或从前往后）两两比较相邻元素的值，若为逆序，则交换它们，直到序列比较完，称这样过程为一趟冒泡排序，最多只需n-1趟排序
//每一趟排序都可以使一个元素移动到最终位置，已经确定最终位置的元素在之后的处理中无需再对比
//如果某一趟排序过程中未发生交换，则算法可提前结束
//空间复杂度：O(1)
//时间复杂度：
//最好情况（有序）：O(n)，比较次数=n-1，交换次数=0
//最坏情况（逆序）：O(n^2)，比较次数=(n-1)+(n-2)+...+1=n(n-1)/2=交换次数,
//最坏情况下要移动3n(n-1)/2（每次交换都需要移动元素三次）
//平均时间复杂度=O(n^2)
//稳定性：稳定（只有A[j-1]>A[i]时才交换）
//适用性：顺序表、链表都可以
//在i所指位置之前的元素都已经有序了
void BubbleSort(int A[],int n){
    for(int i=0;i<n-1;i++){
        bool flag=false;          //表示本趟冒泡是否发生交换的标志
        for(int j=n-1;j>i;j--)    //一趟冒泡排序
            if(A[j-1]>A[j]){      //若为逆序
                swap(A[j-1],A[j]);//交换
                flag=true;
            }
        if(flag==false)
            return;               //本趟遍历后没有发生交换，说明表已经有序
    }
}
//交换
void swap(int &a,int &b){
    int temp=a;
    a=b;
    b=temp;
}

快速排序

//快速排序
//算法思想：在待排序表L[1..n]中任取一个元素pivot作为枢轴（或基准，通常取首元素），通过一趟排序将待排序表划分成独立的两部分L[1...k-1]和L[k+1...n],使得L[1...k-1]中的所有元素小于pivot，L[k+1...n]中的所有元素大于等于pivot，则pivot放在了其最终位置L[k]上，这个过程称为一次划分，然后分别递归地对这两个子表重复上述过程，直至每部分内只有一个元素或空为止，即所有元素放在了其最终位置上
//快速排序是所有内部排序算法中平均性能最优的排序算法
//其算法表现主要取决于递归深度，若每次划分越均匀，则递归深度越低；划分越不均匀，递归深度越深
//n个结点的二叉树，最小高度=⌊log2n⌋+1，最大高度=n
//空间复杂度=O(递归层数)：最好（O(log2n)）；最坏（O(n)）
//时间复杂度=O(n*递归层数)
//最好时间复杂度（O(nlog2n)）-每次选的枢轴元素都能将序列划分成均匀地两部分；
//最坏时间复杂度（O(n^2)）-若序列原本就有序或者逆序，则时间、空间复杂度最高
//平均时间复杂度（O(nlog2n)）
//稳定性：不稳定
void QuickSort(int A[],int low,int high){
    if(low<high){
        int pivotpos=Partition(A,low,high);  //划分
        QuickSort(A,low,pivotpos-1);         //划分左子表
        QuickSort(A,pivotpos+1，high);        //划分右子表
    }
}
//用第一个元素将待排序序列划分成左右两个部分
int Partition(int A[],int low,int high){
    int pivot=A[low];       //第一个元素作为枢轴
    while(low<high){        //用low和high搜索枢轴的最终位置
        while(low<high&&A[high]>=pivot) 
            --high;
        A[low]=A[high];     //比枢轴小的元素移动到左端
        while(low<high&&A[low]<=pivot)
            ++low;          //比枢轴大的元素移动到右端
        A[high]=A[low];
    }
    A[low]=pivot;           //枢轴元素存放到最终位置
    return low;             //返回存放枢轴的最终位置
}

选择排序

简单选择排序

//选择排序（简单选择排序、堆排序）
//算法思想：每一趟（如第i趟）在后面n-i+1(i=1,2,..,n-1)个待排序元素中选取关键字最小的元素，作为有序子序列的第i个元素，直到第n-1趟做完，待排序元素就剩下一个，就不需要再选。
//简单选择排序
//算法思想：每趟在待排序元素中选取关键字最小的元素加入有序子序列，第i趟排序即从L[i...n]中选取关键字最小的元素与L(i)交换，每一趟排序可以确定一个元素的最终位置，这样经过n-1趟排序就可以使得整个排序表有序
//必须进行n-1趟处理
//空间复杂度：O(1)
//时间复杂度：O(n^2)
//元素移动次数不会超过3(n-1)次，最好的情况是移动0次（初始有序）
//元素间比较的次数与序列初始状态无关，始终为n(n-1)/2
//稳定性：不稳定
//适用性：顺序表、链表都可以
void SelectSort(EmlemType A[],int n){
    for(int i=0;i<n-1;i++){      //一共进行n-1趟
        int min=i;               //记录最小元素位置
        for(int j=i+1;j<n;j++)   //在A[i..n-1]中选择最小元素
            if(A[j]<A[min])      //更新最小元素位置
                min=j; 
        if(min!=i)              
            swap(A[i],A[min]);   //封装的swap()共移动元素3次
    }
}

堆排序

//堆排序
//堆-顺序存储的完全二叉树
//结点i的左孩子是2i；右孩子是2i+1；父节点是⌊i/2⌋
//编号=<n/2的结点都是分支结点
//大根堆（根>=左、右）小根堆（根<=左、右）
//空间复杂度：O(1)
//时间复杂度：建堆：O(n)+排序：O(nlog2n)=O(nlog2n)
//结论：一个结点，每下坠一层，最多只需对比关键字两次
//若树高为h，某结点在第i层，则将这个结点向下调整最多只需要下坠h-i层，关键字对比次数不超过2(h-i)
//n个结点的完全二叉树树高h=⌊log2n⌋+1
//建堆的过程，关键字对比次数不超过4n，建堆时间复杂度=O(n)
//堆排序总共需要n-1趟，每一趟交换后都需要将根结点下坠调整
//根结点最多下坠h-1层，每下坠一层，最多需要对比关键字2次，所以每一趟排序复杂度不超过O(h)=O(log2n)
//共n-1趟，总的时间复杂度=O(nlog2n)
//稳定性：不稳定
//基于大根堆的堆排序得到递增序列，基于小根堆的堆排序得到递减序列

//首先建堆，建堆的主要思想是从后调整所有的非终端结点，即结点数除以二向下取整，对于每个结点调用HeadAdjust算法，调整恢复堆的性质，通过这样来建立大根堆；然后第一个元素和最后一个元素交换破环堆，然后调整，如此n-1次（最后一个结点无需排序），每次都是先将堆顶元素和堆底元素交换，然后进行调整，交换一次就能获得一个最大（小）值，排好了一次序


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

//堆排序的完整逻辑
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);   //把剩余的待排序元素整理成堆
    }
}

//将以k为根的子树调整成大根堆
void HeadAdjust(int A[],int k,int len){
    A[0]=A[k];                  //A[0]暂存子树的根结点
    for(int i=2*k;i<=len;i*=2){ //沿key较大的子结点向下筛选
        if(i<len&&A[i]<A[i+1])  //左孩子2i小于右孩子2i+1（左右孩子一样大，优先和左孩子交换）
            i++;                //取key较大的子结点的下标
        if(A[0]>=A[i])          //筛选结束
            break; 
        else{       
            A[k]=A[i];          //将A[i]调整到双亲结点上
            k=i;                //修改k值，以便继续向下筛选
        }
    }
    A[k]=A[0];                  //被筛选结点的值放入最终位置
}

归并排序

//归并排序
//归并是将两个或两个以上的有序表合并成一个新的有序表
//2路归并排序：假设待排序表含有n个记录，则可将其视为n个有序的子表，每个子表长度为1，然后两两归并，得到⌈n/2⌉个长度为2或1的有序表；继续两两归并，如此重复直到合并成一个长度为n的有序表为止
//Merge()的功能是将前后相邻的两个有序表归并成一个有序表
//设两段有序表A[low...mid]、A[mid+1...high]存放在同一顺序表中的相邻位置，先将它们复制到辅助数组B中。每次从对应B中的两个段取出一个记录进行关键字的比较，把较小者放入A中。当数组B中有一段的下标超过其对应的表长（即该段的所有元素都已复制到A中）时，将另一段中的剩余部分直接复制到A中。
ElemType *B=(ElemType *)malloc((n+1)*sizeof(ElemType)); //辅助数组B
void Merge(ElemType A[],int low,int mid,int high){
    //表A的两段A[low...mid]和A[mid+1...high]各自有序，把他们合成一个有序表
    int i,j,k;
    for(k=low;k<=high;k++)
        B[k]=A[k];          //将A所有元素复制到B中
    //每次从B的两段取出一个记录进行关键字比较，较小的放入A中
    //限制条件：i、j不超过各自的段；k是A的下标；一轮比较出A的一个元素
    for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){
        if(B[i]<=B[j])      //比较B的左右两段中的元素
            A[k]=B[i++];    //将较小值复制到A中
        else
            A[k]=B[j++];
    }
    //以下两个while循环只会执行一个
    while(j<=mid)           //若第一个表未检测完，复制
        A[k++]=B[i++];
    while(j<=high)          //若第二个表未检测完，复制
        A[k++]=B[j++];
}
//一趟归并排序会调用⌈n/2h⌉次算法merge()，将L[1...n]中前后相邻且长度为h的有序段进行两两归并，得到前后相邻、长度为2h的有序段，整个归并排序需要进行⌈log2n⌉趟
//递归形式的2路归并排序算法基于分治，分为分解和合并两个过程
//分解：将含有n个元素的待排序表分为各含n/2个元素的子表，采用2路归并排序算法对两个子表递归地进行排序
//合并：合并两个已排序的子表得到排序结果
void MergeSort(Elemtype A[],int low,int high){
    if(low<high){
        int mid=(low+high)/2;     //从中间划分成两个子序列
        MergeSort(A,low,mid);     //对左侧子序列进行递归排序
        MergeSort(A,mid+1,high);  //对右侧子序列进行递归排序
        Merge(A,low,mid,high);    //归并
    }
}
//2路归并的归并树在形态上是一棵倒立的二叉树
//二叉树的第h层最多有2^(h-1)个结点
//若树高为h，则应满足n<=2^(h-1)，即h-1=⌈log2n⌉
//结论：n个元素进行2路归并排序，归并趟数等于⌈log2n⌉
//每趟归并时间复杂度为O(n),则算法时间复杂度为O(nlog2n)
//空间复杂度=O(n),来自于辅助数组B
//稳定性：稳定

基数排序

//基数排序
//基数排序不是基于比较的排序算法
//算法思想：将整个关键字拆分成d位，按照各个关键字位权重递增的次序（如：个，十，百），做d趟分配和收集
//若当前处理的关键字位可能取得r个值，则需要建立r个队列
//分配：顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应队列，一趟分配耗时O(n)
//收集：把各个队列中的结点依次出队并链接，一趟收集耗时O(r)
//空间复杂度：O(r)[r个队列]
//时间复杂度：O(d(n+r))[做d趟分配和收集，一趟分配耗时O(n)，一趟收集耗时O(r)，所以时间复杂度为O(d(n+r))]
//稳定性：稳定
//擅长处理：
//1.数据元素关键字可方便拆分为d组，且d较小
//2.每组关键字取值范围不大，即r较小
//3.数据元素个数n较大

排序算法总结

//平均时间复杂度（时间快）：快些归队（快速排序[O(nlog2n)]，希尔排序[O(n^(1/3))]，归并排序[O(nlog2n)]，堆排序[O(nlog2n)]）
//不稳定的算法：快些选一堆好友来聊天（快速排序，希尔排序，选择排序，堆排序）
//折半插入排序是在直接插入排序的基础上建立的，只是通过使用折半查找算法减少了数据对象的比较次数，但移动次数没有发生改变，所以时间复杂度为O(n^2)
//直接插入，直接比元素，找插入位置平均时间复杂度为O(n)
//折半插入，对半比元素，找插入位置平均时间复杂度为O(log2n)
//每次排序都能至少确定一个元素在其最终位置上的排序算法有：快速排序，选择排序，堆排序，冒泡排序（快速选择一堆帽子）
//元素的移动次数与关键字的初始序列无关的是：基数排序（基数排序不是基于比较的排序算法）
//元素的比较次数与关键字的初始序列无关的是：选择排序（简单选择排序，堆排序）、归并排序、折半插入排序
//算法时间复杂度与关键字初始序列无关的是：选择排序（简单选择排序O(n^2)、堆排序O(nlog2n)）、归并排序(2路O(nlog2n))、基数排序O(d(n+r))
//算法的排序趟数与关键字初始序列无关的是：插入排序（直接插入排序，折半插入排序，希尔排序）、选择排序（简单选择排序、堆排序）、归并排序、基数排序
//算法的排序趟数与关键字初始序列有关的是：冒泡排序、快速排序
//简单选择排序比较次数始终为n(n-1)/2，与关键字的初始序列无关，选择或交换次数为n-1趟（交换次数≠移动次数，待排序序列中确定了最小元素，再与第一个元素交换，因为交换次数与趟数一样）
//简单选择排序记录移动次数较少，当待排序列为正序时，移动次数最少，为0次，当为逆序时，移动次数最多，为3(n-1)次
//m路归并，每选出一个元素需要比较关键字m-1次
//快速排序：时间复杂度=O(n*递归层数) 最好：O(nlog2n) 最坏：O(n^2)
//空间复杂度=O(递归层数) 最好：O(log2n) 最坏：O(n)
//若n较小，可以采用直接插入排序或简单选择排序
//当记录本身信息量较大时，用简单选择排序较好（直接插入排序所需的记录移动次数较简单选择排序的多）
//若文件的初始状态已按关键字基本有序，则采用直接插入排序或冒泡排序（若此时采用快速排序，时间复杂度为O(n^2)）
//快速排序被认为是目前基于比较的内部排序方法中最好的方法，待排序的关键字随机分布时，快速排序的平均时间最短
//若n较大，则应该采用时间复杂度为O(nlog2n)的排序算法：快速排序、堆排序、归并排序
//要求排序稳定且时间复杂度为O(nlog2n)，则选用归并排序
//若n很大，记录的关键字位数较少且可以分解时，采用基数排序
//当记录本身信息量较大，为避免耗费大量时间移动记录，可用链表作为存储结构