默写用

//先序遍历非递归
void PreOrder(BiTNode *bt){
    if(bt!=NULL){
    BiTNode *Stack[maxsize];
    int top=-1;
    BiTNode *p;
    Stack[++top]=bt;
    while(top!=-1||p!=NULL){
        p=Stack[top--];
        visit(p);
        if(p->rchild){
            Stack[++top]=p->rchild;
        }
        if(p->lchild)
            Stack[++top]=p->lchild;
    }
   }
}
//中序遍历非递归
void InOrder(BiTNode *bt){
    if(bt!=NULL){
    BiTNode *Stack[maxsize];
    int top=-1;
    BiTNode *p=bt;
    while(top!=-1||p!=NULL){
        if(p){
            Stack[++top]=p;
            p=p->lchild;
        }
        else{
            p=Stack[top--];
            visit(p);
            p=p->rchild;
        }
    }
 }
}
//后序非递归
typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild,*rchild;
    int tag;
}
void PostOrder(BiTNode *bt){
    if(bt!=NULL){
        BiTNode *Stack[maxsize];
        int top=-1;
        BiTNode *p=bt;
        while(top!=-1||p!=NULL){
            if(p){
                Stack[++top]=p;
                p=p->lchild;
            }
            else{
                p=Stack[top--];
                if(p->rchild&&p->tag==0){
                    Stack[++top]=p->rchild;
                    p=p->rchild;
                }
                else{
                    visit(p);
                    p->tag=1;
                    p=NULL;
                }
            }
        }
    }
}

//层序遍历
typedef struct Queue{
    BiTNode *Q[maxsize];
    int front,rear;
}Queue;
void LevelOrder(BiTNode *bt){
    if(bt!=NULL){
        Queue Q;
        InitQueue(Q);
        BiTNode *P;
        EnQueue(Q,bt);
        while(!isEmpty(Q)){
            DeQueue(Q,p);
            visit(p);
            if(p->lchild)
                EnQueue(Q,p->lchild);
            if(p->rchild)
                EnQueue(Q,p->rchild);
        }
    }
}
//手动模拟队列
void LevelOrder(BiTNode *bt){
    if(bt!=NULL){
        BiTNode *Q[maxsize];
        int front=rear=0;
        BiTNode *p;
        rear=(rear+1)%maxsize;
        Q[rear]=bt;
        while(front!=rear){
            front=(front+1)%maxsize;
            p=Q[front];
            visit(p);
            if(p->lchild){
                rear=(rear+1)%maxsize;
                Q[rear]=p->lchild;
            }
            if(p->rchild){
                rear=(rear+1)%maxsize;
                Q[rear]=p->rchild;
            }
        }
    }
}

#define MaxVertexNum 100
//邻接表
typedef struct ArcNode{//边表结点
    int adjvex;//边指向顶点
    struct ArcNode *next;
}ArcNode;
typedef struct VNode{//顶点表结点
    VertexType data;//顶点数据
    ArcNode *first;
}VNode.AdjList[MaxVertexNum];
typedef struct{
    AdjList vertices;//邻接表
    int vexnum,arnnum;//顶点数，边数
}ALGraph;
//邻接矩阵
typedef char VertexType;//顶点数据类型
typedef int EdgeType;//权值类型
typedef struct{
    VertexType Vex[MaxVertexNum];//顶点表
    EdgeType Edge[MaxVertexNum][MaxVertexNum];//邻接矩阵
    int vexnum,arcnum;
}MGraph;
//广度优先遍历
bool visited[max_vertex_num];
void BFSTrave(Graph G){
    for(int i=0;i<G.vexnum;i++){
        visited[i]=false;
    }
    Queue Q;
    InitQueue(Q);
    for(i=0;i<G.vexnum;i++){
        if(!visited[i]){
            BFS(G,i);
        }
    }
}
void BFS(Graph G,int v0){
    visit(v0);
    visited[v0]=true;
    EnQueue(Q,v0);
    while(!isEmpty(Q)){
        DeQueue(Q,v);
        for(int w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
            if(!visited(w)){
                visit(w);
                visited[w]=true;
                EnQueue(Q,w);
            }
        }
    }
}
//深度优先搜索
void DFSTrave(Graph G){
    for(int i=0;i<G.vexnum;i++)
        visited[i]=false;
    for(i=0;i<G.vexnum;i++){
        if(!visited[i])
            DFS(G,i);
    }
}
void DFS(Graph,int v0){
    visit(v0);
    visited[v0]=true;
    for(w=FirstNeighbor(G,v0);w>=0;w=NextNeighbor(G,v0,w)){
        if(!visited[w])
            visit(w);
        DFS(G,w);
    }
}
//借助栈
void DFS(Graph G,int v0){
    Stack S;
    initStack(S);
    for(int i=0;i<G.vexnum;i++)
        visited[i]=false;
    Push(S,v0);
    visited[v0]=true;
    while(!isEmpty(S)){
        int k=Pop(S);
        visit(k);
        for(int w=FirstNeighbor(G,k);w>=0;w=NextNeighbor(G,k,w)){
            if(!visited[w]){
                Push(S,w);
                visited[w]=true;
            }
        }
    }
}

//冒泡排序
void swap(int a,int b){
    int temp=a;
    a=b;
    b=temp;
}
void BubbleSort(int A[],int n){
    for(int i=0;i<n;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;
    }
}
//快排
int Partition(int A[],int low,int high){
    int pivot=A[low];
    while(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;
}
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);
    }
}

#define maxsize 100
//邻接矩阵
typedef struct{
    VertexType Vex[maxsize];//顶点表
    EdgeType Edge[maxsize][maxsize];//邻接矩阵
    int vexnum,arcnum;//顶点数，边数
}MGraph;
//邻接表
typedef struct ArcNode{//边表结点
    int adjvex;//边指向顶点位置
    struct ArcNode *next;//指向下一条边的指针
    InfoType info;//边的权值
}ArcNode;
typedef struct VNode{//顶点表结点
    VertexType data;//顶点信息
    ArcNode *first;//指向第一条依附该顶点的边的指针
}VNode,AdjList[maxsize];
typedef struct{
    AdjList vertices;//邻接表
    int vexnum,arcnum;
}ALGraph;