利用数据结构写C语言路线规划

要编写一个C语言路线规划程序，可以使用图结构来表示地图和道路网络。

1. 定义节点结构

首先，我们需要定义一个节点结构体，来表示地图上的一个位置。该结构体需要包含以下信息：

- 节点编号
- 节点名称
- 节点坐标

例如：

typedef struct node {
    int id;
    char name[100];
    double x, y;
} node_t;

2. 定义边结构

接下来，我们需要定义一个边结构体，用来表示两个节点之间的道路。该结构体需要包含以下信息：

- 边的编号
- 起点节点
- 终点节点
- 边的长度

例如：

typedef struct edge {
    int id;
    node_t *from, *to;
    double length;
} edge_t;

3. 构建地图

现在，我们可以使用这些结构体来构建地图。我们可以使用邻接表来表示地图的道路网络。邻接表是由一个数组和若干个链表组成的数据结构，数组中的每个元素表示一个节点，链表中的每个元素表示该节点所连接的边。

例如：

#define MAX_NODES 1000
typedef struct graph {
    node_t nodes[MAX_NODES];
    edge_t *edges[MAX_NODES];
    int num_nodes, num_edges;
} graph_t;

4. 添加节点和边

要向地图中添加节点和边，我们可以编写下面的函数：

void add_node(graph_t *g, int id, char *name, double x, double y) {
    node_t *node = &g->nodes[g->num_nodes++];
    node->id = id;
    strcpy(node->name, name);
    node->x = x;
    node->y = y;
}

void add_edge(graph_t *g, int id, int from_id, int to_id, double length) {
    edge_t *edge = malloc(sizeof(edge_t));
    edge->id = id;
    edge->from = &g->nodes[from_id];
    edge->to = &g->nodes[to_id];
    edge->length = length;
    g->edges[from_id] = edge;
    g->num_edges++;
}

5. 查找最短路径

最后，我们可以使用 Dijkstra 算法来查找两个节点之间的最短路径。该算法从起点节点开始，每次找到距离起点最近的节点，并更新它的邻居节点的距离。重复这个过程直到到达终点节点。

例如：

void dijkstra(graph_t *g, int start_id, int end_id) {
    double dist[MAX_NODES];
    int visited[MAX_NODES] = {0};
    int prev[MAX_NODES] = {-1};
    int i, j;

    for (i = 0; i < g->num_nodes; i++) {
        dist[i] = INFINITY;
    }
    dist[start_id] = 0;

    for (i = 0; i < g->num_nodes; i++) {
        int u = -1;
        double min_dist = INFINITY;
        for (j = 0; j < g->num_nodes; j++) {
            if (!visited[j] && dist[j] < min_dist) {
                u = j;
                min_dist = dist[j];
            }
        }
        if (u == -1) {
            break;
        }
        visited[u] = 1;

        for (j = 0; j < g->num_nodes; j++) {
            if (g->edges[u][j] != NULL) {
                int v = g->edges[u][j]->to->id;
                double alt = dist[u] + g->edges[u][j]->length;
                if (alt < dist[v]) {
                    dist[v] = alt;
                    prev[v] = u;
                }
            }
        }
    }

    if (prev[end_id] != -1) {
        printf("Shortest path from %s to %s: ", g->nodes[start_id].name, g->nodes[end_id].name);
        int path[MAX_NODES], path_len = 0;
        for (i = end_id; i != -1; i = prev[i]) {
            path[path_len++] = i;
        }
        for (i = path_len - 1; i >= 0; i--) {
            printf("%s -> ", g->nodes[path[i]].name);
        }
        printf("\n");
    } else {
        printf("No path found from %s to %s\n", g->nodes[start_id].name, g->nodes[end_id].name);
    }
}

这就是一个简单的 C 语言路线规划程序的实现。您可以根据需要进行修改和扩展。