1/1數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告模板校內(nèi)導(dǎo)游系統(tǒng)設(shè)計(jì)

一、設(shè)計(jì)要求

1．問題描述

設(shè)計(jì)一個(gè)校內(nèi)導(dǎo)游程序，為來訪的客人供應(yīng)信息查詢服務(wù)。

2．需求分析

（1）設(shè)計(jì)學(xué)校的校內(nèi)平面圖。選取若干個(gè)有代表性的景點(diǎn)抽象成一個(gè)無向帶權(quán)圖（無向網(wǎng)），以圖中頂點(diǎn)表示校內(nèi)各景點(diǎn)，邊上的權(quán)值表示兩景點(diǎn)之間的距離。

（2）存放景點(diǎn)、名稱、簡介等信息供用戶查詢。

（3）為來訪客人供應(yīng)圖中任意景點(diǎn)相關(guān)信息的查詢。

（4）為來訪客人供應(yīng)圖中任意景點(diǎn)之間的問路查詢。

（5）可以為校內(nèi)平面圖增加或刪除景點(diǎn)或邊，修改邊上的權(quán)值等。

二、概要設(shè)計(jì)

為了實(shí)現(xiàn)以上功能，可以從3個(gè)方面著手設(shè)計(jì)。

1．主界面設(shè)計(jì)

為了實(shí)現(xiàn)校內(nèi)導(dǎo)游系統(tǒng)各功能的管理，首先設(shè)計(jì)一個(gè)含有多個(gè)菜單項(xiàng)的主控菜單子程序以鏈接系統(tǒng)的各項(xiàng)子功能，便利用戶使用本系統(tǒng)。本系統(tǒng)主控菜單運(yùn)行界面如圖7-10所示。

2．存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)

本系統(tǒng)采納圖結(jié)構(gòu)類型（mgraph）存儲(chǔ)抽象校內(nèi)圖的信息。其中：各景點(diǎn)間的鄰接關(guān)系用圖的鄰接矩陣類型（adjmatrix）存儲(chǔ)；景點(diǎn)（頂點(diǎn)）信息用結(jié)構(gòu)數(shù)組（vexs）存儲(chǔ)，其中每個(gè)數(shù)組元素是一個(gè)結(jié)構(gòu)變量，包含景點(diǎn)編號(hào)、景點(diǎn)名稱及景點(diǎn)介紹三個(gè)重量；圖的頂點(diǎn)個(gè)數(shù)及邊的個(gè)數(shù)由重量vexnum、arcnum表示，它們是整型數(shù)據(jù)。

此外，本系統(tǒng)還設(shè)置了三個(gè)全局變量：visited[]數(shù)組用于存儲(chǔ)頂點(diǎn)是否被訪問標(biāo)志；d[]數(shù)組用于存放邊上的權(quán)值或存儲(chǔ)查找路徑頂點(diǎn)的編號(hào)；campus是一個(gè)圖結(jié)構(gòu)的全局變量。

3．系統(tǒng)功能設(shè)計(jì)

本系統(tǒng)除了要完成圖的初始化功能外還設(shè)置了8個(gè)子功能菜單。圖的初始化由函數(shù)initgraph()實(shí)現(xiàn)。依據(jù)讀入的圖的頂點(diǎn)個(gè)數(shù)和邊的個(gè)數(shù)，分別初始化圖結(jié)構(gòu)中圖的頂點(diǎn)向量數(shù)組和圖的鄰接矩陣。8個(gè)子功能的設(shè)計(jì)描述如下。

（1）學(xué)校景點(diǎn)介紹

學(xué)校景點(diǎn)介紹由函數(shù)browsecompus()實(shí)現(xiàn)。當(dāng)用戶選擇該功能，系統(tǒng)即能輸出學(xué)校全部景點(diǎn)的信息：包括景點(diǎn)編號(hào)、景點(diǎn)名稱及景點(diǎn)簡介。

（2）查看掃瞄路線

