题目石铁大校园导航系统学院信息科学与技术学院专业计算机科学与技术学号 20112840 学生姓名刘铸辉指导教师姓名陈娜日期：2013-8-31一．题目与要求实习一校园导游程序[ 问题描述]用无向网表示学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。

要求能够回答有关景点介绍、游览路径等问题。

游客通过终端可询问：（1 ）从某一景点到另一景点的最短路径。

（2 ）游客从公园进入，选取一条最佳路线。

（3 ）使游客可以不重复地浏览各景点，最后回到出口（出口就在入口旁边）。

[ 基本要求]（1 ）将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路，边上的权值表示距离．为此图选择适当的数据结构。

（2 ）把各种路径都显示给游客，由游客自己选择浏览路线。

（3 ）画出景点分布图于屏幕上。

[ 实现提示]（1 ）构造一个无向图G 并用邻接矩阵来存储。

（2 ）利用迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径用二维数组p[i][]来记录，最短路径长度就用一维数组d[i] 存放；i 的范围：0 ～20 。

（3 ）一维数组have[] 是用来记录最短路径出现顶点的顺序。

（4 ）根据起点和终点输出最短路径和路径长度。

二．需求分析本校园导航系统由C语言编写，主要掌握最短路径的实现方法，以及构造无向图G并用邻接矩阵来存储，掌握迪杰斯特拉算法来算最短路径。

1.输入的形式和输出的范围：2.输出的形式：3.程序所能到达的功能：A.图中任意景点的相关信息查询B.任意两个景点间的最短路径C.任意两个景点间的所有路径D.增加有关景点和道路的信息E.删除更新有关景点和道路的信息F.更新有关景点和道路的信息G.显示全景H.退出该系统三．概要设计（1）本程序包含了10个函数①主函数main()②显示操作菜单函数 menu()③景点名称及其简介设置函数 picture(void)④图中任意景点相关信息查询函数 checkscene(algraph g)⑤图中任意两个景点间的最短路径 Dijkstra(algraph g)⑥任意两个景点间的全部路径 alldistance(algraph g)⑦增加有关景点和道路的信息 addscene(algraph g)⑧删除有关景点和道路的信息 delscene(algraph g)⑨更新有关景点和道路的信息 change(algraph g)⑩显示全景 chang()（2）各函数之间的关系menu()picture(void)checkscene(algraph g)Dijkstra(algraph g)main() alldistance(algraph g)addscene(algraph g)delscene(algraph g)change(algraph g)chang()四．详细设计实现概要设计中定义的所有的数据类型，对每个操作给出伪代码，对主程序和其他模块也都需要写出伪代码算法。

