面试题：C语言中结构体指针在复杂数据结构中的应用

#include <stdio.h>
#include <stdlib.h>

// 定义邻接表节点结构体
typedef struct AdjListNode {
    int dest;
    struct AdjListNode* next;
} AdjListNode;

// 定义邻接表结构体
typedef struct AdjList {
    AdjListNode* head;
} AdjList;

// 定义图结构体
typedef struct Graph {
    int V;
    AdjList* array;
} Graph;

// 创建一个新的邻接表节点
AdjListNode* newAdjListNode(int dest) {
    AdjListNode* newNode = (AdjListNode*)malloc(sizeof(AdjListNode));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

// 创建一个图
Graph* createGraph(int V) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->V = V;

    graph->array = (AdjList*)malloc(V * sizeof(AdjList));

    for (int i = 0; i < V; ++i) {
        graph->array[i].head = NULL;
    }

    return graph;
}

// 添加边到图中
void addEdge(Graph* graph, int src, int dest) {
    AdjListNode* newNode = newAdjListNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;
}

// 深度优先搜索辅助函数
void DFSUtil(Graph* graph, int v, int* visited) {
    visited[v] = 1;
    printf("%d ", v);

    AdjListNode* adjList = graph->array[v].head;
    while (adjList != NULL) {
        int adjVertex = adjList->dest;
        if (!visited[adjVertex]) {
            DFSUtil(graph, adjVertex, visited);
        }
        adjList = adjList->next;
    }
}

// 深度优先搜索
void DFS(Graph* graph, int v) {
    int* visited = (int*)malloc(graph->V * sizeof(int));
    for (int i = 0; i < graph->V; ++i) {
        visited[i] = 0;
    }

    DFSUtil(graph, v, visited);

    free(visited);
}

// 释放图的内存
void freeGraph(Graph* graph) {
    for (int i = 0; i < graph->V; ++i) {
        AdjListNode* node = graph->array[i].head;
        AdjListNode* temp;
        while (node != NULL) {
            temp = node;
            node = node->next;
            free(temp);
        }
    }
    free(graph->array);
    free(graph);
}

你可以这样使用这些函数：

int main() {
    int V = 5;
    Graph* graph = createGraph(V);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 0);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 3);

    printf("深度优先搜索从顶点 2 开始:\n");
    DFS(graph, 2);

    freeGraph(graph);
    return 0;
}

数据结构定义：
- AdjListNode 结构体表示邻接表中的节点，包含目标顶点 dest 和指向下一个邻接节点的指针 next。
- AdjList 结构体表示邻接表，包含一个指向邻接表头部的指针 head。
- Graph 结构体表示图，包含顶点数 V 和一个邻接表数组 array。
函数实现：
- newAdjListNode 函数创建一个新的邻接表节点。
- createGraph 函数创建一个具有指定顶点数的图，并初始化邻接表数组。
- addEdge 函数向图中添加一条有向边。
- DFSUtil 是深度优先搜索的辅助递归函数，用于实际的遍历。
- DFS 函数初始化访问数组并调用 DFSUtil 进行深度优先搜索，最后释放访问数组。
- freeGraph 函数释放图占用的内存，包括邻接表节点和图结构体本身。
内存管理：
- 在 createGraph 函数中为图结构体和邻接表数组分配内存。
- 在 newAdjListNode 函数中为邻接表节点分配内存。
- 在 DFS 函数中为访问数组分配内存，并在使用完毕后释放。
- 在 freeGraph 函数中释放图占用的所有内存，包括邻接表节点和图结构体本身，确保没有内存泄漏。
代码健壮性：
- 在 createGraph 和 newAdjListNode 函数中，分配内存后检查是否成功，虽然这里简单处理，但实际应用中可更详细处理内存分配失败情况。
- 在 DFS 函数中，在使用访问数组前初始化，确保其值合理。
- 在 freeGraph 函数中，妥善释放图占用的所有内存，避免内存泄漏。

星途面试题库

面试题：C语言中结构体指针在复杂数据结构中的应用

知识考点

面试题答案