查看掃瞄路線由函數(shù)shortestpath_dij()實(shí)現(xiàn)。該功能采納迪杰斯特拉（Dijkstra）算法實(shí)現(xiàn)。當(dāng)用戶選擇該功能，系統(tǒng)能依據(jù)用戶輸入的起始景點(diǎn)編號(hào)，求出從該景點(diǎn)到其它景點(diǎn)的最短路徑線路及距離。

（3）查看兩景點(diǎn)間最短路徑

C語言與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

查看兩景點(diǎn)間最短路徑由函數(shù)shortestpath_floyd()實(shí)現(xiàn)。該功能采納弗洛伊德（Floyd）算法實(shí)現(xiàn)。當(dāng)用戶選擇該功能，系統(tǒng)能依據(jù)用戶輸入的起始景點(diǎn)及目的地景點(diǎn)編號(hào)，查詢?nèi)我鈨蓚€(gè)景點(diǎn)之間的最短路徑線路及距離。

（4）景點(diǎn)信息查詢

景點(diǎn)信息查詢由函數(shù)seeabout()實(shí)現(xiàn)。該功能依據(jù)用戶輸入的景點(diǎn)編號(hào)輸出該景點(diǎn)的相關(guān)信息。例如，景點(diǎn)編號(hào)、名稱等。

（5）更改圖的信息

更改圖的信息功能由主調(diào)函數(shù)changegraph()及若干個(gè)子函數(shù)完成，可以實(shí)現(xiàn)圖的若干基本操作。例如：增加新的景點(diǎn)、刪除邊、重建圖等。

（6）查詢景點(diǎn)間可行路徑

該功能是查詢兩景點(diǎn)間全部可行路徑，由函數(shù)allpath()和函數(shù)path()實(shí)現(xiàn)，其中path()函數(shù)是直接遞歸函數(shù)。由于是無向網(wǎng)，假如網(wǎng)中的邊數(shù)許多，任意兩個(gè)景點(diǎn)間的全部路徑也會(huì)有限多，但許多路徑是無實(shí)際意義的（有近路，為什么去走遠(yuǎn)路呢？）。所以，本算法在求得的兩景點(diǎn)間全部可行路徑中，限制只輸出路徑長度不超過8個(gè)景點(diǎn)的路線。

（7）打印鄰接矩陣

該功能即輸出圖的鄰接矩陣的值，由函數(shù)printmatrix()實(shí)現(xiàn)。

（8）退出

即退出校內(nèi)導(dǎo)游系統(tǒng)，由exit(0)函數(shù)實(shí)現(xiàn)。

三、模塊設(shè)計(jì)

1．校內(nèi)抽象圖設(shè)計(jì)

以湖北其次師范學(xué)院光谷校區(qū)主要景點(diǎn)為例，抽象完成的無向網(wǎng)如圖7-7所示。全校共抽象出28個(gè)景點(diǎn)，39條道路。各景點(diǎn)分別用圖中的頂點(diǎn)表示，景點(diǎn)編號(hào)從0-27；39條道路分別用圖中的邊表示，邊上的權(quán)值表示景點(diǎn)之間的模擬距離。

2

第7章圖結(jié)構(gòu)及其應(yīng)用3

圖7-7抽象的二師院光谷校區(qū)無向帶權(quán)圖

2．模塊設(shè)計(jì)

本程序包含3個(gè)模塊：主程序模塊、工作區(qū)模塊和無向網(wǎng)操作模塊。調(diào)用關(guān)系如圖7-8所示。

圖7-8模塊調(diào)用示意圖

3．系統(tǒng)子程序及功能設(shè)計(jì)

本系統(tǒng)共設(shè)置18個(gè)子程序，各子程序的函數(shù)名及功能說明如下。

（1）mgraphinitgraph()//圖的初始化

（2）intlocatevex(mgraphc,intv)//查找景點(diǎn)在圖中的序號(hào)

