【趣学C语言和数据结构100例】

问题描述

81.BFS算法求解单源最短路径问题(权值相同也适用)

82.已知一个有向图使用邻接矩阵存储，写出一个算法求图中入度为0的点的个数。

(扩展)已知一个有向图使用邻接矩阵存储，写出一个算法求图中出度为0的点的个数。

83.设计一个算法，统计一个采用邻接表存储的具有n个顶点的无向无权图所有顶点的度

84.折半查找

85.二叉排序树的查找

代码分析

==81.BFS最短路径==
分析：传入图的结构体，u: 表示起始顶点（源点），d[]: 一个整数数组，用于存储从源点 u 到每个顶点的最短距离。visited[]: 一个布尔数组，用于标记每个顶点是否已被访问。先遍历所有的点标计最短距离为-1，每个顶点为已被访问0.创建队列，初始化队列，u 入队，使用广度优先搜索，循环持续进行，直到队列为空。每次循环从队列中取出一个顶点 u，然后遍历其所有未访问的邻接顶点 w。对于每个未访问的邻接顶点 w，将其距离设置为 d[u] + 1（因为边权为1），将其加入队列，并标记为已访问。

==82.有向图邻接矩阵,入度为0的点,出度为0的点==

//邻接矩阵的数据结构
typedef struct {
   
    int edge[Max_num][Max_num]; // 邻接矩阵
    int vexnum; // 图的顶点数
    int edgenum; // 图的边数
} AMGraph;

分析：在邻接矩阵 行为出度，列为入度，传入图G，故函数名为void 函数名(AMGraph G).使用for循环遍历，条件为<图的点。对于每个顶点 i，使用 tag 变量标记其入度是否为 0。初始值为 0，表示入度为 0。内层循环遍历所有其他顶点 j (从 0 到 G.vexnum - 1)，检查 G.edge[j][i] 是否不为 0。G.edge[j][i] 表示从顶点 j 到顶点 i 是否存在边。如果存在边 (不为 0)，则将 tag 设置为 1，表示入度不为 0，并跳出内层循环。如果内层循环结束后 tag 仍然为 0，则表示顶点 i 的入度为 0，count 计数器加 1。函数返回 count，即入度为 0 的顶点数。

==83.有向图邻接表所有顶点的度==
分析：这段代码的核心思想是遍历每个顶点的邻接表，统计邻接表中节点的数量，即该顶点的度。node_degree(ALGraph G) 函数接受一个邻接表表示的图 G 作为输入。外层循环 for(int i=0; i < G.vexnum; i++) 遍历图中的每个顶点。G.vexnum 表示图中顶点的数量。内层循环 while (p ) 遍历当前顶点 i 的邻接表。p 指向邻接表中的弧节点，p->nextarc 指向下一个弧节点。count 变量累加邻接表中节点的数量，最终表示该顶点的度。printf 函数打印每个顶点的度。

==84.折半查找==
分析：传入数组，数组的大小，要查找的k,定义左low右high，如果lowk，就使low=mid+1。到结束如果为找到，返回-1.

==85.二叉排序树的查找==

//二叉树的数据结构
typedef struct Bstnode {
   
    int data;
    int Bstnode *lchild, *rchild;
} Bstnode, *Bstree;

分析：传入树和要找到的值，故函数名为Bstnode* func(Bstree T,int key)，如果树此时的值不为要找的，那么使用while循环一直，如果key<值，则使T为左子树，否则去右字树。最后返回找到的T 。

代码实现

