校园导航系统的数据结构课程设计

软件学院

课程设计汇报书

课程名称______________数据构造_________________

设计题目校园导航系统

专业班级___________软件11-04班_______________

学号____________________________

姓名________________________

指导教师_____________________________

2023年1月

目录

1设计时间

2设计目的

3设计任务

4设计内容

4.1需求分析

4.2总体设计

4.3详细设计

4.4测试与分析

测试

分析................................................

4.5附录..........................................................18

5总结与展望.....................................................25

参照文献..........................................................26

成绩评估..........................................................26

1设计时间

2023年1月20日至2023年1月23日

2设计目的

数据构造是计算机专业的关键课程，是计算机科学0U算法理论基础和软件设计的

技术基础。数据构造是实践性很强的课程。课程设计是加强学生实践能力的一种强有

力手段。⑵

3设计任务

规定学生掌握数据构造的应用、算法的编写、类c语言口勺算法转换成c程序并上

机调试日勺基本措施。课程设计规定学生在完毕程序设计口勺同步可以写出比较规范口勺设

计汇报。严格实行课程设计这一环节，对于学生基本程序设计素养的培养和软件工作

者工作作风H勺训练，将起到明显H勺增进作用。[1]

4设计内容

题目：校园导航系统

设计任务：

给出校园各重要建筑欧I名称信息及有线路联通日勺建筑之间的I距离，运用校园导航

系记录算出给定的起点到终点之间的近来距离及线路。

设计规定：

1、输入各建筑信息及线路信息，构建图。

2、计算给定起点到终点之间近来距离的进行线路。

3、输出线路及总距离。

4.1需求分析

1.程序所能到达的功能；

(1)CreateDN(MGraph*G)——创立有向网G,储存学校H勺各个景点。

(2)ShortPath(MGraphG,intvO,intp[MAX_V][MAX_V],intd[])——求日勺有向网

G中某个顶点到其他顶点I向最短途径及其带权长度。

(3)menu()——目录函数，按照规定选择对应口勺功能。

2、输入日勺形式和输入值的范I制

首先输入导航功能号，只能在x至y之间进行选择；要实现两点之间最短途径导

航，需输入起点和终点号，输入的起点和终点号在所给景点号里选择；要实现某点到

2、阐明主程序的流程

图4.2-2主程序流程图

3.各程序模块之间日勺层次(调用)关系

主程序模块

口

求最短途径模块

构建有向网模块

图423各程序模块之间H勺层次(调用)关系

4.3详细设计

从流程图中口J以看出来，主函数读取顾客指令，根据指令调用函数，最终得到顾

客想要查询的信息。[1]

1.采用邻接表存储构造，定义日勺抽象数据类型：

1)typedefstructArCell寄存构造图日勺权值

(

intadj;

}ArCell,AdjMatrixEMAXVERTEXNUM][MAXVERTEX_NUM];

2)typedefstruct图中顶点表达重要景点，寄存景点的编号、名称、简介等信

息，{

charname[30];

intnum;

charintroduction[100];

}infotype;

3)typedefstruct

infotypevexs[MAX_VERTEX_NUM];

AdjMatrixarcs;

intvexnum,arcnum;

}MGraph;

MGraphb;

2.主程序以及重要函数[2]

1)主函数

voidmain(void)

(

system("color5f");/※修改控制台的)颜色信息，改为白字蓝底的|模式*/

system(z，modecon:cols=140lines=130〃)；/*设置批处理运行时窗口大小的*/

cmd();

)

2)cmd函数通过这个函数实现选择服务项目口勺内容

voidcmd(void)

I

chark;

b=InitGraph();

showl();

Menu();

while(1)

(

scanf("\n%c",&k);

switch(k)

(

case'x:

syslem(/，cls/，);

showl();

Menu();

list();

ShortestPath_DIJ(&b);

printfC----------------------------------欢迎您的使用

-\n〃）；

printf（〃\n请您继续选择服务：〃）；

break;

case'y’:

system（z，clsz，）;

Menu（）;

list（）;

Search（&b）;

printfC---------------------------------------------------欢迎您的使用

--------------------------------------------------\n〃）；

printf（"\n请您继续选择服务：〃）;

break：

case'z':

system（，，cls/，）;

printfC।-----------------------------------------------------------------1\n〃）

printf（〃|感谢使用I\n〃）

printfCI辽宁工程技术大学I\n〃）

printf（"，|智能导航系统I\n〃）

printfC1-----------------------------------------------------------------1\n〃）

exit（0）;

default:

printf（"输入信息错误!\n请输入x或y或z.\n"）;

break;}}

