校園導航實驗報告

1. 問題描述：

以我校為例，設計一個校園導航系統(tǒng)，主要為來訪的客人提供信息查詢。系統(tǒng)有兩類登陸賬號，一類是游客，使用該系統(tǒng)方便校內(nèi)路線查詢；一類是管理員，可以使用該系統(tǒng)查詢校內(nèi)路線，可對校園景點路線可編輯。

1. 需求分析：

設計學校的平面圖，至少包括10個以上景點（場所），每兩個景點間可以有不同道路，且路長也可能不同，找出在游人所在景點到其他景點的最短路徑，或游人輸入的任意兩個景點的最短路徑。

1. 要求
   （1） 以圖中頂點表示校園內(nèi)各景點，存放景點名稱、代號、簡介等信息；以邊表示路徑，路徑權重為路徑長度。
   （2） 為游人提供任意景點相關信息查詢。
   （3）為游人提供任意景點的問路查詢，即任意兩個景點之間的最短路徑。

4.說明書：

本程序?qū)崿F(xiàn)了兩種身份：游客和管理員

其中，游客無登錄密碼，因為其只有查詢功能，誰來查詢都一樣

查詢內(nèi)容包括：任意兩點間距離和某個景點的相關信息

管理員 登錄密碼為：jiangzhiyu

除游客包括的功能外，還包括增刪節(jié)點，增刪路徑，修改景點簡介

5.功能實現(xiàn)：

鄰接矩陣保存圖

每個景點用一個結(jié)構(gòu)體保存其名字和簡介

用哈希表將景點和編號連起來

用Floyd算法實現(xiàn)求解多源多匯最短路

6.調(diào)試與解決問題

將所有輸入都輸入字符串，雖然數(shù)字需要在進一步進行轉(zhuǎn)換，但是這樣程序健壯性就得以保證。

最短路問題解決較為簡單，大部分時間在增加程序健壯性了。

7.源代碼：

