【校园导游】

（一）问题描述
功能要求：设计一个校园导游程序，为来访的客人提供各种信息查询服务。查询服务有：提供任意景点的信息，提供任意两点之间的最短路径，提供任意景点之间的所有路径，提供多个景点之间的最佳访问路径。
输入输出要求：用c语言的方式正确输入输出；
(二)算法结构分析与设计
1.算法中抽象数据类型定义： stack,struct
2.算法主要思路：
(三)算法详细设计
1.采用c++定义相关的数据类型：int，
2.算法中主要函数及其作用
void Creat_vertex() //创建无向图
void Creat_maps() //创建地图的信息
void Search_info() //信息查询
void Floyd() //弗洛伊德·最短路径
void Dfs_allpath(int s,int e) //两景点间所有路径查询
void Bestpath_Multispot() //多景点间访问路线查询
void Dis_map() //地图
(四）代码
#include
#include
#include
#include
#include
using namespace std;
#define INF 999999
#define M 20
int dist[M][M];///距离
int path[M][M];///路径
int Stack[M];///路径栈
int top;///栈顶
int counts;///记录路径数
int visited[M];///标记数组
using namespace std;
struct vertex///景点信息结构体
{
    int num;///景点编号
    char name[20];///景点名称
    char info[300];///景点介绍
};
struct maps
{
    int n;///点数
    int m;///边数
    vertex v[M];
    int edgs[M][M];///邻接矩阵
} g; ///景点图的结构体
void Creat_vertex()
{
    g.v[0].num=1;
    strcpy(g.v[0].name,"南门");
    strcpy(g.v[0].info,"南苑的正门");
    g.v[1].num=2;
    strcpy(g.v[1].name,"多功能馆");
    strcpy(g.v[1].info,"这是举办文艺活动的场所");
    g.v[2].num=3;
    strcpy(g.v[2].name,"食堂");
    strcpy(g.v[2].info,"这里南院的食堂");
    g.v[3].num=4;
    strcpy(g.v[3].name,"主楼");
    strcpy(g.v[3].info,"上机实验一般在这里");
    g.v[4].num=5;
    strcpy(g.v[4].name,"小花园");
    strcpy(g.v[4].info,"南苑的小花园");
    g.v[5].num=6;
    strcpy(g.v[5].name,"九教");
    strcpy(g.v[5].info,"这是九教");
    g.v[6].num=7;
    strcpy(g.v[6].name,"图书馆");
    strcpy(g.v[6].info,"图书馆");
    g.v[7].num=8;
    strcpy(g.v[7].name,"宿舍");
    strcpy(g.v[7].info,"这是女生宿舍");
    g.v[8].num=9;
    strcpy(g.v[8].name,"超市");
    strcpy(g.v[8].info,"这是学校的超市");
    g.v[9].num=10;
    strcpy(g.v[9].name,"六教");
    strcpy(g.v[9].info,"这是综合楼六教");
}
void Creat_maps()
{
    int i,j;
    g.n=10;///10个景点
    g.m=12;///12条双向路径
    for(i=0; i
        for(j=0; j
            g.edgs[i][j]=INF;
        }
    }
    g.edgs[0][1]=g.edgs[1][0]=500;///写入边的信息
    g.edgs[0][6]=g.edgs[6][0]=1000;
    g.edgs[1][3]=g.edgs[3][1]=200;
    g.edgs[1][6]=g.edgs[6][1]=200;
    g.edgs[2][6]=g.edgs[6][2]=400;
    g.edgs[3][4]=g.edgs[4][3]=300;
    g.edgs[4][5]=g.edgs[5][4]=300;
    g.edgs[5][6]=g.edgs[6][5]=300;
    g.edgs[5][7]=g.edgs[7][5]=200;
    g.edgs[5][9]=g.edgs[9][5]=200;
    g.edgs[7][8]=g.edgs[8][7]=100;
    g.edgs[8][9]=g.edgs[9][8]=500;
}
void Search_info()
{
    int i,n;
    printf("河北大学的景点有：n");
    for(i=0; i<10; i++)
    {
        printf("%d:%sn",g.v[i].num,g.v[i].name);
    }
    while(1)
    {
        printf("请输入你想要查询的景点编号：n");
        printf("按0退出nn");
        scanf("%d",&n);
        getchar();
        if(n==0)
        {
            break;
        }
        else if(n<0||n>10)
        {
            printf("输入有误，请重新输入！！！nn");
            continue;
        }
        else
        {
            printf("%d:%sn",g.v[n-1].num,g.v[n-1].name);
            printf("%snn",g.v[n-1].info);
        }
    }
    return ;
}
void Floyd() ///弗洛伊德
{
    int i,j,k;
    for(i=0; i
        for(j=0; j
            dist[i][j]=g.edgs[i][j];
            if(i!=j&&dist[i][j]
                path[i][j]=i;
            }
            else
            {
                path[i][j]=-1;///-1代表不可达
            }
        }
    }
    //printf("%dn",g.n);
    for(k=0; k
        for(i=0; i
            for(j=0; j
                if(dist[i][j]>(dist[i][k]+dist[k][j]))
                {
                    dist[i][j]=dist[i][k]+dist[k][j];///更新
                    path[i][j]=k;         ///path用于记录最短路径上的结点*/
                }
            }
        }
    }
    return ;
}
void Floyd_print(int s, int e)
{
    if(path[s][e]==-1||path[s][e]==e||path[s][e]==s)///递归终止条件
    {
        return;
    }
    else
    {
        Floyd_print(s,path[s][e]);///将中间点作为终点继续打印路径
        printf("%s->",g.v[path[s][e]].name);///打印中间景点名字
        Floyd_print(path[s][e],e);///将中间点作为起点继续打印路径
    }
}

void Dfs_allpath(int s,int e)
{
    int dis=0;
    int i,j;
    Stack[top]=s;
    top++;  ///起点入栈
    visited[s]=1;///标记入栈
    for(i=0; i
        if(g.edgs[s][i]>0&&g.edgs[s][i]!=INF&&!visited[i])
        {
            ///表明两点可达且未被访问
            if(i==e)///DFS到了终点，打印路径
            {
                printf("第%d条路:",counts++);
                for(j=0; j
                    printf("%s->",g.v[Stack[j]].name);
                    if(j
                        dis=dis+g.edgs[Stack[j]][Stack[j+1]];
                    }
                }
                dis=dis+g.edgs[Stack[top-1]][e];
                printf("%sn",g.v[e].name);///打印终点
                printf("总长度是：%dmnn",dis);
            }
            else///不是终点接着DFS
            {
                Dfs_allpath(i,e);
                top--;///支路全被访问一遍,顶点出栈
                visited[i]=0;///出栈点标记为已出栈，允许下次访问
            }
        }
    }
}
void Bestpath_Multispot()
{
    int vNum[M]= {0};
    int i,j,dis;
    j=1;
    dis=0;///统计全程总长
    printf("请输入你要游览的第%d个景点的编号（输入-1结束输入）：",j);
    scanf("%d",&vNum[j-1]);
    while(vNum[j-1]!=-1&&j<10)
    {
        printf("请输入你要游览的第%d个景点编号：",++j);
        scanf("%d", &vNum[j-1]);
        if(vNum[j-1]==-1)
        {
            break;
        }
    }
    printf("n这是最佳访问路径：");
    for(i=0; vNum[i]>0&&vNum[i+1]>0; i++)
    {
        printf("%s->",g.v[vNum[i]-1].name);///输出路径上的起点
        Floyd_print(vNum[i]-1,vNum[i+1]-1);///利用佛洛依德算法
        dis+=dist[vNum[i]-1][vNum[i+1]-1];
    }
    printf("%snn",g.v[vNum[j-2]-1].name);//
    printf("全程总长为：%dmnn",dis);
}

void Dis_menu()
{
    printf("n");
    printf("       ************欢迎使用河北大学南院导游咨询系统***********nn");
    printf("       *****   1.信息查询           ******************n");
    printf("       *****   2.两景点之间最短路查询       ******************n");
    printf("       *****   3.两景点间所有路径查询       ******************n");
    printf("       *****   4.多景点间访问路线查询       ******************n");
    printf("       *****   5.退出系统                   ******************n");
    printf("       *******************************************************n");
    return ;
}
void Dis_map()
{
    printf("n                          *河北大学南院校园地图一览*nn");
    printf("                                                               (9)超市       n");
    printf("                                               (8)宿舍           ◎   n");
    printf("                                                 ◎--------------|          n");
    printf("                                                 |               |           n");
    printf("                                                 |               |    n");
    printf("                          ⑸小花园       (6)九教 |       (10)六教|      n");
    printf("                          ◎                    ◎      ◎       |          n");
    printf("      ⑷主楼◎-------|----------------—-|------|----------------|          n");
    printf("                |          |                    |                 n");
    printf("                |          |                    |                 n");
    printf("                |          |                    ◎                           n");
    printf("                ◎⑵多功能馆            (7)图书馆                      n");
    printf("                |--------------------------------|                          n");
    printf("                |                                |---------------⑶食堂        n");
    printf("                |                                                            n");
    printf("                ◎⑴ 南院正门                                               nn");
}
int main()
{
    int i,n;
    int start,ends;
    Creat_vertex();
    Creat_maps();
    Dis_map();
    while(1)
    {
        Dis_menu();
        printf("请输入需要操作的命令：n");
        scanf("%d",&n);
        getchar();
        if(n<1||n>5)
        {
            printf("输入有误，请重新输入！！！n");
            continue;
        }
        else
        {
            if(n==1)
            {
                Search_info();
            }
            else if(n==2)
            {
                Dis_map();
                printf("请输入起点的景点：n");
                scanf("%d",&start);
                printf("请输入终点的景点：n");
                scanf("%d",&ends);
                Floyd();///弗洛伊德
                printf("从%s到%s最短距离是：%dn",g.v[start-1].name,g.v[ends-1].name,dist[start-1][ends-1]);
                printf("%s->",g.v[start-1].name);
                Floyd_print(start-1, ends-1);
                printf("%sn",g.v[ends-1].name);
            }
            else if(n==3)
            {
                Dis_map();
                counts=1;///起始路径数为1
                printf("请输入起点的景点：n");
                scanf("%d",&start);
                printf("请输入终点的景点：n");
                scanf("%d",&ends);
                Dfs_allpath(start-1,ends-1);
            }
            else if(n==4)
            {
                Dis_map();
                Floyd();///弗洛伊德
                Bestpath_Multispot();
            }
            else if(n==5)
            {
                return 0;
            }
        }

    }
    return 0;
}
【校园导游】

C/C++/C#相关栏目本月热门文章
