数据结构课程设计 校园导航（含源程序及WORD报告）

设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。

#include 
using namespace std; 
#define INFINITY 100 
#define MAXNODE 10 
typedef char ElemType; 
typedef struct 
{ 
int adj; 
}ArcType; 
typedef struct 
{ 
char *city[1];  
}name; 
typedef struct 
{ 
name vertexs[MAXNODE]; 
ArcType arcs[MAXNODE][MAXNODE]; 
int vexnumarcnum; 
}GraphType; 
/*****************求该顶点的位置********************/ 
int LocateVex（GraphType GElemType *u[1]） 
{ 
int i=-1k; 
for（k=0;kif（**（G.vertexs[k].city）==**u） 
{ 
i=k; 
break; 
} 
return i;//失败返回-1 
} 
/*************建立图的邻接矩阵******************/ 
int CreatDN（GraphType *G） 
{ 
int ijkweight; 
ElemType *u1[1]*u2[1]; 
cout<<“请输入图的顶点数和弧数“; 
cin>>G->vexnum>>G->arcnum; 
for（i=0;ivexnum;i++） 
for（j=0;jvexnum;j++） 
G->arcs[i][j].adj=INFINITY; 
cout<<“请输入顶点的信息“; 
for（i=0;ivexnum;i++） 
cin>>*G->vertexs[i].city; 
for（k=0;karcnum;k++） 
{ 
cout<<“请输入第“<cin>>*u1>>*u2>>weight; 
i=LocateVex（*Gu1）; 
j=LocateVex（*Gu2）; 
G->arcs[i][j].adj=weight; 
G->arcs[j][i].adj=weight;//无向图 
} 
return 1; 
} 

/***********从一点到其余各点的最短距离***************/ 
void Dijkstra（GraphType *Gchar *u[1]char *v[1]） 
{ 
int i1=LocateVex（*Gu）; 
int i2=LocateVex（*Gv）;  
int iktj; 
int *d=new int[5];  
int *s=new int[5];  
int *p=new int[5];  
int way[20];//保存路径用 
for（s[i1]=1i=0;ivexnum;i++） //初始化数组dsp 
{  
if（i!=i1） 
{ 
s[i]=0;d[i]=G->arcs[i1][i].adj;way[i]=i; 
if（d[i]p[i]=0; 
else p[i]=-1; 
} 
} 
for（i=0;ivexnum;i++）  
{ 
if（i!=i1） 
{ 
t=INFINITY;k=1;  
for（j=0;jvexnum;j++） 
if（（j!=i1）&&（!s[j]）&&（d[j]{ 
t=d[j];k=j; 
} 
s[k]=1; 
for （j=0;jvexnum;j++） 
if（（j!=i1）&&（!s[j]）&&（d[j]>d[k]+G->arcs[k][j].adj）） 
{ 
d[j]=d[k]+G->arcs[k][j].adj;//d用于保存最短路径的长度 
p[j]=k; 
way[j]=way[k]*10+j;//若该点属于最短路径，则保存该点 
} 
} 
} 

if（d[i2]==100）//不存在路径 
cout<<“对不起，你不能去那“; 
else 
{ 
cout<int a[MAXNODE]b[MAXNODE]a1=0b1=0; 

cout<<“路径为“<<*G->vertexs[i1].city; 
while（way[i2]/10!=0||way[i2]!=0） 
{ 
a[a1]=way[i2]%10; 
a1++;way[i2]=way[i2]/10; 
} 
a1--; 
while（a1>=0） 
{ 
b[b1]=a[a1]; 
cout<<“->“<<*G->vertexs[b[b1]].city; 
b1++;a1--; 
} 
} 
cout<<“\n“<} 

/***************初始化图**************************/ 
GraphType *chushihua（GraphType *G） 
{ 
G=（GraphType*）malloc（sizeof（GraphType））; 

G->vexnum=8; 
G->arcnum=9; 
for（int i=0;ivexnum;i++） 
for（int j=0;jvexnum;j++） 
G->arcs[i][j].adj=INFINITY; 
*G->vertexs[0].city=“前门“;
*G->vertexs[1].city=“图书馆“;
*G->vertexs[2].city=“教一楼“; 
*G->vertexs[3].city=“教二楼“;
*G->vertexs[4].city=“食堂“;
*G->vertexs[5].city=“水房“; 
*G->vertexs[6].city=“操场“;
*G->vertexs[7].city=“商店“; 
*G->vertexs[8].city=“公寓楼“;
*G->vertexs[9].city=“后门“;
G->arcs[0][1].adj=15;G->arcs[1][0].adj=15; 
G->arcs[0][2].adj=40;G->arcs[2][0].adj=40; 
G->arcs[0][3].adj=20;G->arcs[3][0].adj=20; 
G->arcs[2][3].adj=20;G->arcs[3][2].adj=20; 
G->arcs[2][4].adj

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       4512  2010-04-28 11:39  xioayuandaohang\123.cpp

     文件     731648  2011-06-20 09:37  xioayuandaohang\校园导航问题.doc

     目录          0  2011-06-20 09:42  xioayuandaohang

----------- ---------  ---------- -----  ----

               736160                    3