（3）voidpath(mgraphc,intm,intn,intk)//打印序號(hào)為m,n景點(diǎn)間的長度不超過8個(gè)景點(diǎn)的路徑（4）intallpath(mgraphc)//打印兩景點(diǎn)間的景點(diǎn)個(gè)數(shù)不超過8的全部路徑。調(diào)用(3)（5）voidshortestpath_dij(mgraphc)//用Dijkstra算法，求一個(gè)景點(diǎn)到其他景點(diǎn)間的最短路徑，并打印

以下編號(hào)（6）－（12）是圖的基本操作。包括：重建圖、更新信息、刪除、增加結(jié)點(diǎn)和邊等。（6）intcreatgragh(mgraph&c)//建圖。以圖的鄰接矩陣存儲(chǔ)圖（7）intnewgraph(mgraph&c)//更新圖的部分信息。返回值：1

C語言與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

（8）intenarc(mgraph//權(quán)值

}arcell,adjmatrix[MaxVertexNum][MaxVertexNum];//圖的鄰接矩陣類型

4

第7章圖結(jié)構(gòu)及其應(yīng)用

typedefstructvexsinfo//頂點(diǎn)信息

{

intposition;//景點(diǎn)的編號(hào)

charname[32];//景點(diǎn)的名稱

charintroduction[256];//景點(diǎn)的介紹

}vexsinfo;

typedefstructmgraph//圖結(jié)構(gòu)信息

{

vexsinfovexs[MaxVertexNum];//頂點(diǎn)向量（數(shù)組）

adjmatrixarcs;//鄰接矩陣

intvexnum,arcnum;//分別指定頂點(diǎn)數(shù)和邊數(shù)

}mgraph;

（2）全局變量定義

intvisited[35];//用于標(biāo)志頂點(diǎn)是否已經(jīng)訪問過

intd[35];//用于存放權(quán)值或存儲(chǔ)路徑頂點(diǎn)編號(hào)

mgraphcampus;//圖變量（高校校內(nèi)）

2．系統(tǒng)主要子程序具體設(shè)計(jì)

（1）主程序模塊設(shè)計(jì)

主函數(shù)。設(shè)定用戶操作界面的顏色和大小，調(diào)用工作區(qū)模塊函數(shù)。

voidmain()

{

system("color1f");//屏幕顏色設(shè)定

system("modecon:cols=140lines=130");

mainwork();

}

（2）用戶工作區(qū)模塊設(shè)計(jì)

主要工作函數(shù)。操作區(qū)用戶界面設(shè)計(jì)。

voidmainwork()

