#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MaxName 20
#define MaxRoad 40
#define INFINITY 65535 /* ∞设为双字节无符号整数的最大值65535*/
typedef int Vertex; /* 用顶点下标表示顶点,为整型 */
typedef int WeightType; /* 边的权值设为整型 */
typedef char DataType; /* 顶点存储的数据类型设为字符型 */
typedef struct{
int no; //序号
char name[20]; //名称
char infor[40]; //地点信息
}place,Place[MaxName];
void InPlace(place a[MaxName]){
FILE *fp1,*fp2;
int i;
fp1=fopen("地点.txt","r");
fp2=fopen("地点信息.txt","r");
if(fp1==NULL || fp2==NULL){ //判断文件是否打得开
printf("不能打开文件！！");
exit(0);
}
for(i=0;i<MaxName;i++){ //获取需要的信息
fscanf(fp1,"%d%s",&a[i].no,a[i].name);
fscanf(fp2,"%d%s",&a[i].no,a[i].infor);
}
//关闭文件
fclose(fp1);
fclose(fp2);
}
typedef struct{
int last; //道路一端的序号
int next; //道路另一端的序号
char roadname[20]; //道路名称
char roadinfor[40]; //内容
int type; //交通方式：车行、骑行、步行
int len; //长度
}road,Road[MaxRoad];
void InRoad(road a[MaxRoad]){
FILE *fp1,*fp2;
int i;
fp1=fopen("道路.txt","r"); //判断文件是否打得开
fp2=fopen("道路信息.txt","r");
if(fp1==NULL || fp2==NULL){
printf("不能打开文件！！");
exit(0);
}
for(i=0;i<MaxRoad;i++){ //获取需要的信息
fscanf(fp1,"%d%s%d%s",&a[i].type,a[i].roadname,&a[i].len,a[i].roadinfor);
fscanf(fp2,"%d%s%d%s",&a[i].last,a[i].roadname,&a[i].next,a[i].roadinfor);
}
//关闭文件
fclose(fp1);
fclose(fp2);
}
void Lookplace(){
place a[MaxName];
int i,b;
InPlace(a); //导入地点信息
for(i=0;i<MaxName;i++){
printf("%d %s\n",i,a[i].name);
}
printf("请输入查询地点的序号：");
scanf("%d",&b);
if(b<MaxName && b>=0){ //判断查询序号是否正确
printf("\n%s：%s\n",a[b].name,a[b].infor);
}
else printf("\n查询出错，请确认序号查询范围内\n");
}
void Lookroad(){
road a[MaxRoad];
int i;
char b;
InRoad(a);
for(i=0;i<MaxRoad;i++){
printf("%d %s\n",i,a[i].roadname);
}
printf("请输入查询地点的序号：");
scanf("%d",&b);
if(b<MaxRoad && b>=0){
printf("\n%s：%s\n",a[b].roadname,a[b].roadinfor);
}
else printf("\n查询出错，请确认序号查询范围内\n");
}
typedef struct{
char vex[MaxName]; //顶点表
int arc[MaxName][MaxName]; //邻接矩阵
int n,e; //边数，顶点数
}graph;
//判断序号v是否存在于顶点表内
int locatevex(graph g,int v)
{
int i;
for(i=0;i<g.n;i++)
if(g.vex[i]==v)
return i;
return -1;
}
//创建邻接矩阵
void creategraph(graph *g){
int i,j,k,c,v1,v2;
place a[MaxName];
road b[MaxRoad];
InPlace(a);
InRoad(b);
g->n=MaxName;
g->e=MaxRoad;
//将序号存入顶点表内
for(i=0;i<g->n;i++){
g->vex[i]=a[i].no;
}
//初始化
for(i=0;i<g->n;i++)
for(j=0;j<g->n;j++)
g->arc[i][j]=INFINITY;
//将道路长度存入邻接矩阵中
for(k=0;k<g->e;k++)
{
v1=b[k].last;
v2=b[k].next;
i=locatevex(*g,v1);
j=locatevex(*g,v2);
for(c=0;c<g->e;c++)
if(b[c].last==i && b[c].next==j || b[c].next==i && b[c].last==j){
g->arc[i][j]=b[c].len;
g->arc[j][i]=b[c].len;
}
}
}
int DFSvisited[MaxName];/* 访问标志数组*/
/*从第i个顶点出发递归地深度优先遍历图G*/
void DFS(graph g,int i)
{
int j;
place a[MaxName];
InPlace(a);
printf("===》%d.%s",g.vex[i],a[i].name);
DFSvisited[i]=1;
for(j=0;j<g.n;j++)
{
if((g.arc[i][j]>0)&&(DFSvisited[j]==0))
DFS(g,j); //对i的尚未访问的邻接顶点j递归调用DFS
}
}
void DFStravel(graph g){
int i;
place a[MaxName];
InPlace(a);
for(i=0;i<MaxName;i++){
printf("%d %s\n",a[i].no,a[i].name);
}
printf("请输入起始地点的编号：");
scanf("%d",&i);
DFS(g,i);
printf("\n");
}
int Floyd(graph *g)
{
Vertex k,z,x,i,j;
int D[MaxName][MaxName],path[MaxName][MaxName];
place a[MaxName];
InPlace(a);
for(i=0;i<MaxName;i++){
printf("%d %s\n",a[i].no,a[i].name);
}
printf("请输入起始地点的编号：");
scanf("%d",&z);
printf("请输入结束地点的编号：");
scanf("%d",&x);
/* 初始化 */
for ( i=0; i<g->n; i++ )
for( j=0; j<g->n; j++ ) {
D[i][j] = g->arc[i][j];
path[i][j] = -1;
}
for( k=0; k<g->n; k++ )
for( i=0; i<g->n; i++ )
for( j=0; j<g->n; j++ )
if( D[i][k] + D[k][j] < D[i][j] ) {
D[i][j] = D[i][k] + D[k][j];
g->arc[i][j]=D[i][j];
if ( i==j && D[i][j]<0 )
return 0; /* 不能正确解决，返回错误标记 */
path[i][j] = k;
}
printf("\n\n\n最短路程为：%d\n\n\n",g->arc[z][x]);
return 1; /* 算法执行完毕，返回正确标记 */
}
void main(){
int i,z;
graph g;
creategraph(&g);
printf("*******欢迎来到3190704238的课程设计*******\n");
printf(" 1、根据编号查询地点的相关信息\n");
printf(" 2、根据编号查询道路的相关信息\n");
//导航方式我并没有去实现，可以使用road里的type去实现
printf(" 3、指定的出发、目的地点、导航方式（车行、骑行、步行），计算出最短路径\n");
printf(" 4、从指定地点出发游览完其他所有地点的路线信息\n");
printf(" 0、退出系统\n");
for(;;){
printf("请输入你要的选项：");
scanf("%d",&z);
switch(z)
{
case 1:Lookplace();break;
case 2:Lookroad();break;
case 3:Floyd(&g);break;
case 4:DFStravel(g);break;
case 0:exit(0);
}
}
}
