文章目錄

• • 第一章 概述
  • 第二章 概要設計
  • 第三章 詳細設計
  • 第四章 測試與運行

第一章 概述

1.背景和意義
大學校園占比面積大，每年的新生在來到之后難免會遇到人生地不熟的尷尬境地，對于枯燥的地圖很多人也不會看。那么設計一個簡單的新生導游小程序讓新同學在邊玩的過程中認識校園就顯得尤為重要。
2.系統任務和功能
用無向圖表示山東理工大學的校園景點平面圖，圖中頂點存放景點的編號、名稱、簡介等信息，圖中的邊表示景點間的道路，存放路徑長度等信息。要求能夠回答剛剛入校的新生有關景點介紹、游覽路徑等問題。

3.功能：
（1）查詢各景點的相關信息；
（2）提供任意景點之間的路徑查詢，能夠提供兩個頂點之間的所有路徑信息；
（3）能夠提供滿足用戶需求的任意兩個景點間的最優路徑查詢服務（如距離最短、時間最少、換乘最少等）。
（4）能夠提供特定約束條件下的最優訪問路線（如單位時間內、限定步行距離范圍內、限定交通工具下等）。
（5）圖的信息要保存到文件中，并能夠實現文件信息的修訂。
（6）增加、刪除、更新有關景點和道路的信息。

4.數據結構和算法
鄰接矩陣和鄰接表，深度優先搜索（DFS），弗洛伊德
5.創新點和特色
（1）本程序采用功能主界面模式，分為管理員模式與游客模式，可根據不同模式實現不同功能。
（2） 管理員界面與游客界面自動切換；
（3） 弗洛伊德算法路徑的長度可自動計算；
（4） 出行方式多樣，分別是步行、共享單車以及小公交；
（5） 用三維數組判斷可達性；
（6） 根據高德地圖形成校園仿真圖；
（7） 更刪改查之后表格信息不會覆蓋，自動更改；
（8） 文件的信息可以自動導出excel表格；

第二章 概要設計

主程序流程（各函數之間的調用關系）：

Main（）；//主函數 void create(Graph *G ) //構造圖的矩陣存儲 Vertex GetVex(Graph *G, int v) //任意景點的介紹 void PutVertex(Graph *G,int v) //修改景點信息 void InsertVertex (Graph *G,Vertex v) //插入景點 void DeleteVertex(Graph *G, int a) //刪除景點 void InsertArc(Graph *G,int v, int w) //增加路徑 void DeleteArc(Graph*G,int v,int w) //刪除路徑 void PrintPath()//輸出所有路徑的代碼 void DFS(Graph *G,int now,int n) //所有路徑搜索函數 void Floydshort(Graph *G) //查詢經過任意兩景點間的最短時間 void Floyd(Graph *G) //查詢任意兩景點間的最短路徑 int show()//管理員界面顯示 int show_1()//游客界面顯示 void show0(Graph *G)//現實結點名稱和編號 void show3()//輸出校園仿真圖

2.抽象數據類型定義：