）

3）计算最短途径的迪杰斯特拉算法实现[1]

voidShortestPathDIJ（MGraph*G）

（

intv,w,i,min,t=0,x,flag=l,vO,vl,have[100],k;

intfinal[20],D[20],p[23][23];

while(flag)

(

printf(〃请输入起始景点编号：\n");

scanf&vO);

if(v0<0vO>G->vcxnum)

printf("景点编号不存在!〃)；

printf(〃请输入终止景点编号：\n〃)；

scanf&vl);

if(vl<0vl>G->vexnum)

printf(〃景点编号不存在！〃);

if(vO>~O&&vO<G->vexnum&&v1>=0&&v1<G->vexnum)

flag=O;

)

for(v=O;v<G->vexnum;++v)

(

final[v]-0;

D[v]=G->arcs[vO][v].adj;

for(w0;w<G->vexnum;++w)

p[v][w]=INFINITY;

if(D[v]<INFINITY)

(

p[v][vO]-l;

p[v][v]=l;

)

)

D[v0]=0;

final[vO]=l;

have[O]=vO;

for(i=l;i<G->vexnuni;++i)

min=INFINITY;

for(w=0;w<G->vcxnum;++w)

if(!final[w])

if(D[w]<min)

(

v二w;

min=D[w];

}

final[v]=l;

have[k]v;

k'+;

for(w=0;w<G->vexnum;++w)

if(!final[w]&&((min+(G->arcs[v][w].adj))<D[w]))

(

D[w]_min+G->arcs[v][w].adj;

for(x=0;x<G->vcxnum;x++)

pW[x]=p[v][x];

p[w][w]=l;

)

)

for(i-0;i<G->vexnum;i++)

{

if(p[vl][have[i]]==D(

printf(，z->%s”,G->vexs[have[i]].name);)

)

if((vl-vO)-l)printf("\n途径长度：%d\n",G->arcs[vO][vl]);

elseprintf("\n途径长度:%d\n”,D[vl]);

}//ShortestPathDTJend

4)查找函数口勺建立实现顾客对景点查找的实现：

voidSearch(MGraph*G)

(

intk,flag=l;

while(flag)

(

printf(〃请输入要查询的景点编号：〃)；

scanf("%d",&k);

if(k<0k>G->vexnum)

(

printf(〃景点编号不存在!请重新输入景点编号:〃)；

scanf("%d〃，&k);

)

ir(k>=O&&k<G->vexnum)

flag-0;

)

printfC।--------1--------------------------1---------------------------------------

------------------------------1\n〃)；

printf(〃|编号|景点名称|简介

I\n〃)；

printfC|%-4d|%-16s|%-58s|

\n〃，G->vexs[k].num,G->vexs[k].name,G->vexs[k].introduction);

printfC1--------1--------------------------1---------------------------------------

------------------------------1；

}//Searchend

5)对要进行浏览H勺地区H勺平面图输出

voidshowl（）

