C++ 数据结构世博会导航系统

#include "string.h" #include "stdio.h" #include "malloc.h" #include "stdlib.h" #include"WorldExp.h" #include"jianjie.h" #include<iostream> using namespace std; using namespace ns1; using namespace ns2; #define Max 999 #define NUM 15 int D[NUM]; Graph g; void dijistra(int num); void output(int sight1,int sight2); void creat(int a,int v); void menu(); int main(){ creat(15,25); //Dist D[NUM]; void menu1(); menu(); return 0; } void menu1(){ //菜单栏 int a=0; China c; America am; France f; England e; German g; Herland h; Russia r; Japan j; Spanish s; Denmark d; India i; Italy it; Brazil b; Turkey t; Canada ca; cout<<"0 China 1:America 2:France 3:England 4:German"<<endl; cout<<"5:Herland 6:Russia 7:Japan 8:Spanish 9:Denmark"<<endl; cout<<"10:India 11:Italy 12:Brazil 13:Turkey 14:Canada"<<endl; printf("please enter the num of country:"); cin>>a; if(a==0){c.brief();} else if(a==1){am.brief();} else if(a==2){f.brief();} else if(a==3){e.brief();} else if(a==4){g.brief();} else if(a==5){h.brief();} else if(a==6){r.brief();} else if(a==7){j.brief();} else if(a==8){s.brief();} else if(a==9){d.brief();} else if(a==10){i.brief();} else if(a==11){it.brief();} else if(a==12){b.brief();} else if(a==13){t.brief();} else if(a==14){ca.brief();} } void menu(){ int m=0; int v1,v0; do{ cout<<"\n******欢迎使用上海世博会导航系统******"<<endl; cout<<"**********竭诚为您服务**********"<<endl; cout<<"________________________________"<<endl; cout<<"please enter the function:"<<endl; cout<<"1:brief of country 2:路线查询 3:推荐旅游路线 4:return to choose"<<endl; cin>>m; if(m==1){ // creat(15,25); menu1(); //break; } else if(m==2){ printf("\n\n\t请选择起点景点（0～14）："); cin>>v0; printf("\t请选择终点景点（0～14）："); cin>>v1; dijistra(v0); /* 计算两个景点之间的最短路径 */ output(v0,v1); /* 输出结果 */ //break; }else if(m==3){ cout<<"3"<<endl;//break; }else if(m==4){ cout<<"return to choose"<<endl; exit(0); }else{cout<<"error,choose again"<<endl;// break; } } while(m!=4); } void creat(int a,int v){ int i,j; //Graph g; g.vertex[0]="China"; g.vertex[1]="America"; g.vertex[2]="France"; g.vertex[3]="England"; g.vertex[4]="German"; g.vertex[5]="Herland"; g.vertex[6]="Russia"; g.vertex[7]="Japan"; g.vertex[8]="Spanish"; g.vertex[9]="Denmark"; g.vertex[10]="India"; g.vertex[11]="Italy"; g.vertex[12]="Brazil"; g.vertex[13]="Turkey"; g.vertex[14]="Canada"; for(i=0;i<15;i++){ for(j=0;j<15;j++){ g.arc[i][j]=Max; } } g.arc[1][0]=g.arc[0][1]=4; g.arc[2][1]=g.arc[1][2]=2; g.arc[3][2]=g.arc[2][3]=5; g.arc[4][3]=g.arc[3][4]=6; g.arc[0][5]=g.arc[5][0]=6; g.arc[2][6]=g.arc[6][2]=14; g.arc[3][6]=g.arc[6][3]=1; g.arc[6][4]=g.arc[4][6]=12; g.arc[5][7]=g.arc[7][5]=7; g.arc[6][7]=g.arc[7][6]=3; g.arc[5][8]=g.arc[8][5]=3; g.arc[8][7]=g.arc[7][8]=5; g.arc[5][9]=g.arc[9][5]=8; g.arc[5][10]=g.arc[10][5]=5; g.arc[8][10]=g.arc[10][8]=5; g.arc[9][10]=g.arc[10][9]=4; g.arc[9][11]=g.arc[11][9]=2; g.arc[12][6]=g.arc[6][12]=3; g.arc[12][7]=g.arc[7][12]=2; g.arc[13][7]=g.arc[7][13]=7; g.arc[13][8]=g.arc[8][13]=7; g.arc[13][10]=g.arc[10][13]=16; g.arc[12][13]=g.arc[13][12]=8; g.arc[10][14]=g.arc[14][10]=2; g.arc[13][14]=g.arc[14][13]=3; } void dijistra(int num) //迪杰斯特拉算法最短路径函数 num为入口点的编号 { int v,w,i,t; // i、w和v为计数变量 int final[NUM]; int min; for(v=0;v<NUM;v++) { final[v]=0; // 假设从顶点num到顶点v没有最短路径 D[v]=g.arc[num][v];// 将与之相关的权值放入D中存放 for(w=0;w<NUM;w++) // 设置为空路径 g.P[v][w]=0; if(D[v]<999) // 存在路径 { g.P[v][num]=1; // 存在标志置为一 g.P[v][v]=1; // 自身到自身 } } D[num]=0; final[num]=1; // 初始化num顶点属于S集合 // 开始主循环，每一次求得num到某个顶点的最短路径，并将其加入到S集合 for(i=0;i<NUM;++i) //其余G.vexnum-1个顶点 { min=Max; //当前所知离顶点num的最近距离 for(w=0;w<NUM;++w) if(!final[w]) // w顶点在v-s中 if(D[w]<min) // w顶点离num顶点更近 { v=w; min=D[w]; } final[v]=1; // 离num顶点更近的v加入到s集合 for(w=0;w<NUM;++w) // 更新当前最短路径极其距离 if(!final[w]&&((min+g.arc[v][w])<D[w]))// 不在s集合，并且比以前所找到的路径都短就更新当前路径 { D[w]=min+g.arc[v][w]; for(t=0;t<NUM;t++) g.P[w][t]=g.P[v][t]; g.P[w][w]=1; } } } void output(int sight1,int sight2) // 输出函数 { int a,b,c,d=0; a=sight2; //将景点二赋值给a if(a!=sight1) // 如果景点二不和景点一输入重合，则进行... { cout<<"从"<<g.vertex[sight1]<<"到"<<g.vertex[sight2]<<"的最短路径是"<<D[a]<<endl; // 输出sight1到sight2的最短路径长度，存放在D[]数组中 cout<<g.vertex[sight1]; //输出景点一的名称 d=sight1+1; // 将景点一的编号赋值给d for(c=0;c<NUM;++c) { g.P[a][sight1]=0; for(b=0;b<NUM;b++) { if(g.arc[d][b]<999&&g.P[a][b]) // 如果景点一和它的一个临界点之间存在路径且最短路径 { cout<<"--->"<<g.vertex[b]; // 输出此节点的名称 g.P[a][b]=0; d=b; // 将b作为出发点进行下一次循环输出，如此反复 } } } } }