C/C++代码详细解释

Question

#includestdio.h
int main
string.h

Answer 1

两个程序都要吗？
第一个代码：

#include<stdio.h>
#include<stdlib.h>
typedef struct E { //定义顶点信息
    int weight;   //权重
    int vt2; //顶点编号
    struct E* next; //该顶点连接的下一个顶点（终点）
}*edge;
int main(int argc, char const* argv[])
{
    int v, e, dele;
    int v1, v2, w;
    edge temp;
    scanf("%d %d", &v, &e);  //输入顶点个数 和边的个数
    edge* map = (edge*)malloc(v * sizeof(edge));  //申请内存空间，保存所有顶点的信息（动态结构体数组）
    for (int i = 0; i < v; i++) { //初始化所有顶点信息
        //map[i] = (edge)malloc(sizeof(struct E));  //这一句不需要了，上面的mpa已经申请了足够的内存
        map[i]->vt2 = i;  //设置顶点编号
        map[i]->weight = 0; //初始化顶点权重
        map[i]->next = NULL; //初始化该顶点的下一个顶点，这里是通过链表的方式保存以i顶点为顶点的所有边
    }
    for (int j = 0; j < e; j++) {  //输入所有边的信息
        scanf("%d %d %d", &v1, &v2, &w); //输入起点、终点、权重
        edge medge = (edge)malloc(sizeof(struct E));  //申请内存空间，保存每条边的信息
        medge->vt2 = v2; medge->weight = w; medge->next = NULL; //用输入信息设置边的属性
        edge ptr = map[v1];  //找到以v1为起点的顶点，将medge插入

        //插入排序，根据终点的大小，将这条边插入以v1为起点的边的链表中
        while (ptr->next && ptr->next->vt2 < v2) { //这里就是遍历链表，找到medge节点插入的位置（根据终点编号从小到大排序）
            ptr = ptr->next;
        }
        temp = ptr->next; ptr->next = medge; medge->next = temp; //将medge节点插入链表
    } //将边按大小顺序插入到邻接表中
    scanf("%d", &dele); //读取需要删除的边的个数
    for (int k = 0; k < dele; k++) { //读取所有需要删除的边
        scanf("%d %d", &v1, &v2); //读取需要删除的边的起点和终点
        edge ptr = map[v1]; //找到以v1为起点的所有边的链表
        //下面的代码块是找到以v2为终点的边，将其从链表中删除
        while (ptr->next && ptr->next->vt2 != v2) ptr = ptr->next;  //这里就是遍历链表，找到以v2为终点的节点
        temp = ptr->next; ptr->next = ptr->next->next; free(temp); //将找到的节点从链表中删除
    }
    edge ptr;
    for (int m = 0; m < v; m++) {  //遍历所有顶点
        if (map[m]->next) printf("%d:", m); //如果m顶点有边，输出顶点编号
        ptr = map[m]->next; //得到以m为起点的所有边的链表
        while (ptr) { //遍历链表
            printf("(%d,%d,%d)", m, ptr->vt2, ptr->weight); //输出起点、终点和权重
            ptr = ptr->next; //链表节点后移，以便实现对链表的遍历
        }
        if (map[m]->next && m != v - 1)printf("\n"); //如果不是最后一个顶点，且存在以该顶点为起点的边，输出换行符
    }
    return 0;
}

第二段代码：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//建立表头结点表 
vector<int> adjacency[20000]; //声明数组，数组的每个元素都是vector<int>容器，用于存储以i为起点的所有的边（i是数组的下标索引，与顶点编号一致）
int book[20000] ={0}; //这里是存储深度，这里最好初始化为0，否则再部分编译器中会出错
void dfs(int cur) {
    cout << cur << " ";  //输出顶点编号
    book[cur] = 1; //深度设置为1
    //遍历链表中的结点 
    int length = adjacency[cur].size(); //得到以cur为起点的边的个数
    for (int i = 0; i < length; i++) { //遍历这些边
        if (book[adjacency[cur][i]] == 0) {  //如果该边的终点的深度为0（也就是没有计算深度），则输出该终点的深度
            dfs(adjacency[cur][i]); //输出该节点的深度
        }
    }
}
int main() {
    int vertex, edge, vertex1, vertex2;
    cin >> vertex >> edge;  //输入顶点和边的个数
    //输入边 
    for (int i = 0; i < edge; i++) {  //输入所有边的信息
        cin >> vertex1 >> vertex2; //输入起点、终点
        adjacency[vertex1].push_back(vertex2); //adjacency[vertex1]是以vertex1为起点的vector容器，把vertex2插入该容器，也就是把这条边放入以vertex1为起点的边的容器中
    }
    //给邻接表的每个链表的结点排序 
    for (int i = 0; i < vertex; i++) { //对所有的顶点的容器进行排序，每个顶点的容器单独排序（也就是对以i为起点的所有的边进行排序）
        sort(adjacency[i].begin(), adjacency[i].end());//对以i为起点的所有的边进行排序
    }
    //遍历每个结点 
    for (int i = 0; i < vertex; i++) { //遍历所有节点
        if (book[i] == 0) { //如果该节点还没有进行检查深度，则进行深度检查
            dfs(i); //调用dfs进行深度检查
        }
    }
    return 0;
}