实训代码

#include
#include
using namespace std;
#define INF 1324767 //最大值∞
#define MAX_VERTEX_NUM 25

//-----------------定义存储结点----------------
typedef struct
{
char *data[MAX_VERTEX_NUM]; //存储城市
int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //存储城市间距离
int max;
}MGraph;
//----------------初始化交通网----------------
void SetGraph(MGraph *p1)
{
int i,j,k=0;
p1->data[0]="乌鲁木齐";p1->data[1]="呼和浩特";p1->data[2]="北京";p1->data[3]="天津";p1->data[4]="哈尔滨";p1->data[5]="长春";p1->data[6]="沈阳";
p1->data[7]="大连";p1->data[8]="西宁";p1->data[9]="兰州";p1->data[10]="西安";p1->data[11]="郑州";p1->data[12]="徐州";p1->data[13]="上海";
p1->data[14]="成都";p1->data[15]="武汉";p1->data[16]="昆明";p1->data[17]="贵阳";p1->data[18]="株洲";p1->data[19]="南昌";p1->data[20]="福州";
p1->data[21]="南宁";p1->data[22]="柳州";p1->data[23]="广州";p1->data[24]="深圳";
p1->max =25;
for(i=0;i<25;i++)
{
for(j=0;j<25;j++)
{
p1->edge[i][j]=INF;
}
}
// p1->edge[0][9]=1892;
// p1->edge[9][0]=1892;
p1->edge[0][9]=p1->edge[9][0]=1892; p1->edge[1][2]=p1->edge[2][1]=668;
p1->edge[1][9]=p1->edge[9][1]=1145;
p1->edge[2][3]=p1->edge[3][2]=137;
p1->edge[3][6]=p1->edge[6][3]=704; p1->edge[3][12]=p1->edge[12][3]=674;
p1->edge[4][5]=p1->edge[5][4]=242; p1->edge[5][6]=p1->edge[6][5]=305;
p1->edge[6][7]=p1->edge[7][6]=397; p1->edge[8][9]=p1->edge[9][8]=216;
p1->edge[9][10]=p1->edge[10][9]=676; p1->edge[10][11]=p1->edge[11][10]=511;
p1->edge[11][2]=p1->edge[2][11]=695; p1->edge[11][12]=p1->edge[12][11]=349;
p1->edge[12][13]=p1->edge[13][12]=651; p1->edge[13][19]=p1->edge[19][13]=825;
p1->edge[14][10]=p1->edge[10][14]=842; p1->edge[15][11]=p1->edge[11][15]=534;
p1->edge[14][17]=p1->edge[17][14]=967; p1->edge[14][16]=p1->edge[16][14]=1100;
p1->edge[15][18]=p1->edge[18][15]=409; p1->edge[16][17]=p1->edge[17][16]=639;
p1->edge[17][18]=p1->edge[18][17]=902; p1->edge[17][22]=p1->edge[22][17]=607;
p1->edge[18][19]=p1->edge[19][18]=367; p1->edge[19][20]=p1->edge[20][19]=622;
p1->edge[21][22]=p1->edge[22][21]=255; p1->edge[22][18]=p1->edge[18][22]=672;
p1->edge[23][18]=p1->edge[18][23]=675; p1->edge[23][24]=p1->edge[24][23]=140;
}

//-------------------查找城市位置---------------------

//---------确定起点城市位置--------
int Locate1(MGraph *p2)
{
char* city = new char[10];
int i;
printf("输入要查询的起点城市名：");
scanf("%s",city);
for(i=0;i<25 && strcmp(city,p2->data[i])!=0;i++)
continue;
if(i<25)
return(i);
return(-1);
}
//---------------确定终点城市位置------------------
int Locate2(MGraph *p2)
{
char* city = new char[10];
int i;
printf("输入要查询的终点城市名：");
scanf("%s",city);
for(i=0;i<25 && strcmp(city,p2->data[i])!=0;i++)
continue;
if(i<25)
r

eturn(i);
return(-1);
}

