• 安阳旅游地图规划（未完成）

    1. #include <stdio.h>
    2. #include <stdlib.h>
    3. #include <string.h>
    4. #include <stdbool.h>
    5. #define MaxNum 10
    6. #define INFINITY 9999
    7. #define MaxStringLength 100
    8.  
    9. typedef struct GNode {
    10.     int NumVertex;
    11.     int NumEdge;
    12.     int Vertexs[MaxNum][MaxNum];
    13.     char VertexData[MaxNum][MaxStringLength];
    14. } Graph;
    15.  
    16. typedef struct view{
    17. 	char viewname[100];
    18. 	char viewinformation[1000];
    19. }view;
    20. void enter(view v[],char*name,char*information,int i){
    21. 		strcpy(v[i].viewname,name);
    22. 		strcpy(v[i].viewinformation,information);
    23. }
    24. void visit(Graph* graph, int vertex) {
    25.     printf("%s ", graph->VertexData[vertex]);
    26. }
    27.  
    28. Graph* Make_Graph(int NumVertex, int NumEdge) {
    29.     Graph* graph = (Graph*)malloc(sizeof(Graph));
    30.     graph->NumVertex = NumVertex;
    31.     graph->NumEdge = 0;
    32.     for (int i = 0; i < NumVertex; i++) {
    33.         for (int j = 0; j < NumVertex; j++) {
    34.             graph->Vertexs[i][j] = 0;
    35.         }
    36.     }
    37.     return graph;
    38. }
    39.  
    40. void Add_Edge(Graph* graph, int vertex1, int vertex2, int weight) {
    41.     if (graph == NULL || graph->NumVertex == 0) {
    42.         printf("error");
    43.         return;
    44.     }
    45.     graph->Vertexs[vertex1][vertex2] = weight;
    46.     graph->Vertexs[vertex2][vertex1] = weight;
    47. }
    48.  
    49. void Add_Vertex_Data(Graph* graph, int vertex, char* name) {
    50.     if (graph == NULL || vertex > graph->NumVertex - 1 || vertex < 0) {
    51.         printf("error");
    52.         return;
    53.     }
    54.     strcpy(graph->VertexData[vertex], name);
    55. }
    56.  
    57. void DFS(Graph* graph, int vertex, void (*visit)(Graph*, int), bool visited[]) {
    58.     visit(graph, vertex);
    59.     visited[vertex] = true;
    60.     for (int i = 0; i < graph->NumVertex; i++) {
    61.         if (graph->Vertexs[vertex][i] != 0 && !visited[i] && graph->Vertexs[vertex][i] != INFINITY) {
    62.             DFS(graph, i, visit, visited);
    63.         }
    64.     }
    65. }
    66.  
    67. void dijkstra(Graph* graph, int start, bool visited[]) {
    68.     int T[MaxNum][2];
    69.     for (int i = 0; i < graph->NumVertex; i++) {
    70.         T[i][0] = INFINITY;
    71.         T[i][1] = -1;
    72.         visited[i] = false;
    73.     }
    74.     T[start][0] = 0;
    75.     T[start][1] = -1;
    76.     for (int i = 0; i < graph->NumVertex - 1; i++) {
    77.         int mindist = INFINITY;
    78.         int minindex = -1;
    79.         for (int j = 0; j < graph->NumVertex; j++) {
    80.             if (!visited[j] && T[j][0] < mindist) {
    81.                 mindist = T[j][0];
    82.                 minindex = j;
    83.             }
    84.         }
    85.         visited[minindex] = true;
    86.         for (int k = 0; k < graph->NumVertex; k++) {
    87.             if (!visited[k] && graph->Vertexs[minindex][k] != 0 && T[minindex][0] + graph->Vertexs[minindex][k] < T[k][0]) {
    88.                 T[k][0] = T[minindex][0] + graph->Vertexs[minindex][k];
    89.                 T[k][1] = minindex;
    90.             }
    91.         }
    92.     }
    93.     int end;
    94.     printf("请输入目的地编号：");
    95.     scanf("%d", &end);
    96.     printf("距离为：%d\n", T[end][0]);
    97.     printf("路线为：%d ", end);
    98.     int temp = T[end][1];
    99.     while (temp != -1) {
    100.         printf("<- %d ", temp);
    101.         temp = T[temp][1];
    102.     }
    103. }
    104.  
    105. int main() {
    106. 	FILE *fp;
    107. 	fp=fopen("data.txt","r");
    108.     bool visited[MaxNum];
    109.     for (int i = 0; i < MaxNum; i++) {
    110.         visited[i] = false;
    111.     }
    112.     int NumVertex = 10;
    113.     int NumEdge = 19;
    114.     Graph* graph = Make_Graph(NumVertex, NumEdge);
    115.     for (int i = 0; i < NumVertex; i++) {
    116.         char* name = (char*)malloc(sizeof(char) * 100);
    117.         printf("请输入%d号景点的名称：\n", i);
    118.         fscanf(fp,"%s", name);
    119.         Add_Vertex_Data(graph, i, name);
    120.     }
    121.     for (int i = 0; i < NumEdge; i++) {
    122.         int v1, v2, weight;
    123.         printf("请输入两个景点的编号和距离：\n");
    124.         fscanf(fp,"%d %d %d", &v1, &v2, &weight);
    125.         printf("从%d号景点到%d号景点的距离%d:\n", v1, v2, weight);
    126.         Add_Edge(graph, v1, v2, weight);
    127.         printf("\n");
    128.     };
    129.     for(int i=0;i<NumVertex;i++){
    130.     	char*name=(char*)malloc(sizeof(char)*100);
    131.     	char*information=(char*)malloc(sizeof(char)*1000);
    132.     	view v[10];
    133.     	fscanf(fp,"%s",name);
    134.     	fscanf(fp,"%d",information);
    135. 		enter(v,name,information,i); 
    136. 	}
    137.     for (int i = 0; i < graph->NumVertex; i++) {
    138.         printf("%s\n", graph->VertexData[i]);
    139.     }
    140.     
    141.     DFS(graph, 0, visit, visited);
    142.     printf("\n\n");
    143.     int start;
    144.     system("cls");
    145.     printf("                                                                               \n");
    146.     printf("                                                                               \n");                                 
    147.     printf("                  |-------------0殷墟------1袁林-------2中国文字博物馆         \n");
    148.     printf("                  |              |                  |             |            \n");
    149.     printf("6红旗渠------------              |                  |             |            \n");
    150.     printf("    |             |              |---------------4羑里城-----------            \n");
    151.     printf("    |             |              |                  |             |            \n");
    152.     printf("    |             |              |                  |             |            \n");
    153.     printf("7太行大峡谷-------|-------------3长春观----------5岳飞庙-------   |            \n");
    154.     printf("                                                              |   |            \n");
    155.     printf("                                                               8二帝陵         \n");
    156.     printf("                                                                  |            \n");
    157.     printf("                                                                  |            \n");
    158.     printf("                                                               9明福寺         \n");
    159.     printf("                                                                               \n");
    160.     printf("                                                                               \n");
    161.     printf("                                                                               \n");
    162.     printf("                                                                               \n");
    163.     int choice;
    164.     do{
    165.     	scanf("%d",&choice);
    166.     	if(choice==1){
    167.     		
    168. 		}
    169. 		if(choice==2){
    170. 			
    171. 		}
    172.     	if(choice==3){
    173.     		
    174. 		}
    175. 	}while(choice!=0);
    176.     printf("请输入出发地地点编号：");
    177.     scanf("%d", &start);
    178.     dijkstra(graph, start, visited);
    179.     fclose(fp);
    180.     return 0;
    181. }

    殷墟

    袁林

    文字博物馆

    长春观

    羑里城

    岳飞庙

    红旗渠

    太行大峡谷

    二帝陵

    明福寺
    0 1 5
    0 2 8
    0 3 30
    0 4 20
    0 6 70
    1 2 5
    1 4 20
    2 4 20
    2 8 75
    3 4 40
    3 5 35
    3 6 60
    3 7 30
    4 5 5
    4 8 60
    5 8 55
    5 9 60
    6 7 30
    8 9 40

    a
    b
    c
    d
    e
    f
    g
    h
    i
    j
    0 1 5
    0 2 8
    0 3 30
    0 4 20
    0 6 70
    1 2 5
    2 4 21
    2 8 75
    3 4 40
    3 5 35
    3 6 60
    3 7 30
    4 8 60
    5 8 55
    5 9 60
    6 7 30
    8 9 40

    1. #include <stdio.h>
    2. #include <stdlib.h>
    3. #include <string.h>
    4. #include <stdbool.h>
    5. #define MaxNum 10
    6. #define INFINITY 9999
    7. #define MaxStringLength 100
    8.  
    9. typedef struct GNode {
    10.     int NumVertex;
    11.     int NumEdge;
    12.     int Vertexs[MaxNum][MaxNum];
    13.     char VertexData[MaxNum][MaxStringLength];
    14. } Graph;
    15.  
    16. typedef struct view{
    17. 	char viewname[100];
    18. 	char viewinformation[1000];
    19. }view;
    20. void enter(view v[],char*name,char*information,int i){
    21. 		strcpy(v[i].viewname,name);
    22. 		strcpy(v[i].viewinformation,information);
    23. }
    24. void print_view(view v[]){
    25. 	for(int i=0;i<10;i++){
    26. 		printf("景点名称：%s\n",v[i].viewname);
    27. 		printf("景点介绍：%s\n",v[i].viewinformation);
    28. 		printf("\n");
    29. 	}
    30. }
    31. void visit(Graph* graph, int vertex) {
    32.     printf("%s ", graph->VertexData[vertex]);
    33. }
    34.  
    35. Graph* Make_Graph(int NumVertex, int NumEdge) {
    36.     Graph* graph = (Graph*)malloc(sizeof(Graph));
    37.     graph->NumVertex = NumVertex;
    38.     graph->NumEdge = 0;
    39.     for (int i = 0; i < NumVertex; i++) {
    40.         for (int j = 0; j < NumVertex; j++) {
    41.             graph->Vertexs[i][j] = 0;
    42.         }
    43.     }
    44.     return graph;
    45. }
    46.  
    47. void Add_Edge(Graph* graph, int vertex1, int vertex2, int weight) {
    48.     if (graph == NULL || graph->NumVertex == 0) {
    49.         printf("error");
    50.         return;
    51.     }
    52.     graph->Vertexs[vertex1][vertex2] = weight;
    53.     graph->Vertexs[vertex2][vertex1] = weight;
    54. }
    55.  
    56. void Add_Vertex_Data(Graph* graph, int vertex, char* name) {
    57.     if (graph == NULL || vertex > graph->NumVertex - 1 || vertex < 0) {
    58.         printf("error");
    59.         return;
    60.     }
    61.     strcpy(graph->VertexData[vertex], name);
    62. }
    63.  
    64. void DFS(Graph* graph, int vertex, void (*visit)(Graph*, int), bool visited[]) {
    65.     visit(graph, vertex);
    66.     visited[vertex] = true;
    67.     for (int i = 0; i < graph->NumVertex; i++) {
    68.         if (graph->Vertexs[vertex][i] != 0 && !visited[i] && graph->Vertexs[vertex][i] != INFINITY) {
    69.             DFS(graph, i, visit, visited);
    70.         }
    71.     }
    72. }
    73.  
    74. void dijkstra(Graph* graph, int start, bool visited[]) {
    75.     int T[MaxNum][2];
    76.     for (int i = 0; i < graph->NumVertex; i++) {
    77.         T[i][0] = INFINITY;
    78.         T[i][1] = -1;
    79.         visited[i] = false;
    80.     }
    81.     T[start][0] = 0;
    82.     T[start][1] = -1;
    83.     for (int i = 0; i < graph->NumVertex - 1; i++) {
    84.         int mindist = INFINITY;
    85.         int minindex = -1;
    86.         for (int j = 0; j < graph->NumVertex; j++) {
    87.             if (!visited[j] && T[j][0] < mindist) {
    88.                 mindist = T[j][0];
    89.                 minindex = j;
    90.             }
    91.         }
    92.         visited[minindex] = true;
    93.         for (int k = 0; k < graph->NumVertex; k++) {
    94.             if (!visited[k] && graph->Vertexs[minindex][k] != 0 && T[minindex][0] + graph->Vertexs[minindex][k] < T[k][0]) {
    95.                 T[k][0] = T[minindex][0] + graph->Vertexs[minindex][k];
    96.                 T[k][1] = minindex;
    97.             }
    98.         }
    99.     }
    100.     int end;
    101.     printf("请输入目的地编号：");
    102.     scanf("%d", &end);
    103.     printf("最短距离为：%dkm\n", T[end][0]);
    104.     printf("最短路线为：%s ", graph->VertexData[end]);
    105.     int temp = T[end][1];
    106.     while (temp != -1) {
    107.         printf("<- %s ", graph->VertexData[temp]);
    108.         temp = T[temp][1];
    109.     }
    110. }
    111.  
    112. int main() {
    113. 	FILE *fp;
    114. 	fp=fopen("data.txt","r");
    115.     bool visited[MaxNum];
    116.     for (int i = 0; i < MaxNum; i++) {
    117.         visited[i] = false;
    118.     }
    119.     int NumVertex = 10;
    120.     int NumEdge = 19;
    121.     Graph* graph = Make_Graph(NumVertex, NumEdge);
    122.     for (int i = 0; i < NumVertex; i++) {
    123.         char* name = (char*)malloc(sizeof(char) * 100);
    124.         printf("请输入%d号景点的名称：\n", i);
    125.         fscanf(fp,"%s", name);
    126.         Add_Vertex_Data(graph, i, name);
    127.     }
    128.     for (int i = 0; i < NumEdge; i++) {
    129.         int v1, v2, weight;
    130.         printf("请输入两个景点的编号和距离：\n");
    131.         fscanf(fp,"%d %d %d", &v1, &v2, &weight);
    132.         printf("从%d号景点到%d号景点的距离%d:\n", v1, v2, weight);
    133.         Add_Edge(graph, v1, v2, weight);
    134.         printf("\n\n");
    135.     };
    136.     view v[10];
    137.     for(int i=0;i<10;i++){
    138.     	char*name=(char*)malloc(sizeof(char)*100);
    139.     	char*information=(char*)malloc(sizeof(char)*1000);
    140.     	printf("请输入景点名称："); 
    141.     	fscanf(fp,"%s",name);
    142.     	printf("请输入景点信息：");
    143.     	fscanf(fp,"%s",information);
    144. 		enter(v,name,information,i); 
    145. 	}
    146.     printf("\n\n");
    147.     int choice;
    148. 	int start;
    149.     do{
    150.     	
    151.         printf("                                                                               \n");
    152.         printf("                                                                               \n");                                 
    153.         printf("                  |-------------0殷墟------1袁林-------2中国文字博物馆         \n");
    154.         printf("                  |              |                  |             |            \n");
    155.         printf("6红旗渠------------              |                  |             |            \n");
    156.         printf("    |             |              |---------------4羑里城-----------            \n");
    157.         printf("    |             |              |                  |             |            \n");
    158.         printf("    |             |              |                  |             |            \n");
    159.         printf("7太行大峡谷-------|-------------3长春观----------5岳飞庙-------   |            \n");
    160.         printf("                                                    |         |   |            \n");
    161.         printf("                                                    |          8二帝陵         \n");
    162.         printf("                                                    |             |            \n");
    163.         printf("                                                    |             |            \n");
    164.         printf("                                                    |----------9明福寺         \n");
    165.         printf("                                                                               \n");
    166.         printf("                                                                               \n");
    167.         printf("*******************************河南安阳旅游地图********************************\n");
    168.         printf("                                                                               \n");
    169.     	printf("              【1】景点名称及相关信息\n");
    170.     	printf("              【2】深度遍历景点\n");
    171. 		printf("              【3】获取最短路径\n");
    172. 		printf("               请输入你的选项：\n");
    173. 		scanf("%d",&choice);
    174. 		printf("\n\n\n");
    175. 		if(choice==1){
    176. 			print_view(v);
    177. 			printf("\n");
    178. 		} 
    179. 		if(choice==2){
    180. 			int num;
    181. 			printf("请输入作为遍历起点的景点编号：");
    182. 			scanf("%d",&num);
    183. 			DFS(graph, num, visit, visited);
    184. 			printf("\n");
    185. 		}
    186. 		if(choice==3){
    187. 			printf("请输入出发地地点编号：\n");
    188.             scanf("%d", &start);
    189.             dijkstra(graph, start, visited);
    190.             printf("\n");
    191. 		}
    192. 	}while(choice!=0);
    193. 	fclose(fp);
    194.     return 0;
    195. }

  • 相关阅读:
    【UV打印机】电气之负压系统(二)
    PC_DRAM
    【考研数学】数学“背诵手册”（二）| 线代及概率论部分
    libevent学习——辅助类型和函数
    羊了个羊通关秘籍
    Java --- JVM虚拟机栈
    读书笔记：Effective C++ 2.0 版，条款43(多继承)、条款44(概念明确)、条款45-50(杂项)
    五、3d场景的卡片展示的创建
    Linux三剑客
    浅析云南某大学门户网密码加密算法
  • 原文地址：https://blog.csdn.net/2302_80380793/article/details/137870619