{

intyourchoice;

campus=initgraph();

printf("\n歡迎使用校內(nèi)導(dǎo)游程序\n");printf("\n歡迎來到湖北其次師范學(xué)院!\n\n");printf("\n菜單選擇\n\n");printf("1.學(xué)校景點(diǎn)介紹2.查看巡游路線\n");

5

C語言與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

printf("3.查詢景點(diǎn)間最短路徑4.景點(diǎn)信息查詢\n");printf("5.更改圖信息6.查詢景點(diǎn)間可行路徑\n");printf("7.打印鄰接矩陣8.退出\n");printf("\n\n");printf("請輸入你的選擇：");

scanf("%d",

while(!(yourchoice==1||yourchoice==2||yourchoice==3||yourchoice==4||yourchoice==5||yourchoice==6||yourchoice==7||yourchoice==8))

{

printf("輸入選擇不明確，請重新輸入\n");

scanf("%d",

}

while(1)

{

switch(yourchoice)

{

case1:system("cls");browsecompus(campus);break;

case2:system("cls");shortestpath_dij(campus);break;

case3:system("cls");shortestpath_floyd(campus);break;

case4:system("cls");seeabout(campus);break;

case5:system("cls");changegraph(campus);break;

case6:system("cls");allpath(campus);break;

case7:system("cls");printmatrix(campus);break;

case8:system("cls");exit(0);break;

default:break;

}

printf("\n歡迎使用校內(nèi)導(dǎo)游程序\n");

printf("\n歡迎來到湖北其次師范學(xué)院!\n\n");

printf("\n菜單選擇\n\n");

printf("1.學(xué)校景點(diǎn)介紹2.查看巡游路線\n");

printf("3.查詢景點(diǎn)間最短路徑4.景點(diǎn)信息查詢\n");

printf("5.更改圖信息6.查詢景點(diǎn)間可行路徑\n");

printf("7.打印鄰接矩陣8.退出\n");

printf("\n\n");

printf("\n請輸入你的選擇：");

scanf("%d",

}//endwhile(1)

}//mainwork

6

第7章圖結(jié)構(gòu)及其應(yīng)用

（3）無向網(wǎng)操作主調(diào)模塊設(shè)計(jì)

intchangegraph(mgraph

printf("\n請問是要\n\n(1)再次建圖(2)刪除結(jié)點(diǎn)(3)刪除邊\n");

printf("\n(4)增加結(jié)點(diǎn)(5)增加邊(6)更新信息\n\n(7)打印鄰接矩陣(8)返回?\n\n");scanf("%d",printf("\n\n");

while(!(yourchoice==1||yourchoice==2||yourchoice==3||yourchoice==4||yourchoice==5||yourchoice==6||yourchoice==7||yourchoice==8))

{

printf("輸入選擇不明確，請重輸\n");

scanf("%d",

}

while(1)

{

switch(yourchoice)

{

case1:creatgragh(c);break;//重建圖，調(diào)用(6)

case2:delvex(c);break;//刪除頂點(diǎn)，調(diào)用(10)

case3:delarc(c);break;//刪除邊，調(diào)用(11)

case4:envex(c);break;//增加頂點(diǎn)，調(diào)用(9)

case5:enarc(c);break;//增加邊，調(diào)用(8)

case6:newgraph(c);break;//更新圖的信息，調(diào)用(7)

case7:printmatrix(c);break;//輸出鄰接矩陣，調(diào)用(12)

case8:return1;//返回主菜單

}

printf("\n請問是要\n\n(1)再次建圖(2)刪除結(jié)點(diǎn)(3)刪除邊\n");

printf("\n(4)增加結(jié)點(diǎn)(5)增加邊(6)更新信息\n\n(7)打印鄰接矩陣(8)返回?\n\n");

scanf("%d",printf("\n\n");

while(!(yourchoice==1||yourchoice==2||yourchoice==3||yourchoice==4||yourchoice==5||yourchoice==6||yourchoice==7||yourchoice==8))

{

printf("輸入選擇不明確，請重輸\n");

scanf("%d",

}

}//endwhile(1)

return1;

}//changegraph

7

C語言與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

（4）求兩景點(diǎn)間的全部路徑

intallpath(mgraphc)

{//4.求兩景點(diǎn)間的全部路徑

//算法中將路徑起始點(diǎn)編號(hào)m存入d[0]數(shù)組元素中，并將其頂點(diǎn)訪問標(biāo)志設(shè)置為1，即visited[m]=1//然后調(diào)path()函數(shù)求由m動(dòng)身到景點(diǎn)n的全部路徑。

intk,i,j,m,n;

printf("\n\n請輸入你要查詢的兩個(gè)景點(diǎn)編號(hào):\n\n");

scanf("%d%d",printf("\n\n");

m=locatevex(c,i);//調(diào)用2，確定該頂點(diǎn)是否存在。若存在，返回該頂點(diǎn)編號(hào)n=locatevex(c,j);

d[0]=m;//存儲(chǔ)路徑起點(diǎn)m(intd[]數(shù)組是全局變量)

for(k=0;k",c.vexs[d[s]].name);//輸出該路徑。s=0時(shí)為起點(diǎn)m

printf("%s\n\n",c.vexs[d[s]].name);//輸出最終一個(gè)景點(diǎn)名(即頂點(diǎn)n的名字，此時(shí)s==k)}

else

{

s=0;

while(sc.vexnum)

{

printf("\n你所輸入的景點(diǎn)編號(hào)不存在\n");

printf("請重新輸入：");

scanf("%d",

}//while

for(v=0;v%s",c.vexs[v].name);

printf("\n總路線長為%d米\n\n",d[v]);

}//for

}//shortestpath_dij

（6）用弗洛伊德（floyd）算法，求兩景點(diǎn)間的最短路徑并打印

voidshortestpath_floyd(mgraphc)

{//14.用floyd算法，求各對頂點(diǎn)v和w間的最短路經(jīng)p[][]及其帶權(quán)長度d[v][w]

//若p[v][w][u]==1；則u是v到w的當(dāng)前求得的最短路經(jīng)上的頂點(diǎn)

inti,j,k,v,u,w,d[35][35],p[35][35][35];

for(v=0;vc.vexnum||jc.vexnum)

{

printf("\n你所輸入的景點(diǎn)編號(hào)不存在！");

printf("\n請重新輸入動(dòng)身點(diǎn)和目的地編號(hào)：\n\n");

scanf("%d%d",printf("\n\n");

}

printf("%s",c.vexs[k].name);//輸出動(dòng)身景點(diǎn)名稱

for(u=0;u%s",c.vexs[j].name);//輸出目的地景點(diǎn)名稱

printf("\n\n\n總長為%d米\n\n\n",d[k][j]);

}//shortestpath_floyd

11

C語言與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

12

五、測試分析

系統(tǒng)運(yùn)行主界面如圖7-10所示。

圖7-10校內(nèi)導(dǎo)游系統(tǒng)主菜單

各子功能測試運(yùn)行結(jié)果如下。

1．學(xué)校景點(diǎn)介紹

在主菜單下，用戶輸入1回車，運(yùn)行結(jié)果如圖7-11所示。

圖7-11二師院光谷校區(qū)景點(diǎn)名稱及簡介

2．查看掃瞄路線

在主菜單下，用戶輸入.2回車，依據(jù)屏幕提示輸入一個(gè)景點(diǎn)編號(hào)4回車后，系統(tǒng)會(huì)給出由景點(diǎn)4到其余27個(gè)景點(diǎn)的最短掃瞄線路及最短距離。運(yùn)行結(jié)果的截圖如圖7-12所示。

不足之處：線路的編排受景點(diǎn)編號(hào)的影響，有些可能不合理。

第7章圖結(jié)構(gòu)及其應(yīng)用13

圖7-12從一個(gè)景點(diǎn)動(dòng)身的掃瞄路線圖

3．查看兩景點(diǎn)間最短路徑

在主菜單下，用戶輸入3回車，依據(jù)屏幕提示輸入一個(gè)動(dòng)身景點(diǎn)編號(hào)及目的地景點(diǎn)編號(hào)：317回車后，運(yùn)行結(jié)果如圖7-13所示。

不足之處：線路的編排受景點(diǎn)編號(hào)的影響，有些可能不合理。

圖7-13任意兩個(gè)景點(diǎn)之間的最短掃瞄路線圖

4．景點(diǎn)信息查詢

在主菜單下，用戶輸入4回車，依據(jù)屏幕提示輸入一個(gè)要查詢的景點(diǎn)編號(hào)20回車后，運(yùn)行結(jié)果如圖7-14所示。

不足之處：僅能依據(jù)景點(diǎn)編號(hào)進(jìn)行查詢，可以增加依據(jù)景點(diǎn)名進(jìn)行查詢的功能。

圖7-14景點(diǎn)信息查詢

5．更改圖的信息

在主菜單下，用戶輸入5回車后消失二級(jí)菜單界面，運(yùn)行結(jié)果如圖7-15所示。再進(jìn)一步做選擇，可以實(shí)現(xiàn)圖的相關(guān)基本操作。

C語言與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

14

圖7-15更改圖的信息

6．查詢景點(diǎn)間可行路徑

本算法在求得的兩景點(diǎn)間全部可行路徑中，限制只輸出路徑長度不超過8個(gè)景點(diǎn)的路線。在主菜單下，用戶輸入6回車，依據(jù)屏幕提示輸入要查詢的兩個(gè)景點(diǎn)編號(hào)：517回車后，運(yùn)行結(jié)果截圖如圖7-16所示。本功能由遞歸函數(shù)實(shí)現(xiàn)，所以當(dāng)圖中的邊數(shù)過多時(shí)，可能造成死循環(huán)而得不到正確結(jié)果。

不足之處：線路的編排受景點(diǎn)編號(hào)的影響，有些可能不合理。

圖7-16查詢兩景點(diǎn)間的可行路徑

7．打印鄰接矩陣

在主菜單下，用戶輸入7回車，即可輸出圖的鄰接矩陣的值。如圖7-17所示。

圖7-17圖的鄰接矩陣

8．退出

在主菜單下，用戶輸入8回車，即退出校內(nèi)導(dǎo)游系統(tǒng)。

第7章圖結(jié)構(gòu)及其應(yīng)用

六、源程序清單

#defineInfinity1000

#defineMaxVertexNum35

#defineMAX40

#include

#include

#include

#include

#include

typedefstructarcell

{//邊的權(quán)值信息

intadj;//權(quán)值

}arcell,adjmatrix[MaxVertexNum][MaxVertexNum];//圖的鄰接矩陣類型

typedefstructvexsinfo

{//頂點(diǎn)信息

intposition;//景點(diǎn)的編號(hào)

charname[32];//景點(diǎn)的名稱

charintroduction[256];//景點(diǎn)的介紹

}vexsinfo;

typedefstructmgraph

{//圖結(jié)構(gòu)信息

vexsinfovexs[MaxVertexNum];//頂點(diǎn)向量(數(shù)組)

adjmatrixarcs;//鄰接矩陣

intvexnum,arcnum;//分別指定頂點(diǎn)數(shù)和邊數(shù)

}mgraph;

//全局變量

intvisited[35];//用于標(biāo)志是否已經(jīng)訪問過

intd[35];//用于存放權(quán)值或存儲(chǔ)路徑頂點(diǎn)編號(hào)

mgraphcampus;//圖變量(高校校內(nèi))

//1.對圖初始化

mgraphinitgraph()

{

inti=0,j=0;

mgraphc;

c.vexnum=28;//頂點(diǎn)個(gè)數(shù)

c.arcnum=39;//邊的個(gè)數(shù)

for(i=0;i=0

c.arcs[n][m].adj=c.arcs[m][n].adj;

}

}

return1;

}//creatgragh

//7.更新圖的部分信息。返回值:1

intnewgraph(mgraph//計(jì)數(shù)。用于記錄要修改的對象的個(gè)數(shù)

inti,m,n,t,distance,v0,v1;

printf("\n下面請輸入你要修改的景點(diǎn)的個(gè)數(shù)：\n");

scanf("%d",

while(changenumc.vexnum)

{

printf("\n輸入錯(cuò)誤！請重新輸入");

scanf("%d",

}

for(i=0;ic.arcnum)

{

printf("\n輸入錯(cuò)誤！請重新輸入");

scanf("%d",

}

printf("\n下面請輸入更新邊的信息：\n");

19

C語言與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

for(i=1;i=0

c.arcs[n][m].adj=c.arcs[m][n].adj;

}

}

return1;

}//newgraph

//8.增加一條邊。返回值：1

intenarc(mgraph

printf("\n請輸入邊的起點(diǎn)和終點(diǎn)編號(hào),權(quán)值：");

scanf("%d%d%d",

while(mc.vexnum||nc.vexnum)

{

printf("輸入錯(cuò)誤，請重新輸入：");

scanf("%d%d",

}

if(locatevex(c,m)c.vexnum)

{

printf("\n輸入錯(cuò)誤！請重新輸入");

s