//----------------迪杰斯特拉算法----------------

void Dijkstra(MGraph *graph,int n,int y,int v)
{ //更换起点、终点的参数位置，直接输出顺序路径
int dist[MAX_VERTEX_NUM],path[MAX_VERTEX_NUM];
int s[MAX_VERTEX_NUM];
int mindis, i,j ,u, pre;
//char express;
//char **shuchu;
for(i=0;i{
dist[i]=graph->edge[v][i];//距离初始化
s[i]=0; //s[]置空
if (graph->edge[v][i]else path[i]=-1;
}//for
s[v] = 1; path[v] = 0; //初始化，v顶点属于S集
//开始主循环，每次求得v0到某个v顶点的最短路径，并加v到s集。
for(i=0;i{
mindis = INF; //当前所知离v顶点的最近距离
u=-1;
for(j=0;jif(s[j]==0&& dist[j]{
u=j;
mindis=dist[j];
}
if (u!=-1) //找到最小距离的顶点u
{
s[u]=1; //离v顶点最近的u加入S集
for (j=0;jif (s[j]==0)
if (graph->edge[u][j]edge[u][j])){
dist[j]=(dist[u]+graph->edge[u][j]);
path[j]=u;
} //if
}//if
}//for

//-----输出***点对点***城市***的最短路径------
cout <<"\n Dijkstra 算法求解如下：\n";
if (y!=v)
{
cout <<" "<data[y]<<"->"<data[v]<<": ";
if (s[y]==1)
{
cout <<"路径长度为"<pre=y;
cout<<"路径为:";
do
{
//shuchu[20][10]=graph->data[pre];
cout<data[pre]<<"---》";
pre=path[pre];
}while(pre!=v);//while
cout<data[pre]<}//if
else
cout<<"不存在路径"<}//if
}//Dijkstra
//----------输出最短路径（全部输出！！！）----------
/* cout<<"\n Dijkstra 算法求解如下：\n";
for(i=0;i{
if (i!=v)
{
cout <<" "<"<if (s[i]==1)
{
cout <<"路径长度为"<pre=i;
cout<<"路径逆序为";
while(pre!=v)
{
cout<< pre<<",";
pre=path[pre];
}//while
cout<}//if
else
cout<<"不存在路径"<}//if
}//for
*/
//----------------------主函数---------------------
int main( )
{
int x,y;
char Man;
MGraph *G;
G=(MGraph *)malloc(sizeof(MGraph)); //分配图的结构体空间
SetGraph(G); //构造邻接矩阵存储交通图
printf("************************城市交通咨询系统****************************\n");
printf("***********************请输入操作：开始查询输入：s **********************\n");
printf("***********************请输入操作：退出程序输入：q **********************\n");
printf("***********************请输入操作：继续查询输入：c **********************\n");
loop1:{cout<<"请输

入要进行的操作："<//n=0;
cin>>Man;
// scanf("%c",&Man); ///此处不能用scanf函数,流状态读取字符会在缓冲区保留下一个控制字符
///等下次执行函数时直接读取省去用户输入！！！造成意想不到的程序错误！
}

if(Man=='s'||Man=='c')
{
// char c = getchar();
x=Locate1(G);
y=Locate2(G); //查找所输入的城市位置
if(x==-1 || y==-1) //判断所输入的城市存在与否
{printf("输入的城市不存在！请重新执行操作！\n");
goto loop1;
}
Dijkstra(G,25,x,y); //调用迪杰斯特拉算法球的最短路径
goto loop1;
}
if(Man!='c' && Man!='q' && Man!='s')
{
//getchar();
printf("输入有误！请重新输入！");

goto loop1;
}
if(Man=='q') goto loop2;
loop2: return 0; //为了合理控制程序走向，加了goto（loop2）语句
//loop2: ; //所以更改主函数类型，其实也可以令loop2为空
}