[数据结构与算法]23王道数据结构栈、队列、树、图、查找章节相关算法题总结(伪代码)

3.判断所给的操作序列是否合法，假设操作序列已经存入一维数组中

算法思想：遍历数组，统计进栈和出栈操作的次数，若不等则序列非法

非法的情况：

①空栈时执行出栈操作，即出栈操作次数大于进栈操作次数，在执行过程中查看

②最后栈不为空，即进栈操作次数大于出栈操作次数，执行操作结束后查看

bool Judge(char arr[]{

    int count1 = 0,count2 = 0;

    for(int i = 0;i !='\0';i++){

        if(arr[i] == 'I'){
            count1++;
        }else{
            count2++;
        }

        if(count2 > count1){
            printf("序列非法");
            return false;
        }
    }

    if(count1 != count2){
            printf("序列非法");
            return false;
    }

     printf("序列合法");
     return true;
}

4.判断表头指针为L的字符单链表是否对称

算法思想：定义一个字符数组，当作栈使用，先进后出，让链表的前一半的字符进栈，后出栈与链表后一半的字符一一做比较，若全相等，则是对称字符链表

bool Judge_Char_Link(LinkList L,int n){//假设L带头节点，n为链表长度
    
    //初始化栈
    char arr[n/2];
    int top = -1;

    LinkList cur = L->next;

    //将链表前半部分元素入栈(n为奇数时，不包括中间节点)
    for(int i = 0;i < n/2;i++){

        arr[++top] = cur->val;
        cur = cur->next;

    }

    if(n%2 != 0){//n为奇数时，让指针指向中间节点的下一个节点
        cur = cur->next;
    }

    //从栈顶至栈底与链表后半部分元素进行一一比较
    while(top > -1 && cur->val == arr[top]){
        top--;
        cur = cur->next;
    }    

    if(top != -1){
        return false;
    }else{
        return true;
    }
}

5.共享栈的进栈、出栈操作算法

算法思想：定义一个变量记录要操作的栈号，1表示栈指针初值为-1的栈，2表示栈指针初值为MaxSize的栈，入栈判满，出栈判空

typedef struct{
    ElemType val[MaxSize];
    int top[2];
}SqStack;//共享栈结构

//入栈操作
bool Push(SqStack S,int i,ElemType x){
    
    if(i < 1 || i > 2){
        print("栈号非法");
        return false'
    }

    if(S.top[0] + 1 == S.top[1]){//栈满
        return false;
    }

    switch(i){

        case 1:
            S.val[++S.top[0]] = x;
            return true;
            break;

        case 2:
            S.val[--S.top[1]] = x;
            return true;
            break;
    }

}

//出栈操作
bool Pop(SqStack S,int i,ElemType &x){

   if(i < 1 || i > 2){
        print("栈号非法");
        return false'
    }

    switch(i){

        case 1:
            if(S.top[0] == -1){//1号栈空
                return false;
            }else{
                x = S.val[S.top[0]--];
                return true;
            }

        case 2:

            if(S.top[1] == MaxSize){//2号栈空
                return false;
            }else{
                x = S.val[S.top[1]++];
                return true;
            }
 }

1.带标志域循环队列的入队和出队操作算法

算法思想：用标记域区分rear==front时栈空或栈满

typedef struct{
    ElemType queue[Maxsize];
    int front,rear;
    int tag;//初始时rear == front此时tag = 0，表示队空，插入导致rear==front此时tag=1，表示队满
}SqQueue;

bool EnQueue(SqQueue Q,ElemType x){

    if(rear == front && tag == 1){//队满
        return false;
    }    
    
    Q.rear = (Q.rear + 1)%Maxsize;
    Q.queue[Q.rear] = x;
   
    Q.tag = 1;//可能队满
    return true;
}

bool DeQueue(SqQueue Q,ElemType &x){
    
    if(Q.front == Q.rear && Q.tag == 0){
        print("队空");
        return false;
    }
    
    Q.front = (Q.front + 1)%Maxsize;
    x = Q.queue[Q.front];
    
    Q.tag = 0;//可能队空
    return true;
}

2.借助于空栈S，将队列Q中的元素进行逆置

算法思想：将队中元素出队入栈，在出栈入队

void Revese_Queue(SqStack &S,SqQueue Q){

    while(QueueEmpty(Q) != true){
        DeQueue(Q,x);
        Push(S,x);
    }

    while(StackEmpty(S) != true){
        Pop(S,x);
        EnQueue(Q,x);     
    }
}

3.用两个栈S1、S2模拟队列入队，出队以及判断队列是否为空

算法思想：两个栈规格相同

①入队操作:入队判满，如果S1满且S2栈不为空，则队满，否则若S1栈未满，入S1栈，若S1满，S2栈为空，将S1栈中元素出栈压入S2栈，再将其压入S1栈。

②出队操作：出队判空，若S1,S2栈均为空，则队空，否则若S2栈不为空，则出栈元素，若S2栈为空且S1栈不为空，将S1栈元素出栈压入S2栈中，再将其出栈。

//判断队空
bool QueueEmpty(SqStack S1,SqStack S2){
    if(StackEmpty(S1) && StackEmpty(S2)){
        return true;
    }else{
        return false;
    }
}

//入队操作
bool EnQueue(SqStack S1,SqStack S2,ElemType x){
    
    if(StackOverflow(S1)){//StackOverflow是判断栈满函数

        if(StackEmpty(S2) != true){
            return false;
        }else{
            while(StackEmpty(S1) != true){
                Pop(S1,cur);
                Push(S2,cur);
            }
            Push(S1,x);
            return true;
        }
        
    }else{
        Push(S1,x);
        return true;
    }  
}


//出队操作
bool DeQueue(Stack &S1,Stack &S2,EmleType &x){

    if(QueueEmpty(S1,S2)){
        return false;
    }else if(StackEmpty(S2) != true){
        Pop(S2,x);
        return true;
    }else{
        while(StackEmpty(S1) != true){
            Pop(S1,cur);
            Push(S2,cur);
        }
        Pop(S2,x);
        return true;
    }
}

4.求以孩子兄弟存储结构的森林(树)的叶子结点数

算法思想：原树中的叶子结点就是孩子兄弟存储结构中左孩子结点为空的结点,注意树没有严格的左右孩子节点之分，孩子节点从左到右

typedef struct CSNode{
   struct BiTNode *lchild,*rsibling;
   ElemType val;
}CSNode,*CSTree;

int leafNodeNumber_dfs(CSTree root){

    if(!root){
        return 0;
    }else if(root->lchild){//若当前节点有左孩子
        return leafNodeNumber_dfs(root->lchild) + leafNodeNumber_dfs(root->rsibling);
    }else{//无左孩子节点，叶子节点加1
        return 1+leafNodeNumber_dfs(root->rsibling);
    }   
}

5.树以孩子兄弟为存储结构，设计递归算法求树的深度

算法思想：原树高就是在孩子兄弟存储结构中左子树高度+1和右兄弟子树高度两者的最大者

int postOrder(CSTree root){

    if(!root){
        return 0;
    }
    
    int lchildHight = postOrder(root->lchild);
    int rsiblingHight = postOrder(root->rsibling);

    return lchildHight + 1 > rsiblingHight ? lchildHight + 1 : rsiblingHight;
}

6.已知一棵树的层次序列和每一个结点的度，构造此树的孩子-兄弟链表

算法思想：按照层次序列遍历各个顶点，若当前顶点的度大于1，表示该顶点有多个孩子，让当前顶点的左孩子指针指向第一个孩子节点，并从左至右依次链接孩子节点。

void CreateCsTree_Degree(CsTree &T,DateType e[],int degree[],int n){

    CsTree pointer = (CsTree)malloc(sizeof(CsNode)*MaxSize);
    
    int i,j,d,k = 0;
    for(i= 0;i < n;i++){//初始化
        pointer[i] = e[i];
        pointer[i]->lchild = pointer[i]->rsibling = NULL;
    }

    for(int i = 0;i < n;i++){//按照层次序列遍历各个节点

        d = degree[i];//获取当前节点的度即孩子个数

        if(d){//如果该节点有孩子节点

            k++;//孩子节点序号
            
            pointer[i]->lchild = pointer[k];//当前节点的左指针指向其左孩子节点
        
            for(int j = 1;j < d;j++){//若左孩子有兄弟节点,让孩子节点的右指针逐个指向右兄弟

                k++;
                pointer[k-1]->rsibling = poninter[k];

            }
        }
    }
}

4.将图的邻接表表示转化为邻接矩阵表示的算法

算法思想:从上到下扫描顶点表的边表结点，若顶点i有边表结点j，则邻接矩阵arcs[i][j] = 1;

void convert(ALGraph G,int arcs[MaxVertexNum][MaxVertexNum]){//邻接矩阵已初始化

    for(int i = 0;i < G.vexnum;i++){

        ArcNode* cur = G.vertices[i].first;

        while(cur){
            arcs[i][cur->adjvex] = 1;
            cur = cur->next;
        }
    }
}

6.当无向图G中度为奇数的顶点个数为不大于2的偶数时则该图存在EL路径，判断图是否存在EL路径,图用邻接矩阵存储

算法思想：遍历邻接矩阵中各顶点的度，统计度为奇数的顶点个数

bool isExistEL(MGraph G){
    
    int oddDegreeNum = 0;
    
    for(int i = 0;i < G.vexnum;i++){

        int degree = 0;
        
        for(int j = 0;i < G.vernum;j++){

            if(G.Edge[i][j] == 1){
                degree++;
            }
        }

        if(degree % 2 != 0){
            oddDegreeNum++;
        }      
    }

    if(oddDegreeNum == 0 || oddDegreeNum == 2){
        return true;
    }else{
        return false;
    }
}

2.判断无向图G是否为一颗树

算法思想：无向图G若为一棵树即为n个顶点，边数为n-1的连通图，遍历该图，若一次能够访问所有顶点则表示连通，且边数为顶点数减一表示该图为树

int vNum,aNum;//记录无向图的边数和顶点数

bool isTree(ALGraph G){

    for(int i = 0;i < G.vexNum;i++){//初始化顶点访问标记数组
        visited[i] = false;
    }

    DFS(G,1);//从顶点1开始遍历图

    if(G.vexNum == vNum && arcNum == 2*(vNum-1))){//判断是否连通且是否为树(边数为顶点数减一)
        return true;
    }else{
        return false;
    }

    
}

void DFS(ALGraph G,int v){
    
    //访问并标记该顶点
    visit(v);
    visited[v] = true; 
    
    vNum++;//统计顶点数

    struct ArcNode* cur = G.vertices[v].first;

    while(cur){

        aNum++;//统计边数

        if(!visited[cur->adjvex]){
            DFS(G,cur->adjvex);
        }
        
        cur = cur->next; 
    } 
}

3.图的深度优先遍历DFS算法的非递归算法(图采用邻接表存储结构)

算法思想：借助于栈，将当前出栈节点的各邻节点依次入栈并标记已入栈，待出栈时，再访问节点

void DFS_Non_RC(ALGraph G,int v){

    SqStack S;
    InitStack(S);//初始化栈

    for(int i = 0;i < G.vexnum;i++){//初始化进栈标记数组
        visited[i] = false;
    }

    Push(S,v);
    visited[v] = true;//标记顶点v是否进栈
        
    while(StackEmpty(S) != true){//从各顶点边表的右至左进行深度优先遍历

        Pop(S,v);
        visit(v);//访问顶点v
        struct ArcNode* cur = G.vertices[v].first;

        while(cur){
        
            if(!visited[cur->adjvex]){
                Push(S,cur->adjvex);    
                visited[cur->adjvex] = true;      
            }
            cur = cur->next;
        }     
    }
}

4.分别用基于DFS和BFS算法判断以邻接表为存储结构的有向图中是否存在由顶点vi到vj的路径(i!=j)

算法思想：从顶点vi出发可以遍历到顶点vj就表示顶点vi到vj有路径

bool isRoadDFS(ALGraph G,int i,int j){

    if(i == j){
        return true;
    }
  
    visited[i] = true;

    struct ArcNode* cur = G.vertices[i].first;
    
    while(cur){

        if(!visited[cur->adjvex]){
            isRoadDFS(G,cur->adjvex,j);
        }

        cur = cur->next;
    } 

    return false;
}

bool isRoadBFS(ALGraph G,int i,int j){

    SqQueue Q;
    InitQueue(Q);

    visit(i);
    EnQueue(Q,i);
    visited[i] = true;//访问进队并标记

    while(QueueEmpty(Q) != true){
        
        DeQueue(Q,i);
        if(i == j){//出队并检查该顶点是否为目标顶点
            return true;
        }
    
        struct ArcNode* cur = G.vertices[i].first;

        while(cur){//将当前顶点的邻接点访问进队并标记

            if(!visited[cur->adjvex]){
                visit(cur->adjvex);
                EnQueue(Q,cur->adjvex);
                visited[cur->adjvex] = true;
            }
            cur = cur->next;
        }   
    }

    return false;
}

5.输出顶点vi到vj的所有简单路径(图用邻接表存储)

算法思想：由于设置了访问标记数组，故vi到vj的路径必是简单路径

void FindPath(ALGraph G,int v1,int v2,int path[],int d){
    //v1和v2是顶点vi和vj的数组下标，path数组存储vi到vj的路径，d是path数组的下标，初值为0

    path[d++] = v1;
    visited[v1] = true;

    if(v1 == v2){//输出v1到v2的简单路径
        for(int i = 0;i < d;i++){
            printf("%d,"path[i]);
        }
        visited[v2] = 0;//设置目标结点为未访问状态，以便下条路径访问
        return;//由于是找简单路径，v2必不可能在路径之中们只能是路径的终点。所以返回上一层
    }
    struct ArcNode* p = G.vertices[v1].first;//指向邻接边表结点

    while(p){
        int w = p->adjvex;
        if(!visited[w]){
            FindPath(G,w,v2,path,d);
        }
        p = p->next;
    }

    visited[v1] = 0;//恢复顶点的初始状态
}

6.有向无环图的拓扑排序(DFS算法实现)

算法思想：最后的拓扑排序就是递归结束时间从大到小排序所形成的顶点序列

//假设图用邻接表存储
bool visited[MaxVertexNum];//访问标记数组
bool finishedTime[MaxVertexNum];//该数组存储每个顶点完成递归所需的时间，假设完成一层递归时间为1
int time = 0;//记录每个顶点递归完成的时间

void DFSTreaveral(ALGraph G){
    for(int i = 0;i<G.vexNum;i++){
        visited[i] = false;
    }

    for(int i = 0;i < G.vexNum;i++){//从顶点0开始访问
        if(!visited[i]){
            DFS(G,i);
        }
        
    }
}

void DFS(ALGraph G,int v){

    visit(v);
    visited[v] = true;

    struct ArcNode* p = G.vertices[v].first;
    while(p){
        int w = p->adjvex;
        if(!visited[w]){
            DFS(G,w);
        }
        p = p->next;
    }

    time++;
    finishedTime[v] = time;
}

//逆拓扑排序(DFS实现):将访问顶点的操作放在递归函数结束的前一步
void DFSTreaveral(ALGraph G){
    for(int i = 0;i<G.vexNum;i++){
        visited[i] = false;
    }

    for(int i = 0;i < G.vexNum;i++){//从顶点0开始访问
        if(!visited[i]){
            DFS(G,i);
        }
        
    }
}

void DFS(ALGraph G,int v){
   
    visited[v] = true;

    struct ArcNode* p = G.vertices[v].first;
    while(p){
        int w = p->adjvex;
        if(!visited[w]){
            DFS(G,w);
        }
        p = p->next;
    }

   visit(v);
}

5.写出折半查找的递归算法,初始调用时，low为1，high为ST.length

typedef struct{
    ElemType Val[MaxSize]; //0号留空，从1开始存储元素
    int length;
}STable;//待查找有序顺序表的数据结构

int BinSearch(STable ST,ElemType key,int low,int high){

    if(low > high){
        return 0;//递归终止条件
    }

    int mid = (low+high)/2;
    if(ST.Val[mid] > key){
        BinSearch(ST,key,low,mid-1);//前半部分进行二分查找
    }else if(ST.Val[mid] < key){
        BinSearch(ST,key,mid+1,high);//后半部分进行二分查找
    }else{
        return mid;
    }
}

6.使得经常被检索的结点位于表的前端的顺序检索(从前到后一个一个找)策略算法(将被检索的结点与前驱结点进行交换。

①顺序结构实现 :从前到后找，找到指定结点与前面的结点交换位置
int SqSearch(STable arr,ElemType key){
    int temp;
    int i = 0;
    while(arr.Val[i]!=key && i < arr.length);

    if(i < arr.length && i > 0){
        temp = arr.Val[i];
        arr.Val[i] = arr.Val[i-1];
        arr.Val[i-1] = temp;
        return i-1;
    }else{
        return -1;
    }
}

②链式结构实现
LinkList ListSearch(LinkList L,ElemType key){

    if(!L){
        return NULL;
    }

    LinkList curr = L->next,pre = L;
    while(curr && curr->val != key){
        curr = curr->next;
        pre = curr;
    }

    if(pre != L && curr){
        ElemType temp = curr->val;
        curr->val = pre->val;
        pre->val = temp;
    }else{
        return NULL;
    }
}