数据结构图应用实验报告：C语言实现图的基本操作

本次实验是关于数据结构图的应用，主要目的是通过编写C语言程序，实现图的基本操作，包括创建图，添加/删除节点，添加/删除边，遍历图等。通过本次实验，我们能够更深入地了解图的数据结构和算法。

一、实验环境

本次实验使用的是Visual Studio 2019开发环境，操作系统为Windows 10。

二、实验过程

1. 创建图

图是由若干个节点和若干条边组成的数据结构，我们可以通过动态申请内存，建立一个邻接矩阵来表示图。邻接矩阵是一个二维数组，其中每个元素表示一条边的权重，如果两个节点之间没有边相连，则该元素为0。

在本次实验中，我们定义了一个结构体来表示图的节点，包括节点的名称和节点的编号。同时，定义了一个邻接矩阵，用来表示图的边。代码如下：

#define MAX_VERTEX_NUM 100 //图的最大节点数
typedef struct {
    int data; //节点编号
    char name[20]; //节点名称
}VertexType; //节点结构体
typedef struct {
    int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵
    int vexnum, arcnum; //节点数和边数
    VertexType vexs[MAX_VERTEX_NUM]; //节点数组
}MGraph; //图的结构体

2. 添加/删除节点

图的节点是图的基本组成部分，我们可以通过调用函数，添加/删除图的节点。当添加一个节点时，我们需要先判断图是否已满，如果未满，则将节点加入节点数组中，并将节点数加1。当删除一个节点时，我们需要将该节点从节点数组中删除，并将与该节点相关的边从邻接矩阵中删除。代码如下：

//添加节点
void add_vertex(MGraph* G, int v, char name[]) {
    if (G->vexnum == MAX_VERTEX_NUM) {
        printf('图已满，无法添加节点！\n');
        return;
    }
    G->vexs[G->vexnum].data = v;
    strcpy_s(G->vexs[G->vexnum].name, name);
    G->vexnum++;
}
//删除节点
void delete_vertex(MGraph* G, int v) {
    int i, j;
    for (i = 0; i < G->vexnum; i++) {
        if (G->vexs[i].data == v) {
            for (j = i; j < G->vexnum - 1; j++) {
                G->vexs[j] = G->vexs[j + 1];
            }
            G->vexnum--;
            for (j = 0; j < G->vexnum; j++) {
                G->edges[i][j] = G->edges[i + 1][j];
                G->edges[j][i] = G->edges[j][i + 1];
            }
            G->arcnum--;
            break;
        }
    }
}

3. 添加/删除边

图的边用邻接矩阵表示，当添加一条边时，我们需要指定边的起点和终点，以及边的权重。当删除一条边时，我们只需要将邻接矩阵中对应的元素赋值为0即可。代码如下：

//添加边
void add_edge(MGraph* G, int v1, int v2, int weight) {
    G->edges[v1][v2] = weight;
    G->edges[v2][v1] = weight;
    G->arcnum++;
}
//删除边
void delete_edge(MGraph* G, int v1, int v2) {
    G->edges[v1][v2] = 0;
    G->edges[v2][v1] = 0;
    G->arcnum--;
}

4. 遍历图

图的遍历是指从图的某个节点开始，按照一定的规则访问图中所有节点的过程。在本次实验中，我们实现了深度优先遍历和广度优先遍历两种遍历方式。深度优先遍历是通过递归实现的，广度优先遍历则需要借助队列来实现。代码如下：

//深度优先遍历
void DFS(MGraph* G, int v, int visited[]) {
    int i;
    visited[v] = 1;
    printf('%d:%s ', G->vexs[v].data, G->vexs[v].name);
    for (i = 0; i < G->vexnum; i++) {
        if (G->edges[v][i] != 0 && visited[i] == 0) {
            DFS(G, i, visited);
        }
    }
}
//广度优先遍历
void BFS(MGraph* G, int v, int visited[]) {
    int i, j, w;
    int queue[MAX_VERTEX_NUM];
    int front = 0, rear = 0;
    printf('%d:%s ', G->vexs[v].data, G->vexs[v].name);
    visited[v] = 1;
    queue[rear++] = v;
    while (front != rear) {
        w = queue[front++];
        for (i = 0; i < G->vexnum; i++) {
            if (G->edges[w][i] != 0 && visited[i] == 0) {
                visited[i] = 1;
                printf('%d:%s ', G->vexs[i].data, G->vexs[i].name);
                queue[rear++] = i;
            }
        }
    }
}

三、实验结果

我们通过编写C语言程序，实现了图的基本操作，包括创建图，添加/删除节点，添加/删除边，遍历图等。程序运行结果如下图所示：

四、实验总结

通过本次实验，我们更深入地了解了图的数据结构和算法。图是一种非常重要的数据结构，在计算机科学、网络通信、社交网络分析等领域都有广泛的应用。掌握图的基本操作和遍历算法，对我们深入学习和研究相关领域的算法和应用具有重要的意义。