{printfC\t\t★★欢迎使用辽宁工程技术大学智能导航系统★★'＜）;

printf（〃\t\t\t辽宁工程技术大学葫芦岛校区平面图\n\n〃）；

printf(，z\t学校北门\n〃）；

printf(〃\t1\n〃)；

printf(〃\tI--行政楼---------静远楼\n〃）；

printf(z，\t11\n〃)；

printfC\t1耘慧楼\n"）;

printf(〃\t11\n〃)；

printf("\t11\n〃)；

printf("\t体育场尔雅楼\n〃）;

printfC\t11M);

printf(/z\t二食堂1\n〃)；

printfC\t11\n〃)；

printfC\tD楼1\n〃)；

printf(〃\tE楼一|1\n〃)；

printfC\tC楼1\n〃)；

printf(〃\t11\n〃)；

printf(〃\t小体育场，篮球场・—综合楼---------小拱桥\n〃）；

printf(/z\t111\n〃);

printf(，z\t1一食堂1\n〃)；

printf(〃\t浴池一——B楼一-A楼一-------------\n〃);

6）顾客根据显示的学校景点序号，查询景点信息:

voidlist（）

（

printf（〃学校景点列表:\n〃）；

printf（〃0:学校南门〃）；

printf（"1:静远楼"）;

printf（"2:耘慧楼〃）；

printf（〃3:尔雅楼〃）；

printf（"4:小拱桥\n〃）;

printf（"5:A楼"）;

printf（"6:B楼〃）；

printf（〃7:一食堂〃）；

printf（"8:综合楼\n〃）；

printf（"9:行政楼〃）；

printf（"10:体育场"）;

printf（〃11:二食堂"）;

printf（"12:D楼〃）；

printf（〃13:E楼\n〃）；

printf（"14:C楼"）;

printf（"15:浴池〃）;

printf（"16:篮球场、足球场\n\n〃）;

）

7）目录函数对本系统提供的服务进行提醒，以便顾客使用;

voidMenu（）

printf（〃\n辽宁工程技术大学葫芦岛校区导游图\n〃）;

printf（-------------------------------------------1M）

printf（"x.选择出发点和目的地W）

printf（〃y.查看景点信息\nO

printf（〃z.退出系统\n〃）

printf（-------------------------------------------1\n〃）

printf（〃请选择服务〃）;

）

8)对无向网口勺构建以便于实现本系统H勺功能

MGraphInitGraph(void)

MGraphG;

inti,j;

G.vexnum=17;〃顶点是17个

G.arcnum=25;〃弧线有25个

for（i=0;i<G.vexnum;i++）

G.vexs[i].num=i;

strcpy（G.vexs[0].name,'学校北门“）;

strcpy（G.vexs[0].introduction,”学校的正门,行政楼高高矗立,气势宏伟”）；

strcpy（G.voxs[1].name,〃静远楼〃）;

strcpy（G.vexs[l].introduction,”电控、电信学院用楼,设有图书馆、阅览室等。

〃）；

strcpy（G.vexs[2].name,〃耘慧楼〃）;

strcpy（G.vexs[2].intrcduction,〃软件、工商学院用楼，设有若干机房，为同学提

供更多以便。〃）；

strcpy（G.vcxs[3].name,〃尔雅楼〃）;

strcpy（G.vexs[3].intrcduction,〃学生上课、自习的I地方。"）;

strcpy（G.vexs[4].name,〃小拱桥"）;

strcpy（G.vexs[4].intrcduction,”连接生活区和教学区的|桥。〃）；

strcpy（G.vexs[5].name,“A楼〃）；

strcpy（G.vexs[5].introduction,"男生宿舍”）;

strcpy（G.vexs[6].name,"B楼"）;

strcpy（G.vexs[6].intrcduction,“女生宿舍”）;

strcpy（G.vexs[7].name,*一食堂”）;

strcpy（G.vexs[7].intrcduction,”食堂，可用饭卡吃饭”）；

strcpy（G.vexs[8].name,“综合楼〃）;

strcpy（G.vexs[8].introduction,〃校区内的）百货大楼〃）;

strcpy（G.vexs[9].name,〃行政楼〃）;

strcpy（G.vexs[9].intrcduction,〃学校行政办公场所,校区最高H勺建筑“）;

strcpy（G.vexs[10].name,“体育场”）;

strcpy（G.vexs[10].introduction,"运动会举行地〃）;

strcpy（G.vexs[ll].name,"二食堂"）;

strcpy（G.vexs[ll].introduction,〃校区最实惠日勺食堂，内有回民餐厅”）;

strcpy（G.vexs[12].name,"D楼"）;

strcpy（G.vexs[12].introduction,"男生宿舍”）；

strcpy（G.vexs[13].name,“E楼〃）；

strcpy（G.vexs[13].introduction,"男生宿舍”）;

strcpy（G.vexs[14].name,〃C楼“）;

strcpy（G.voxs[14].introduction,‘女生宿舍”）;

strcpy（G.vexs[15].name,”浴池〃）;

strcpy（G.vexs[15].introduction,“学生洗澡欧J地方”）；

strcpy（G.vexs[16].name,〃篮球场、足球场〃）;

strcpy（G.vexs[16].introduction,“比赛以及学生运动H勺地方〃）;

for（i=0;i<G.vexnum;i++）

for（j-0;j<G.vcxnum;j++）

G.arcs[i][j].adj=INFIMTY;

G.arcs[0][1].adj=50;

G.arcs[l][2].adj=15;

G.arcs[l][3].adj=40;

G.arcs[2][3].adj=30;

G.arcs[0][3].adj-90;

G.arcs[3][4].adj=30;

G.arcs[4][9].adj=1000;

G.arcs[4][5].adj=20;

G.arcs[5][6].adj=10;

G.arcs[6][7].adj=8;

G.arcs[6][8].adj=12;

G.arcs[7][8].adj=7;

G.arcs[0][9].adj=30;

G.arcs[9][10].adj=500;

G.arcs[10][11].adj=25;

G.arcs[ll][12].ad,j=8;

G.arcs[12][13].adj=5;

G.arcs[13][14].adj=10;

G.arcs[12][14].adj=10;

G.arcs[14][15].adj=150;

G.arcs[15][16].adj=3;

G.arcs[5][15].adj=15。；

G.arcs[4][15].adj=30;

G.arcs[l][11].adj=300;

G.arcs[8][14].adj=40;

for(i=0;i<G.vexnum;i++)

for(j=0;j<G.vexnum;j+4)

G.arcs[j][i].adj-G.arcs[i][j].adj;

returnG;

}//InitGraphend

