校园导航系统

时间:2022-06-27 10:16:28

#include "string.h"
#include "stdio.h"
#include "stdlib.h"
#define Max 32767
#define NUM 48
typedef struct ArcCell
{
    int adj; /* 相邻接的景点之间的路程 */
}ArcCell; /* 定义边的类型 */
typedef struct VertexType
{
    int number; /* 景点编号 */
    char* view; /* 景点名称 */
    char* desc; /* 景点描述 */
}VertexType; /* 定义顶点的类型 */
typedef struct
{
    VertexType vex[NUM]; /* 图中的顶点,即为景点 */
    ArcCell arcs[NUM][NUM]; /* 图中的边,即为景点间的距离*/
    int vexnum,arcnum; /* 顶点数,边数 */
}MGraph; /* 定义图的类型 */
MGraph G; /* 把图定义为全局变量*/
int P[NUM][NUM];
long int D[NUM]; /* 辅助变量存储最短路径长度 */
int x[48]={0};
void CreateUDN(int v,int a); /* 造图函数 */
void shuoming(); /*说明函数*/
void ShortestPath(int num); /*最短路径函数*/
void output(int sight1,int sight2); /*输出函数*/
char Menu(); /* 主菜单 */
void search(); /* 查询景点信息 */
char SearchMenu(); /* 查询子菜单 */
void HaMiTonian(int); /*哈密尔顿图的遍历*/
void NextValue(int);
void display(); /* 显示遍历结果 */
void main() /* 主函数 */
{
    int v0,v1;
    char ck;
    CreateUDN(NUM,198);
    do
    {
        ck=Menu();
        switch(ck)
        {
            case '1':
                system("cls");
                shuoming(); /* 输出景点列表 */
                printf("\n\n\t\t\t请选择起点景点(0~47):");
                scanf("%d",&v0);
                printf("\t\t\t请选择终点景点(0~47):");
                scanf("%d",&v1);
                ShortestPath(v0); /* 计算两个景点之间的最短路径 */
                output(v0,v1); /* 输出结果 */
                printf("\n\n\t\t\t\t请按任意键继续...\n");
                getchar();
                getchar();
                break;
            case '2':
                search();
                break;
            case '3':
                system("cls");
                shuoming();
                x[0]=1;
                HaMiTonian(1);
                printf("\n\n\t\t\t\t请按任意键继续...\n");
                getchar();
                getchar();
                break;
        }
    }while(ck!='t');
}

char Menu() /* 主菜单 */
{
    char c;
    int flag;
    do{
        flag=1;
        system("cls");
        shuoming();
        printf("\n"); /* 输出景点列表 */
        printf("\t\t\t┏━━━━━━━━━━━━━━━┑\n");
        printf("\t\t\t┃ ┃\n");
        printf("\t\t\t┃ 1、查询景点路径 ┃\n");
        printf("\t\t\t┃ 2、查询景点信息 ┃\n");
        printf("\t\t\t┃ 3、推荐参观路线 ┃\n");
        printf("\t\t\t┃ t、退出 ┃\n");
        printf("\t\t\t┃ ┃\n");
        printf("\t\t\t┗━━━━━━━━━━━━━━━┛\n");
        printf("\t\t\t\t请输入您的选择:");
        scanf("%c",&c);
        if(c=='1'||c=='2'||c=='3'||c=='t')
            flag=0;
    }while(flag);
    return c;
}

char SearchMenu() /* 查询子菜单 */
{
    char c;
    int flag;
    do{
        flag=1;
        system("cls");
        shuoming();
        printf("\n");
        printf("\t\t\t┏━━━━━━━━━━━━━━━┑\n");
        printf("\t\t\t┃ ┃\n");
        printf("\t\t\t┃ 1、按照景点编号查询 ┃\n");
        printf("\t\t\t┃ 2、按照景点名称查询 ┃\n");
        printf("\t\t\t┃ t、返回 ┃\n");
        printf("\t\t\t┃ ┃\n");
        printf("\t\t\t┗━━━━━━━━━━━━━━━┛\n");
        printf("\t\t\t\t请输入您的选择:");
        scanf("%c",&c);
        if(c=='1'||c=='2'||c=='t')
        flag=0;
    }while(flag);
    return c;
}

