校园导航（C++)

2023-10-27 19:06| 来源: 网络整理| 查看: 265

这是刚2020年7月份刚上完《数据结构与算法分析》这门课的时候提交的课程大作业。当时还取得了不错的成绩，现在回头来看简直是太拉胯了，整个项目所有函数、过程等都放在了一个文件，还将各个函数特意用注释隔开为了让老师阅读方便觉得自己简直是良心学生，至于C++的面向对象这些特性更是完全没影子。

//----------------------------（没错，就是这样的横线） void path_print(int start, int end,int path_arr[]) //打印最短路径

写这篇文章是打算将我的辣鸡代码重构一下，由于时间太长了，所以正好一边在这里梳理一边修改我的代码。（这里提供的还是过程性 C++，修改后的代码会随着上传）

1.题目：校园导游系统 1.1 问题描述

设计一个校园导游系统，为来校参观的人们提供建筑和道路信息查询服务。

1.2 功能描述设计一个所在学校的建筑和道路平面图，所含建筑不少于10个，并建立全局坐标，按照全局右手定则确定角度；存储各建筑点的信息，包括位置坐标（二维）和简要介绍（例如：G栋，理学楼）；提供图中任意建筑点的相关信息查询，即输入关键字可输出相关信息（例如：输入G栋；给出结果：G栋，理学楼，坐标（2, 3））；提供图中多个建筑点的最佳访问路线查选，即求途经n（任意）个景点的最短路径，并给出所经过的点的方位和长度。（给定开始和结束景点，并一共包含n个景点，从A栋到G栋，途径A-B-C-D-F-G，在B点位于A点30°方向并距离A点5）；提供任意建筑点问路查询，即查询某个建筑到其他任意一个建筑点的最短路径，并按照路径长度从小到大的顺序排列（不能使用迪杰斯特拉算法）。 1.3 实现提示以图中顶点表示校内各建筑点，存放建筑名称、代号、简介等信息，以边表示道路，存放道路长度等相关信息一般情况下，校园道路是双向通行，可设校园平面图是一个无向网，顶点和边均含有相关信息 2.实现过程 2.1 获取地图数据 2.1.1坐标测量

因为每个地点只需要获得二维坐标，因此以学校大门为原点建立坐标系，在高德地图（打钱！）上大致量出来距离即可。坐标测量（这里选多少点都无所谓，反正也不用手动规划路径，当然是越多可能分数越高）

struct building//建筑信息结构体 { string name;//建筑名称 int x;//坐标 int y; string information;//建筑信息 }; const int BUILDING_NUMBER=16; //结构数组存储所有建筑信息 building arr[BUILDING_NUMBER] = {//序号，名称，坐标，信息}; 2.1.2路径测量

路径测量图中的点不全代表关键结点，有的只是为了使测量准确设置的中继点。接下来用邻接矩阵将所有信息存起来

const int MAX_NUMBER = 9999;//定义一个很长的路径代表不通,直接用INT_MAX会导致后续计算溢出 int weight[BUILDING_NUMBER][BUILDING_NUMBER] = {//详细路径} 2.1.3 地图显示

（这一步完全是内卷的真实体现，在和同学交流的过程中发现大家竟然用符号把地图绘制出来了，震惊！赶紧自己也安排上）地图打印（我弄的就是这效果，完全是cout+各种符号拼成的，听说卷王们画得很优美）

void campus_maps()//打印地图 { cout cout string find_name; cout find_name; int sequence = find_sequence(find_name); while (sequence == -1) { cout find_name; sequence = find_sequence(find_name); } cout cout start_name; sequence = find_sequence(start_name); } int end_arr[BUILDING_NUMBER - 1];//定义一个终点数组 int j = 0; for (int i = 0; i end_arr[j] = i; j++; } } length_sort_all(sequence, end_arr, path_matrix, short_path_table);//对给定起点到所有终点按路径长度进行排序 cout cout front >> behind; int front_sequence = find_sequence(front); int behind_sequence = find_sequence(behind); while (front_sequence == -1 || behind_sequence == -1) { cout front >> behind; front_sequence = find_sequence(front); behind_sequence = find_sequence(behind); } cout node_number; stack[0] = front_sequence;//将起点入栈 for (int i = 0; i int i = 0; for (i; i return i; break; }; }; return -1;//没找到返回-1 }

本来直接输入输入string遍历查询就可以了，但是由于后面要用到矩阵的时候，还是需要某一点的序号，所以这里也干脆先找到序号，然后再访问arr[i]。实现效果：查询模式

2.2.3 功能：问路模式—实现指定点到所有点的最短路径

这个需求有点特别，需要给定一个点，求出对其他所有点的最短路径，这里使用弗洛伊德（Floyd）算法。这个算法是照着《大话数据结构》一步一步码出来的。

void short_path_floyd(int weight[][BUILDING_NUMBER], int path_matrix[][BUILDING_NUMBER], int short_path_table[][BUILDING_NUMBER]) { int v, w, k; for (v = 0; v short_path_table[v][w] = weight[v][w]; path_matrix[v][w] = w; } } for (k = 0; k for (w = 0; w short_path_table[v][w] = short_path_table[v][k] + short_path_table[k][w]; path_matrix[v][w] = path_matrix[v][k]; } } } } } 2.2.4 输入任意起点和终点以及需要途径点的数量，打印最短路径和导航

记得这个需求跟老师确认了很久才搞清楚是要干嘛。演示如下图：导航演示利用深度优先搜索将所有符合要求的路径找出来再排序：

void dfs(int start,int stop,int node_number)//深度优先搜索路径 { int i, j; for (i = 0; i if (i == stop)//如果深搜到了终点，就输出刚才经过的路径 { path_length += weight[start][i]; for (j = 0; j visited[i] = true; path_length += weight[start][i]; int length = weight[i][start];//暂存路长信息 weight[start][i] = MAX_NUMBER; weight[i][start] = MAX_NUMBER; stack[m] = i;//将该点存起来 m++; dfs(i,stop,node_number);//接着深搜 visited[i] = false; weight[start][i] = length; weight[i][start] = length; path_length -= weight[start][i]; m--; } } } }

这个DFS的的编写历程颇为坎坷，是折磨我最久的一个部分，看过很多博主的写法，在各路大神的基础上有了我这个魔改版本。主要是那时候还没有理解递归的精髓，我一直以为递归返回之后后面的语句就不再执行了，打通了这个心结之后，自我感觉数据结构和算法算是真正入门了。（菜鸡本鸡）

递归的终极奥义：递归==套娃

求方位：

double angle(int front, int behind)//求方位角 { double x1 = arr[front].x; double y1 = arr[front].y; double x2 = arr[behind].x; double y2 = arr[behind].y; double angle_rad=atan( (y1 - y2)/ (x1 - x2));//计算两点间的方向（弧度表示） angle_rad = angle_rad * 180 / acos(-1);//返回角度表示 if (x2 y1) return angle_rad + 180; else if (x2

【本文地址】

校园导航（C++)

校园导航（C++)

今日新闻

推荐新闻