3.函数H勺调用关系图。[3]

图4.3-3函数H勺调用关系图

1、

4.4测试与分析

测试

输入导航功能X

请选拄服务学校景点列表：

学技南门广静远楼2:耘慧楼3：尔雅楼4：小拱桥

5：A楼6：B楼7：一食堂8：综合楼

九行政楼10：体育场11：二福堂12：D楼13：E楼

14：C楼15：浴池16：篮球场、足球场

情输入起始景点编号:

输入起始点和终点号0和16,输出对『、川勺最短途径和途径长度；重新选择导航功

能v

请输入起始景点编号：

p

请输入终止景点编号：

巳〉学校南门一〉尔雅楼一〉小拱桥一）浴池一＞篮球场、足球场

路径长度：工53

-------------------------------------欢迎您的使用---------

请您继续选择服务J

选择导航功能y,输入，出发点2,输出景点2的简介。

请输入要查询的景点编号

景,点名称简介

静远楼电控、电信学院用楼，设有图书馆、阅览室等。

欢迎您的使用--------------------------------

清您继续选择服务:

选择导航功能3,退田导航系统。

辽赢铲

Pressanykeytocontinue

若要实现导航功能x时输入错误，输出时就无路经。重新输入起始点，结束点。

请输入起始景点编号：

番输入终止景点编号：

L12

景点编号不存在，请输入起始景点编号:

若要实现功能2时输入错误，就会提醒不存在这个地方。

京黔薪黑犒懿:景点编号

4.4.2分析

1.调试过程中碰到的问题是怎样处理的以及对设计与实现的回忆讨论和分析；

在调试日勺过程中发目前导航功能2中缺乏判断语句，使得输入错误顶点时，没有

提醒出现错误的I运行成果，在进行导航功能2之前加一种判断语句就可以了。这次欧I

程序设计重要是设计求最短途径H勺算法，这个算法比较复杂，我根据书上算法一步步

地进行分析，并通过请教同学和上网查有关程序，花费了很长时间在使得这个算法能

正常运行。

4.5附录⑴⑵⑶

ttdefineINFINITY10000

#defineMAXVERTEXNUM40

#defineMAX40

#include<stdlib.h>

#include<stdio.h>

#include<conio.h>

#include<string.h>

typedefstructArCell

(

intadj;/*途径长度*/

}ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedefstruct/*图中顶点表达重要景点，寄存景点的编号、名称、简介等信息，*/

(

charname[30];

intnum;

charintroduction[100]

}infotype;

typedefstruct

(

infotypevexs[MAX_VERTEX_NUM];

AdjMatrixarcs;

intvexnum,arcnum;

}MGraph;

