Demo entry 6780796

maps

   

Submitted by anonymous on Dec 29, 2018 at 07:19
Language: C. Code size: 13.0 kB.

#include "func.h"
char info[][100]={
    {},
    {"学校的正大门,气势恢宏"},
    {"雷丁学院的主要教学区"},
    {"体育馆,内有羽毛球馆、健身房等等,大型活动的开办地"},
    {"文德楼,主要教学区,分为N,C,S三个区域,一楼有自提柜"},
    {"东苑食堂,东苑篮球场,硕园,晖园"},
    {"北门,学校出口之一"},
    {"小东门,目前在施工中"},
    {"尚贤楼,数统院的院办,教学区"},
    {"明德楼,主要教学区"},
    {"中苑老食堂,中苑新食堂,沁园,中苑体育场"},
    {"人才公寓,门外有快递点"},
    {"计算机楼,计软院院办"},
    {"图书馆,学习的好地方,位置很紧缺"},
    {"西苑新食堂,文园,西苑操场"},
    {"滨江学院的教学区"}

};
//打印主界面
void PrintMenu()
{
    printf("|=============================================================================================|\n");
    printf("|                                   南信大校园导航                                            |\n");
    printf("|=============================================================================================|\n");
    printf("\t\t\t\t [1] 打印校园平面图 \n");
    printf("\t\t\t\t [2] 指定起点到终点的所有路径 \n");
    printf("\t\t\t\t [3] 指定起点到终点的最短路径 \n");
    printf("\t\t\t\t [4] 查询地点的详细信息\n");
    printf("\t\t\t\t [5] 定制路线\n");
    printf("\t\t\t\t [0] 退出 \n");
    printf("\n");
    printf("\t\t\t\t @made by 20178315010 \n");
}
void PrintMap()
{
    printf("                      +--------【11】                   【6】                           \n");
    printf("                      |             \\                    \\                          \n");
    printf("                      |            【12】                 \\                         \n"); 
    printf("                      |                 \\                  \\                        \n");
    printf("                【14】-------【13】-------【9】--------------【5】------【3】            \n");
    printf("                 /                                                       \\          \n");
    printf("                /                                                        【1】        \n"); 
    printf("               /                                                ---------/           \n");
    printf("              /                                                /                     \n");
    printf("            【15】--------------【10】--【8】-----【4】--------【2】\n");
    printf("                                  \\   /                                            \n");
    printf("                                   【7】\n");
    printf("\n");
    printf("          [1] 正门\t[4] 文德楼\t[7] 小东门\t[10] 中苑\t[13] 图书馆\n");
    printf("          [2] 雷丁学院\t[5] 东苑\t[8] 尚贤楼\t[11] 人才公寓\t[14] 西苑\n");
    printf("          [3] 体育馆\t[6] 北门\t[9] 明德楼\t[12] 计算机楼\t[15] 滨江学院\n");
}

