校园导游咨询系统

1、1-需求分析1、1创建结点（旅游景点）创建该旅諒景2就是在啸序表中完成得，在顺序表中，首先要创建结点结构体， 将该结构体命名为SeqList,成员变量有数组1 ist与s i ze,分别用来表示最大元 素个数（即旅游景点得最大个数）与顺序表中当前存储得数据元素个数，顺序表可 以完成得功能有求当前数据元素个数，插入数据元素，删除数据元素，取数据元 素.1、2创建图在构造图得操作中包括结点得插入（实参包括AdjMGraph水G, DasTyp v ,n ,Ro wColW e i g ht E ,e）分别表示在该* G得结构体中得Se q li s t Vertices 中插入结点，在* G得结构

2、体中得edge Ma x V e rtices MaxVer t ices得边数组中插入边信息结点分别为行下标、列下标、权值，该*G得结构体 中numO f Edges,e表示边得条数，即将e得值给它。结点得顺序表初始化，在 该函数中也应包括一个结构体边信息结构体:成员包括行下标、列下标、权值.并 将该结构体命名为RowC o lWe i ght。1、3图得实现在该函数中要使用Se q Li s t头文件，在该文件中要真正进行插入边与结点首先 在该函数中应该定义一个结构体AdjMGraph,在该结构体得成员变量包括存放 结点得顺序表定义为s e q lis t Vertices、存放边得邻接矩

3、阵用ed g eMaxV e rtic e s MaxVer t ices表示，边得条数 n u mOfEd g eSo 初始化 AdjMGraph 中 得成员变量线性表与边数及存放边得邻接矩阵。然后在顺序表中插入结点，在邻 接矩阵中插入边JW除边，删除结点。取序号为V得结点得第一个邻接结点，取 序号为V 1得邻接结点V 2结点得下一个邻接结点1、4求最短路径在该函数中，应该有四个参数，两个位输入参数,分别为带权图G与源点（景点起 点）序号v 0,两个为输出参数,分别为d ist a nce与path , di s tanc e 用来 存放达到得从源点v0到其余各结点得最短距离，p a th用

4、来存放最短路径 得下标.1、从江西农业大学得平面地图中选取岀6个有代表性得景点。2、为来访得客人提供图中任意景点得路径查询，即查询任意两个景点之间得最短 简单路径。当用户输入正确时，为用户输出任意两景点得最短路径;当用户输入 不合法时，提示用户输入有误并返回让用户重新输入。3、为来访客人推荐参观最短路线.2、概要设计1 首先用邻接矩阵存储校园图.2。用数据结构知识创建校园图。3手动给校园图赋上相关信息（景点名称、代号、简介），路径及路径长度。4 利用C语言知识编写查找景点相关信息得程序。5 利用迪杰斯特拉算法计算任意两点之间得最短路径。6o最后用一个主函数m a in输出各项结果。1创建校园图