MGraphb;

voidcmd(void);

MGraphInitGraph(void);

voidshowl();

voidlist();

voidMenu(void);

voidShortcstPathDIJ(MGraph*G);

voidSearch(MGraph*G);

intLocateVex(MGraph^G,char*v);

voidmain(void)

(

system("color5f〃)；/*修改控制台的颜色信息、，改为白字蓝底的模式*/

system("modecon:cols=140lines=130，/);/*设置批处理运行时窗口大小改I*/

cmd();

/********自定义函数***************/

/*cmd函数(根据目录选择要进行的项目)*/

voidcmd(void)

chark;

b=lnitGraph();

showl();

Menu();

while(l)

(

scanf("\n%c〃，&k);

switch(k)

(

case'x':

systemCcls");

showl();

Menu();

list();

ShortestPathDIJ(&b);

printf(*---------------------------------欢迎您日勺使用

---------------------------------\n〃)；

printf(〃\n请您继续选择服务:〃)；

break;

case'y':

system("cis");

Menu();

list();

Search(&b);

printfC---------------------------------欢迎您时使用

---------------------------------\n〃)；

printf(〃\n请您继续选择服务:〃);

break;

case'z':

system("cis");

printf(，z।-------------------------------------------1\n〃)

printfC|感谢使用I\n〃)

printfC|辽宁工程技术大学I\n〃)

printfC|智能导航系统I\n〃)

printfC"1-------------------------------------------1\n〃)

exit(0);

default:

printf("输入信息错误！\n请输入x或y或z.\n〃);

break;}}

}

/*迪杰斯特拉算法来计算出起点到各个顶点之间的最短途径,v0为起点*/

voidShortestPathJ)!J(MGraph*G)

(-

intv,w,i,min,t=0,x,flag=l,vO,vl,have[100],k;

intfinal[20],D[20],p[23][23];

while(flag)

(

printf(”请输入起始景点编号:\n〃)；

scanf&v0);

if(v0<0vO>G->vexnum)

printf("景点编号不存在！”)；

printf("请输入终止景点编号：\n");

scanf&vl);

if(vl<0vl>G->vexnum)

printf(〃景点编号不存在!〃)；

if(v0>-0&&v0<G->vexnum&&v1>=0&&vl<G->vexnum)

flag=0;

)

for(v=0;v<G->vexnuni;++v)

{

final[v]=0;

D[v]=G->arcs[vO][v].adj;

for(w0;w<G->vexnum;++w)

p[v][w]INFINITY;

if(D[v]<INFINITY)

p[v][vO]=l;

p[v][v]=l;

D[vO]=O;

final[vO]=l;

have[O]=vO;

for(i=l;i<G->vexnum;++i)

{

min=INFINITY;

for(w=0;w<G->vexnum;++w)

if(!final[w])

if(D[w]<min)

(

v二w;

min=D[w];

}

final[v]=l;

have[k]=v;

k++;

for(w=0;w<G->vexnum;++w)

if(!final[w]&&((min+(G->arcs[v][w].adj))<D[w]))

(

D[w]=min+G->arcs[v][w].adj;

for(x=0;x<G->vexnum;x++)

p[w][x]=p[v][x];

p[w][w]=l;

)

)

for(i=0;i<G->vexnum;i++)

{

if(p[vl][have[i]]==l){

printf(*-->%s”,G->vexs[have[i]].name);)

)

if((vl-vO)—Dprintf("\n途径长度:%d\n",G->arcs[vO][vl]);

elseprintf("\n途径长度:%d\n",DLvlJ);

}//ShortestPathDIJend

/*查找函数口勺建立*/

voidSearch(MGraph*G)

(

intk,flag=1;

while(flag)

printf(〃请输入要查询H勺景点编号:〃)；

scanf("%d〃，&k);

if(k<0k>G->vexnum)

(

printf(〃景点编号不存在!请重新输入景点编号:〃)；

scanf&k);

}

if(k>=O&&k<G->vexnum)

flag=O;

)

printf("।---------1---------------------------1------------------------------------------------------------

--------------------------------1\n");

printfC|编号|景点名称|简介

I\n〃)；

printfCI%-4d|%-16s|%-58s|

\n〃，G->vexs[k].num,G->vexs[k].name,G->vexs[k].introduction);