void search() /* 查询景点信息 */
{
    int num;
    int i;
    char c;
    char name[40];
    do
    {
        system("cls");
        c=SearchMenu();
        switch (c)
        {
            case '1':
                system("cls");
                shuoming();
                printf("\n\n\t\t请输入您要查找的景点编号:");
                scanf("%d",&num);
                for(i=0;i<NUM;i++)
                {
                    if(num==G.vex[i].number)
                    {
                    printf("\n\n\t\t\t您要查找景点信息如下:");
                    printf("\n\n\t\t\t%-25s\n\n",G.vex[i].desc);
                    printf("\n\t\t\t按任意键返回...");
                    getchar();
                    getchar();
                    break;
                    }
                }
                if(i==NUM)
                {
                    printf("\n\n\t\t\t没有找到!");
                    printf("\n\n\t\t\t按任意键返回...");
                    getchar();
                    getchar();
                }
                break;
            case '2':
                system("cls");
                shuoming();
                printf("\n\n\t\t请输入您要查找的景点名称:");
                scanf("%s",name);
                for(i=0;i<NUM;i++)
                {
                    if(!strcmp(name,G.vex[i].view))
                    {
                        printf("\n\n\t\t\t您要查找景点信息如下:");
                        printf("\n\n\t\t\t%-30s\n\n",G.vex[i].desc);
                        printf("\n\t\t\t按任意键返回...");
                        getchar();
                        getchar();
                        break;
                    }
                }
                if(i==NUM)
                {
                    printf("\n\n\t\t\t没有找到!");
                    printf("\n\n\t\t\t按任意键返回...");
                    getchar();
                    getchar();
                }
                break;
        }
    }while(c!='t');
}