5、：(1)先定义节点个数N,边得最大值(Max weig ht),节点(景点名称、景点信息)， 邻接点，边，顶点向量,当前顶点数与边数。(2 )先给一个节点赋上其相关信息，然后再用p = (Node)malloc(sizeof (edge node)语句申请下一结点,再给所申请得节点赋上相关信息，直到节点 数为N=6为止。(3)读入道路得起始点,为邻接矩阵得边赋相应得值。时(4)节点与边得相关信息都弄好了后，校园图也就创建好了.2.利用函数Num e给1 0个节点赋上相应得名称，利用函数Informati o n给 各节点添加相应得介绍信息。3 .利用函数trav g raph来查找景点信息，要

6、查找景点名称时调用Name函数, 要查找景点介绍信息时调用I nf o rmati o n函数.4o手动创建一个校园图AdjMGraph g creat(AdjMGgr p h *G),然后为相应得 边赋上真正得值。5o用distance 数组来存放任意两景点之间得最短路径.6.用ma i n函数来输出结果:用s wi t ch语句分别输出，要创建校园图时调用 AdjMGra p hgraphc r eat函数;查找景点相关信息时调用s e arc h函数；要查找任 意两景点之间得最短路径时，先输入您U前所在得位置，再输入您得U得地，最后 调用pa th函数。3 详细设计#de f in e

7、N10#d e fine#define#includ eMAXSize2 0图中顶点数得最大值MAXedg30/图中边数得最大值s t d i o、h#inclu d e s tring h #inc 1 ude # include t y pede f i nt AdjMGraph MAXSize MAXS i ze;/ 存放邻接矩阵得 权值信息ty p ede f structi n t v exs MAXS ize；A d jMGr a p h s； / Matri x _Graph： /图得邻接矩阵表示法。ty p e d e f s tr u c t numo fedge/Mnt a

8、dj vex；邻接矩阵结点序号int length；定义道路长度ochar in fo10； 定义景点名称oc h arinfo2l 0 0； 定义景点详细信息st r uct n u mofedge * n e xt； 定义指向下一个结点得指针 n umof e dg e , *Nod e ； 将该结构体重新命名为*Nodetypedef structchar n a m e 1 0；存储景点得名称数组cha r information 100;/具体得介绍此景点信息数组s t ruct num o f e d g e次link;指向下一个景点得指针 vextices；创建景点及其信息结构体

9、typedef str u ct EdgeMnt leng h ；边得权值，表示路径长度、int i vex, jvex：表示两个连接得结点得位置变量os t ruct Edge *next：/指向下一条边得指针变量 Ed g eT y pe;/边及其信息、typ e d ef s tmctint num; 结点编号。ch a r n a me10； 结点名称 v e rtex;/ /存放结点信息结构体typed e f st r u c tover t ex v e x s MAXSize；存放结点数组元素信息ointe d ges MA XS i ze MAXSize; /存放边得邻接矩阵

10、 adj max, a dj：/表示图得结构体FILE * f p； 文件得读取vo i d clrscr () 清屏s ystem (” c 1 s )；void c r e a tgrap h ( v e xtices g, in t *n, E d geType e, a dj m axa dj) /创建校园图v extice s g 表示存放景点信息数组,n表示下一个 景点,E dgeT y p e e 表示存放边得信息数组，adj max *ad j表示下一条边得信 息数组i n t b, i,s,d,l e n;/b代表结点之间得边数s t ruct numof e dge *p,

11、 *q；定义图得结构体if (fp = fopen (“ “，” r”)= NULL) 打开文件，对文件进行读得操 作oprintf ( ”文件打开错误!n ” )：get c har ()； 获取景点信息ex i t (0)；f s canf( f p, ” % d %dn , n,&b)；/ /读入景点个数与边数for (i = 1 ; i ve x s i 、n a me, g i、n ame)； / /将景点得名 字赋给图中得结点信息。g i 、li n k = NULL;/初始化节点得下一个结点信息 f or (i = 1; i le n g h; / /将各个边得长度值记录下来ad

12、j-ed g es s d = e i、le n gh;为邻接矩阵中相应得边赋值adj- e d g e sd s = e i、le n g h y / 该矩阵为对称矩阵故 edges d s = e d g ess d ;dp = (Node)mal 1 oc (sizeof(nuniof e dge) )；/ / 为一个新得结点开辟动态空间。p n ext = NULL;/ /初始化开辟空间得下一个结点q = (Node) mallo c (sizeof (numofed g e ) ; / /为一个新得结点开辟 动态空间q- next= NULL； 初始化开辟空间得下一个结点P - a

13、djvex = d;/将边得列号给结点信息得结构体中记录邻接矩阵得序号成员。p-len gth = len;将边得长度值给结点信息得结构体中得道路成员 strcpy (p一i n fo,gd、name)； 为景点赋名称 st r cpy (p-i n fo2, g d 、info r mati o n); /为景点赋介绍信息dq一adj vex = s；/为景点赋序号，道路长度2 q 1 e n gth =1 en;Wcpy(qinfo,g s 、nam e )；为景点赋名称2 s t r c p y (qinfo2, gs、information);/为景点赋介绍信息p-ne x t = g

14、 s、link; 使P指针指向第s行得下一行，头插法建 立邻接表g s、I in k = p;使p指针指向第s行得下一行得下一行q next= g d、link;/使q指针指向第d列得下一列，头插法建立邻接表 g d 、link = q; /使q指针指向第d列得下一列，头插法建立邻接表 0printf (”校园旅游图已经建立！ nH);ge t c h ar();voi d Name(int i)swi tch （i） 为景点添加具体得名字地点case 1:M p r intf（n 1:教 n ） ;break；ca s e 2：o p r i n t f （2:二教 n）； break：ca

15、se 3:0 p rintf （” 3:五教n）； b reak;c ase 4 :pr i ntf （ ” 4：新图书馆n”）;b r e ak；ca s e 5 ：pri n tf（5：老图书馆n”）； break;case 6:printf （ 6：北区食堂 n H）;br e a k；ca s e 7 :prin t f （” 7:南区食堂n”）； break：case 8：printf （ 8：大学生活动中心n ）； break;case 9：Mpr i n tf（9:圆形报告厅n ）； bre a k；case 1 0 :printf（” 10：体育馆n”）;break;de f

16、ault：o p r int f （景点编号输入错误！请输入1一10得数字编号！ nnM）； b r e ak； / *N a me*/v oid Informa t ion（i n t i ）/*景点介绍*/swit c h（i）为景点添加介绍信息cas e 1:p r int f （“一教:这就是一栋比较古老得建筑楼，但就是当您路过这里， 会听到朗朗得读书声，很励志得地方n“）； b reak;c a se 2:op rintf （ ”二教：这栋楼真得很令人不满意，不瞧平面图很难找到，其次, 它就就是一个2得形状n“）;bre a k：6 c ase 3:p r i n tf（五教：这栋教

17、学楼应该就是新建得，总体瞧上去还令人比较 满意，周边环境也挺好得n）ibreak；ca s e 4：oprintf （”新图书馆:虽然很小，但就是还过得去，学习环境很好，还有自 修室，阅览室等学习场所n“）ibreak；case 5:oprintf （”老图书馆：很少去，听说藏得书一般就是艺术类得书籍，建筑学, 美术还有音乐方面等书籍n ”）； brea k :c a s e 6：print f C北区食堂：有时候味道太重，太咸，但就是平时味道不错，就 是学生就餐得主要餐厅。nn “）;break；case 7:sprint f （ ”南区食堂：味道偏清淡，三楼得南昌风味得快餐店味道较好n ”

18、 ）； b r ea k ;6 c as e 8 :pr i ntf（”大学生活动中心：在体育馆旁边，举办活动得主要场所，每次 晚上路过那里都会听到在举办活动，很热闹n”）； break：cas e 9:沖门ntf （”圆形报告厅：太小了，如果要求全院得人都参加专业类得报告，则会有 很多晚来得人站在后面，没有足够得座位n”）； break；Mas e 1 0：pr i nt f （体育馆：上体育课得主要场地，比较空旷，平时会有很多学 生在那里训练，打羽毛球得时候与练轮滑得时候最精彩了n”）；b reak;defaul t :Mpri n t f （”景点编号输入错误！请输入l-】0得数字编号！

19、 nnH）； break; /* I nformati on*/v oi d s earchgraph（ve x t ice s g jnt m adj ma x adj）/ / 1 查找指定景点信息6i n t i = Lflag = 1 Jen; / / le n存储要查询得景点得序号cha r c h；pr i nt f（请输入您要查询得景点序号：n”）； /提示用户输入景点序号 sea n f （” d”，& 1 en）；getchar （） ;/获取该序号对应得景点名称与景点信息P r i nt f （”此景点得名称就是:”）；Name （le n ）；oprintf （”此景点得介

20、绍就是:”）；I n formation（l e n）;ddo oprintf（就是否继续？ Y/N”）;Q scan f （n%c n，&ch）;0 g etchar（）；if（c h = Y | I ch = y ） 继续。fla g = 1；Q M = 1；6 printf（请输入您要查询得景点序号:n）；0s canf （ “ d”,&len）；0 get c h a r （）；printf (”此景点得名称就是：u ):oName (len)；P rint f (”此景点得介绍就是:“);。1 n f o rmation( 1 en);2 co n t i n u e ；o e 1

21、s eo flag = 0 ；/不继续o b r e ak：jwhil e (1)；vo i d cr e at(Mat r ix _Gra p h *G)o i n t i, j；ofor (i= 1 ； i=N； i+) Gvexsi =i； / 初始化，0 号位不用。for (i= 1 ;iv=N； i +)of or ( j =1 ； j s i j =0;/初始值为 0.。G) s 12=2； G) s 1 9 =5； /表示景点一到景点二得距离就 是2。KJ) s 2 1 =2;G s2 3 =5;G s 2 4 =4； G-s2 9=6； /将景点间得距离初始化G-) s 32