void Choice()
{
    int choice;
    MGraph G;
    CreateFixedGraph(&G);
    printf("\t您的选择[请输入选择序号]:");
    scanf("%d",&choice);
    switch(choice)
    {
        case 1:PrintMap();break;  //打印校园平面图
        case 2:SearchAll(&G);break; //查找所有路径
        case 3:SearchShort(&G);break; //查找最短路径
        case 4:SearchInfo(&G);break; //查询指定地点的详细信息
        case 5:Custom(&G);break;    //定制路径
        case 0:break;
        default:
            printf("无效选项!\n");
    }
    if(choice!=0)
    {
        getchar();
        printf("\t\t\t\t[enter]键返回...\n");
        getchar();
        PrintMenu();
        Choice();
    }
}
void CreateFixedGraph(MGraph *G)
{
    char vex[][50]={
    //  0    1        2          3         4          5        6
        {},{"正门"},{"雷丁学院"},{"体育馆"},{"文德楼"},{"东苑"},{"北门"},
    //      7         8          9       10        11          12
        {"小东门"},{"尚贤楼"},{"明德楼"},{"中苑"},{"人才公寓"},{"计算机楼"},
    //      13       14        15
        {"图书馆"},{"西苑"},{"滨江学院"}
    };
   int edge[][3]=
    {
        {0,0,0},
        {1,2,230},
        {1,3,260},
        {2,3,50},
        {2,4,440},
        {2,5,360},
        {3,4,440},
        {3,5,410},
        {4,5,240},
        {4,8,360},
        {4,9,310},
        {5,9,280},
        {5,6,130},
        {7,10,370},
        {7,8,320},
        {8,10,360},
        {8,9,130},
        {9,10,400},
        {9,12,300},
        {10,13,330},
        {10,11,650},
        {11,12,480},
        {11,13,510},
        {13,14,660},
        {14,15,400}
    };

    int vexlen=LENGTH(vex)-1;
    int edgelen=LENGTH(edge)-1;
    //printf("%d %d",vexlen,edgelen);
    G->vexnum=vexlen;
    G->arcnum=edgelen;
    //清理arcs
    for(int i = 1; i <= G->vexnum; i++){
        for(int j = 1; j <= G->vexnum; j++){
            G->arcs[i][j] = INFINITY;
        }
    }

    //初始化vexs[]
    for(int i=1;i<=G->vexnum;i++)
    {
        G->vexs[i].NO=i;
        strcpy(G->vexs[i].name,vex[i]);
        //printf("%s",G->vexs[i].name);
    }
    //初始化arcs
    char name1[50],name2[50];
    for(int i=1;i<=G->arcnum;i++)
    {
        G->arcs[edge[i][0]][edge[i][1]]=edge[i][2];
        G->arcs[edge[i][1]][edge[i][0]]=edge[i][2];
    }
    //printf("done!");
}
int LocateVex(MGraph *G,char name[])
{
    for(int i=1;i<=G->vexnum;i++)
    {
        if(!strcmp(G->vexs[i].name,name))
            return i;
    }
    return -1;
}
void PrintGraph(MGraph *G)
{
    for(int i=1;i<=G->vexnum;i++)
        printf("%12s",G->vexs[i].name);
    printf("\n");
    for(int i=1;i<=G->vexnum;i++){
        for(int j=1;j<=G->vexnum;j++)
        {
            if(G->arcs[i][j]==INFINITY)
                printf("           #");
            else
                printf("%12d",G->arcs[i][j]);
        }
        printf("\n");
    }
}
int visited[MAX_VERTEX_NUM+1]; //是否已经访问过的标志
int pre[MAX_VERTEX_NUM+1];     //存放一条路各顶点的坐标
void SearchAll(MGraph *G)
{
    int start,end;
    int dist =0 ; //起始点距离
    char s[50],e[50];
    printf("\t请输入起点:");
    scanf("%s",s);
    start=LocateVex(G,s);
    while(start==-1)
    {
        printf("\t不存在此地点!\n");
        printf("\t请重新输入:");
        scanf("%s",s);
        start=LocateVex(G,s);
    }
    printf("\t请输入终点:");
    scanf("%s",e);
    end=LocateVex(G,e);
    while(end==-1)
    {
        printf("\t不存在此地点!\n");
        printf("\t请重新输入:");
        scanf("%s",e);
        end=LocateVex(G,e);
    }
    //清零
    for(int i=1;i<=MAX_VERTEX_NUM;i++)
    {
        visited[i]=0;
    }
    visited[start]=1; //访问起点
    pre[1]=start;     //路径的第一个起点
    printf("从%s到%s可以这么走:\n",G->vexs[start].name,G->vexs[end].name);
    SearchDFS(G,start,end,1,dist);

}
void SearchDFS(MGraph *G,int start,int end,int length,int dist)
{
    if(pre[length]==end&&length<G->vexnum) //已经找到一条通路,就直接把存在pre里面的这条通路打印出来
    {
        printf("%s ",G->vexs[pre[1]].name);//打印起点
        for(int i=2;i<=length;i++)
        {
            printf("--->%s",G->vexs[pre[i]].name);
            if(G->arcs[pre[i-1]][pre[i]]!=INFINITY)
                dist+=G->arcs[pre[i-1]][pre[i]];   //计算距离
        }
        printf("\nthe distance:%d\n",dist);
        dist=0;//重置dist=0
    }
    else
    {
        int count=1;
        while(count<=G->vexnum){ //对每个节点深度访问一下
            if(!visited[count]&&G->arcs[pre[length]][count]!=INFINITY) //该节点没访问过且能从上一节点与该节点是通的
            {
                visited[count]=1;
                pre[length+1]=count;
                SearchDFS(G,count,end,length+1,dist);
                visited[count]=0; //后面走不下去就回退,去掉访问标志
            }
            count++;
        }
    }
}
void SearchShort(MGraph *G)
{
    int start,end;
    int dist[MAX_VERTEX_NUM+1]; //存放所有搜索出来的distance值
    int path[MAX_VERTEX_NUM+1][MAX_VERTEX_NUM+1]={0};
    char s[50],e[50];
    printf("\t请输入起点:");
    scanf("%s",s);
    start=LocateVex(G,s);
    while(start==-1)
    {
        printf("\t不存在此地点!\n");
        printf("\t请重新输入:");
        scanf("%s",s);
        start=LocateVex(G,s);
    }
    printf("\t请输入终点:");
    scanf("%s",e);
    end=LocateVex(G,e);
    while(end==-1)
    {
        printf("\t不存在此地点!\n");
        printf("\t请重新输入:");
        scanf("%s",e);
        end=LocateVex(G,e);
    }
    SearchDIJ(G,start,end,dist,path);
}
int SearchDIJ(MGraph *G,int start,int end,int dist[],int path[][MAX_VERTEX_NUM+1])
{
    int mindist;//最短距离

    //初始化
    for(int i=1;i<=G->vexnum;i++)
    {
        dist[i]=G->arcs[start][i];    //读入开始行的邻接信息
        if(G->arcs[start][i]!=INFINITY)
            path[i][1]=start;         //记录path,第一步都是从start开始
    }
    path[start][0]=1;   //记录开始行状态是已被录入,即已被访问

    //找最短路径
    int keep; //记录每轮最小的节点序号
    for(int i=2;i<=G->vexnum;i++)
    {
        mindist =INFINITY;
        for(int j=1;j<=G->vexnum;j++)
        {
            if(!path[j][0]&&dist[j]<mindist)
            {
                mindist=dist[j];
                keep=j;
            }
        }
        if(mindist == INFINITY) break;
        path[keep][0]=1; //将dist最小行标记为以访问

        //修改dist[]状态,更新最小路径
        for(int j=1;j<=G->vexnum;j++)
        {
            if(!path[j][0]&&G->arcs[keep][j]<INFINITY&&G->arcs[keep][j]+dist[keep]<dist[j])
            //该节点未被收录且最小keep行到该节点可通且源点到keep行加上keep行到j小于当前记录的原点到j的距离
            {
                //更新dist
                dist[j]=dist[keep]+G->arcs[keep][j];
                int t=1;
                while(path[keep][t])
                {
                    path[j][t]=path[keep][t]; //更新j前面的走法为keep的走法
                    t++;
                }
                path[j][t]=keep; //然后最后一步走到keep,这样距离当前最短
                path[j][t+1]=0;
            }
        }
    }
    if(dist[end]==INFINITY)
    {
        printf("\t此路不通!!!!!!\n");
        return ;
    }
    //否则输出最短路径
    printf("从%s到%s最快的走法:",G->vexs[start].name,G->vexs[end].name);
    printf("%s",G->vexs[start].name);
    for(int j=2;path[end][j];j++)
        printf("--->%s ",G->vexs[path[end][j]].name);
    printf("--->%s",G->vexs[end].name);
    printf("\nthe min distance:%d\n",dist[end]);
    return dist[end];
}
void SearchInfo(MGraph *G)
{
    char input[50];
    printf("\t请输入想要查询的地点:");
    scanf("%s",input);
    int index=LocateVex(G,input);
    if(index==-1)
    {
        printf("\t没有该地点!");
        return;
    }
    printf("\t%d ",index);
    printf("%s的详细介绍:\n",input);
    printf("\t%s\n",info[index]);
}
void Custom(MGraph *G)
{
    int start,end;
    int distall =0 ; //起始点距离
    int dist[MAX_VERTEX_NUM+1]; //存放所有搜索出来的distance值
    int path[MAX_VERTEX_NUM+1][MAX_VERTEX_NUM+1]={0};
    char s[50],e[50];
    printf("\t请输入起点:");
    scanf("%s",s);
    start=LocateVex(G,s);
    while(start==-1)
    {
        printf("\t不存在此地点!\n");
        printf("\t请重新输入:");
        scanf("%s",s);
        start=LocateVex(G,s);
    }
    printf("\t请输入终点:");
    scanf("%s",e);
    end=LocateVex(G,e);
    while(end==-1)
    {
        printf("\t不存在此地点!\n");
        printf("\t请重新输入:");
        scanf("%s",e);
        end=LocateVex(G,e);
    }
    char fplace[50];
    int place;
    printf("\t请输入你想途经的一个地点:");
    scanf("%s",fplace);
    place=LocateVex(G,fplace);
    while(place==-1)
    {
        printf("\t不存在此地点!\n");
        printf("\t请重新输入:");
        scanf("%s",fplace);
        place=LocateVex(G,fplace);
    }
    //清零
    for(int i=1;i<=MAX_VERTEX_NUM;i++)
    {
        visited[i]=0;
    }
    visited[start]=1; //访问起点
    pre[1]=start;     //路径的第一个起点
    printf("从%s到%s且途经%s可以这么走:\n",G->vexs[start].name,G->vexs[end].name,G->vexs[place].name);
    CustomAll(G,start,place,end,1,distall);
    printf("===========================================================\n");
    CustomShort(G,start,place,end,dist,path);
}
void CustomAll(MGraph *G,int start,int place,int end,int length,int dist)
{
    int flag=0;
    if(pre[length]==end&&length<G->vexnum) //已经找到一条通路,就直接把存在pre里面的这条通路打印出来
    {
        for(int i=1;i<=length;i++)
        {
            if(pre[i]==place)
            {
                flag = 1;
                break;
            }
        }
        if(flag){
        printf("%s ",G->vexs[pre[1]].name);//打印起点
        for(int i=2;i<=length;i++)
        {
            printf("--->%s",G->vexs[pre[i]].name);
            if(G->arcs[pre[i-1]][pre[i]]!=INFINITY)
                dist+=G->arcs[pre[i-1]][pre[i]];   //计算距离
        }
        printf("\nthe distance:%d\n",dist);
        dist=0;//重置dist=0
        }
        else
        {
            //printf("\t无法找到合适路线\n");
        }
    }
    else
    {
        int count=1;
        while(count<=G->vexnum){ //对每个节点深度访问一下
            if(!visited[count]&&G->arcs[pre[length]][count]!=INFINITY) //该节点没访问过且能从上一节点与该节点是通的
            {
                visited[count]=1;
                pre[length+1]=count;
                CustomAll(G,count,place,end,length+1,dist);
                visited[count]=0; //后面走不下去就回退,去掉访问标志
                
            }
            count++;
        }
    }
}
void CustomShort(MGraph *G,int start,int place,int end,int dist[],int path[][MAX_VERTEX_NUM+1])
{
    int before = SearchDIJ(G,start,place,dist,path);
    int after  =SearchDIJ(G,place,end,dist,path);
    printf("\t合计最短路径:%d",before+after);
}

    

This snippet took 0.03 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).