printf(z，1---------1---------------------------1------------------------------------------------------------

--------------------------------1\n0;

1//Searchend

voidshowl()

printfC\t\t★★欢迎使用辽宁工程技术大学智能导航系统★★"〃);

printf(〃\t\t\t辽宁工程技术大学葫芦岛校区平面图\n\n〃)；

printfC\t学校北门\n〃）；

printfC\t1\n〃)；

printfC\t1——行政楼------------------静远楼\n"）；

printf(〃\t11\n〃)；

printf(〃\t1耘慧楼\n"）;

printf(〃\t11\n〃)；

printf("\t11\n〃)；

printf(，z\t体育场尔雅楼\n〃）；

printfC\t11\n〃)；

printf(z，\t二食堂1\n〃）;

printf(〃\t11M)；

printf("\tD楼|\n");

printf(〃\tE楼一|I\n〃);

printf(^XtOS|\n〃)；

printfC\t11\n〃)；

printf(/z\t小体育场，篮球场一综合楼--------------小拱桥\n〃）；

printf(z，\t111\n〃)；

printf(〃\t1一食堂1\n〃）；

printf(〃\t浴池--------B楼一A楼------------\n〃）;

voidlist（）

（

printf（〃学校景点列表:\n〃）；

printf（〃0:学校南门〃）；

printf（〃1:静远楼〃）；

printf（〃2:耘慧楼〃）;

printf（"3:尔雅楼"）;

printf（"4:小拱桥\n"）;

printf（，z5:A楼"）;

printf（"6:B楼"）;

printf（"7:一食堂"）;

printf（"8:综合楼\n〃）；

printf（"9:行政楼"）;

printf（"10:体育场"）;

printf（"11:二食堂〃）；

printf（〃12:D楼〃）；

printf（T3:E楼;

printf（"14:C楼"）;

printf（〃15:浴池〃）；

printf（〃16:篮球场、足球场\n\n〃）;

}

/*目录函数H勺构建*/

voidMenu（）

（

printfC\n辽宁工程技术大学葫芦岛校区导游图\n〃）;

printfC।-----------------------------------------------------------------1'n"）;

printfC|x.选择出发点和目的地I\n"）;

printf（"|y.查看景点信息I\rT）;

printf（"|z.退出系统I'n"）;

printfC1-----------------------------------------------------------------1\n〃）;

printf（"请选择服务”）;

}

/*MGraph函数（图的构建）*/

MGraphInitGraph（void）

MGraphG;

inti,j;

G.vexnum=17;〃顶点是17个

G.arcnum二25;〃弧线有25个

for（i0;i〈G.vexnum;i++）

G.vexs[i].num=i;

strcpy（G.vexs[0].name,“学校北门〃）;

strcpy（G.vexs[0].introduction,“学校的正门,行政楼高高矗立,气势宏伟”）;

strcpy（G.vexs[l].name,〃静远楼“）;

strcpy（G.vexs[l].introduction,“电控、电信学院用楼,设有图书馆、阅览室等。

〃）；

strcpy（G.vexs[2].name,"耘慧楼"）;

strcpy（G.vexs[2].introduction,”软件、工商学院用楼,设有若干机房,为同学提

供更多以便。〃）；

strcpy（G.vexs[3].name,“尔雅楼”）;

strcpy（G.vexs[3].intrcduction,"学生上课、自习的I地方。“）;

strcpy（G.vexs[4].name,“小拱桥〃）;

strcpy（G.vexs[4].intrcduction,〃连接生活区和教学区的J桥。”）；

strcpy（G.vexs[5].nag"A楼〃）；

strcpy（G.vexs[5].introduction,"男生宿舍”）;

strcpy（G.vexs[6].name,"B楼"）；

strcpy（G.vexs[6].introduction,“女生宿舍〃）;

strcpy（G.vexs[7].name,*-食堂”）；

strcpy（G.vexs[7].introduction,〃食堂,可用饭卡吃饭"）;

strcpy（G.vexs[8].name,〃综合楼”）;

strcpy（G.vexs[8].introduction,“校区内欧J百货大楼〃）;

strcpy（G