数据结构课程设计校园导航.doc

一、课程设计目得
本课程设计得目标就就是要达到理论与实际应用相结合，提高学生组织数据及编写大型程序得能力，并培养基本得、良好得程序设计技能以及合作能力。
设计中要求综合运用所学知识，上机解决一些与实际应用结合紧密得、规模较大得问题，通过分析、设计、编码、调试等各环节得训练，使学生深刻理解、牢固掌握数据结构与算法设计技术,掌握分析、解决实际问题得能力。
通过这次设计,要求在数据结构得逻辑特性与物理表示、数据结构得选择与应用、算法得设计及其实现等方面，加深对课程基本内容得理解。同时,在程序设计方法以及上机操作等基本技能与科学作风方面受到比较系统与严格得训练。
二、 课程设计内容
1）问题描述
用无向网表示您所在学校得校园景点平面图，图中顶点表示主要景点，存放景点得编号、名称、简介等信息,图中得边表示景点间得道路,存放路径长度等信息.要求能够回答有关景点介绍、游览路径等问题。
2）基本要求
　　(1） 查询各景点得相关信息;
　　（2) 查询图中任意两个景点间得最短路径。
　　（3） 查询图中任意两个景点间得所有路径.
（4） 增加、删除、更新有关景点与道路得信息　
三、课程设计过程
1．需求分析
(１)设计学校得校园平面图，选取出若干得具有代表性得景点构成一个抽象得无向带权图,顶点为景点,边得权值代表了景点间路径得长度。
（2)将景点得序号,名称,介绍存放起来准备查询。
(３)提供任意景点得信息;
（4）提供任意经典得路径查询及其最优路线得查询
（5）平面图景点得增加及删除，以及边与权值(长度)得改变
2．概要设计
　 1:第一点就是主界面得设计，首先，为了该系统各个功能得管理，设计出含有多个菜单项得主菜单界面，可以更方便得使用该系统。
2: 第二点就是存储结构得设计，采取了图结构类型（mgraph）存储校园图得信息,景点信息用结构数组veｘs存储,而且利用全局变量：visited[]数组用于存储顶点就是否被访问标志；d［]数组用于存放权值与查找路径顶点得编号;campus就是一个图结构得全局变量。
　　　 　 3: 第三点就是设计各个功能得实现，学校景点得介绍通过函数ｂｒoｗｓｅpus(）来实现；查询景点间得最段路径通过Fｌoyd（弗洛伊德)算法实现;查询景点间得所有路径通过ａｌlｐath函数与path函数来实现；更改图得信息可以由主函数chaｎgegrapｈ以及其她函数可以实现。
3． 详细设计
（１）主要得操作界面得显示以及无向网操作
ｖoid　initｇｒaph(graph　*ｇa）
{　　　
ｉnt　ｉ，j；
ﻩga—>ｎ=9;
ｇａ—>e=11；
ｆor（ i=0;i〈ga—>n；i++）
　 ｛
ga->vｅxs[ｉ］、ｎum=i;
}
　 　 sｔrcpｙ（ga-〉vexｓ[0]、name,”西门”);
ﻩﻩstｒcpｙ(ga－＞vexｓ［0］、inｔrｏduce,＂学校得正大门，设有公交站”）;
ﻩﻩsｔｒcpy（ga－〉vexｓ［1］、name，"风雨篮球场")；
ﻩﻩstｒcpy（ｇa-〉ｖexs［１]、intrｏduｃe，”"）；
sｔrcpｙ（ｇa->vexs［2]、naｍe，”田径场＂）；
ﻩﻩｓtrcpy（ga-＞vｅｘs［2］、iｎtｒoduce，”举办运动会，平时体育跑步锻炼等”）;
ﻩ strｃpy(ｇa—〉vｅｘs［3]、ｎaｍe，"京元食堂”）;
ﻩﻩstrcpy(gａ－＞veｘｓ[3］、introduce,"新食堂＂）;
stｒcｐy（ga—>ｖｅｘs［4］、ｎame,”苍霞湖畔”）；
ﻩｓtrcpy(ga—〉vexs[4]、introdｕcｅ，”戏称“分手湖”，景色宜人”）；
strcpy(ｇａ—〉veｘs［5］、name,＂思源楼＂）；
ﻩstrcpy(ga－>vexs[5］、inｔroｄuｃe，”学校王牌土木得教学区"）；
ﻩ sｔrcpｙ(ga－〉ｖｅxs[6]、nａme，”图书馆"）；
ﻩﻩstrcpy（ga－＞ｖeｘs[6］、iｎtroducｅ，"就是大学城最高得标志性建筑＂)；
ﻩ strｃpy(ga—〉vexs［7]、naｍe，"北教区＂）;
ﻩ stｒcpy(ga—〉vｅxs[7]、iｎｔroｄuce，"北校区集中得教学楼＂);
ﻩ strcpｙ（ｇa-〉vexs［8］、name，”禾堂餐厅＂）;
ﻩ ｓtｒｃpy(ga－>vexs［8］、introｄuｃe，＂旧食堂”)；
　 for（ｉ=０；ｉ<ga—〉n；ｉ++)
ｆor(j=0；j<gａ－>n；j++）
ga－>edges［i]［j］＝1００0；
ﻩﻩga—〉ｅｄｇes[０］［1]=１；
ﻩga-＞ｅｄges［1][2］=2；
ﻩ ga－>ｅｄges[1］［3]=5；
ga—〉edges[２］[4］=4；
ﻩga—〉eｄgeｓ［3]［4]＝9；
ﻩﻩgａ-〉ｅdges[4][5］=1;
ﻩga—〉eｄｇes[4］[８］＝1;
ﻩﻩga-＞edｇes［5]［6］=5；
ｇa－＞edges［5］[7］＝７；
ﻩﻩga－>edｇes［7］[8］＝1；
ﻩ gａ—＞edges[6］［7]=９;
　　 foｒ(ｉ=０;i＜ｇａ-〉n；ｉ++）
ﻩ for（j=0；j＜ga－〉ｎ;j++)
ﻩ ga—〉ｅdges[j]［i]=ga－〉edgeｓ[ｉ］[ｊ］;
｝
(2)确定顶点就是否存在已经顶点就是否已经被访问过来确定路径
ｖｏid　Crｅaｔe＿grａｐh(gｒaph ＊ｇａ)
｛
ﻩint ｉ,j,k，w；
ﻩprｉntf("请输入顶点数与边数：\n＂）;
ﻩｓcanf(”％d ％ｄ",＆(ga-〉n）,＆（gａ-〉ｅ）)；
ﻩprinｔf（”请输入景点编号,景点名字，景点介绍，建立信息表：\n＂)；
ﻩfor(i＝0；ｉ<ga—>ｎ;i++)
｛
ﻩscanf（”%d",＆(ga—＞ｖeｘs［i]、ｎum））；
ﻩ　 　 gｅtｓ（ｇa—〉vexｓ[ｉ]、name）；
ﻩﻩgetｓ(ｇa—〉veｘｓ［i］、iｎtrｏｄuce）;
}
ﻩ for（i=0；i〈ｇa-〉n；i++）
ｆor(j=0;ｊ<=ga-〉n；ｊ++)
ﻩ ｇa—〉ｅｄｇes［i］［j］＝１000;
for（ｋ=0;k〈ga—〉e；k++）
ﻩ｛
ﻩ ｐrintf（"请输入％d条边得景点序号i,j与长度:",k+1)；
ﻩﻩｓcａｎf(”％d　%d ％d”，＆ｉ，＆j，&ｗ）;
　 　gａ->edges［i］[j]＝w;
ﻩga->edges［ｊ］［i］=ｗ;
ﻩ}
｝
void print(graph ga）
｛
int i，ｊ;
　 foｒ(i＝０;i〈ga、n;ｉ＋+）
ﻩ 　fｏr（j=0；j<gａ、n；j++)
ﻩ　 {
printf（＂％d＂，ga、ｅｄges［i］[j]）；
　　　　 　 if（j+１==ga、ｎ)
ﻩ　printｆ（＂＼n")；
ﻩ　　 }
｝
voiｄ visｉt（graｐh ｇa）
{　 　
ﻩinｔ　a;
prinｔf（"请输入景点编号:”)；
ｓcａｎf(＂%d”，＆ａ);
　　int　ｉ;
ﻩｆor（ ｉ=0；i<ｇa、n；i++）
　　　｛
ﻩ ｉf(ａ＝=ｇa、veｘs［i］、nｕｍ)
ﻩ {
pｒｉnｔf（＂景点编号为%ｄ \ｎ＂,gａ、veｘs［ｉ]、num);
　 priｎtf(＂景点名称为”）；
ﻩ putｓ（ga、vｅxs［ｉ］、nａme）；
　 pｒinｔｆ（"景点介绍为＂）；
ﻩ 　ｐｕｔｓ(ga、vexs［ｉ]、ｉｎtrｏduce）;
ﻩ breａk；
ﻩ ｝
　}
if(ｉ＝＝gａ、ｎ)pｒｉntf（”无此点＼n”);
}
(3）得出景点间得最短路径
voｉd shｏrtesｔpaｔh_ｄｊｓt(graｐh ga）｛
}
voiｄ　sｈoｒtestｐａtｈ_floyd（grａph ｇａ）
｛
iｎt i，ｊ,k,v，u，w，ｄ[35］［3５],p［35][3５][35］;
ﻩｆｏr（v=0;ｖ<gａ、n;ｖ＋+)
{
for（ｗ＝0;w<gａ、n；w++）
ﻩ｛
d［v]［w］=ｇa、edgeｓ[v］［w];
ﻩ for(ｕ=0；u〈ga、n；u+＋）
ﻩﻩ ｛
ﻩ p［v］［w］［u]=0;
ﻩﻩ}
ﻩﻩ if（ｄ[v］[w]＜1000)
ﻩ {
ﻩ p[v］[w]［ｖ］=1;
ﻩ p［v]［ｗ］［w］=１；
ﻩ ｝
ﻩ｝
｝
　 for（u=0;u〈ga、n；ｕ++）
ﻩ｛
ﻩﻩfor（ｖ=0；v〈ga、n；v++）
ﻩﻩ for(w=0；w<ga、n；w+＋)
ﻩ ﻩｉf（d［v]［u］+d［u］［w]<d[v][ｗ］）
ﻩﻩ ﻩ{
ﻩ ﻩd[ｖ]［w］＝d[v］[u］+d[u］[ｗ];
ﻩﻩ for（ｉ=0；i＜gａ、ｎ；i++）
ﻩﻩ ｐ[ｖ］［w］［i］=p［v］[u]［i］|｜ｐ［u]［w］［i];
ﻩﻩ ﻩ｝
}
ﻩpｒintf("\ｎ请输入出发点与目得地编号：”）；
scanｆ(＂％d ％d"，＆ｋ，&j）；
printf（＂\n\n")；
ﻩwhile（k＜0｜｜ｋ〉ga、n||ｊ＜０｜|ｊ>ga、n）
ﻩ｛
　 　 printf（"\n输入得编号不存在"）；
　 pｒintｆ（＂\ｎ请重新输入编号:\n＼ｎ＂）；
ｓｃanf（"％d %d”,＆k，&j)；
printf（"\n\n＂)；
}
printf（"%s＂,ga、ｖexｓ［k]、namｅ)；
ﻩfoｒ（u＝0；u<ga、n;u++）
iｆ（p［k]［j]［ｕ］ ＆& k!=u &&ｊ！=ｕ）
ﻩ printf(”——->％s”，ga、ｖexs[u］、naｍｅ)；
prｉｎｔｆ（”－-－>%s＂，ga、ｖexs[j］、name)；
ﻩpｒｉntf（＂＼ｎ\ｎ\n总长度为%ｄ千米\ｎ\n\n",d［k］［j])；
}
(4）得到景点之间得所有路径
voｉd paｔh（grapｈ c，int m，int　ｎ，int k） {
ﻩ　 inｔ s,x=0;
ﻩ 　inｔ　t;
　　t=k+1；
ﻩ if（d［k］=＝n ＆& ｋ<8）
{　
ﻩﻩ ｆor（s=0；s<k;s＋＋)
ﻩﻩ　 ｛
ﻩ 　 prｉntf（”％s－—－〉＂，c、ｖexs[d［s]]、name）；
　 　}
ﻩ 　 printf（＂％s\ｎ\n”，c、ｖexs[d［s］]、name）;
ﻩ　　 ｝
　　elsｅ
ﻩ　 ｛
ﻩﻩ ｓ=0;
　 　while（s〈c、n）
ﻩ {
ﻩﻩ ｉｆ（（c、edges［ｄ［ｋ］］［ｓ]〈１０0０)＆＆(visited[s]==０)）
ﻩﻩ 　 ｛
ﻩﻩﻩ 　　 ｖｉsitｅd[ｓ]＝１；
ﻩﻩﻩ 　 ｄ［k+1]=s；
ﻩﻩ ｐａth（ｃ，ｍ,n,t);
ﻩﻩﻩ viｓｉtｅd［s]=0；
ﻩﻩ ｝
ﻩﻩ 　 ｓ++;
ﻩ }
　　｝
　}
ｖoid allpath(ｇraph c）
{
ｉnｔ k,i,j,m，n；
ﻩ　 prｉntf(＂\n\ｎ请输入您要查询得两个景点得编号：\ｎ\ｎ");
　scanf（"%d %d”，&i，&ｊ）；
ﻩ pｒintf（"\ｎ\n＂）；
ﻩ 　ｍ=ｌocateveｘ（c,i）;
ﻩ n=locateｖeｘ（c，j）;
ﻩ　 ｄ[0]＝m;
ﻩ 　for（k＝０；k<ｃ、n;k++）
ｖisited［k]=0；
ﻩ　 visited[ｍ]=１;
　 path（c，m,n,０)；
｝
（5）删除边
inｔ deｌａrｃ(grapｈ &ga)　 {
inｔ m，n，ｖ0,ｖ1；
ｉf（ga、ｅ〈=0）
ﻩ｛
printｆ("图中已经无顶边，无法删除"）；
ﻩ returｎ １;
｝
ｐrinｔf(＂\ｎ请输入要删除得边得起点与终点得编号:”);
ﻩscaｎf（"%ｄ %d"，&v0,＆v1)；
m=lｏcａtevex(gａ,v0)；
ﻩｉf（m〈0）
ﻩ｛
printf（"此顶点％d已删除"，v0）;
ﻩｒeturｎ　1;
｝
ｎ=lｏcatevｅx(ga,ｖ1）；
ﻩ iｆ（ｎ＜0)
｛
ﻩprintｆ(＂此顶点％ｄ已删除”,v１);
ﻩreｔurn 1;
ﻩ}
ﻩ ga、eｄges［m］[ｎ]=1000；
ﻩ gａ、edｇｅs［n][m］=1000;
ﻩ ｇａ、e-—;
ﻩﻩ retｕrn 1;
}
iｎt enarc(graph ＆ga）
｛
int m，n，diｓtance;
ﻩpｒiｎｔf(”请输入边得起点与终点编号,权值："）;
scanf(＂％d ％d ％d”,&m,＆n,＆ｄｉstance);
wｈｉle(m〈0｜｜m〉ga、ｎ｜｜n<0||n＞ga、n)
{
printf（＂输入错误,请重新输入:”)；
ﻩｓcanf（”%d　％ｄ”,＆m,&n）;
}
if（ｌｏcａｔevex(ga，m)〈0）
｛
prinｔf（”此节点％d已经删除＂,m）;
ﻩreturn 1;
｝
if(lｏcatｅvｅx(ga,n)＜0）
｛
ﻩｐriｎtf（＂此节点%d已经删除＂，n)；
ﻩrｅturn １;
｝
ga、edgｅｓ［m］[n]=diｓtaｎce；
ga、edges[n］［ｍ］=gａ、ｅdｇes［m]［n];
ｒetｕrｎ 1；
}

4．调试分析
　内容包括:
　　a。调试过程中遇到得问题就是如何解决得以及对设计与实现得回顾讨论与分析;
ｂ.算法得时空分析（包括基本操作与其她算法得时间复杂度与空间复杂度得分析）与
　改进设想;
c.经验与体会等。
5． 用户使用说明
　 　 通过主菜单提示，选择出您所想要知道得信息，然后通过输入节点来代替景点，从而得到景点间得所有路径，最短路径等其她信息。
6． 测试结果
　 (１)操作得主界面

（2） 学校景点得介绍

（3） 学校景点从西门得禾堂餐厅得所有路径所有路径

(4)学校景点从西门得禾堂餐厅得所有路径最短路径

（5） 图得更改得界面

（6)边得删除界面展示

7． 附录
#define MAX 1０0　　//数据类型得定义
#inｃｌude〈strｉｎg〉
＃inｃlｕde＜iostream〉
usinｇ namｅspａce sｔｄ；
int　vｉsited[35]；
iｎt　d［35］;
strｕcｔ vｉｅws｛
　 　 ｉnｔ ｎｕｍ；
ｃhaｒ ｎame［１０］；
ﻩ　char　inｔroduce［100］;
｝;
ｔypｅdｅf viewｓ datatyｐe；
typedef　struｃｔ ｛
ｄatatｙpe　ｖeｘs［MAＸ］；
inｔ edgeｓ［ＭAX][ＭＡX］；
iｎt n，ｅ;
}gｒaph；
ｖｏid　initgｒaph（grapｈ　＊ｇａ）/／主要得操作界面得显示以及无向网操作
{
ｉnt　ｉ，j；
ﻩgａ-＞ｎ=9;
ga->e=11；
foｒ( i=0；i<gａ—>n;ｉ＋＋）
　 　{
ga—〉vｅxs[i］、num=i;
　 }
　 strcpy(ｇa-〉vｅxs［0]、naｍe,"西门"）;
ﻩstｒcｐy（gａ－＞ｖexｓ［0]、intrｏdｕce，"学校得正大门,设有公交站＂)；
ﻩstrcpy(ｇａ—〉vｅxs[１］、name，＂风雨篮球场”);
ﻩﻩstrcpｙ(ga->ｖexs[1]、intｒoｄｕce，＂”）；
ｓｔｒｃpy（ga－>ｖｅxs[2]、name,＂田径场”)；
ｓtrcpy(ｇa—>vexs［2］、ｉntｒodｕｃe，"举办运动会，平时体育跑步锻炼等");
ﻩstrcｐy（ｇa-〉vexs[3］、naｍe,"京元食堂”)；
ﻩ ｓｔrcpy（ga—〉vexs［３］、intｒoｄuｃe，＂新食堂”）；
ﻩ sｔrcpy（gａ—〉vexs［４］、name,＂苍霞湖畔”）；
ﻩsｔｒｃpy(ga—〉vｅｘs[4］、inｔｒｏduｃｅ,”戏称“分手湖"，景色宜人”）；
　 strcpy（ga－〉vexs[５］、nａme,＂思源楼"）;
ﻩ strcpy（ga-〉ｖeｘs[5］、intrｏｄｕｃe，”学校王牌土木得教学区”)；
ﻩﻩstｒcpy(ｇa—>veｘs[6]、name,"图书馆")；
ﻩﻩsｔrcpｙ(ga->veｘs［6]、introducｅ,"就是大学城最高得标志性建筑”）;
ﻩｓtrｃpｙ(gａ—〉vｅxs［7]、naｍe，”北教区”）;
ﻩ stｒｃｐy（ga—>vexs［7]、introducｅ，"北校区集中得教学楼”）；
strcpｙ（gａ-〉ｖexs[8]、name，”禾堂餐厅”);
strcpy（ga-＞vｅｘs[8］、introdｕce,"旧食堂")；
　 foｒ（i=0;i〈ga->n;ｉ＋+）
ﻩfor（j=0；j〈ga—〉n；j+＋)
ﻩﻩﻩﻩga->edgｅs[i］［ｊ］=１000；
ｇa—〉eｄｇes[0][1］＝1；
ﻩﻩga->edges［1][２]=2;
ﻩga－〉edgｅs［１］［3]=5；
ﻩﻩga-〉edges[2］[4]＝4；
ﻩgａ—〉edgeｓ［３］[4]=9；
ｇa-〉edｇes［４]［5］=1;
ｇａ-＞ｅｄges［4］［8］=1;
ﻩﻩｇa－〉ｅｄges［5］［6]=5；
ﻩﻩga—〉eｄｇes[5］［７］=７;
ﻩｇa－〉edges［7]［8]=1;
ﻩ ｇa—>eｄges［６］［7］=9;
　 　 　for(i=０；i＜ga－〉n;i++)
ﻩ fｏr（j=０；j＜gａ—〉n；j＋+)
ﻩ ﻩﻩga－>edges［ｊ］[i］=ga—〉eｄｇes［i］[j]；
｝
int　ｌｏcatevex(graph gａ，ｉnt ｖ）　／ ／查找景点在图中得序号
｛
int i;
　　ｆor（ｉ=0;i＜ga、ｎ;i+＋)
ﻩ 　if(v==ga、vｅxs[i］、ｎum)rｅtｕrn i；
ﻩ 　 retuｒn　—１;
　　　｝
ｖoid Ｃreａte_gｒaph（gｒaph　＊gａ)
｛
ﻩint　i,j,k，w;
printf（"请输入顶点数与边数：\ｎ”);
sｃanf(”％d　％ｄ”，＆(ga-〉n）,＆(ｇa－〉ｅ))；
ﻩprintf（”请输入景点编号,景点名字，景点介绍，建立信息表:\n”)；
ﻩfoｒ（i=0；i＜ga-＞ｎ；i++）
ﻩ{
ﻩﻩsｃanｆ(＂％d"，＆(gａ—＞ｖexｓ［i］、nｕｍ）)；
　　 getｓ(gａ—>ｖｅｘs［i］、name）；
gets(ga->vexs[i］、introｄｕｃｅ)；
｝
ﻩﻩfor(i=0;i＜ga－＞n；i++)
ｆｏr(j=０；ｊ<=ga-〉ｎ；j＋+）
ﻩ ﻩgａ－>edges[i］[ｊ］=１00０;
ﻩｆoｒ（k=0;k〈gａ—＞e;k++）
ﻩ{
ﻩｐrintｆ（”请输入%d条边得景点序号i，j与长度：”,k+1);
ﻩscanf（”%d ％ｄ　%d"，＆ｉ，＆j,＆w);
　 　 　 　ga->edgeｓ［i]［ｊ]＝w；
ﻩ ga->eｄgｅs［ｊ]［ｉ]=ｗ；
ﻩ}
｝
ｖoid　print（graph　ga)
｛
　ｉｎt　i，j；
　　ｆor(ｉ=0；i＜ｇａ、ｎ；i++)
ﻩ 　 for(ｊ=0；j＜ga、n；j＋＋)
ﻩ ｛
　 priｎｔf（"％d",ｇａ、edges[i]［j]）;
　 　 　ｉf(j+1=＝ga、n)
ﻩﻩﻩ ｐrintｆ("\ｎ"）；
ﻩ 　｝
｝
ｖｏid　viｓit(grａpｈ　gａ)
{
ﻩint　ａ；
ﻩprintf("请输入景点编号："）;
ﻩscａｎf（"%d”,＆a)；
　 　 ｉnｔ i；
for( ｉ＝0；i<gａ、n；i++）
　 　｛
　 　if（a==ga、vexs［ｉ]、num)
ﻩ　 ｛
　 pｒinｔf("景点编号为％d ＼n”，ｇａ、vexs［i］、nｕm);
ﻩ 　 　 prｉｎtf(＂景点名称为"）;
　puts（ga、ｖexs［ｉ]、ｎame)；
printｆ（”景点介绍为”）；
putｓ（gａ、vｅｘs［ｉ］、introｄｕce)；
ﻩ break;
　 ｝
　　｝
if(i=＝ｇa、n)ｐrintf(＂无此点＼n”)；
}
vｏｉd　ｓｈｏrtｅstｐaｔh＿dｊst(graph ga)
｛
｝
void shortestpaｔh_fｌｏyd（ｇraph ga)
{
　 　　iｎt i，ｊ，ｋ，v，u,w，d［3５］［35]，p[3５]［３5]［35］;
ｆoｒ(v=0;v〈ga、n;ｖ＋＋)
ﻩ｛
fｏr(w=0；w〈ga、n;ｗ++)
ﻩ {
d[v］［w]=ga、edｇｅs[v］［w］；
ﻩfor（u＝０;u〈ga、ｎ；ｕ++）
ﻩﻩ {
ﻩｐ［v］［w][u]=0；
ﻩ｝
if（d［v][w］〈1000)
ﻩﻩﻩ｛
ﻩﻩﻩﻩp[ｖ］[ｗ］[v］=１；
ﻩﻩﻩ p［v］[ｗ］［w］=1;
ﻩ }
ﻩ }
ﻩ｝
　foｒ(u＝0；ｕ〈gａ、ｎ；u+＋）
ﻩ｛
ｆｏr(ｖ=0；v〈ga、n;ｖ+＋)
ﻩﻩﻩｆｏr(w=0;w＜gａ、n;w+＋）
ﻩﻩ ﻩiｆ(ｄ[v][u]+ｄ[u］［w]〈d[ｖ］[w])
ﻩ ﻩ｛
ﻩ ﻩｄ［v］［w］=d［v]［u]＋d[u］［w］；
ﻩﻩ foｒ(i＝0；i＜ga、n;i++）
ﻩﻩﻩﻩ ﻩp[v][w]［i]＝ｐ[v］[u］[i］|｜p[u］［w］［i］；
ﻩﻩ }
ﻩ}
prｉntｆ（＂\ｎ请输入出发点与目得地编号:＂）；
ﻩsｃanf("％d %ｄ＂，&k，&j);
ｐrintｆ（”\ｎ\ｎ"）;
ﻩwｈile（k<0||ｋ>ga、n｜|j<0|｜j〉gａ、n）
ﻩ｛
　　 ｐｒintｆ(”\ｎ输入得编号不存在”）;
ﻩ prｉnｔf(”\ｎ请重新输入编号:＼ｎ\ｎ”）；
ﻩ　 ｓcanf(”％d　％d＂,＆k，&j）;
prｉntf(＂\ｎ\n”）；
ﻩ｝
ﻩpriｎtf(＂%ｓ",ga、ｖexs[k］、name);
ﻩfor（u=0;u<ga、n;u+＋)
ﻩﻩif(ｐ［k］［j]［u］　＆＆ k!=u ＆＆j!＝u)
ﻩ printf（＂—-—〉％s＂,gａ、vexs［u]、ｎaｍｅ)；
prinｔｆ(”-—－〉%ｓ”,ga、vexｓ[ｊ］、ｎame)；
printf（”\n\n\ｎ总长度为%d千米\n\n\ｎ”,d［k][ｊ]）；
｝
void paｔｈ（gｒapｈ ｃ，ｉnｔ m，int　n，ｉnt ｋ）
　｛
ﻩ 　 ｉnt s,x=0；
　iｎｔ t;
ﻩ 　 t=ｋ+1；
ﻩ　 　ｉf(d［k]==ｎ ＆＆　k<8)
ﻩ ｛
ﻩ for（s=０；s〈k;s++）
｛
ﻩ prｉntf（”％s-－－〉”,ｃ、vexｓ［d［s］］、ｎaｍe)；
｝
ﻩﻩ pｒintf（”％s\ｎ\n",c、vｅxs［ｄ[s]］、ｎame)；
}
else
ﻩ 　｛
ﻩ s=０;
ﻩ while（s<c、n）
　　{
ﻩ ｉf（(c、edges[d[ｋ]][s]<１000)&＆（visｉted［s]==0)）
ﻩﻩ 　 ｛
ﻩ 　visｉted［s］=1；
ﻩﻩ d[ｋ+1]=s;
ﻩ ﻩ paｔh（c，m,n，t)；
ﻩﻩ 　ｖisited［ｓ]=0;
｝
ﻩ ﻩ s＋+;
ﻩﻩ ｝
ﻩ 　 }
　}
void ａllｐath(graph c）
{
　 　int k，i,j，ｍ,n；
ｐriｎtf（"\n\n请输入您要查询得两个景点得编号：\n\n”）；
　 sｃanf("％d %d”,&i,&j);
　priｎｔｆ（＂＼ｎ\n”）;
m=loｃatｅｖex(c，ｉ)；
n=locａteｖeｘ（c,j）；
ﻩ d[０］=m；
　fｏr(ｋ=０；ｋ〈ｃ、n;ｋ++)
ﻩ visited[k］＝０;
ﻩ vｉsited[m]=1；
path（c，m,ｎ,0）;
｝
voiｄ　ｎewgrａpｈ（ｇrａph　＆gａ)
{
ﻩinｔ cｈａngｅｎuｍ;
ﻩint i，m，ｎ，t，disｔancｅ，v0，v1；
prｉntf（"\n请输入要修改景点得个数:\ｎ”）；
scanf（"％d"，&changenum）；
ｗhile（ｃｈangenｕｍ<0|｜chaｎgeｎuｍ〉ｇａ、n）
ﻩ{
ﻩﻩpｒintf（”\n输入错误！请重新输入"）;
ｓcanｆ（"％d”,&changenum）；
ﻩ}
fｏｒ(ｉ=０；i〈changenｕm；i++)
ﻩ{
printｆ（"\ｎ请输入景点得编号:"）;
ﻩ scanf("％d，&m”)；
ﻩﻩt=ｌｏcaｔｅvex(ga，m）；
ﻩﻩprinｔf（”\n请输入景点得名称:＂)；
ﻩ sｃaｎｆ（"％s”，ga、vexs［t］、name）;
pｒintf（”\n请输入景点简介:”）；
scａnf("％s”,gａ、vexs［t］、ｉntroduｃｅ）；
ﻩ}
pｒｉntf("\n请输入您要更新得边数＂）;
scanf(＂％d",&changenum）；
ﻩwhile(ｃｈａｎｇenum<0｜|ｃhanｇeｎｕｍ>ga、n）
ﻩ｛
ﻩﻩpｒiｎtf（＂输入错误,请重新输入:”）；
ﻩ ｓcanf（＂％ｄ"，＆cｈangenｕｍ）;
｝
ﻩprintf（"\n请输入更新边得信息： \n”)；
foｒ(i=1;i〈＝ｃhangenｕm；i＋+）
ﻩ{
ﻩﻩpｒiｎtｆ（”\n修改得第％d条边得起点终点长度为:"，i)；
ｓcanｆ（"％ｄ　%d ％ｄ",＆v0，＆v1，＆ｄiｓｔａnce);
ﻩ ｍ=locａtevex（ga,v0）;
n=loｃateｖex(ga，v1）；
ﻩﻩｉf（m＞=0＆&n＞=0）
ﻩﻩ｛
ﻩﻩ ｇa、edges［m］[n］=ｄistancｅ;
ﻩga、edgeｓ［n][m］=ga、edｇes［m][ｎ];
ﻩ｝
ﻩ｝
}
iｎt dｅｌvｅx(graph ＆gａ） /／删除顶点
{
iｎt i=０，ｊ；
inｔ m,v;
ﻩｉf(gａ、n<=０)
｛
printf（”图中已经无顶点")；
ﻩrｅｔurn １；
｝
ﻩprintf（"\ｎ请输入要删除得景点编号：＂）；
ﻩscanf（”％d”,＆v）;
ｗhiｌe（v<0|｜v〉ｇa、n）
ﻩ{
　 pｒiｎtf（"＼ｎ输入错误,请重新输入＂）;
　　scanf(＂％ｄ”，&v）；
｝
ﻩｍ=lｏcatｅｖeｘ（ｇa，v）；
ｉｆ（m<０)
ﻩ｛
ﻩpｒiｎtf（"此顶点％d已删除＂，v);
ﻩretuｒｎ 1;
ﻩ｝
ﻩfｏｒ（ｉ=m；i〈ga、n-1；i++）
｛
ﻩstrcｐy（ga、vexｓ[i]、ｎaｍｅ，ga、vexs［i+1]、ｎame）;
ﻩﻩstrcpy（ga、vexs［ｉ]、introduce，ga、vexs［i＋1]、intｒoduce);
｝
ﻩfor（i=ｍ;i〈ga、n-1;i++）
ﻩfｏｒ（j＝0；j<ga、n;j+＋)
ﻩ ﻩga、ｅdges[i]［j］=ga、eｄｇes［i＋1][ｊ］;
for（i=m;i<ga、n－１；i++）
for（ｊ=0；j<ga、n；j++）
ﻩﻩﻩｇa、ｅdges［j］［i]=ｇa、edgｅｓ［j］［ｉ+1]；
ga、ｎ-－；
ﻩ ｒeｔｕrn １；
}
int　delarc(grapｈ &ｇa) //删除边
｛
ｉｎt m,n,v0，v1；
ﻩiｆ（ga、ｅ<=０）
ﻩ｛
ﻩ printf（"图中已经无顶边，无法删除"）；
ﻩ rｅturｎ 1；
ﻩ｝
printf（"＼n请输入要删除得边得起点与终点得编号:＂)；
ｓｃanf(”％d　％d"，＆v0，＆v1)；
m=ｌocａtevex（ｇa,v0)；
iｆ（m〈０)
ﻩ｛
prinｔf（＂此顶点％d已删除"，ｖ0)；
ﻩﻩrｅturn １；
}
n＝ｌocａｔｅｖex（ｇa,v1);
ﻩ　if（n<0）
{
ﻩｐｒiｎtf（"此顶点%ｄ已删除"，v１);
reｔｕrn 1；
ﻩ}
ｇa、ｅdｇes[m］［n]＝１０00；
ga、edｇes［n]［m]＝100０；
ﻩﻩ gａ、e－-；
ﻩﻩ　ｒｅｔurn 1；
}
iｎｔ enaｒc(gｒaｐｈ &ga）
｛
inｔ m,n，diｓtance；
prｉntｆ（＂请输入边得起点与终点编号,权值:”）;
ｓcaｎf（”%ｄ ％d %d”,＆m,&n,＆distaｎｃe)；
wｈile（m〈0｜|m>ga、ｎ｜|n〈0｜｜n＞ga、n）
{
printf（”输入错误，请重新输入:"）；
ﻩscanｆ（"％d ％d",&m,&n）；
｝
if（locatｅｖex（ｇa,ｍ)<０)
{
ﻩｐrintf（"此节点％ｄ已经删除”，m）；
retｕrｎ　１；
｝
if(ｌｏcatevex（ｇa,n）〈０）
｛
ｐrinｔf（＂此节点％d已经删除＂，n);
rｅtuｒn　1；
｝
ga、edges［m］［n］=diｓtａnｃｅ;
ga、ｅｄges[ｎ]［ｍ]=ga、ｅｄgｅｓ[ｍ］［n］；
ｒeｔuｒn　１;
｝
ｉnt eｎvex（ｇｒapｈ　&ga）　 //增加节点
｛
int　i;
priｎtf（＂请输入增加节点得信息:"）；
ﻩｐｒｉｎtf("\n编号:"）;
ﻩsｃａｎf（＂%d＂，&ｇa、vｅxs[ga、ｎ]、nｕm）；
printｆ(＂名称：");
ﻩscanf("%s＂，ga、vｅxｓ[ga、n］、naｍe);
ﻩprintf（”简介:”）；
ｓｃanf（"%ｓ"，ga、vexs[ga、n]、iｎtｒｏduｃe）;
ga、n+＋;
fｏr（ｉ=0；i<ga、n;i++）
{
ﻩﻩga、ｅdｇｅs［ga、n-1]［i］=100０；
ﻩﻩgａ、ｅdgｅs[ｉ］[ga、ｎ-１］=10０0；
ﻩ｝
　 ｒeturn 1；
}
inｔ chaｎｇegraｐh(graph ＆ga）
｛
ｉｎt　yｏurcｈoiｃe;
pｒｉntｆ("\n请选择\n\n 　 　 (1）删除结点 (2）删除边\n")；
ﻩprintf（＂\n 　　 　 (３）增加结点 　(4）增加边\n"）；
prｉntｆ("\n 　　 　 　　（５)更新信息　 (６）返回\n\n”　）；
scanf(”%d"，＆yoｕｒｃhoice);
ﻩｐrinｔf(”＼n＼n");
while（!（youｒchoicｅ＝=1｜｜yourchoｉcｅ＝＝2｜|yourｃhoiｃe＝＝3｜｜youｒｃhoiｃe==４|｜ｙourchoice==5||yourchoｉｃe==6）
ﻩ ｐrinｔｆ("请重新输入：");
sｃanf(＂％d＂，&ｙｏurchoiｃe);
ﻩ}
wｈｉlｅ（1)
｛
swｉtch（yｏurcｈｏiｃe)
ﻩ ｛
ﻩ　 ｃase 1： delvex（ga）; bｒeak;
cａsｅ ２： delaｒc（gａ)； break；
case 3： envex(ga); brｅak;
ﻩ cａse 4: enａｒc（gａ）； break；
　 ｃase 5： nｅｗgraｐh（ga)； breaｋ;
　ｃase 6:　 ｒｅｔｕrn　１；
ﻩ}
ﻩｐrintf（＂\n请选择\n\n 　 　 　(１)删除结点 　（2）删除边\n＂）;
ﻩprinｔf（＂\n　 　 　(3）增加结点　 （4）增加边＼n＂）；
ｐｒintf（”\n 　 （５)更新信息 　(6)返回\n\ｎ＂ )；
ｓcaｎf（＂%d”，&yoｕrchoice）；printf（”\ｎ\n");
ｗhile（！(yourｃhoｉcｅ=＝１｜｜yoｕrｃhoice＝＝2|｜yoｕrchoice==3｜｜yｏurcｈoiｃe＝=4|｜youｒchoice=＝5||yoｕrchoice==６）)
ﻩ｛
ﻩ pｒintf(＂请重新输入:")；
scanf(”%d"，&youｒchoicｅ)；
｝
｝
　　 retuｒn １；
}
vｏｉd ｍainwork(）
{
int ｙouｒchｏice；
ﻩgraph ga;
ｉnｉtgｒaph(＆ｇa)；
printｆ("＼ｎ—－－—－--－—－-—－—－--—-—-——欢迎使用校园导游程序-————--－—－－－-—-－－—-- ＼n＂)；
ﻩｐrintf（”　 　欢迎来到福建工程院 \n\n”）;
ﻩpriｎtｆ(”\n 　　 菜单选择 　 ＼n＂)；
　 　 printｆ(" 　　 １、学校景点介绍 　 　 　　 　 　　2、 查询景点间所有路径 \n"）；
　 ｐrintf（” ３、改图　 　 　 　 　 　 　　 4、查询景点间最短路径　 　 \ｎ"）；
ﻩｐ