#include<bits/stdc++.h>using namespace std;const int N = 110;//存圖int idx=12;//當前有多少景點int g[N][N];int gc[N][N];//存景點struct scenic_spot {string name;//相關信息string introduction;}spot[N];map<string, int> mp;//初始化圖中點的信息void Init_scenic() {spot[1].name = "體檢中心";spot[2].name = "操場";spot[3].name = "校門北口";spot[4].name = "銀杏景觀";spot[5].name = "邯鄲音樂廳";spot[6].name = "圖書館";spot[7].name = "餐廳";spot[8].name = "網(wǎng)計學院";spot[9].name = "信息學部";spot[10].name = "花園景觀";spot[11].name = "校門東口";spot[12].name = "校門南口";for (int i = 1; i <= idx; i++)mp[spot[i].name] = i;spot[1].introduction = "雖然是體檢中心，但我感覺都沒怎么去過";spot[2].introduction = "風雨操場，新建的體育館特別棒";spot[3].introduction = "用來連接教學區(qū)和生活區(qū)";spot[4].introduction = "秋天落葉非常美，一定要來看看";spot[5].introduction = "沒去過，不知道";spot[6].introduction = "很大很豪華，學習氛圍超級好，很適合學習";spot[7].introduction = "三層餐廳，尚飲食堂";spot[8].introduction = "網(wǎng)計學院yyds";spot[9].introduction = "沒去過";spot[10].introduction = "挺好看的，就是離得有點遠";spot[11].introduction = "現(xiàn)在也用來連接教學區(qū)和生活區(qū)了";spot[12].introduction = "正門口哦";}//初始化圖void Init_Map() {memset(g, 0x3f, sizeof g);g[1][2] = 350, g[2][3] =200, g[3][4] =100, g[1][5] =200, g[2][5] =480, g[5][6] =400;g[2][6] = 280, g[3][7] =100, g[4][7] =100, g[5][8] =500, g[5][9] =500, g[9][10] =150;g[6][10] = 160, g[6][11] =300, g[10][11] =200, g[7][11] =100, g[8][12] =400;g[9][12] = 400, g[10][12] =500, g[11][12] =600;for (int i = 1; i <= idx; i++)for (int j = 1; j <= idx; j++) { if (g[i][j] != 0x3f3f3f3f)g[j][i] = g[i][j]; if (i == j)g[i][j] = 0; }}//初始化多源最短路void Init_MinMap() {for (int i = 1; i <= idx; i++)for (int j = 1; j <= idx; j++) gc[i][j] = g[i][j];for (int k = 1; k <= idx; k++)for (int i = 1; i <= idx; i++)for (int j = 1; j <= idx; j++)gc[i][j] = min(gc[i][j], gc[i][k] + gc[k][j]);}//查詢?nèi)我鈨牲c間距離void check_two() {fflush(stdin);cout << "請輸入您的起點：" << endl;string s1, s2;getline(cin, s1);while (mp.count(s1) == 0) {cout << "您輸入的景點不存在，請重新輸入：" << endl;getline(cin, s1);}cout << "請輸入您的終點：" << endl;getline(cin, s2);while (mp.count(s2) == 0) {cout << "您輸入的景點不存在，請重新輸入：" << endl;getline(cin, s2);}if (gc[mp[s1]][mp[s2]] == 0x3f3f3f3f)cout << "此兩點不互通" << endl;else cout << "最短距離為：" << gc[mp[s1]][mp[s2]] << endl;}//查詢某個節(jié)點的信息void query() {cout << "請輸入您感興趣的景點：" << endl;string s;getline(cin, s);while (mp.count(s) == 0) {cout << "地圖中沒有這個景點！重新輸入：" << endl;getline(cin, s);}int x = mp[s];bool fg = true;for (int i = 1; i <= idx; i++) {if (i == x)continue;if (g[x][i] != 0x3f3f3f3f) {if (fg) {fg = false;cout << "與該景點相鄰的景點有：" << endl;cout << spot[i].name << " 相距" << g[x][i] << "米" << endl;}else {cout << spot[i].name << " 相距" << g[x][i] << "米" << endl;}}}if (spot[x].introduction.size() != 0) {cout << "簡介：" << endl;cout << spot[x].introduction << endl << endl;}else cout << "無簡介" << endl;}//判斷是否繼續(xù)bool goon() {string s;getline(cin, s);while (s.size() != 1 || s[0] - '0' != 1 && s[0] - '0' != 2) {cout << "請輸入1或者2，不要搗亂！" << endl;getline(cin, s);}if (s[0] - '0' == 1)return true;return false;}//增加一個點void add_spot() {cout << "請輸入您要加入的景點名稱：" << endl;string s;getline(cin, s);while (s.size()==0) {cout << "輸入不能為空" << endl;getline(cin, s);}while (mp.count(s) != 0) {cout << "這個景點我們已經(jīng)添加過了！重新輸入：" << endl;getline(cin, s);}mp[s] = ++idx;spot[idx].name = s;cout << "接下來請您輸入與此景點直接相連的景點名稱及路徑長度(注意：名稱和長度輸入完各自按回車)" << endl;cout << "如果您輸入完了，請輸入“no”" << endl;string s1="";int dist=0;getline(cin, s1);while (s.size() == 0) {cout << "輸入不能為空" << endl;getline(cin, s);}while (s1 != "no") {if (mp.count(s1) == 0) {cout << "這個景點名稱錯誤，它并沒有出現(xiàn)在已有地圖中，請您重新輸入：" << endl;getline(cin, s1);continue;}string ss;getline(cin, ss);bool st = true;while (true) {if (ss.size() == 0) { getline(cin, ss); continue; }for (int i = 0; i < ss.size(); i++)if (!isdigit(ss[i]))st = false;if (st)break;else {cout << "請輸入一個整數(shù)：" << endl;st = true;getline(cin, ss);}}for (int i = 0; i <ss.size(); i++) {dist *= 10;dist += ss[i] - '0';}g[mp[s1]][idx] = g[idx][mp[s1]] = dist;cout << "新路徑添加成功,請繼續(xù)" << endl;getline(cin, s1);}Init_MinMap();}//刪除一個點void del_spot() {fflush(stdin);cout << "請輸入您要刪除的景點名稱：" << endl;string s;getline(cin, s);while (mp.count(s) == 0) {cout << "地圖中沒有這個景點！重新輸入：" << endl;getline(cin, s);}int x = mp[s];for(int i=1;i<=idx;i++)for (int j = 1; j <= idx; j++) {if (i == x || j == x)g[i][j] = 0x3f3f3f3f;}Init_MinMap();mp.erase(s);}//增加一條路徑void add_road() {fflush(stdin);cout << "請輸入您要增加路徑的起點：" << endl;string s1,s2;getline(cin, s1);while (mp.count(s1) == 0) {cout << "地圖中沒有這個景點！重新輸入：" << endl;getline(cin, s1);}cout << "請輸入您要增加路徑的終點：" << endl;getline(cin, s2);while (mp.count(s2) == 0) {cout << "地圖中沒有這個景點！重新輸入：" << endl;getline(cin, s2);}if (g[mp[s1]][mp[s2]] != 0x3f3f3f3f) {cout << "地圖中已有路徑，是否覆蓋？" << endl;cout << "1.覆蓋?? 2.重新選擇景點" << endl;if (goon()) {cout << "請輸入路徑長度：" << endl;int dist;cin >> dist;g[mp[s1]][mp[s2]] = g[mp[s2]][mp[s1]] = dist;}else { system("cls");? add_road(); }}else {cout << "請輸入路徑長度：" << endl;int dist;cin >> dist;g[mp[s1]][mp[s2]] = g[mp[s2]][mp[s1]] = dist;}}//刪除一條路徑void del_road() {fflush(stdin);cout << "請輸入您要刪除路徑的起點：" << endl;string s1, s2;getline(cin, s1);while (mp.count(s1) == 0) {cout << "地圖中沒有這個景點！重新輸入：" << endl;getline(cin, s1);}cout << "請輸入您要刪除路徑的終點：" << endl;getline(cin, s2);while (mp.count(s2) == 0) {cout << "地圖中沒有這個景點！重新輸入：" << endl;getline(cin, s2);}g[mp[s1]][mp[s2]] = 0x3f3f3f3f;}//修改某個點的簡介void Modify() {cout << "請問您想修改哪個節(jié)點的簡介？" << endl;string s, s1;getline(cin, s);while (mp.count(s) == 0) {cout << "地圖中沒有這個景點！重新輸入：" << endl;getline(cin, s);}cout << "請輸入其新的簡介：" << endl;getline(cin, s1);spot[mp[s]].introduction = s1;}//游客登錄void Visitor() {cout << "親愛的游客，歡迎來到河北大學！我們將為您提供搜索功能" << endl;cout << "請問您想查詢什么呢？" << endl;cout << "1.任意兩點間距離??? 2.某個景點的相關信息" << endl;if (goon())check_two();else query();cout << "請問您還要繼續(xù)搜索嗎？" << endl;cout<<"1.繼續(xù)?? 2.退出" << endl;string s;getline(cin, s);while (s.size() != 1 || s[0] - '0' != 1 && s[0] - '0' != 2) {cout << "請輸入1或者2，不要搗亂！" << endl;getline(cin, s);}if (s[0] - '0' == 1) {Visitor();}}//管理員登錄void Admin() {cout << "親愛的管理員：" << endl;cout << "請輸入您所需的功能：" << endl;cout << "1.查詢兩景點間距離" << endl;cout << "2.增加節(jié)點" << endl;cout << "3.刪除節(jié)點" << endl;cout << "4.增加道路" << endl;cout << "5.刪除道路" << endl;cout << "6.修改已有節(jié)點信息" << endl;cout << "7.某個景點的相關信息" << endl;string s;getline(cin, s);while (s.size() != 1 || s[0] - '0' <= 0 && s[0] - '0' > 6) {cout << "請按要求輸入，不要搗亂！" << endl;getline(cin, s);}if (s[0] - '0' == 1) {check_two();}else if (s[0] - '0' == 2) {add_spot();}else if (s[0] - '0' == 3) {del_spot();}else if (s[0] - '0' == 4) {add_road();Init_MinMap();}else if (s[0] - '0' == 5) {del_road();Init_MinMap();}else if (s[0] - '0' == 6) {Modify();}else {query();}cout << "您還要繼續(xù)嗎？" << endl;cout << "1.繼續(xù)?? 2.退出" << endl;if (goon()) {system("cls");Admin();}}//登錄void Enroll() {cout << "歡迎使用河北大學導航服務" << endl;cout << "現(xiàn)在是蔣志宇同學為您導航" << endl;cout << "請問您是游客還是管理員：" << endl << "1.游客?? 2.管理員"<<endl;string s;getline(cin, s);while (s.size() != 1 || s[0] - '0' != 1 && s[0] - '0' != 2) {cout << "請輸入1或者2，不要搗亂！" << endl;getline(cin, s);}system("cls");if (s[0] - '0' == 1) {Visitor();}else {cout << "請輸入密碼：" << endl;string s;getline(cin, s);while (s != "jiangzhiyu") {cout << "密碼錯誤，重新輸入：" << endl;getline(cin, s);}system("cls");Admin();}}int main() {//初始化Init_scenic();Init_Map();Init_MinMap();//登錄Enroll();return 0;}