C/C++校园导航图的实现 |
您所在的位置：网站首页 › 介绍景点的题目 › C/C++校园导航图的实现 |
C/C++校园导航图的实现
|
C/C++校园导航图的实现
课程设计题目2——校园导航图的实现 一、设计内容 (1)设计一个学校的校园平面图，所选结点不少于30个。以图中顶点表示校园各景点，存放景点名称、代号、简介等信息:以边表示路径，存放路径长度等相关信息。 (2)为来往客人提供图中任意景点相关信息的查询。 (3)为来往客人提供图中任意景点的问路查询，即任意2个景点间的最短路径,给出具体路径和路径长度。 二、设计要求 (1)除了完成基本功能外,最好能提供实时路径查询，例如某条路径的临时关闭（需在程序中实现）后的最短路径的计算。 (2)提交设计报告，报告包括代码、设计思路〔流程图）和实现界面截图等。 设计思想程序需要先构建邻接矩阵，将读入的顶点和边的信息存入邻接矩阵(Adjacency Matrices)，然后通过迪杰斯特拉(Dijkstra)算法求两点之间的最短路径。 部分代码 #include #include #include #include /*顶点属性*/ typedef struct _tVertex { char name[256]; /*属性名称*/ char description[1024]; /*属性描述*/ } Vertex, * pVertex; /*顶点列表*/ typedef struct _tVertexList { int len; /*表长度*/ pVertex data; /*表元素*/ } VertexList, * pVertexList; /*权值*/ typedef unsigned int WEIGHT, * pWEIGHT; /*邻接矩阵*/ typedef struct _tAdjacentMatrix { int size; /*矩阵顶点个数*/ WEIGHT* data; /*矩阵权值元素*/ } AdjacentMatrix, * pAdjacentMatrix; /*图结构*/ typedef struct _tGraph { VertexList vertexes; /*顶点描述信息*/ AdjacentMatrix adjmatrix; /*顶点连接关系*/ } Graph, * pGraph; enum { VISIT_STATE_VOID, /*未标记*/ VISIT_STATE_MARK /*已标记*/ }; /*顶点被访问标识*/ typedef unsigned char VISIT, * pVISIT; /*Dijkstra算法需要用到的数据结构*/ typedef struct _tDijkstra { int len; pVISIT vis; pWEIGHT dis; int* pre; } Dijkstra, * pDijkstra; #define INFINITELY_GREAT ~0U /*无穷大*/ /*创建顶点列表*/ void generateVertexList(pVertexList list, int vertexes) { list->len = vertexes; list->data = (pVertex)malloc(sizeof(Vertex) * list->len); memset(list->data, 0U, sizeof(Vertex) * list->len); } /*创建邻接矩阵*/ void generateAdjacentMatrix(pAdjacentMatrix adjmatrix, int vertexes) { adjmatrix->size = vertexes; adjmatrix->data = (pWEIGHT)malloc(sizeof(WEIGHT) * (vertexes * vertexes)); memset(adjmatrix->data, INFINITELY_GREAT, sizeof(WEIGHT) * (vertexes * vertexes)); } /*销毁顶点列表*/ void freeVertexList(pVertexList list) { if (list) { if (list->data) { free(list->data); list->data = NULL; } } } /*销毁邻接矩阵*/ void freeAdjacentMatrix(pAdjacentMatrix adjmatrix) { if (adjmatrix) { if (adjmatrix->data) { free(adjmatrix->data); adjmatrix->data = NULL; } } } /*创建图*/ pGraph generateGraph(int vertexes) { pGraph graph = (pGraph)malloc(sizeof(Graph)); memset(graph, 0U, sizeof(Graph)); generateVertexList(&graph->vertexes, vertexes); generateAdjacentMatrix(&graph->adjmatrix, vertexes); return graph; } /*销毁图*/ void freeGraph(pGraph graph) { if (graph) { freeVertexList(&graph->vertexes); freeAdjacentMatrix(&graph->adjmatrix); free(graph); } } /*设置顶点名称*/ void setVertexName(pGraph graph, int index, const char* name, const char* summary) { strcpy(graph->vertexes.data[index].name, name); strcpy(graph->vertexes.data[index].description, summary); } /*获取顶点名称*/ const char* getVertexName(pGraph graph, int index) { return graph->vertexes.data[index].name; } /*查找顶点索引*/ int findVertexIndex(pGraph graph, const char* name) { int index = 0; while (index < graph->vertexes.len) { if (strcmp(graph->vertexes.data[index].name, name) == 0) { return index; } ++index; } return -1; } /*设置两相邻顶点的边的权值*/ void setEdgeWeight(pGraph graph, int from, int to, WEIGHT weight) { graph->adjmatrix.data[(graph->adjmatrix.size * from) + to] = weight; } /*得到两相邻顶点的边的权值*/ WEIGHT getEdgeWeight(pGraph graph, int from, int to) { return graph->adjmatrix.data[(graph->adjmatrix.size * from) + to]; } 测试数据 17 46 图书馆 这是学校的图书馆。 综合楼 这是学校的综合楼。 实验楼 这是学校的实验楼。 餐厅 这是学校的餐厅。 南门 这是学校的南门。 东门 这是学校的东门。 西门 这是学校的西门。 北门 这是学校的北门。 操场 这是学校的操场。 家属楼 这是学校的家属楼。 中心湖 这是学校的中心湖。 正门 这是学校的正门。 南区食堂 这是学校的南区食堂。 北区食堂 这是学校的北区食堂。 东区食堂 这是学校的东区食堂。 西区食堂 这是学校的西区食堂。 生物楼 这是学校的生物楼。 图书馆 综合楼 123 综合楼 图书馆 123 图书馆 餐厅 256 餐厅 图书馆 256 综合楼 实验楼 243 实验楼 综合楼 243 综合楼 餐厅 242 餐厅 综合楼 242 餐厅 实验楼 279 实验楼 餐厅 279 餐厅 南门 369 南门 餐厅 369 实验楼 南门 372 南门 实验楼 372 南门 操场 466 操场 南门 466 操场 东门 308 东门 操场 308 操场 正门 188 正门 操场 188 正门 西门 375 西门 正门 375 正门 南区食堂 115 南区食堂 正门 115 操场 南区食堂 261 南区食堂 操场 261 操场 中心湖 294 中心湖 操场 294 东门 西门 137 西门 东门 137 西门 北门 269 北门 西门 269 西门 家属楼 236 家属楼 西门 236 南区食堂 中心湖 278 中心湖 南区食堂 278 南区食堂 北区食堂 149 北区食堂 南区食堂 149 北区食堂 东区食堂 144 东区食堂 北区食堂 144 中心湖 南区食堂 565 南区食堂 中心湖 565 西区食堂 生物楼 104 生物楼 西区食堂 104 东区食堂 生物楼 376 生物楼 东区食堂 376 运行效果
链接：程序源码下载地址 提取码：1111 |
【本文地址】
今日新闻 |
推荐新闻 |