22、=5： G-s34 =7;G s 3 7 = 5;G-s 3 9 = 6； G- s 3 1 0 =6；o G-s 4 2 =4； G-s4 6 =7： G-s 4 10=7；G-s 5 6 =4;Gs57=6;G- s 5 8 =8；G- s 64 =7： G-s6 5 =4;G-s6 7=3； Gs 610= 7；oGs 7 6=3； G- s7 8 =4 ； G- s 7 10 =6;G- s 8 5= 8 ； G-s 87=4;G-s 89=9；G-s 9 1=5;Gs 9 2 =6； Gs 9 3j =6； G-) s 9 8 =9； G-s 1 0 3 = 6 ； G-s 1 0

23、4 = 7 ； G-) s 1 0 6 =7 ； G- s 10 7 =6;fo r ( i =1； i s i j =0 )G-) s i j = MAX S i z e;/没有被重新赋值得，表示两景点之间/没有路，用MAX表示无穷大.vo i d Mindistan c e(Matr i x _Grap h *G, i n t s , in t e)M n t i, j , u, c=l,t, v ;Mnt r N+l N+】；/用来存放路径上得景点.MntT N ,flag N, d N；ofor ( i =0； i=N ； i+)f or (j= 0 : jv=N； j +) r L

24、i j= 0 : / 初始值为 0.0 for (i=l ； iv二N;i+)0 T订=-l； /初始值为一1。0 flagi =1;/初始值为 1。d 订二MAX Size ；/路径长度初始值为无穷大，用MAX表示.o flag s = 0 ;/修改标识.while (c=N) “ t= MAXSiz e ；0f or( i = 1 ； is s i if(flag j & di +G- s Ti j s T i j ;v=j;0 o if (r v 0! = 1 )0002 oU= 1 ；3 0wh i le(rT 订u !=0)0000 2 ow o o r v u =r Ti u： u

25、+： dddd 0曲V ll =V；ddddd aw 吐v 0=1;Q aTc = v；dflagv = 0 ;皿 “d c =t；Q回 C+；00 pri n t f ( n nThe pa t h i s:n(%d)”，s);j=l;h ile(re j !=0) 3 printf (n-(%d) r e j) ；j+； /显示路径。o pri n tf( n n ”)；i n t main ()/主函数“ n t i, j;M a tri x _Graph G;c rea t ( &G)；in t n= 0；景点数目ve x t i c e s g MAX Si z e ；/ 1保存顶点

26、及其信息Ed g eType eMAXedg； /保存边及其信息a djmax adj; / /保存边与定点ch a r c ho i c e = x*；wh i I e (1)0 2 c lrscr();prin t f( nntt t *校园导游系统*nn”)； /提示用户正 确根据需要输入数字Qpr i n tf(n t ttk文件读入并创建校园图:nn”);o pH n tf (” t tt2、查询景点详细信息:nn ” );dprintf (”tt t 3、查找两景点间最短路径：nn)；p rintf(” tttO、退出nnH);Mpr i nt f (” Please enter

27、you r cho i c e (03) :n H)；choi c e = g etchar ();switc h (ch o ic e )。case 1:Qclrs c r();0c rea t g ra p h (g,& n , e, &adj)；/ /创建图(景点，景点数，边，边与景点)。op rintf ( ”n打开文件错误n ” );get char();break；2 c ase 2*:0 dclrs c r ()；0se a rchgraph (g, n, adj)； /查询景点信息wgetc h ar ()；break；6 case 31Qc 1 r scr()；0 Oprin

28、 t f (2您目前得位置就是：n);scan f (” d,& i )；g e tchar ();0 Opri n tfC 2您得目得地就是：n”)；oscanf (%d , & j );o 0 g e tchar ()；6Mindistan c e(&G, i, j );/查找最短路径Qg e tchar()；cr e at ( &G)；20 d o o Mp r i n tf(” 就是否继续? Y/N u )；3叱 h arch；3 Mnt f la g = 1 ;3 s c a n f ( * %c”,&ch ); oooogetc h a r ( )； noif(ch = Y II

29、ch = y *) 就是否继续000 Q w f 1 a g = 1；0 doo j = 1 ；6P r int f (”2您目前得位置就是:n )；ogoscanf(” %d”，&i);oowgetchar () ;/获取输入得数字对应得地点a pr i ntf ( w 2您得目得地就是：n )；scanf (” d”，& j )；3getch ar ()；0 mM i n d is t a n c e (& G , i,j)； / /查找最短路径ddge t char()：ere a t (&G)；0 co n ti n ue ；2Q elseoz flag = 0;不继续皿 break：

30、while(l )；Q br e ak;6c a se 01d c 1 r scr()；a pr intf(” n * 按任意键退出* *)； setc h ar ()；wex i t (0)；wb r e a k ；d e f a u It：a p rintf (n输入错误，请重新输入0-3之间得数字：n)；g e tchar ();d b r eak;0 g e tcha r ();4调试分析4、1测试数据当起点输入1 1终点输入10时，景点不存在，程序提示重新输入;当起点输入0 （教学主楼）终点输入10时，终点景点不存在，程序提示重新输入；当起点输入 3 （五教）终点输入4 （新图书馆）时，景点都存在，屏幕打印出两景点最短路径： 五教一新图书馆，最短路径约为6当输入1时，则按景点编号查询，当输入6 （北区食堂）时，屏幕上打印出此景点信息：有时候味道太重，太咸，但就是