（1）结点类型和指针类型typedef struct {int adj;int *info;}sceneinfo;typedef struct adjlist{int num;char *sight;char *description;}adjlist;typedef struct algraph{adjlist ver[MAXNUM];sceneinfo arcs[MAXNUM][MAXNUM];int vexnum,arcnum;} algraph;（2）图的基本操作①主菜单//主菜单int menu(void){ int i;printf("\n-------------------------欢迎来到莱震德瑞hui 校园导航系统!!-----------------------------------------------------\n");printf("1.图中任意景点的相关信息查寻\n");printf("2.任意两个景点间的最短路径\n");printf("3.任意两个景点间的所有路径\n");printf("4.增加有关景点和道路的信息\n");printf("5.删除更新有关景点和道路的信息\n");printf("6.更新有关景点和道路的信息\n");printf("7.显示全景\n ");printf("8.退出该系统\n ");printf("---------------------------让辉哥带大家在石家庄铁道大学翱翔吧!!------------------------------------------------------\n");printf("请输入你要进行的操作：");scanf("%d",&i);return(i);}②景点名称及其简介void picture(void){ int i,j;m.vexnum=11;m.arcnum=16;for(i=0;i<m.vexnum;i++)m.ver[i].num=i;m.ver[0].sight="xiaomen";m.ver[1].sight="学校大门，一教";m.ver[2].sight="图书馆";m.ver[3].sight="操场";m.ver[4].sight="体育馆";m.ver[5].sight="青春苑";m.ver[6].sight="办公楼";m.ver[7].sight="第一实验楼";m.ver[8].sight="第九实验楼";m.ver[9].sight="第九宿舍楼";m.ver[10].sight="家属院";m.ver[1].description="进入学校大门就可以看见一教，一教西面是二教和三教";m.ver[2].description="自习和阅读的心灵家园，后身是第二实验楼";m.ver[3].description="跑道和足球场";m.ver[4].description="室内篮球场和游泳场";m.ver[5].description="学生活动中心和综合餐厅";m.ver[6].description="办公中心，包括开元楼和春晖楼";m.ver[7].description="挨着医院和综合教学楼，物理实验";m.ver[8].description="计算机和电工实验，西邻机械学院";m.ver[9].description="生活区中心，西邻超市水房澡堂，东临一，二三食堂";m.ver[10].description="教职工住处，在学校最北面";for(i=0;i<m.vexnum;++i)for(j=0;j<m.vexnum;++j)m.arcs[i][j].adj=INF;m.arcs[1][2].adj=m.arcs[2][1].adj=100;m.arcs[1][3].adj=m.arcs[3][1].adj=300;m.arcs[2][6].adj=m.arcs[6][2].adj=500;m.arcs[3][5].adj=m.arcs[5][3].adj=600;m.arcs[1][4].adj=m.arcs[4][1].adj=220;m.arcs[4][5].adj=m.arcs[5][4].adj=600;m.arcs[4][9].adj=m.arcs[9][4].adj=450;m.arcs[4][6].adj=m.arcs[6][4].adj=650;m.arcs[5][7].adj=m.arcs[7][5].adj=300;m.arcs[6][8].adj=m.arcs[8][6].adj=600;m.arcs[10][9].adj=m.arcs[9][10].adj=100;m.arcs[7][10].adj=m.arcs[10][7].adj=250;m.arcs[7][9].adj=m.arcs[9][7].adj=280;m.arcs[8][9].adj=m.arcs[9][8].adj=400;m.arcs[8][4].adj=m.arcs[4][8].adj=100;}③图中任意景点相关信息查询void checkscene(algraph g){ int i,j;char ch;while(1){ sceneplace();printf("请输入你要查询的景点的编号:");scanf("%d",&i);if(i>p || i<0)printf("输入错误！！\n");else{for(j=0;j<=p;j++){ if(i==j){ printf("你要查询的景点的相关信息如下：\n");printf("%d\t\t%s\n",g.ver[i].num,g.ver[i].sight);printf("%s\n",g.ver[i].description);}}}printf("是否继续查询?(y|n):");scanf("%s",&ch);if(ch=='N'||ch=='n')break;}}④图中任意两个景点间的最短路径void Dijkstra(algraph g){ char ch;int path1[MAXNUM];int dist[MAXNUM];int s[MAXNUM];int mindis,i,j,u,n=p;int l,k;int v0,po;while(1){sceneplace();printf("请输入出发景点的序号：");scanf("%d",&v0);printf("请输入目的景点的序号：");scanf("%d",&po);for(i=0;i<n;i++){ dist[i]=g.arcs[v0][i].adj;s[i]=0;if(g.arcs[v0][i].adj!=INF)path1[i]=v0;elsepath1[i]=-1;}s[v0]=1;path1[v0]=0;for(i=0;i<n;i++){ mindis=INF;u=-1;for(j=0;j<n;j++)if(s[j]==0 && dist[j] < INF){ u=j;mindis=dist[j];}s[u]=1;for(j=0;j<n;j++)if(s[j]==0)if(g.arcs[u][j].adj < INF&& dist[u]+g.arcs[u][j].adj<dist[j]){ dist[j]=dist[u]+g.arcs[u][j].adj;path1[j]=u;}}dispath(g,dist,path1,s,n,v0,po);printf("\n是否继续查询?(y|n):");scanf("%s",&ch);if(ch=='N'||ch=='n')break;}}⑤任意两个景点间的全部路径void path(algraph g,int i,int j,int k){int s,ko;if(r[k]==j){a++;printf("第%d条:",a);for(s=0;s<=k-1;s++){ printf("%s",g.ver[r[s]].sight);printf("-->");}printf("%s\n",g.ver[r[s]].sight);}s=0;while(s<g.vexnum){if(s!=i){ ko=r[k];if(g.arcs[ko][s].adj != INF && visited[s]==0) { visited[s]=1;r[k+1]=s;path(g,i,j,k+1);visited[s]=0;}}s++;}}void alldistance(algraph g){ int i,j,k,l;char sh;while(1){ sceneplace();printf("\n请选择出发景点的序号：");scanf("%d",&i);printf("\n请选择目地景点的序号：");scanf("%d",&j);for(k=0;k<g.vexnum;k++)if(i==g.ver[k].num) i=k;for( l=0;l<g.vexnum;l++)if(j==g.ver[l].num) j=l;printf("从%s到%s的所有游览路径有:\n",g.ver[i].sight,g.ver[j].sight); r[0]=i;for(k=0;k<1;k++){ visited[i]=0;a=0;path(g,i,j,0);}printf("继续查询?(y|n):");scanf("%s",&sh);if(sh=='N'||sh=='n')break;}}⑥增加有关景点和道路的信息void addscene(algraph g){int j,i,b;char yi,mon[10],moh[100];while(1){ sceneplace();g.ver[p].num=p;printf("请输入新景点的名称：");scanf("%s",mon);m.ver[p].sight=(char*)malloc(10);strcpy(m.ver[p].sight,mon);printf("\n请输入新景点的相关简介：");scanf("%s",moh);m.ver[p].description=(char*)malloc(100);strcpy(m.ver[p].description,moh);g.vexnum=g.vexnum+1;for(j=0;j<p;++j){ m.arcs[p][j].adj=INF;m.arcs[j][p].adj=INF;}printf("\n请问有几个景点与该景点直接相通：");scanf("%d",&i);printf("\n请输入与该景点相通的景点的序号及它们之间的距离：");for(j=0;j<i;j++){ printf("\n请输入第%d个景点的序号:",j+1);scanf("%d",&b);printf("\n请输入该两个景点之间的距离：");scanf("%d",&g.arcs[p][b].adj);g.arcs[b][p].adj=g.arcs[p][b].adj;m.arcs[b][p].adj=g.arcs[p][b].adj;m.arcs[p][b].adj=m.arcs[b][p].adj;}printf("你输入的景点信息是：\n");printf("%d \t%s \t %s\n\n ", g.ver[p].num,m.ver[p].sight,m.ver[p].description);g.arcnum=g.arcnum+i;p=p+1;m.vexnum=p;sceneplace();printf("是否继续添加?(y|n):");scanf("%s",&yi);if(yi=='N'||yi=='n')break;}}⑦删除有关景点和道路的信息void delscene(algraph g){ int i,j,k,l;char sh;while(1){sceneplace();printf("\n请输入你将要删除的景点序号:");scanf("%d",&i);for(k=0;k<g.vexnum;k++)if(i==g.ver[k].num) j=k;m.ver[j].sight=NULL;for(l=1;l<m.vexnum;++l){ m.arcs[l][j].adj=INF;m.arcs[j][l].adj=INF;}m.vexnum=m.vexnum-1;sceneplace();printf("删除继续?(y|n):");scanf("%s",&sh);if(sh=='N'||sh=='n')break;}}⑧更新有关景点和道路的信息void change(algraph g){ int i,b,j,th,fh,k;char sh,mon[10],moh[100];while(1){sceneplace();printf("请输入你将要修改信息的景点序号:");scanf("%d",&i);for(k=0;k<g.vexnum;k++)if(i==g.ver[k].num) j=k;printf("-----------------------------------------\n"); printf("1.景点名称\t2.景点简介\t3.道路消息\n");printf("-----------------------------------------\n"); printf("请输入你要进行的操作的序号：");scanf("%d",&th);switch(th){ case 1:printf("请输入新景点名称：");scanf("%s",mon);g.ver[j].sight=mon;m.ver[j].sight=g.ver[j].sight;break;case 2:printf("请输入新景点简介：");scanf("%s",moh);m.ver[j].description=(char*)malloc(100);strcpy(m.ver[j].description,moh);break;case 3:printf("请输入要修改的与该景点相通的景点的距离的序号个数：");scanf("%d\n",&fh);for(k=0;k<fh;k++){ printf("请输入要修改的第%d个景点的序号:",j+1);scanf("%d\n",&b);printf("请重新输入该两个景点之间的距离：");scanf("%d",&m.arcs[j][b].adj);m.arcs[b][j].adj=m.arcs[j][b].adj;}}sceneplace();printf("继续修改?(y|n):");scanf("%s",&sh);if(sh=='N'||sh=='n')break;}⑨显示全景略⑩主函数int main(){picture();printf("\n------------------------------校园导航系统----------------------------------------------\n");sceneplace();for(;;){switch(menu()){ case 1:checkscene(m);break;case 2:Dijkstra(m);break;case 3:alldistance(m);break;case 4:addscene(m);break;case 5:delscene(m);break;case 6:change(m);break;case 7:chang(m);break;case 8:printf("感谢你使用辉哥校园导航系统!!辉哥又一次带大家拯救了世界!!再见!!\n");exit(0);default:printf("输入错误!!请重新输入你要进行的操作!!\n");}}}五．调试分析在调试删除修改功能过程中，删除的总是不正确，删除的结果显示，没有将要删除的景点删掉，最后发现删除的结点不正确，删除应该与输入的值和头结点next比较，而不是头结点。