问题描述：创建一个至少有15个点的有向网表示的某个旅游景点的导游图。顶点代表景点,类型为字符串（例如，泰山导游图：“天地广场门”，“十八盘”，“冯玉祥墓”，“桃花峪门”，“中天门”，“南天门”，“玉皇顶”等），弧表示两个景点之间可以直达，弧上的权值表示两个景点之间的路程（公里数），弧上还有到达方法的信息（有步行和索道两种）。建立一个游客咨询系统。
1.基本要求
（1）创建图的存储结构。
（2）输入两个景点名，就可以得到从一个景点到达另一个景点的所有简单路径、相应路径的路程公里数、行走的方法（每一段是步行，还是坐索道）；
（3）输入两个景点名，就可以得到其最短路径，即：路程最短的行进方法；如果两者无路径可通，就得出“两景点不可达的信息”。
2.重点、难点
重点：
（1）通过实验掌握图状结构数据的存储与表式；
（2）通过实验掌握对图的存储、遍历、运算等各种操作；
（3）深入理解图的特征及应用；
难点：
（1）任意两个景点所有路径的计算；
（2）最短路径的计算与算法设计。
3.源代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 |
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<time.h> #define N 15 #define MAX 999 int min_len[N]; int route[N][N]; int visited[N]; int flag[N]; int stack[N]; int path[N][N]; int temp[N][N]; int start=99,end=99; int v,w,m=1; int static n=0; typedef struct { char name[N][20]; int length[N][N]; char way[N][N]; }Point; void init_path() { int i,k; for(i=0;i<N;i++) { path[i][0]=start;path[i][1]=i; for(k=2;k<N;k++) path[i][k]=999; } } void read_file(Point *info) { int i=0,j; char ch[N][10]; FILE *fp1,*fp2,*fp3; if((fp1=fopen("view_name.txt","r"))==NULL){ printf("Open failed!!!\n");exit(0); } if((fp2=fopen("view_length.txt","r"))==NULL){ printf("can not open file!"); exit(0); } if((fp3=fopen("view_way.txt","r"))==NULL){ printf("can not open file!"); exit(0); } for(i=0;i<N;i++) fscanf(fp1,"%s",&info->name[i]); fclose(fp1); for(i=0;i<N;i++){ for(j=0;j<N;j++){ fscanf(fp2,"%d",&info->length[i][j]); temp[i][j]=info->length[i][j]; } } fclose(fp2); for(i=0;i<N;i++){ for(j=0;j<N;j++) fscanf(fp3,"%c",&info->way[i][j]); } fclose(fp3); } void output_view(Point *info) { int i,j; printf("一共有%d个景点,关系如下:\n\n ",N); for(i=0;i<N;i++) printf("%-7s",info->name[i]); printf("\n"); for(i=0;i<N;i++) for(j=0;j<=N;j++) { if(j==0)printf("%-3s",info->name[i]); if(j!=N)printf("%4d(%c)",info->length[i][j],info->way[i][j]); else printf("\n"); } } void Dijkstra(Point *info) { int i=1,j,min; for(v=0;v<N;v++) //循环初始化 { flag[v]=0; min_len[v]=info->length[start][v]; for(w=0;w<N;w++) route[v][w]=0; //设空路径 if(min_len[v]<MAX) { route[v][start]=1; route[v][v]=1; } } min_len[start]=0; flag[start]=0; //初始化start顶点属于集合S for(i=1;i<N;i++) //开始主循环 每次求得v0到某个顶点v的最短路径 并加v到集合S中 { min=MAX; for(w=0;w<N;w++) if(!flag[w]) //如果w顶点在V-S中 { //这个过程最终选出的点 应该是选出当前V-S中与S有关联边 //且权值最小的顶点 书上描述为当前离start最近的点 if(min_len[w]<min) { v=w; min=min_len[w]; } } flag[v]=1; //选出该点后加入到合集S中 for(w=0;w<N;w++) //更新当前最短路径和距离 { if(!flag[w]&&(min+info->length[v][w]<min_len[w])) { for(j=0;j<N;j++) path[w][j]=path[v][j]; for(j=0;j<N;j++) if(path[w][j]==999) {path[w][j]=w;break;} min_len[w]=min+info->length[v][w]; route[w][w]=1; } } } } void DFS(Point *info,int p) { int i,j,len; visited[p]=1; for(i=0;i<N;i++) { if(info->length[p][i]!=MAX) { if(i==end) { n++;printf("第%d条： ",n); for(j=0;j<m;j++) { stack[m]=end; //printf("(%d,%s,%c)-->",stack[j]+1,info->name[stack[j]],info->way[stack[j]][stack[j+1]]); printf("(%s)---%c--->",info->name[stack[j]],info->way[stack[j]][stack[j+1]]); } //printf("%d(%s)\n\n",end+1,info->name[end]); printf("(%s)\n\n",info->name[end]); } else if(!visited[i]) { info->length[p][i]=MAX; visited[i]=1; stack[m]=i; m++; DFS(info,i); info->length[p][i]=temp[p][i]; visited[i]=0; m--; } } } } void receive(Point *info) { int i; char a[20],b[20]; printf("\n输入起点和终点标号,按# #退出：");scanf("%s%s",a,b); printf("得出所有简单路径和最短路径\n"); if(strcmp(a,"#")==0&&strcmp(b,"#")==0)return; for(i=0;i<N;i++) { if(strcmp(a,info->name[i])==0)start=i; if(strcmp(b,info->name[i])==0)end=i; } init_path(); //for(i=0;i<N;i++)printf(" %d ",min_len[i]); if(start==99||end==99)printf("输入错误，请重新输入景点名\n"); else { Dijkstra(info); //for(i=0;i<N;i++)printf(" %d ",min_len[i]); //printf("@%d %d %d",start,end,min_len[end]); if(min_len[end]!=MAX) { printf("景点%s到景点%s最短路径长度为:%d\n所有简单路径:\n", info->name[start],info->name[end],min_len[end]); for(i=0;i<N;i++) visited[i]=0; stack[0]=start; DFS(info,start); printf("一共有%d条路径!\n",n); printf("景点%s到景点%s最短路径长度为:%d\n", info->name[start],info->name[end],min_len[end]); printf("最短路径为: "); for(i=0;i<N;i++) { if(path[end][i+1]==999)break; //printf("(%d,%s)--%c-->",path[end][i]+1,info->name[path[end][i]],info->way[path[end][i]][path[end][i+1]]); printf("(%s)---%c--->",info->name[path[end][i]],info->way[path[end][i]][path[end][i+1]]); } //printf("%d(%s)\n",path[end][i]+1,info->name[path[end][i]]); printf("(%s)\n",info->name[path[end][i]]); } else {printf("\n非常抱歉！！！景点%s无法到达%s",info->name[start],info->name[end]);} printf("\n"); } start=end=99;n=0; } int main() { int i,j=0; char x; Point *view_info=NULL; view_info=(Point *)malloc(sizeof(Point)); read_file(view_info); msgbox(view_info); printf("输入操作："); while(scanf("%c",&x)!=EOF) { switch(x) { case 'S':msgbox(view_info);receive(view_info);printf("输入操作：");break; case 'E':exit(0); default :cur_sys();msgbox(view_info);printf("输入操作：");continue; } } printf("谢谢使用！！！"); } |