void CreateUDN(int v,int a) /* 造图函数 */
{
    int i,j;
    G.vexnum=v; /* 初始化结构中的景点数和边数 */
    G.arcnum=a;
    for(i=0;i<G.vexnum;++i)
        G.vex[i].number=i; /* 初始化每一个景点的编号 */


/*    G.vex[0].view ="南大门"; G.vex[1].view ="音乐楼"; G.vex[2].view ="学生会堂";
    G.vex[3].view ="停车场"; G.vex[4].view ="博雅楼"; G.vex[5].view ="观物山";
    G.vex[6].view ="办公楼"; G.vex[7].view ="田径场"; G.vex[8].view ="润泽苑";
    G.vex[9].view ="实训楼"; G.vex[10].view="馥园餐厅"; G.vex[11].view="东门";
    G.vex[12].view="体育中心"; G.vex[13].view="次出口"; G.vex[14].view="篮球场";
    G.vex[15].view="足球场"; G.vex[16].view="篮球场"; G.vex[17].view="听心湖";
    G.vex[18].view="惟行楼"; G.vex[19].view="图书馆"; G.vex[20].view="美术楼";
    G.vex[21].view="农学楼"; G.vex[22].view="医学楼"; G.vex[23].view="惟真楼";
    G.vex[24].view="惟实楼"; G.vex[25].view="西门"; G.vex[26].view="聂耳广场";
    G.vex[27].view="篮球场"; G.vex[28].view="篮球场"; G.vex[29].view="网球场";
    G.vex[30].view="青年中心"; G.vex[31].view="澄明苑"; G.vex[32].view="博文楼";
    G.vex[33].view="博识楼"; G.vex[34].view="停车场"; G.vex[35].view="飨园餐厅";
    G.vex[36].view="足球场"; G.vex[37].view="篮球场"; G.vex[38].view="篮球场";
    G.vex[39].view="国际学术交流中心"; G.vex[40].view="高尔夫球场"; G.vex[41].view="专家公寓";
    G.vex[42].view="青年职工公寓"; G.vex[43].view="产业孵化基地"; G.vex[44].view="南大门";
    G.vex[45].view="自机学院实训用房"; G.vex[46].view="城建学院实训用房"; G.vex[47].view="实训基地";*/
    /* 初始化没一个景点名及其景点描述 */
   /* G.vex[0].desc ="本校的正大门"; G.vex[1].desc ="音乐学院专用教学楼"; G.vex[2].desc ="举办文艺会的场所";
    G.vex[3].desc ="停放车辆的地下车场"; G.vex[4].desc ="中和楼"; G.vex[5].desc ="校园的一座小山";
    G.vex[6].desc ="教务处"; G.vex[7].desc ="田径场"; G.vex[8].desc ="宿舍共14栋超市校园警卫";
    G.vex[9].desc ="实训基地"; G.vex[10].desc="食堂、教工和回族食堂"; G.vex[11].desc="东门";
    G.vex[12].desc="室内体育馆"; G.vex[13].desc="次出口"; G.vex[14].desc="篮球场";
    G.vex[15].desc="足球场"; G.vex[16].desc="篮球场"; G.vex[17].desc="美丽的小湖";
    G.vex[18].desc="教学楼 含医务室、展览馆"; G.vex[19].desc="图书馆"; G.vex[20].desc="美术学院专用教学楼";
    G.vex[21].desc="农学院专用教学楼"; G.vex[22].desc="医学院专用教学楼"; G.vex[23].desc="教学楼";
    G.vex[24].desc="惟实楼"; G.vex[25].desc="西门"; G.vex[26].desc="校园的主要广场";
    G.vex[27].desc="篮球场"; G.vex[28].desc="篮球场"; G.vex[29].desc="网球场";
    G.vex[30].desc="排练舞蹈的基地"; G.vex[31].desc="学生宿舍、超市、新知图书";G.vex[32].desc="教学楼";
    G.vex[33].desc="博识楼"; G.vex[34].desc="停车场"; G.vex[35].desc="飨园餐厅";
    G.vex[36].desc="足球场"; G.vex[37].desc="篮球场"; G.vex[38].desc="篮球场";
    G.vex[39].desc="国际学术交流"; G.vex[40].desc="高尔夫球场"; G.vex[41].desc="专家公寓";
    G.vex[42].desc="青年职工公寓"; G.vex[43].desc="产业孵化基地"; G.vex[44].desc="南大门";
    G.vex[45].desc="自机学院实训用房"; G.vex[46].desc="城建学院实训用房"; G.vex[47].desc="实训基地";*/
    /* 这里把所有的边假定为20000,含义是这两个景点之间是不可到达 */
    /*for(i=0;i<G.vexnum;++i)
        for(j=0;j<G.vexnum;++j)
            G.arcs[i][j].adj=Max;
    G.arcs[0][1].adj =G.arcs[1][0].adj =100;
    G.arcs[0][3].adj =G.arcs[3][0].adj =150 ;
    G.arcs[0][4].adj =G.arcs[4][0].adj =50;
    G.arcs[0][6].adj =G.arcs[6][0].adj =700;
    G.arcs[0][7].adj =G.arcs[7][0].adj =800;
    G.arcs[0][8].adj =G.arcs[8][0].adj =500;
    G.arcs[0][11].adj =G.arcs[11][0].adj =1000;
    G.arcs[0][13].adj =G.arcs[13][0].adj =1500;
    G.arcs[0][19].adj =G.arcs[19][0].adj =1100;
    G.arcs[0][25].adj =G.arcs[25][0].adj =1500;
    G.arcs[0][44].adj =G.arcs[44][0].adj =2100;
    G.arcs[1][2].adj =G.arcs[2][1].adj =20;
    G.arcs[1][4].adj =G.arcs[4][1].adj =100;
    G.arcs[2][3].adj =G.arcs[3][2].adj =70;
    G.arcs[2][4].adj =G.arcs[4][2].adj =150;
    G.arcs[3][5].adj =G.arcs[5][3].adj =70;
    G.arcs[3][7].adj =G.arcs[7][3].adj =550;
    G.arcs[3][19].adj =G.arcs[19][3].adj =800;
    G.arcs[3][20].adj =G.arcs[20][3].adj =300;
    G.arcs[3][21].adj =G.arcs[21][3].adj =70;
    G.arcs[4][5].adj =G.arcs[5][4].adj =200;
    G.arcs[4][7].adj =G.arcs[7][4].adj =100;
    G.arcs[4][19].adj =G.arcs[19][4].adj =600;
    G.arcs[5][6].adj =G.arcs[6][5].adj =250;
    G.arcs[5][19].adj =G.arcs[19][5].adj =200;
    G.arcs[5][20].adj =G.arcs[20][5].adj =350;
    G.arcs[6][7].adj =G.arcs[7][6].adj =150;
    G.arcs[6][18].adj =G.arcs[18][6].adj =270;
    G.arcs[6][19].adj =G.arcs[19][6].adj =600;
    G.arcs[7][8].adj =G.arcs[8][7].adj =200;
    G.arcs[8][9].adj =G.arcs[9][8].adj =150;
    G.arcs[8][10].adj =G.arcs[10][8].adj =50;
    G.arcs[8][12].adj =G.arcs[12][8].adj =300;
    G.arcs[8][14].adj =G.arcs[14][8].adj =160;
    G.arcs[10][11].adj =G.arcs[11][10].adj =350;
    G.arcs[11][12].adj =G.arcs[12][11].adj =200;
    G.arcs[12][13].adj =G.arcs[13][12].adj =250;
    G.arcs[13][17].adj =G.arcs[17][13].adj =130;
    G.arcs[13][25].adj =G.arcs[25][13].adj =950;
    G.arcs[13][27].adj =G.arcs[27][13].adj =180;
    G.arcs[13][31].adj =G.arcs[31][13].adj =550;
    G.arcs[14][15].adj =G.arcs[15][14].adj =120;
    G.arcs[15][16].adj =G.arcs[16][15].adj =20;
    G.arcs[15][18].adj =G.arcs[18][15].adj =150;
    G.arcs[16][17].adj =G.arcs[17][16].adj =190;
    G.arcs[17][18].adj =G.arcs[18][17].adj =60;
    G.arcs[17][19].adj =G.arcs[19][17].adj =200;
    G.arcs[17][26].adj =G.arcs[26][17].adj =280;
    G.arcs[17][27].adj =G.arcs[27][17].adj =170;
    G.arcs[17][30].adj =G.arcs[30][17].adj =150;
    G.arcs[17][35].adj =G.arcs[35][17].adj =400;
    G.arcs[18][19].adj =G.arcs[19][18].adj =100;
    G.arcs[18][26].adj =G.arcs[26][18].adj =240;
    G.arcs[18][30].adj =G.arcs[30][18].adj =400;
    G.arcs[19][20].adj =G.arcs[20][19].adj =230;
    G.arcs[19][26].adj =G.arcs[26][19].adj =30;
    G.arcs[20][22].adj =G.arcs[22][20].adj =150;
    G.arcs[21][22].adj =G.arcs[22][21].adj =50;
    G.arcs[22][23].adj =G.arcs[23][22].adj =100;
    G.arcs[23][24].adj =G.arcs[24][23].adj =150;
    G.arcs[23][25].adj =G.arcs[25][23].adj =50;
    G.arcs[23][32].adj =G.arcs[32][23].adj =50;
    G.arcs[24][26].adj =G.arcs[26][24].adj =50;
    G.arcs[24][33].adj =G.arcs[33][24].adj =50;
    G.arcs[25][26].adj =G.arcs[26][25].adj =350;
    G.arcs[25][32].adj =G.arcs[32][25].adj =50;
    G.arcs[25][44].adj =G.arcs[44][25].adj =500;
    G.arcs[26][30].adj =G.arcs[30][26].adj =260;
    G.arcs[26][35].adj =G.arcs[35][26].adj =200;
    G.arcs[27][28].adj =G.arcs[28][27].adj =20;
    G.arcs[28][29].adj =G.arcs[29][28].adj =20;
    G.arcs[29][30].adj =G.arcs[30][29].adj =200;
    G.arcs[29][31].adj =G.arcs[31][29].adj =200;
    G.arcs[30][31].adj =G.arcs[31][30].adj =200;
    G.arcs[31][35].adj =G.arcs[35][31].adj =120;
    G.arcs[31][36].adj =G.arcs[36][31].adj =200;
    G.arcs[31][37].adj =G.arcs[37][31].adj =180;
    G.arcs[32][33].adj =G.arcs[33][32].adj =180;
    G.arcs[32][38].adj =G.arcs[38][32].adj =600;
    G.arcs[32][39].adj =G.arcs[39][32].adj =160;
    G.arcs[33][34].adj =G.arcs[34][33].adj =20;
    G.arcs[33][39].adj =G.arcs[39][33].adj =150;
    G.arcs[33][40].adj =G.arcs[40][33].adj =200;
    G.arcs[34][35].adj =G.arcs[35][34].adj =230;
    G.arcs[35][38].adj =G.arcs[38][35].adj =150;
    G.arcs[35][40].adj =G.arcs[40][35].adj =300;
    G.arcs[36][37].adj =G.arcs[37][36].adj =50;
    G.arcs[37][38].adj =G.arcs[38][37].adj =50;
    G.arcs[38][45].adj =G.arcs[45][38].adj =50;
    G.arcs[39][40].adj =G.arcs[40][39].adj =200;
    G.arcs[39][41].adj =G.arcs[41][39].adj =50;
    G.arcs[40][41].adj =G.arcs[41][40].adj =50;
    G.arcs[40][42].adj =G.arcs[42][40].adj =50;
    G.arcs[41][42].adj =G.arcs[42][41].adj =50;
    G.arcs[42][43].adj =G.arcs[43][42].adj =50;
    G.arcs[43][44].adj =G.arcs[44][43].adj =100;
    G.arcs[44][46].adj =G.arcs[46][44].adj =100;
    G.arcs[45][46].adj =G.arcs[46][45].adj =50;
    G.arcs[45][47].adj =G.arcs[47][45].adj =150;
    G.arcs[46][47].adj =G.arcs[47][46].adj =150;*/
   
   
}
void shuoming() /* 说明函数 */
{
    int i,k=0;
    printf("\n\t\t******************欢迎烟台大学校园导航旅游程序****************\n");
    printf("\t__________________________________________________________________\n");
    printf("\t\t景点名称\t\t↓\t景点描述\n");
    printf("\t________________________________↓_________________________________\n");
    for(i=0;i<NUM;i++)
    {
        printf("\t%c (%2d)%-10s\t\t↓\t%-30s%c\n",25,i,G.vex[i].view,G.vex[i].desc,24); /* 输出景点列表 */
        k=k+1;
    }
    printf("\t________________________________↓_________________________________\n");
}
void ShortestPath(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.arcs[num][v].adj;/* 将与之相关的权值放入D中存放 */
        for(w=0;w<NUM;w++) /* 设置为空路径 */
            P[v][w]=0;
        if(D[v]<32767) /* 存在路径 */
        {
            P[v][num]=1; /* 存在标志置为一 */
            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.arcs[v][w].adj)<D[w])) /*不在s集合,并且比以前所找到的路径都短就更新当前路径 */
            {
                D[w]=min+G.arcs[v][w].adj;
                for(t=0;t<NUM;t++)
                P[w][t]=P[v][t];
                P[w][w]=1;
            }
    }
}
void output(int sight1,int sight2) /* 输出函数 */
{
    int a,b,c,d,q=0;
    a=sight2; /* 将景点二赋值给a */
    if(a!=sight1) /* 如果景点二不和景点一输入重合,则进行... */
    {
        printf("\n\t从%s到%s的最短路径是",G.vex[sight1].view,G.vex[sight2].view);/* 输出提示信息 */
        printf("\t(最短距离为 %dm.)\n\n\t",D[a]); /* 输出sight1到sight2的最短路径长度,存放在D[]数组中 */
        printf("\t%s",G.vex[sight1].view); /* 输出景点一的名称 */
        d=sight1; /* 将景点一的编号赋值给d */
        for(c=0;c<NUM;++c)
        {
            gate: /* 标号,可以作为goto语句跳转的位置 */
            P[a][sight1]=0;
            for(b=0;b<NUM;b++)
            {
                if(G.arcs[d][b].adj<32767&&P[a][b]) /* 如果景点一和它的一个临界点之间存在路径且最短路径 */
                {
                    printf("-->%s",G.vex[b].view); /* 输出此节点的名称 */
                    q=q+1; /* 计数变量加一,满8控制输出时的换行 */
                    P[a][b]=0;
                    d=b; /* 将b作为出发点进行下一次循环输出,如此反复 */
                    if(q%48==0)
                        printf("\n");
                    goto gate;
                }
            }
        }
    }

}
void HaMiTonian(int m) /* 哈密顿图的遍历 */
{
    if(m>48)
        return;
    L: NextValue(m);
    if(x[m]==0)
        return;
    if(m==7&&G.arcs[0][x[48]-1].adj!=20000)
        display();
    else
        HaMiTonian(m+1);
    goto L;
}
void NextValue(int k)
{
    int j;
    l:x[k]=(x[k]+1)%10;
    if(x[k]==0)
        return;
    if(G.arcs[x[k-1]-1][x[k]-1].adj!=20000)
    {
        for(j=0;j<k;j++)
            if(x[j]==x[k])
                goto l;
        return;
    }
    else
        goto l;
}
void display()
{
    int i=0;
    printf("\n\n\t");
    for(i=0;i<48;i++)
        printf("%s->",G.vex[x[i]-1].view);
    printf("出口");
    printf("\n");
}