ADT Graph{ 數據對象V：V具有相同特性的數組元素的集合，稱為點集。 數據關系R:R={VR}VR={<v,w>|v,w ?V且P(v,w),<v,w>表示從v到w的弧，謂詞P（v,w）定義了弧<v,w>的意義或信息。}

第三章 詳細設計

1.圖的結構

typedef struct //點的結構 {char name[20];char features[100]; } Vertex; //矩陣結構體 typedef struct //圖的結構 {Vertex vexs[100];int edges[500][500];int n,e;//點和邊數 } Graph;

2.各個函數的偽代碼：

定義全局變量 int block[105]; int STA[105],top; 主函數main { show0(&G);//顯示初始界面 if(a==111)//管理員界面顯示 {if(data==1)//查詢景點介紹else if(data==2)//修改景點信息else if(data==3)//添加景點else if(data==4)//刪除景點else if(data==5)//添加道路 else if(data==6)//刪除道路 else if(data==7)//校園仿真圖 else if(data==8)//回到游客界面 } else（a==222）//游客界面顯示 {if(data==1)查詢景點信息else if(data==2)查詢最短時間路徑else if(data==3)查詢最短長度路徑else if(data==4)校園仿真圖else if(data==6)退出系統 } }//初始化圖的矩陣存儲（讀取文件） void InitializeG(Graph* G) {MyFileIO f;vector<vector<string> > ver_strArray = f.readFile(verInfo);//讀取節點信息vector<vector<string> > road_strArray = f.readFile(roadInfo);//讀取道路信息for (int i = 0; i < ver_strArray.size(); i++)//節點信息初始化{strcpy(G->vexs[i].name, ver_strArray[i][1].c_str());strcpy(G->vexs[i].features, ver_strArray[i][2].c_str());}G->n = ver_strArray.size();//初始化節點個數for (int i = 0; i < 50; i++)for (int j = 0; j < 50; j++){G->edges[i][j] = G->edges[j][i]= INF;}//初始化道路信息G->e = 0;for (int i = 0; i < road_strArray.size(); i++)for (int j = i; j < road_strArray[i].size(); j++){G->edges[i][j] = G->edges[j][i]= stoi(road_strArray[i][j]);if (G->edges[i][j] != 0 && G->edges[i][j] != INF)G->e++;} }//遍歷景點 int ergodic(Graph* G, int v) {int i;for (i = 0; i < G->n; i++){if (i == v)return v;}return -1; } void display(Graph* G) {int k = -1;int i, j;printf("\n\n");for (i = 0; i <= G->n; i++) {printf("\n");for (j = 0; j <= G->n; j++) {if (G->time[i][j] < INF) {printf("%d ", G->time[i][j]);}else if (i == j){printf(" 0 ");}else {printf(" ∞ ");}}}printf("\n\n"); } //任意景點的介紹 Vertex GetVex(Graph* G, int v) {int j;j = ergodic(G, v);if (j == -1){printf(" 無此景點\n\n\n\n");}else{printf("%s", G->vexs[v].name);Vertex a = G->vexs[j];return a;} } int block[105]; int STA[105], top;//修改景點信息 void PutVertex(Graph* G, int v) {int j;j = ergodic(G, v);if (j == -1)printf("無景點\n");else{char s[500];printf("\n");printf(" 輸入修改后的景點信息：\n");printf(" ");//scanf("%s", s);cin >> s;strcpy(G->vexs[j].features, s);printf("\n");printf(" 修改完成\n");} } //插入景點 void InsertVertex(Graph* G) {Vertex v;char str_name[100], str_info[100];int edge, a[100], i, a1[100], b;printf(" 請輸入景點名稱:\n\n");printf(" ");scanf("%s", str_name,20);strcpy(v.name, str_name);printf("\n");printf(" 請輸入景點介紹：\n\n");printf(" ");scanf("%s", str_info,100);strcpy(v.features, str_info);printf("\n");printf(" 請輸入新增景點的邊數：\n\n");printf(" ");scanf("%d", &edge);printf("\n");printf(" 請輸入與新增景點連通的景點編號以及路徑長度：\n\n");G->e += edge;G->n = G->n + 1;G->vexs[G->n - 1] = v;for (i = 1; i <= G->n; i++)G->edges[G->n - 1][i] = G->edges[i][G->n - 1] = INF;//初始化G->edges[G->n - 1][G->n - 1] = 0;//自身到自身為0for (i = 1; i <= edge; i++){printf(" ");scanf("%d %d", &a1[i], &b);//編號和長度a[i] = ergodic(G, a1[i]);G->edges[G->n - 1][a[i]] = G->edges[a[i]][G->n - 1] = b;printf("\n");} } //刪除景點 void DeleteVertex(Graph* G, int a) {int h, b = 0, i;h = ergodic(G, a);if (h == -1){printf(" 無此景點\n\n\n\n\n");}else{//節點遷移for (int k = h; k < G->n - 1; k++) {strcpy(G->vexs[k].features, G->vexs[k + 1].features);strcpy(G->vexs[k].name, G->vexs[k + 1].features);}//列數量計算for (i = 0; i < G->n; i++){if (G->edges[h][i] != INF && G->edges[h][i] != 0){//G->edges[h][i] = G->edges[i][h] = INF;G->e--;}}//cout <<"--------邊數--------"<< G->e << endl;//數組整理：行、列遷移//行遷移for (int k = h; k < G->n - 1; k++) {for (int v = 0; v < G->n; v++) {G->edges[k][v] = G->edges[k + 1][v];}}//列遷移for (int k = h; k < G->n - 1; k++) {for (int v = 0; v < G->n; v++) {G->edges[v][k] = G->edges[v][k + 1];}}G->n--;//節點數量計算} } //增加路徑 void InsertArc(Graph* G, int v, int w) {int length;printf(" 請輸入新加道路的長度:\n\n");printf(" ");scanf("%d", &length);int a = ergodic(G, v);int b = ergodic(G, w);G->edges[a][b] = G->edges[b][a] = length; } //刪除路徑 void DeleteArc(Graph* G, int v, int w) {int a = ergodic(G, v);int b = ergodic(G, w);if (a == -1 || b == -1){printf(" 無此景點\n\n\n\n\n");}elseG->edges[a][b] = G->edges[b][a] = INF; } //輸出所有路徑的代碼 void PrintPath() {printf("%d", STA[0]);for (int i = 1; i <= top; ++i)printf("->%d", STA[i]);printf("\n"); } //所有路徑搜索函數 void DFS(Graph* G, int now, int n) {block[now] = 1;STA[++top] = now;if (now == n) PrintPath();for (int i = 0; i < G->n; i++)if (block[i] == 0 && G->edges[now][i] < INF)DFS(G, i, n);top--;block[now] = 0; }//根據地點名確定地點序號 int Locate(Graph* G, char name[]) {int i;for (i = 0; i < G->n; i++) {//圖中含有該景點，找到其序號if (!strcmp(G->vexs[i].name, name))return i;}return -1; }//查詢經過任意兩景點間的最短時間 void Floydshort(Graph* G) {int v, u, i, w, k, j, flag = 1, p[20][20][20], D[20][20];for (v = 0; v < G->n; v++)for (w = 0; w < G->n; w++){D[v][w] = G->edges[v][w];for (u = 0; u < G->n; u++)p[v][w][u] = 0;if (D[v][w] < INF){p[v][w][v] = 1;p[v][w][w] = 1;}}for (u = 0; u < G->n; u++)//中轉點for (v = 0; v < G->n; v++)//源點for (w = 0; w < G->n; w++)//終點if (D[v][u] + D[u][w] < D[v][w])//不滿足三角不等式就更新距離{D[v][w] = D[v][u] + D[u][w];for (i = 0; i < G->n; i++)p[v][w][i] = p[v][u][i] || p[u][w][i];}int da, v1 = 1, v2 = 3, v3 = 6, ab;while (flag){printf("請輸入出發點和目的地的編號:");scanf("%d %d", &k, &j);if (k<0 || k>G->n || j<0 || j>G->n)//判斷輸入是否合法{printf("景點編號不存在!請重新輸入出發點和目的地的編號:");scanf("%d %d", &k, &j);}if (k >= 0 && k < G->n && j >= 0 && j < G->n)flag = 0;printf("請選擇您的出行方式：1.步行 2.共享單車 3.小公交\n");cin >> da;if (da == 1)ab = v1;else if (da == 2)ab = v2;else if (da == 3)ab = v3;else printf("沒有該交通工具\n");}printf("%s", G->vexs[k].name);for (u = 0; u < G->n; u++)if (p[k][j][u] && k != u && j != u)printf(" *** %s", G->vexs[u].name);//輸出到某個點的最短路徑printf(" *** %s", G->vexs[j].name);if (D[k][j] == INF)printf(" 不存在通路!!!\n");else printf(" 經過此總路線最少需要%dmin\n", D[k][j] / (ab * 60)); } //查詢任意兩景點間的最短路徑void Floyd(Graph* G) {int v, u, i, w, k, j, flag = 1, p[20][20][20], D[20][20];for (v = 0; v < G->n; v++)for (w = 0; w < G->n; w++){D[v][w] = G->edges[v][w];for (u = 0; u < G->n; u++)p[v][w][u] = 0;if (D[v][w] < INF){p[v][w][v] = 1;p[v][w][w] = 1;}}for (u = 0; u < G->n; u++)//中轉點for (v = 0; v < G->n; v++)//源點for (w = 0; w < G->n; w++)//終點if (D[v][u] + D[u][w] < D[v][w])//不滿足三角不等式就更新距離{D[v][w] = D[v][u] + D[u][w];for (i = 0; i < G->n; i++)p[v][w][i] = p[v][u][i] || p[u][w][i];}while (flag){printf("請輸入出發點和目的地的編號:");scanf("%d %d", &k, &j);if (k<0 || k>G->n || j<0 || j>G->n)//判斷輸入是否合法{printf("景點編號不存在!請重新輸入出發點和目的地的編號:");scanf("%d %d", &k, &j);}if (k >= 0 && k < G->n && j >= 0 && j < G->n)flag = 0;}printf("%s", G->vexs[k].name);for (u = 0; u < G->n; u++)if (p[k][j][u] && k != u && j != u)printf(" *** %s", G->vexs[u].name);//輸出到某個點的最短路徑printf(" *** %s", G->vexs[j].name);if (D[k][j] == INF)printf(" 不存在通路!!!\n");else printf(" 總路線長%dm\n", D[k][j]); }int show() {printf(" 管理員頁面 \n");printf(" 1.景點介紹 \n\n");printf(" 2.修改景點信息 \n\n");printf(" 3.增加景點 \n\n");printf(" 4.刪除景點 \n\n");printf(" 5.增加道路 \n\n");printf(" 6.刪除道路 \n\n");printf(" 7.查看校園導航仿真圖 \n\n");printf(" 8.退出導航 \n\n");printf("請選擇相應的功能: ");int data;scanf("%d", &data);return data; }int show_1() {printf(" 游客頁面 \n");printf(" 1.景點介紹 \n\n");printf(" 2.查找任意兩個景點所需的最短時間路徑 \n\n");printf(" 3.查找任意兩個景點最短路徑 \n\n");printf(" 4.查看校園導航仿真圖 \n\n");printf(" 5.查詢起點到終點的所有路徑 \n\n");printf(" 6.退出導航 \n\n");printf("請選擇相應的功能: ");int data;scanf("%d", &data);return data; } void show0(Graph* G) {int i;for (i = 0; i < G->n; i++){printf(" %d->%s\n", i, G->vexs[i].name);} } void show3() {printf(" |----------------學生宿舍區(9)-----------------| \n");printf(" | | | \n");printf(" | | | \n");printf(" | 第三餐廳(7) | \n");printf(" | / \ | \n");printf(" | / \ | \n");printf("計算機科學與技術學院(8)-----稷下湖景區(6) \ | \n");printf(" | \\ \ | \n");printf(" | \\ 第二體育場(3) | \n");printf(" | \\ / \ | \n");printf(" | \\ / \ | \n");printf(" | \\ / \ | \n");printf(" | \\ / \ | \n");printf(" 逸夫圖書館(1)----第三教學樓(2) 大紅爐(5) \n");printf(" | \\ / | \n");printf(" | \\ / | \n");printf(" | 一號實驗樓(4)------鴻遠樓(10) | \n");printf(" | | | \n");printf(" | | | \n");printf(" | | | \n");printf(" | | | \n");printf(" |--------------------------------學校南門(0)---| \n");printf("\n\n");}//將圖信息保存到文件 void SaveFile(vector<vector<string> > c,Graph *G,int flag) {MyFileIO f;vector<string> s;//容器存放矩陣每一行的各個元素c.clear();//值為1表示只需修改景點信息，2表示只需修改道路信息，3表示需全部修改if (flag == 1|| flag == 3) {for (int i = 0; i < G->n; i++) {s.clear();s.push_back(to_string(i));s.push_back(G->vexs[i].name);s.push_back(G->vexs[i].features);c.push_back(s);//矩陣一行為一個元素}f.writeFile(verInfo, c);}c.clear();if (flag == 2|| flag == 3) {for (int i = 0; i < G->n; i++) {s.clear();for (int j = 0; j < G->n; j++)s.push_back(to_string(G->edges[i][j]));c.push_back(s);}f.writeFile(roadInfo, c);}}

第四章 測試與運行

主界面:

管理員界面：

游客界面:

最短時間查詢：

最短路徑查詢：

總結

以上是生活随笔為你收集整理的新生导游系统的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。