設(shè)計(jì)目的
現(xiàn)在的大學(xué)占地面積越來(lái)越大油昂，建筑物越來(lái)越多震贵，功能越來(lái)越多樣擎宝，校內(nèi)的道路也是縱橫交錯(cuò)籍铁，校園導(dǎo)航系統(tǒng)可以幫助用戶更加快速的了解學(xué)校的路線贮聂，建筑布局及建筑物的基本信息等(用戶主要是新生、家長(zhǎng)寨辩、教職工吓懈、外來(lái)參觀人員等)，在幫助用戶了解校園路線靡狞、實(shí)現(xiàn)導(dǎo)航的功能的基礎(chǔ)上耻警，校園導(dǎo)航系統(tǒng)還錄入了學(xué)校各個(gè)地點(diǎn)的相關(guān)信息，以供使用者更方便快捷的找到目的地甸怕。
隨著科學(xué)技術(shù)的不斷發(fā)展甘穿，計(jì)算機(jī)科學(xué)日漸成熟，其強(qiáng)大的功能已為人們所深刻認(rèn)識(shí)梢杭，它己進(jìn)入人類社會(huì)的各個(gè)領(lǐng)域并發(fā)揮著越來(lái)越重要的作用温兼。采用計(jì)算機(jī)進(jìn)行校園導(dǎo)航已成為衡量校園數(shù)字化的重要標(biāo)志。校園導(dǎo)航效率的好壞對(duì)于來(lái)校參觀的客人和學(xué)校管理者來(lái)說(shuō)都至關(guān)重要武契，在很大程度上影響著校園的數(shù)字化建設(shè)和學(xué)校的影響力募判。因此，本次課程設(shè)計(jì)研究的校園導(dǎo)航系統(tǒng)具有一定的使用價(jià)值和現(xiàn)實(shí)意義咒唆。
設(shè)計(jì)需求
1.從西南大學(xué)的平面圖中選取一些有代表性的景點(diǎn)届垫，抽象成一個(gè)無(wú)向帶權(quán)圖.
2.使用迪杰斯特拉算法提供最優(yōu)路徑查詢
設(shè)計(jì)內(nèi)容
該校園導(dǎo)航的使用者分為游客和管理者，功能如下：
游客
-針對(duì)游客的校園導(dǎo)航使用說(shuō)明
-查看校園全景圖全释，附有校園地點(diǎn)的所有路線情況
-輸入任意地點(diǎn)装处，查詢?cè)摰攸c(diǎn)的信息，包括地點(diǎn)介紹和相關(guān)路線
-輸入任意兩地點(diǎn)浸船，輸出兩點(diǎn)之間的所有簡(jiǎn)單路線
-輸入任意兩地點(diǎn)妄迁，輸出兩點(diǎn)之間的一條中轉(zhuǎn)次數(shù)最少的最短路線
-輸入任意兩地點(diǎn)，輸出兩點(diǎn)之間的一條帶權(quán)路徑最短的最有路線
-輸入任意地點(diǎn)李命，輸出從該點(diǎn)出發(fā)的最佳布網(wǎng)方案
管理員(除游客功能外登淘，還有以下功能)
-使用管理員功能首先需要登錄，登陸成功方可使用導(dǎo)航管理員功能
-可以在地圖中添加新地點(diǎn)
-可以在地圖中添加新路線
-可以在地圖中撤銷舊路線
-注冊(cè)新的管理員帳號(hào)
各個(gè)模塊詳細(xì)的功能描述
導(dǎo)航使用說(shuō)明：描述該導(dǎo)航應(yīng)該如何使用项戴，具有什么功能
校園平面簡(jiǎn)圖：輸出一張有校園所有地點(diǎn)的平面圖形帮，可以直觀的看出校園地點(diǎn)的分布槽惫。這是利用了每個(gè)地點(diǎn)所存儲(chǔ)的坐標(biāo)，通過(guò)對(duì)矩陣元素的遍歷辩撑，輸出了各地點(diǎn)的具體方位界斜。并且在平面圖下面以這樣的形式附有校園兩地點(diǎn)相連的所有路線信息：起點(diǎn)<—->終點(diǎn):xxx m
查看地點(diǎn)信息：任意輸入一個(gè)地點(diǎn)序號(hào)，輸出該地點(diǎn)的介紹合冀，以及所有與該地點(diǎn)連通的路線及其距離
查詢簡(jiǎn)單路徑：任意輸入兩個(gè)地點(diǎn)各薇，輸出兩地點(diǎn)間所有的簡(jiǎn)單路徑。利用圖的深度搜索遍歷君躺，用棧將經(jīng)過(guò)的地點(diǎn)序號(hào)存起來(lái)峭判，然后每條路線的地點(diǎn)逐個(gè)輸出，最后得到所有簡(jiǎn)單路徑
查詢最短路徑：任意輸入兩個(gè)地點(diǎn)棕叫，輸出兩地點(diǎn)間一條中轉(zhuǎn)次數(shù)最少的路線林螃。利用圖的廣度搜索遍歷，用隊(duì)列將要遍歷的地點(diǎn)存起來(lái)俺泣，通過(guò)對(duì)隊(duì)列的操作得到中轉(zhuǎn)次數(shù)最少的路線
查詢最優(yōu)路徑：任意輸入兩個(gè)地點(diǎn)疗认，輸出兩地點(diǎn)間一條帶權(quán)路徑最短的路線。利用迪杰斯特拉算法伏钠，通過(guò)對(duì)dist和 path的操作得出最終的最短路線
最佳布網(wǎng)方案：任意輸入一個(gè)地點(diǎn)横漏，輸出從該點(diǎn)出發(fā)的最佳布網(wǎng)方案。這是利用了最小生成樹的思想熟掂，運(yùn)用了Prim算法的思想
添加新地點(diǎn)：輸入新地點(diǎn)的名稱和坐標(biāo)缎浇，通過(guò)對(duì)文件增刪改的操作，將新地點(diǎn)存儲(chǔ)到文件里赴肚，就生成了一張新地圖
添加新路線：輸入新路線的起點(diǎn)素跺、終點(diǎn) 、距離尊蚁，通過(guò)對(duì)文件增刪改的操作亡笑，將新路線存儲(chǔ)到文件里，就生成了一條新路線
撤銷舊路線：輸入要撤銷路線的起點(diǎn)横朋、終點(diǎn)、距離百拓，通過(guò)對(duì)文件增刪改的操作琴锭，將改動(dòng)后的路線信息存儲(chǔ)到文件里
管理員的登錄：管理員可在此輸入帳號(hào)和密碼進(jìn)行登錄，在輸入密碼時(shí)也可以選擇是否隱藏密碼衙传，如果輸入帳號(hào)密碼不對(duì)應(yīng)决帖，則可重新輸入，若錯(cuò)誤三次則自動(dòng)退出系統(tǒng)蓖捶。通過(guò)對(duì)用戶輸入的帳號(hào)密碼和“admin.txt”文件里保存的帳號(hào)密碼進(jìn)行比較地回，如果相同則可登錄
管理員的注冊(cè)：管理員可在此輸入帳號(hào)和密碼進(jìn)行注冊(cè)，密碼需要輸入兩遍，相同則注冊(cè)成功刻像。通過(guò)對(duì)“admin.txt”文件增刪改的操作畅买，將新帳號(hào)和密碼存儲(chǔ)到文件里，就生成了一個(gè)新的管理員帳號(hào)
隊(duì)列的操作：有隊(duì)列的判空细睡、隊(duì)列的初始化谷羞、出隊(duì)、入隊(duì)函數(shù)
創(chuàng)建無(wú)向圖：采用鄰接矩陣的結(jié)構(gòu)溜徙，通過(guò)對(duì)“路線信息”文件和“地點(diǎn)介紹”文件的讀取湃缎，將信息存儲(chǔ)到鄰接矩陣中，然后創(chuàng)建出帶權(quán)無(wú)向圖
游客和管理員菜單：游客和管理員可在其對(duì)應(yīng)的菜單頁(yè)面進(jìn)行功能選擇
重點(diǎn)設(shè)計(jì)及相關(guān)代碼
數(shù)據(jù)結(jié)構(gòu)類型的選擇：鄰接矩陣
#define MAXVEX 50
#define INFINITY 32768
#define MAXL 20
#define MAXC 66
int visited[INFINITY];
int stack[INFINITY];
int count;
struct user //保存管理員帳號(hào)密碼的結(jié)構(gòu)體
{
char id[20]; //管理員帳號(hào)
char passwd[20]; //管理員密碼
struct user *next;
};
typedef struct //保存地點(diǎn)信息的結(jié)構(gòu)體
{
int No; //校園地點(diǎn)序號(hào)
char name[20]; //校園地點(diǎn)名
char description[200]; //地點(diǎn)描述
}Vextype;
typedef struct //鄰接矩陣
{
int arcs[MAXVEX][MAXVEX]; //邊集
Vextype vex[MAXVEX]; //頂點(diǎn)集
int vexnum; //頂點(diǎn)數(shù)目
int arcnum; //邊數(shù)目
}AdjMatrix;
typedef struct //坐標(biāo)矩陣
{
int point; //該點(diǎn)是否為校園地點(diǎn)
char name[20]; //該點(diǎn)校園地點(diǎn)名
int No; //該點(diǎn)校園地點(diǎn)序號(hào)
}SchoolMap;
typedef struct Node
{
int date; //隊(duì)列元素的值蠢壹，存儲(chǔ)地點(diǎn)序號(hào)
struct Node *next;
}LinkQueueNode;
typedef struct
{
LinkQueueNode *front; //頭指針
LinkQueueNode *fear; //尾指針
}LinkQueue;
int IsEmpty(LinkQueue *Q) //隊(duì)列判空
{
if(Q->front == Q->fear)
return 1;
else
return 0;
}
int InitQueue(LinkQueue *Q)//隊(duì)的初始化
{
Q->front = (LinkQueueNode *)malloc(sizeof(LinkQueueNode));
if(Q->front != NULL) {
Q->fear = Q->front;
Q->front->next = NULL;
return 1;
}
else {
return 0;
}
}
創(chuàng)建帶權(quán)無(wú)向圖
// 采用鄰接矩陣創(chuàng)建無(wú)向圖
int Create(AdjMatrix *G,SchoolMap M[MAXL][MAXC])
{
int i,j,weight,m,n;
FILE *fp1;
fp1=fopen("路線信息.txt","r");
//從"路線信息.txt"文件中讀取校園圖的景點(diǎn)數(shù)目和路線數(shù)目
fscanf(fp1, "%d %d", &G->vexnum, &G->arcnum);
//初始化鄰接矩陣
for(i = 1; i <= G->vexnum; i++)
for(j = 1; j<= G->vexnum; j++) {
G->arcs[i][j] = INFINITY;
}
//讀取"路線信息.txt"文件中兩點(diǎn)序號(hào)及距離嗓违，并賦值給鄰接矩陣
while(fscanf(fp1,"%d %d %d",&i,&j,&weight) != EOF) {
G->arcs[i][j] = weight;
G->arcs[j][i] = weight;
}
fclose(fp1);
FILE *fp2;
fp2 = fopen("地點(diǎn)介紹.txt", "rt");
//從"地點(diǎn)介紹.txt"文件中讀取校園圖中的景點(diǎn)名及描述
for(i = 1; i <= G->vexnum; i++) {
G->vex[i].No = i; // 將頂點(diǎn)集中的地點(diǎn)序號(hào)設(shè)為i值
// fscanf()函數(shù)是根據(jù)數(shù)據(jù)格式(format)，從輸入流(stream)中讀入數(shù)據(jù)图贸，存儲(chǔ)到argument中靠瞎，遇到空格和換行時(shí)結(jié)束。
// 數(shù)據(jù)依次是：地點(diǎn)名稱求妹、乏盐、、地點(diǎn)簡(jiǎn)介
fscanf(fp2, "%s %d %d %s", G->vex[i].name,&m,&n,G->vex[i].description);
M[m][n].point = 1;
M[m][n].No = i;
strcpy(M[m][n].name,G->vex[i].name);
}
fclose(fp2);
return 1;
}
查詢所有簡(jiǎn)單路徑：深度搜索遍歷DFS算法
void DFS(AdjMatrix *G, int m, int i, int end)
{
int j,k;
for(j = 1; j <= G->vexnum; j++){
if(G->arcs[i][j] != INFINITY && visited[j] == 0) {
visited[j] = 1;
if(j == end) {
count++;
printf("★%d.",count);
for(k = 1; k < m; k++) {
printf("%s->", G->vex[stack[k]].name);
}
printf("%s\n", G->vex[end].name);
visited[j] = 0;
}
else {
stack[m] = j;
m++;
DFS(G, m, j, end);
m--;
visited[j] = 0;
}
}
}
}
查詢中轉(zhuǎn)次數(shù)最少路徑：廣度搜索遍歷BFS算法
void BFS(AdjMatrix *G, int start, int end)
{
int vis[INFINITY];
int i, num;
int w, v;
LinkQueue *Q;
Q=(LinkQueue*)malloc(sizeof(LinkQueue));
if(start == end)
return;
memset(vis, 0, INFINITY);
vis[start] = 1;
InitQueue(Q);
EnterQueue(Q, start);
while(Q->front != Q->fear){
DeleteQueue(Q, &v);
num = v;
for(i = 1;i <= G->vexnum; i++){
if(G->arcs[num][i] != INFINITY) {
w = i; //求出當(dāng)前節(jié)點(diǎn)的第一個(gè)鄰接點(diǎn)（求出序號(hào)）
while(w != -1){
if(vis[w] == 0){
if(w == end){
BFS(G, start, num);
printf("%s->",G->vex[num].name);
return;
}
vis[w] = 1;
EnterQueue(Q, w);
w = NextAdjVertex(G, w, v);
//w是求的得第一個(gè)鄰接點(diǎn)制恍，v是相對(duì)w下一個(gè)鄰接點(diǎn)(求出下一個(gè)鄰接點(diǎn)的序號(hào))
}
break;
}
}
}
}
}
查詢帶權(quán)路徑最短：Dijkstra算法
// Dijkstra算法
void Dijkstra(AdjMatrix *G, int start, int end, int dist[], int path[][MAXVEX])
{
int mindist, i, j, k, t = 1;
for(i = 1; i <= G->vexnum; i++) {
dist[i] = G->arcs[start][i]; //對(duì)dist數(shù)組初始化
if(G->arcs[start][i] != INFINITY)
path[i][1] = start; //如果該弧存在父能，則path[i][1]為源點(diǎn)
}
path[start][0] = 1; //start加入到S中
for(i = 2; i <= G->vexnum; i++) { //尋找各條最短路徑
mindist = INFINITY;
for(j = 1; j <= G->vexnum; j++)
if(!path[j][0] && dist[j] < mindist) {
k = j;
mindist = dist[j];
}
if(mindist == INFINITY)
return ;
path[k][0] = 1; //找到最短路徑，將該點(diǎn)加入到S集合中
for(j = 1; j <= G->vexnum; j++) { //修改路徑
if(!path[j][0] && G->arcs[k][j] < INFINITY && dist[k]+G->arcs[k][j] < dist[j]) {
dist[j] = dist[k] + G->arcs[k][j];
t = 1;
while(path[k][t] != 0) {
path[j][t] = path[k][t];
t++;
}
path[j][t] = k;
path[j][t+1] = 0;
}
}
}
for(i = 1; i <= G->vexnum; i++)
if(i == end)
break;
printf("\n ★★★%s--->%s的最短路線為: 從%s",G->vex[start].name,G->vex[end].name,G->vex[start].name);
for(j = 2; path[i][j] != 0; j++) {
printf("->%s",G->vex[path[i][j]].name);
}
printf("->%s, 距離為%d m\n",G->vex[end].name,dist[i]);
printf("\n\t\t\t\t\t按任意鍵返回...");
getch();
}
最佳布網(wǎng)方案：最小生成樹Prim算法
// prim算法構(gòu)建最小生成樹
void Prim(AdjMatrix *G, int start)
{
struct
{
int adjvex;
int lowcost;
}closedge[MAXVEX];
int i, e, k, m, min;
closedge[start].lowcost = 0;
// 對(duì)除了出發(fā)點(diǎn)以外deep所有頂點(diǎn)初始化對(duì)應(yīng)的closedge數(shù)組
for(i = 1; i <= G->vexnum; i++) {
if(i != start) {
closedge[i].adjvex = start;
closedge[i].lowcost = G->arcs[start][i];
}
}
for(e = 1; e <= G->vexnum-1; e++) //控制選中的n-1條符合條件的邊
{
//選擇權(quán)值最小的邊
min = INFINITY;
for(k = 1; k <= G->vexnum; k++) {
if(closedge[k].lowcost != 0 && closedge[k].lowcost < min) {
m = k;
min = closedge[k].lowcost;
}
}
printf("\t\t\t\t\t從%s---%s:%d m\n", G->vex[closedge[m].adjvex].name,G->vex[m].name,closedge[m].lowcost);
closedge[m].lowcost = 0;
for(i = 1; i <= G->vexnum; i++) {
if(i != m && G->arcs[m][i] < closedge[i].lowcost) {
closedge[i].lowcost = G->arcs[m][i];
closedge[i].adjvex = m;
}
}
}
printf("\n\t\t\t\t\t按任意鍵返回...");
getch();
}
測(cè)試結(jié)果
初始界面
游客界面
管理員登錄
管理員界面
導(dǎo)航說(shuō)明界面
校園平面簡(jiǎn)圖
查詢景點(diǎn)信息
查詢簡(jiǎn)單路線
查詢中轉(zhuǎn)次數(shù)最少的路徑
查詢最優(yōu)路徑
查詢最佳布網(wǎng)方案
添加新地點(diǎn)
添加新路線
撤銷舊路線
管理員注冊(cè)
寫在后面
終于寫完啦＞簧瘛：瘟摺！
剛了好幾個(gè)星期＞槲ā０拧！
這個(gè)項(xiàng)目幾乎囊括了數(shù)據(jù)結(jié)構(gòu)大部分知識(shí)坡慌，在這個(gè)過(guò)程中查了不少的資料黔酥，也看了不少視頻，總結(jié)了許多洪橘。雖然這個(gè)demo還有bug跪者，后面會(huì)繼續(xù)改進(jìn)！
