1234.cpp

用c写的校园导游系统 用弗洛依德算法实现,能够查询校园任意两个景点的最佳路径.

/*
                                    校园导游咨询
  [问题描述]   
          设计一个校园导游程序，为来访的客人提供各种信息查询服务。   
  [基本要求]   
          (1)设计你的学校的校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。   
          (2)为来访客人提供图中任意景点相关信息的查询。   
          (3)为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。   
  [测试数据]   
          由个人根据实际情况自行指定。   
  [实现提示]   
          一般情况下，校园的道路是双向通行的，可设校园平面图是一个无向网。顶点和边均含有相关信息。
*/

/*包含头文件*/
#include<stdio.h> 
#include<process.h>
#include<iomanip>
using namespace std;
/*定义符号常量*/
#define INT_MAX 10000
#define n 10

/*定义全局变量*/
int cost[n][n];/* 边的值*/
int shortest[n][n];/* 两点间的最短距离*/
int path[n][n];/* 经过的景点*/

/*自定义函数原型说明*/
void introduce();
int shortestdistance();
void floyed(); 
void display(int i,int j);

void main() 
{/*主函数*/
    int i,j; 
    char k; 
    for(i=0;i<=n;i++)
        for(j=0;j<=n;j++)
            cost[i][j]=INT_MAX; 
    cost[1][2]=cost[2][1]=2;
    cost[2][3]=cost[3][2]=1;
    cost[2][4]=cost[4][2]=2;
    cost[3][4]=cost[4][3]=4;
    cost[1][4]=cost[4][1]=5;
    cost[2][5]=cost[5][2]=3;
    cost[5][10]=cost[10][5]=8;
    cost[5][6]=cost[6][5]=2;
    cost[6][7]=cost[7][6]=1;
    cost[7][8]=cost[8][7]=3;
    cost[7][9]=cost[9][7]=3;
    cost[8][9]=cost[9][8]=4;
    cost[1][1]=cost[2][2]=cost[3][3]=cost[4][4]=cost[5][5]=0; 
    cost[6][6]=cost[7][7]=cost[8][8]=cost[9][9]=cost[10][10]=0;
    while(1)
    { 
        printf("----------------欢迎使用校园导游系统!----------------\n");
        printf("1.景点信息查询………请按 i (introduc)键\n");
        printf("2.景点最短路径查询…请按 s (shortestdistance)键\n");
        printf("3.退出系统……………请按 e (exit)键\n");
        printf("学校景点列表:\n");
        printf("1:学校正门  ");
        printf("2:教学楼    ");
        printf("3:足球场    ");
        printf("4:篮球场    ");
        printf("5:建行取款机\n");
        printf("6:办公楼    ");
        printf("7:网球场    ");
        printf("8:图书馆    ");
        printf("9:西园餐厅  ");
        printf("10:宿舍楼\n");
        printf("请选择服务:");
        scanf("\n%c",&k); 
        switch(k) 
        { 
            case 'i':
                printf("进入景点信息查询:");
                introduce();
                break; 
            case 's':
                printf("进入最短路径查询:");
                shortestdistance();
                break; 
            case 'e':
                exit(0); 
            default:
                printf("输入信息错误！\n请输入字母i或s或e.\n");
                break; 
        } system("cls");
    } 
}/*main*/

void introduce()
{/*景点介绍*/
    int a;
    printf("您想查询哪个景点的详细信息?请输入景点编号:");
    scanf("%d",&a);
    getchar();
    printf("\n");
    switch(a)
    {
        case 1: 
            printf("1:学校正门\n\n　　学校的正门，气势宏伟。\n\n");break;
        case 2: 
            printf("2:教学楼\n\n　　学生上课及的场地，共有五层，配有微机室语音室等。\n\n");break; 
        case 3: 
            printf("3:足球场\n\n　　学生体育课或足球比赛使用场地。\n\n");break; 
        case 4: 
            printf("4:篮球场\n\n　　学校篮球场，早上进行升旗仪式和早操的场地。\n\n");break; 
        case 5: 
            printf("5:建行取款机\n\n　　学校设立的建设银行取款处，内有atm提款机。\n\n");break; 
        case 6: 
            printf("6:办公楼\n\n　　学校的主要办公楼之一，是进行校务管理的办公楼。\n\n");break; 
        case 7: 
            printf("7:网球场\n\n　　学生使用的网球场地。\n\n");break; 
        case 8: 
            printf("8:图书馆\n\n　　学校信息资源中心，内设大量的自习室，图书量丰富。\n\n");break; 
        case 9: 
            printf("9:西园餐厅\n\n　　学校最大的食堂分两层，上层是广播站。\n\n\n");break; 
        case 10: 
            printf("10:宿舍楼\n\n　　主要是男生的住宿处，共有三座。\n\n");break; 
        default:
            printf("景点编号输入错误！请输入1->10的数字编号！\n\n"); break; 
    }system("pause");system("cls");
}/*introduce*/

int shortestdistance()
{/*要查找的两景点的最短距离*/
    int i,j; 
    printf("请输入要查询的两个景点的编号(1->10的数字编号并用','间隔):");
    scanf("%d,%d",&i,&j);
    if(i>n||i<=0||j>n||j<0)
    {
        printf("输入信息错误！\n\n");
        printf("　　请输入要查询的两个景点的编号(1->10的数字编号并用','间隔):\n");
        scanf("%d,%d",&i,&j);
    }
    else
    {
        floyed();
        display(i,j);
    }
    return 1;
}/*shortestdistance*/

void floyed()
{/*用floyed算法求两个景点的最短路径*/
    int i,j,k; 
    for(i=1;i<=n;i++) 
        for(j=1;j<=n;j++) 
        {
            shortest[i][j]=cost[i][j];
            path[i][j]=0; 
        }
    for(k=1;k<=n;k++) 
        for(i=1;i<=n;i++) 
            for(j=1;j<=n;j++)
                if(shortest[i][j]>(shortest[i][k]+shortest[k][j])) 
                {/*用path[][]记录从i到j的最短路径上点j的前驱景点的序号*/
                    shortest[i][j]=shortest[i][k]+shortest[k][j];
                    path[i][j]=k;
                    path[j][i]=k;
                } 
}/*floyed*/

void display(int i,int j)
{/* 打印两个景点的路径及最短距离 */
    int a,b;
    a=i;
    b=j;
    printf("您要查询的两景点间最短路径是:\n\n");
    if(shortest[i][j]!=INT_MAX)
    {
        if(i<j)
        { 
            printf("%d",b);
            while(path[i][j]!=0)
            {/* 把i到j的路径上所有经过的景点按逆序打印出来*/
                printf("<-%d",path[i][j]);
                if(i<j)
                    j=path[i][j]; 
                else 
                    i=path[j][i];
            } 
            printf("<-%d",a);
            printf("\n\n"); 
            printf("(%d->%d)最短距离是:%d米\n\n",a,b,shortest[a][b]);
        }
        else 
        {
            printf("%d",a);
            while(path[i][j]!=0)
            {/* 把i到j的路径上所有经过的景点按顺序打印出来*/
                printf("->%d",path[i][j]);
                if(i<j)
                    j=path[i][j]; 
                else 
                    i=path[j][i]; 
            } 
            printf("->%d",b);
            printf("\n\n"); 
            printf("(%d->%d)最短距离是:%5d米\n\n",a,b,shortest[a][b]);
        } 
    } 
    else
        printf("输入错误！不存在此路！\n\n");
    printf("\n");system("pause");system("cls");
}/*display*/