#include<stdio.h>
int mian(){
   
//    81.BFS算法求解单源最短路径问题(权值相同也适用)
void BFS_min(Groph G,int u,int d[],bool visited[]){
   
    for(int i=0;i<G.vex.num;i++){
   
        d[i]=-1;
        visited[i]=false;
    }
    d[u]=0;
    visited[u]=true;
    Queue Q;    //创建 队列
    InitQueue(&Q);    // 初始化队列
    EnQueue(Q,u);    //u入对 
    while(!IsEmpty(Q)){
   
        DeQueue(Q,u);
        for(int w=FirstNeighbor(Q,u);w>=0;w--){
   
            w=NextNeighbor(Q,u,w);
            if(visited[w]==false){
   
                d[w]=d[u]+1;
                EnQueue(Q,w);
                visited[w]=true;
            }
        }
    }
}

//    82.已知一个有向图使用邻接矩阵存储，写出一个算法求图中入度为0的点的个数。
//    邻接矩阵 行为出度，列为入度 
typedef struct {
   
    int edge[Max_num][Max_num]; // 邻接矩阵
    int vexnum; // 图的顶点数
    int edgenum; // 图的边数
} AMGraph;
int sum_zero(AMGraph G){
   
    int count=0,tag;
    for(int i=0;i<G.vexnum;i++){
   
        tag=0;
        for(int j=0;j<G.vexnum;j++){
   
            if(G.edge[j][i]!=0){
   
                tag=1;
                break;
            }
        }
        if(tag==0){
   
            count++;
        }
    }
    return count;
}    
//(扩展)已知一个有向图使用邻接矩阵存储，写出一个算法求图中出度为0的点的个数。
int sum_zero(AMGraph G){
   
    int count=0,tag;
    for(int i=0;i<G.vexnum;i++){
   
        tag=0;
        for(int j=0;j<G.vexnum;j++){
   
            if(G.edge[i][j]!=0){
   
                tag=1;
                break;
            }
        }
        if(tag==0){
   
            count++;
        }
    }
    return count;
}

//    83.设计一个算法，统计一个采用邻接表存储的具有n个顶点的无向无权图所有顶点的度    
void node_degree(ALGraph G){
   
    ArcNode *p;
    for(int i=0;i<G.vexnum;i++){
   
        int count=0;
        p=G.vertices[v].firstarc;
        while(p){
   
            count++;
            p=p->nextarc;
        }
        printf("结点%d的度为%d",i,count);
    }
}

//    84.折半查找
int func(int l[],int n,int k){
   
    int low=0,high=n-1,mid;
    while(low<high){
   
        min=(low+high)/2;
        if(l[mid]==k){
   
            return min;
        }
        else if(l[mid]<k){
   
            high=mid-1;
        }else{
   
            low=mid+1;
        }
    }
    return -1;
}

//    85.二叉排序树的查找
typedef struct Bstnode {
   
    int data;
    int Bstnode *lchild, *rchild;
} Bstnode, *Bstree;
Bstnode* func(Bstree T,int key){
   
    while(T && T->dada!=key){
   
        if(key<T->dada){
   
            T=T->lchild;
        }else{
   
            T=T->rchild;
        }    
    }
    return T;
}


}

    return 0;
}

总结

本文探讨了五个经典的算法问题及其C语言实现，涵盖了图论和树结构的基本概念和操作。这些问题包括使用BFS算法求解单源最短路径问题、统计有向图中入度和出度为0的点的个数、统计无向无权图中所有顶点的度、折半查找和二叉排序树的查找。这些算法不仅在理论上具有重要意义，而且在实际应用中也非常广泛。

BFS算法求解单源最短路径问题是图论中的一个基础问题，通过广度优先搜索，我们可以找到从源点到其他所有顶点的最短路径。这种方法适用于权值相同的情况，通过队列实现，能够保证找到的路径是最短的。

统计有向图中入度和出度为0的点的个数的问题，涉及到对邻接矩阵的遍历和判断。这两个问题分别对应于图中没有入边和出边的顶点，对于图的分析和处理具有重要意义。

统计无向无权图中所有顶点的度的问题，通过遍历邻接表来实现。每个顶点的度即其邻接表中节点的数量，这个统计对于理解图的结构和特性非常有帮助。

折半查找是一种高效的查找算法，它通过二分数组来减少查找时间，适用于有序数组中的查找操作。折半查找的时间复杂度为O(log n)，远高于顺序查找的O(n)。

二叉排序树的查找是树结构操作的一个基础问题。二叉排序树（BST）是一种特殊的二叉树，其中每个节点的值都大于其左子树中的任何值，且小于其右子树中的任何值。这种特性使得BST在查找、插入和删除操作上都非常高效。

这些算法的实现不仅展示了C语言在数据处理和结构操作方面的能力，也体现了算法设计的基本思想，如广度优先搜索、二分查找和树结构操作。通过这些算法的学习，我们可以更好地理解数据结构和算法的基本概念，提高解决实际问题的能力。

总的来说，这些算法问题不仅锻炼了编程能力，也加深了对算法和数据结构的理解。通过这些问题的解决，我们可以逐步提高自己的编程技能，为将来的学习和工作做好准备。这些算法的掌握对于计算机专业的学生和软件开发人员来说都是非常重要的。