資料結構 校園導遊

題目6：校園導遊咨詢 實驗類型（驗證/設計/創新）：設計 學時：16

課程設計内容：

設計一個校園導遊程式，為來訪的客人提供各種資訊查詢服務。要求：

4.設計上海工程技術大學的校園平面圖，所含景點不少于10個。各景點資訊包括代号、名稱、簡介等資訊。

5.為來訪客人提供圖中任意景點相關資訊的查詢（利用不同的周遊方法）。

6.為來訪客人提供圖中任意景點的問路查詢，即查詢任意兩個景點之間的一條最短的簡單路徑。

課程設計要求：

熟練掌握最短路徑的求解方法；能夠運用最短路徑的求解方法實作校園導遊咨詢；了解複雜資料對象在計算機中的存儲形式。

重點難點：

【本課程設計重點】校園平面圖的存儲和最短路徑的求解方法。

【本課程設計難點】最短路徑求解算法的實作。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#define INF 0x3f3f3f3f;
#define n 10
using namespace std;
const int max_v=50;
int path[max_v][max_v];
 
typedef struct
{
    char name[20];
    char code[20];
    char intro[100];
}DataType;
 
typedef struct
{
    int num;
    DataType data;
}View;
 
typedef struct
{
    View view[max_v];
    int pl[max_v][max_v];
    int vexnum,arcnum;
}AMGraph;
 
void DisplayTu(){
    printf("***------------------學校平面圖--------------------***\n\n");
    printf("***                       實訓樓(2)              ***\n");
    printf("***   交通工程中心(10)--------|   |---------行政樓(3)  ***\n");
    printf("***        |                圖書館(1)      |       ***\n");
    printf("***        第二圖文中心(9)        |            |       ***\n");
    printf("***         |             教學樓(5)      |       ***\n");
    printf("***         |                 |            |       ***\n");
    printf("***   體育館(8)                 |            |       ***\n");
    printf("***     |                     |            |       ***\n");
    printf("***     |                     ---------東操場(4)   ***\n");
    printf("***     ---食堂(7)---三期宿舍(6)-------------|       ***\n\n");
    printf("***------------------------------------------------***\n\n");
    system("pause");
    system("cls");
}
 
void init(AMGraph &AM){
    int i=1;
    AM.view[i].num=i;
    strcpy(AM.view[i].data.code,"1");
    strcpy(AM.view[i].data.name,"圖書館");
    strcpy(AM.view[i].data.intro,"圖書館館迎門而立，俯瞰國道，是學校的标志性建築.");
    i++;
    AM.view[i].num=i;
    strcpy(AM.view[i].data.code,"2");
    strcpy(AM.view[i].data.name,"實訓樓");
    strcpy(AM.view[i].data.intro,"位于圖書館前,中央立着國旗,使其威嚴莊重.");
    i++;
    AM.view[i].num=i;
    strcpy(AM.view[i].data.code,"3");
    strcpy(AM.view[i].data.name,"行政樓");
    strcpy(AM.view[i].data.intro,"這是學校做高的一棟樓，是老師們辦公的地方.");
    i++;
    AM.view[i].num=i;
    strcpy(AM.view[i].data.code,"4");
    strcpy(AM.view[i].data.name,"東操場");
    strcpy(AM.view[i].data.intro,"這裡是鍛煉的地方，可以在這裡玩橄榄球，足球等");
    i++;
    AM.view[i].num=i;
    strcpy(AM.view[i].data.code,"5");
    strcpy(AM.view[i].data.name,"教學樓");
    strcpy(AM.view[i].data.intro,"是同學們上課學習的地方.");
    i++;
    AM.view[i].num=i;
    strcpy(AM.view[i].data.code,"6");
    strcpy(AM.view[i].data.name,"三期宿舍");
    strcpy(AM.view[i].data.intro,"這裡主要是女生們住的地方");
    i++;
    AM.view[i].num=i;
    strcpy(AM.view[i].data.code,"7");
    strcpy(AM.view[i].data.name,"食堂");
    strcpy(AM.view[i].data.intro,"這裡是學生老師吃飯的地方，有很多的美食.");
    i++;
    AM.view[i].num=i;
    strcpy(AM.view[i].data.code,"8");
    strcpy(AM.view[i].data.name,"體育館");
    strcpy(AM.view[i].data.intro,"這裡是學校上體育課的地方，同時也是各種賽事的舉辦地方.");
    i++;
    AM.view[i].num=i;
    strcpy(AM.view[i].data.code,"9");
    strcpy(AM.view[i].data.name,"第二圖文中心");
    strcpy(AM.view[i].data.intro,"這裡擁有大量的圖書，同時也是全校的卡務中心.");
    i++;
    AM.view[i].num=i;
    strcpy(AM.view[i].data.code,"10");
    strcpy(AM.view[i].data.name,"交通中心");
    strcpy(AM.view[i].data.intro,"這裡主要是電子電氣學院的學生做實驗的地方，同時也有許多老師的辦公室.");
    for(int j=1;j<=i;j++)
        for(int k=1;k<=i;k++){
            if(k==j)
                AM.pl[j][k]=0;
            else
                AM.pl[j][k]=INF;
            path[j][k]=k;
        }
        //這裡是設定路徑 
    AM.pl[1][2]=AM.pl[2][1]=50;
    AM.pl[1][3]=AM.pl[3][1]=300;
    AM.pl[2][3]=AM.pl[3][2]=200;
    AM.pl[2][10]=AM.pl[10][2]=460;
    AM.pl[1][5]=AM.pl[5][1]=200;
    AM.pl[1][10]=AM.pl[10][1]=400;
    AM.pl[3][5]=AM.pl[5][3]=800;
    AM.pl[3][4]=AM.pl[4][3]=900;
    AM.pl[4][5]=AM.pl[5][4]=400;
    AM.pl[5][10]=AM.pl[10][5]=500;
    AM.pl[5][9]=AM.pl[9][5]=400;
    AM.pl[5][6]=AM.pl[6][5]=700;
    AM.pl[8][10]=AM.pl[10][8]=150;
    AM.pl[8][9]=AM.pl[9][8]=100;
    AM.pl[6][8]=AM.pl[8][6]=260;
    AM.pl[6][7]=AM.pl[7][6]=50;
    AM.pl[6][4]=AM.pl[4][6]=1000;
    AM.pl[7][8]=AM.pl[8][7]=200;
    AM.pl[9][10]=AM.pl[10][9]=50;
}
 
