数据结构课设_校园导游咨询<含实验报告>.cpp

#include <string> #include <stdio.h> #include <malloc.h> #include <iostream> using namespace std; #define Max 20000 #define NUM 9 typedef struct ArcCell { int adj; }ArcCell; typedef struct VertexType { int number; string sight; string description; }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[9]={0}; void CreateUDN(int v,int a); void narrate(); 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,11); do { ck=Menu(); switch(ck) { case '1': system("cls"); // narrate(); printf("\n\n\t\t\t请选择起点景点（0～8）："); scanf("%d",&v0); printf("\t\t\t请选择终点景点（0～8）："); 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"); //narrate(); x[0]=1; HaMiTonian(1); printf("\n\n\t\t\t\t请按任意键继续...\n"); getchar(); getchar(); break; }; }while(ck!='e'); } char Menu() { char c; int flag; do{ flag=1; system("cls"); narrate(); printf("\n\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┃ e、退出 ┃\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=='e') flag=0; }while(flag); return c; } char SearchMenu() { char c; int flag; do{ flag=1; system("cls"); narrate(); printf("\n\t\t┏━━━━━━━━━━━━━━━┑\n"); printf("\t\t\t┃ ┃\n"); printf("\t\t\t┃ 1、按照景点编号查询 ┃\n"); printf("\t\t\t┃ 2、按照景点名称查询 ┃\n"); printf("\t\t\t┃ e、返回 ┃\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=='e') flag=0; }while(flag); return c; } void search() { int num; int i; char c; char name[20]; do { system("cls"); c=SearchMenu(); switch (c) { case '1': system("cls"); narrate(); 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].description); 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': narrate(); system("cls"); printf("\n\n\t\t请输入您要查找的景点名称："); scanf("%s",name); for(i=0;i<NUM;i++) { if(name!=G.vex[i].sight)//!strcmp(name,G.vex[i].sight) { printf("\n\n\t\t\t您要查找景点信息如下:"); printf("\n\n\t\t\t%-25s\n\n",G.vex[i].description); 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!='e'); } 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].sight="行政楼"; G.vex[0].description="学校领导，办公室之地。"; G.vex[1].sight="大礼堂"; G.vex[1].description="业余活动，举办各种晚会。"; G.vex[2].sight="11教"; G.vex[2].description="教室，自习室"; G.vex[3].sight="10教"; G.vex[3].description="教室，自习室"; G.vex[4].sight="图书馆"; G.vex[4].description="阅览，借阅图书"; G.vex[5].sight="第八食堂"; G.vex[5].description="餐饮休闲"; G.vex[6].sight="小河"; G.vex[6].description="休闲，放松心情"; G.vex[7].sight="第九食堂"; G.vex[7].description="餐饮休闲"; G.vex[8].sight="学23"; G.vex[8].description="休息"; 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=12; G.arcs[0][2].adj=G.arcs[2][0].adj=6; G.arcs[0][3].adj=G.arcs[3][0].adj=5; G.arcs[1][4].adj=G.arcs[4][1].adj=11; G.arcs[2][4].adj=G.arcs[4][2].adj=2; G.arcs[3][5].adj=G.arcs[5][3].adj=4; G.arcs[5][7].adj=G.arcs[7][5].adj=9; G.arcs[4][6].adj=G.arcs[6][4].adj=2; G.arcs[4][7].adj=G.arcs[7][4].adj=14; G.arcs[6][8].adj=G.arcs[8][6].adj=7; G.arcs[7][8].adj=G.arcs[8][7].adj=3; } void narrate() { int i,k=0; printf("\n\t\t*****************欢迎使用校园导游程序***************\n"); 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 (%2d)%-10s\t\t\t|\t%-25s\n",i,G.vex[i].sight,G.vex[i].description); k=k+1; } printf("\t________________________________|_________________________________\n"); } void ShortestPath(int num) { int v,w,i,t; int final[NUM]; int min; for(v=0;v<NUM;v++) { final[v]=0; D[v]=G.arcs[num][v].adj; for(w=0;w<NUM;w++) P[v][w]=0; if(D[v]<20000) { P[v][num]=1; P[v][v]=1; } } D[num]=0; final[num]=1; for(i=0;i<NUM;++i) { min=Max; for(w=0;w<NUM;++w) if(!final[w]) if(D[w]<min) { v=w; min=D[w]; } final[v]=1; for(w=0;w<NUM;++w) if(!final[w]&&((min+G.arcs[v][w].adj)<D[w])) { 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; if(a!=sight1) { printf("\n\t从%s到%s的最短路径是",G.vex[sight1].sight,G.vex[sight2].sight); printf("\t(最短距离为 %dm.)\n\n\t",D[a]); printf("\t%s",G.vex[sight1].sight); d=sight1; for(c=0;c<NUM;++c) { gate:; P[a][sight1]=0; for(b=0;b<NUM;b++) { if(G.arcs[d][b].adj<20000&&P[a][b]) { printf("-->%s",G.vex[b].sight); q=q+1; P[a][b]=0; d=b; if(q%8==0) printf("\n"); goto gate; } } } } } void HaMiTonian(int m) { if(m>8) return; L: NextValue(m); if(x[m]==0) return; if(m==7&&G.arcs[0][x[8]-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<8;i++) printf("%s->",G.vex[x[i]-1].sight); printf("出口"); printf("\n"); }