用C语言写一个程序完成这个文档里的任务
时间: 2024-12-23 11:20:20 浏览: 5
项目一初识C语言推选PPT文档.ppt
根据您提供的文档内容,以下是用C语言编写的程序,实现了文档中的所有功能:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VEX 10
#define MAX_NAME 100
#define MAX_INFO 10000
#define INFINITY 65535
typedef struct {
char name[MAX_NAME];
char info[MAX_INFO];
} VertexType;
typedef struct {
VertexType vexs[MAX_VEX];
int arcs[MAX_VEX][MAX_VEX];
int vexnum, arcnum;
} MGraph;
// 初始化图
void createGraph(MGraph *G, const char *filename) {
FILE *fp = fopen(filename, "r");
if (!fp) {
printf("无法打开文件 %s\n", filename);
exit(1);
}
fscanf(fp, "%d%d", &G->vexnum, &G->arcnum);
for (int i = 0; i < G->vexnum; i++) {
fscanf(fp, "%[^,],%[^\n]", G->vexs[i].name, G->vexs[i].info);
fgets(G->vexs[i].info, MAX_INFO, fp); // 读取剩余的景点信息
}
for (int i = 0; i < G->vexnum; i++) {
for (int j = 0; j < G->vexnum; j++) {
G->arcs[i][j] = (i == j ? 0 : INFINITY);
}
}
for (int k = 0; k < G->arcnum; k++) {
char start[MAX_NAME], end[MAX_NAME];
int weight;
fscanf(fp, "%s %s %d", start, end, &weight);
int s = -1, e = -1;
for (int i = 0; i < G->vexnum; i++) {
if (strcmp(start, G->vexs[i].name) == 0) s = i;
if (strcmp(end, G->vexs[i].name) == 0) e = i;
}
if (s != -1 && e != -1) {
G->arcs[s][e] = G->arcs[e][s] = weight;
}
}
fclose(fp);
}
// 打印图的信息
void printGraph(const MGraph *G) {
printf("顶点数: %d, 边数: %d\n", G->vexnum, G->arcnum);
for (int i = 0; i < G->vexnum; i++) {
printf("%s: %s", G->vexs[i].name, G->vexs[i].info);
}
printf("\n邻接矩阵:\n");
for (int i = 0; i < G->vexnum; i++) {
for (int j = 0; j < G->vexnum; j++) {
printf("%d ", G->arcs[i][j]);
}
printf("\n");
}
}
// 查询景点信息
void queryVertexInfo(const MGraph *G, const char *vertexName) {
for (int i = 0; i < G->vexnum; i++) {
if (strcmp(vertexName, G->vexs[i].name) == 0) {
printf("%s: %s\n", vertexName, G->vexs[i].info);
return;
}
}
printf("未找到景点 %s\n", vertexName);
}
// Dijkstra算法求最短路径
void dijkstra(const MGraph *G, int start, int end, int *dist, int *prev) {
int visited[MAX_VEX] = {0};
dist[start] = 0;
for (int count = 0; count < G->vexnum - 1; count++) {
int minDist = INFINITY;
int u = -1;
for (int v = 0; v < G->vexnum; v++) {
if (!visited[v] && dist[v] <= minDist) {
minDist = dist[v];
u = v;
}
}
visited[u] = 1;
for (int v = 0; v < G->vexnum; v++) {
if (!visited[v] && G->arcs[u][v] && dist[u] + G->arcs[u][v] < dist[v]) {
dist[v] = dist[u] + G->arcs[u][v];
prev[v] = u;
}
}
}
}
// 打印最短路径
void printShortestPath(const MGraph *G, int start, int end) {
int dist[MAX_VEX], prev[MAX_VEX];
for (int i = 0; i < G->vexnum; i++) {
dist[i] = INFINITY;
prev[i] = -1;
}
dijkstra(G, start, end, dist, prev);
if (dist[end] == INFINITY) {
printf("没有从 %s 到 %s 的路径\n", G->vexs[start].name, G->vexs[end].name);
return;
}
printf("从 %s 到 %s 的最短路径为 %d 米\n", G->vexs[start].name, G->vexs[end].name, dist[end]);
int path[MAX_VEX], pathIndex = 0;
int current = end;
while (current != -1) {
path[pathIndex++] = current;
current = prev[current];
}
printf("路径: ");
for (int i = pathIndex - 1; i >= 0; i--) {
printf("%s -> ", G->vexs[path[i]].name);
}
printf("\b\b \n");
}
int main() {
MGraph G;
createGraph(&G, "graph.txt");
int choice;
do {
printf("1. 查询景点信息\n");
printf("2. 查询最短路径\n");
printf("3. 退出\n");
printf("请输入选择: ");
scanf("%d", &choice);
switch (choice) {
case 1: {
char vertexName[MAX_NAME];
printf("请输入景点名称: ");
scanf("%s", vertexName);
queryVertexInfo(&G, vertexName);
break;
}
case 2: {
char startName[MAX_NAME], endName[MAX_NAME];
printf("请输入起始景点名称: ");
scanf("%s", startName);
printf("请输入结束景点名称: ");
scanf("%s", endName);
int start = -1, end = -1;
for (int i = 0; i < G.vexnum; i++) {
if (strcmp(startName, G.vexs[i].name) == 0) start = i;
if (strcmp(endName, G.vexs[i].name) == 0) end = i;
}
if (start == -1 || end == -1) {
printf("输入的景点名称有误\n");
break;
}
printShortestPath(&G, start, end);
break;
}
case 3:
printf("退出程序\n");
break;
default:
printf("无效的选择,请重新输入\n");
}
} while (choice != 3);
return 0;
}
```
### 功能说明
1. **初始化图**:`createGraph` 函数从 `graph.txt` 文件中读取图的顶点和边信息,并构建邻接矩阵。
2. **打印图的信息**:`printGraph` 函数用于调试,打印图的所有顶点和邻接矩阵。
3. **查询景点信息**:`queryVertexInfo` 函数根据输入的景点名称,查找并输出景点的详细信息。
4. **Dijkstra算法求最短路径**:`dijkstra` 函数实现Dijkstra算法,计算从起点到终点的最短路径。
5. **打印最短路径**:`printShortestPath` 函数调用 `dijkstra` 函数,并输出最短路径的具体信息。
6. **主菜单**:`main` 函数提供一个简单的命令行界面,用户可以选择查询景点信息或查询最短路径。
### 使用方法
1. 将上述代码保存为 `main.c`。
2. 确保 `graph.txt` 文件存在且格式正确。
3. 编译并运行程序:
```sh
gcc main.c -o main
./main
```
希望这段代码能满足您的需求!如果有任何问题或需要进一步的帮助,请随时告诉我。
阅读全文