void Display(AMGraph AM){
    printf("以下是全部景點的代号和名稱:\n\n");
    printf("代号\t\t名稱\n");
    for(int i=1;i<=n;i++)
        printf("%s\t\t%s\n",AM.view[i].data.code,AM.view[i].data.name);
    printf("\n");
}
 
void Edit(AMGraph &AM){
    printf("歡迎編輯景點資訊！\n");
    Display(AM);
    printf("請輸入要編輯的景點的代号:\n");
    char q[20];
    cin>>q;
    for(int i=1;i<=n;i++){
        if(strcmp(AM.view[i].data.code,q)==0){
            printf("請輸入新的景點資訊：\n");
            printf("[提示:按照 代号、名稱、介紹順序輸入!]\n\n");
            cin>>AM.view[i].data.code;
            cin>>AM.view[i].data.name;
            cin>>AM.view[i].data.intro;
            printf("修改成功！\n\n");
        }
    }
    system("pause");
    system("cls");
}
 
void Query(AMGraph AM){
    printf("歡迎查詢景點資訊！\n");
    Display(AM);
    printf("請輸入要查詢的景點的代号：\n\n");
    char q[20];
    cin>>q;
    for(int i=1;i<=n;i++){
        if(strcmp(AM.view[i].data.code,q)==0){
            printf("該景點的具體資訊如下:\n");
            printf("名稱:%s\n",AM.view[i].data.name);
            printf("簡介:%s\n\n",AM.view[i].data.intro);
        }
    }
    system("pause");
    system("cls");
}
 
void ShortestPath(AMGraph AM){
    printf("歡迎查詢景點路徑！\n");
    Display(AM);
    printf("請輸入要查詢的兩景點的編号:\n");
    int a,b;
    scanf("%d%d",&a,&b);
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
                if(AM.pl[i][k]+AM.pl[j][k]<AM.pl[i][j]){
                    AM.pl[i][j]=AM.pl[i][k]+AM.pl[j][k];
                    path[i][j]=path[i][k];
                }
            }
    int sum=0,t;
    printf("您查詢的景點 %s 到 %s 之間的最短路徑為:\n",AM.view[a].data.name,AM.view[b].data.name);
    while(a!=b){
        printf("%s->",AM.view[a].data.name);
        t=a;
        a=path[a][b];
        sum+=AM.pl[t][a];
    }
    printf("%s\n\n",AM.view[b].data.name);
    printf("兩景點之間的路徑長度為:%dm\n\n",sum);
    system("pause");
    system("cls");
}
 
void Menu(){
    printf("--------校園導遊咨詢--------\n\n");
        printf("       1.景點平面圖展示.\n");
        printf("       2.基本資訊修改.\n");
        printf("       3.景點資訊查詢.\n");
        printf("       4.景點路徑查詢.\n");
        printf("       5.退出.\n\n");
        printf("------------------------------\n\n");
}
 
int main()
{
    AMGraph AM;
    init(AM);
    while(1){
        Menu();
        printf("請選擇功能:\n\n");
        int a;
        scanf("%d",&a);
        if(a==5){
            printf("---------------------\n");
            printf("謝謝使用！旅途愉快！\n");
            printf("---------------------\n");
            break;
        }
        else if(a!=1&&a!=2&&a!=3&&a!=4){
            printf("您的輸入選擇不符合要求，請重新輸入！\n");
            continue;
        }
        switch(a){
            case 1:DisplayTu();break;
            case 2:Edit(AM);break;
            case 3:Query(AM);break;
            case 4:ShortestPath(AM);break;
        }
    }
    return 0;
}
 

 
       

運作：