数据结构课程设计——校园导游

2021年9月7日 6点热度 0条评论 来源: 学习吧TOTORO

南 通 大 学

计算机科学与技术学院

数据结构课程设计报告

姓    名:

**         

班    级:

网工**   

学    号:

******     

指导老师:

*******         

选    题:

校园导游       

日    期:

2018.01.18       

 

           

           

         

         

 

 

  • 问题分析及功能设计

校园占地几千亩,生活设施分布较散;校园内景色优美,景点甚多。在校园内移动,因时间、交通工具和用户兴趣等原因,需要选择线路。本设计的主要任务是为在南通大学新校区内生活、购物、参观,学习的人们提供行走路线查询、选择、景点介绍的帮助。

以下是校园导游系统应具备的功能:

  1. 根据用户需求智能推荐相关地点。
  2. 粗略展示校园平面图。
  3. 罗列各个景点,实现对某个景点的详细查询。

(4)给出到某个景点的最佳路线。

(5)管理员可以修改景点信息。

struct VertexNode{     //创造一个存储景点及其该景点信息的顶点

  • 数据结构设计

为了实现以上的功能,达到寻找最短路线的目的,我选择无向网的邻接矩阵存储方式。

景点信息有多个数据项,可分别设计结构体:

1.道路(弧)数据项表示:

struct ArcNode{        

      int adj;            //该弧指向的顶点位置

      char *info;          //该弧相关信息的指针

};

2.景点(顶点)数据项表示:

      int number;

      char *view;

      char *info;

};

3.整个图数据项表示:

    struct MGraph{       //创建地图

       VertexNode vex[NUM];

       ArcNode arcs[NUM][NUM];

       int vexnum,arcnum;      //顶点数,边数

};

 

三、算法设计

3.1地图(无向网)的创建

MGraph g;

int P[NUM][NUM];

long int D[NUM];

int x[13]={0};

void CreateMap(int v,int a);

 

void CreateMap(int v,int a)

{

     int i,j;

     g.vexnum=v;

     g.arcnum=a;

     for(i=1;i<g.vexnum;++i)

    g.vex[i].number=i;

     g.vex[0].view="名称";

     g.vex[0].info="景点简介";

     g.vex[1].view="西门";

     g.vex[1].info="西门外交通便利,外是南通市近几年来的新开发地段,有繁华的商业街,购物中心等";

     g.vex[2].view="西操场";

     g.vex[2].info="含一个大型体育场,一个小型足球场和排球场,及篮球场,是通大师生锻炼身体的最佳场所";

     g.vex[3].view="一食堂";

     g.vex[3].info="位于学校西部,面积不大但菜色齐全,种类繁多,口味偏重,三楼设有独立包厢";

     g.vex[4].view="北门";

     g.vex[4].info="位于学校北部,几年刚刚改造成为与外界往来的出入口,外方便乘坐公交,附近有妇幼保健院";

     g.vex[5].view="一超市";

     g.vex[5].info="位于学校中西部,与校内自助银行,邮政,眼睛店相连,主要出售学生日常生活学习用品";

     g.vex[6].view="图书馆";

     g.vex[6].info="坐落于学校中央,面朝内湖,建筑造型独特,藏书丰富,另含校史馆及张骞艺术馆";

     g.vex[7].view="校园服务中心";

     g.vex[7].info="位于二食堂西部,是于2017年新建成的,内设有移动联通服务店,自助银行取款机,奶茶店,深受大学生青睐";

     g.vex[8].view="小北街";

     g.vex[8].info="位于学校北门,以小饭店居多,是吃饭休息的绝佳选择";

     g.vex[9].view="纺化楼";

     g.vex[9].info="位于学校西南部,是南通大学纺织学院的主要教学楼,以及生命科学学院实验研究室,造型独特,是拍照及佳的好地方";

    g.vex[10].view="二超市";

     g.vex[10].info="与二食堂同属一栋建筑,面积大,商品全,且有打印复印点,出售复习资料";

     g.vex[11].view="逸夫楼";

     g.vex[11].info="由邵逸夫先生捐献的三栋教学楼,建筑简洁大方,其中7号楼为我校行政办公楼,该楼南边有张謇先生雕像";

     g.vex[12].view="二食堂";

     g.vex[12].info="二食堂是我校综合食堂,饮食类型丰富,满足了不同地域大学生需求;含清真食堂,教工食堂,三楼是大学生活动中心";

     g.vex[13].view="范曾艺术馆";

     g.vex[13].info="该馆外观造型独特,颇具风格,于2014年开馆,国内首家范曾艺术馆,收藏范曾先生画作";

     g.vex[14].view="体育馆";

     g.vex[14].info="主要供击剑、篮球及乒乓球用的运动场,举办过许多大型赛事及宣讲活动,设施齐全";

     g.vex[15].view="东操场";

     g.vex[15].info="位于学校东部,含篮球场、网球场及其他运动设施,是许多学生活动的举办地";

     g.vex[16].view="医疗服务中心";

     g.vex[16].info="位于二食堂附近,是为通大师生服务的小型医疗中心";

     for(i=1;i<g.vexnum;++i)

     {

            for(j=1;j<g.vexnum;++j)

            {

                   g.arcs[i][j].adj=Max;

                   g.arcs[i][j].info=NULL;

            }

     }

     g.arcs[1][2].adj=g.arcs[2][1].adj=200;

    g.arcs[1][3].adj=g.arcs[3][1].adj=400;

    g.arcs[1][9].adj=g.arcs[9][1].adj=600;

    g.arcs[2][4].adj=g.arcs[4][2].adj=300;

    g.arcs[3][5].adj=g.arcs[5][3].adj=500;

    g.arcs[3][6].adj=g.arcs[6][3].adj=200;

    g.arcs[4][8].adj=g.arcs[8][4].adj=30;

     g.arcs[4][5].adj=g.arcs[5][4].adj=100;

    g.arcs[5][6].adj=g.arcs[6][5].adj=50;

     g.arcs[5][7].adj=g.arcs[7][5].adj=200;

    g.arcs[6][7].adj=g.arcs[7][6].adj=100;

    g.arcs[7][10].adj=g.arcs[10][7].adj=30;

    g.arcs[9][3].adj=g.arcs[3][9].adj=500;

    g.arcs[10][12].adj=g.arcs[12][10].adj=10;

    g.arcs[10][11].adj=g.arcs[11][10].adj=300;

     g.arcs[12][16].adj=g.arcs[16][12].adj=20;

    g.arcs[12][13].adj=g.arcs[13][12].adj=700;

    g.arcs[12][14].adj=g.arcs[14][12].adj=600;

     g.arcs[13][15].adj=g.arcs[15][13].adj=400;

     g.arcs[14][15].adj=g.arcs[15][14].adj=100;

 

}

3.2 最短路径

void Dijkstra(int num)

{                         //最短路径

     int v,w,i,t;

     int final[NUM];

     int min;

     for(v=1;v<NUM;v++)

     {

            final[v]=0;     //辅助数组

            D[v]=g.arcs[num][v].adj;  //存放v0到v的最短距离

            for(w=1;w<NUM;w++)

                   P[v][w]=0;

            if(D[v]<32767)

            {

                   P[v][num]=1;

                   P[v][v]=1;

            }

     }

     D[num]=0;

     final[num]=1;

     for(i=1;i<NUM;++i)

     {

            min=Max;

            for(w=1;w<NUM;++w)

                   if(!final[w])

                          if(D[w]<min)

                          {

                                 v=w;

                                 min=D[w];

                          }

                          final[v]=1;

                          for(w=1;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 view1,int view2)

{                               //全部最短路径

     int a,b,c,d,q=0;

     a=view2;

     if(a!=view1)

     {

            cout<<"从"<<g.vex[view1].view<<"到"<<g.vex[view2].view<<'\n'

                <<"最短距离为" <<D[a]<<'\t' <<g.vex[view1].view;

            d=view1;

            for(c=0;c<NUM;++c)

            {

            gate:;

                   P[a][view1]=0;

                   for(b=0;b<NUM;b++)

                   {

                          if(g.arcs[d][b].adj<32767&&P[a][b])

                          {

                                 cout<<"-->"<<g.vex[b].view;

                                 q=q+1;

                                 P[a][b]=0;

                                 d=b;

                    if(q%8==0) cout<<'\n';

                                 goto gate;

                          }

                   }

            }

            cout<<'\n';

     }

}

3.3 管理界面

 

cout<<"要修改的景点的景点序号"<<endl;

cin>>v2;

cout<<"要修改的信息是:1.景点名称   2.景点简介"<<'\n';

cin>>ck3;

switch(ck3)

{

            case '1':

                   cout<<"输入新的景点名称:"<<'\n';

                   cin>>char1;

                   g.vex[v2].view=char1;

         break;

 

            case '2':

                      cout<<"输入新的景点简介:"<<'\n';

                          cin>>char2;

             g.vex[v2].info=char2;

     break;

     };

 

3.4 在主函数中使用开关语句实现各个功能的调用

int mian()

{

     int v0,v1;

  char ck1,ck2;

     CreateMap(NUM,17);

     Do

{

            case '1':  //玩转通大          

            case '2':  //2:通大地图

            case '3':  //3:景点及其介绍 

            case '4':  // 4:最佳游览路线

            case '5':  //5:最短路径查询 } }

  • 调试与运行
  • (1)管理界面

(2)玩转通大

 

(3)通大地图

 

(4)最短距离:

 

(5)景点信息查询:

 

(6)最佳路径:

 

  • 总结

    校园导游这一课程设计,我首先是思考了整个我需要实现的界面功能,这些功能确定之后要分别找出对应解决问题的算法,首先要创建一个地图,我采用的无向网图的邻接矩阵的存储方式,用到的算法有迪杰斯特拉求最短路径的算法,在算法实践中遇到了许许多多大大小小的问题,在创建邻接矩阵的时候,我不知道用什么方式去存储顶点及其顶点信息,后来用数组来存储顶点,开始用一维数组,后面改进用二维数组;求最短路径时采用迪杰斯特拉的算法,一开始也是丈二的和尚摸不着头脑,无从下手,又查看数据结构课本,C++课本以及其他资料,确定所需要的顶点,代全路径的长度;除此之外就是实现功能分工的时候,对语法知识掌握的不牢,大一的时候学习C++存在很多语法方面知识的欠缺,看书有的时候靠自己还真的理解不了,总之这个过程很漫长同时也充满乐趣!

   下面说一点我自己的感想:课设这一周以来,我几乎每天除了吃饭睡觉就是对着我的电脑或者机房的电脑,眼睛的确很受不了,经常熬夜到半夜,但是尽管这样,还是没能解决课程设计中所遇到的问题,平时老师没有给我们安排上机课,自控能力差的我,就很少自己动手去解决问题,去上机实践,知识上课时学到了理论方面的东西,根本没有真真正正的去实践,所以要在一周的时间内完全靠自己写出一份完整的课程设计的代码,真难得有难度;有句话真的说的很对,世界上没有真正的捷径可走,要学到真东西,真的要付出时间和精力,靠从其他途径获得的结果不会长久的,比如百度,比如抄袭别人的,真的这些外门途径,旁门左道真的不可取,我想我这学期课设的收获更多的应该是学会真正的动手实践,也从优秀的同学身上看到了人家的努力认真和付出!加油吧!

  

  • 参考文献及其他参考途径
  1. 徐慧等,数据结构实践教程,清华大学出版社
  2. 陈建平等,C++程序设计教程,高等教育出版社
  3. 徐慧等,数据结构,清华大学出版社
  4. 百度文库和CSDN博客

七.附源程序

 

#include<iostream>

#include<stdio.h>

using namespace std;

#define Max 5000  //带权路径最大长度

#define NUM 17   //最大顶点数

char Menu()

{

         char c;

         int flag;

         do{

                   flag=1;

                   cout<<endl;

        cout<<"              南通大学欢迎您!"<<endl;

        cout<<"       ----------------------------"<<endl;

        cout<<"       |   1: 玩转通大            |\n"

            <<"       |   2:通大地图            |\n"

            <<"       |   3:景点及其介绍      |\n"

            <<"       |   4:最佳游览路线      |\n"

            <<"       |   5:最短路径查询        |\n"<<endl;

        cout<<"       ----------------------------"<<endl;

        cout<<"请选择功能:";

                   cin>>c;

                   if(c=='1'||c=='2'||c=='3'||c=='4'||c=='5')

                            flag=0;

         }while(flag);

         return c;

}

 

 

 

struct ArcNode{        

         int adj;            //该弧指向的顶点位置

         char *info;          //该弧相关信息的指针

};

 

struct VertexNode{     //创造一个存储景点及其该景点信息的顶点

         int number;

         char *view;

         char *info;

};

 

struct MGraph{       //创建地图

         VertexNode vex[NUM];

         ArcNode arcs[NUM][NUM];

         int vexnum,arcnum;      //顶点数,边数

};

 

 

MGraph g;

int P[NUM][NUM];

long int D[NUM];

int x[13]={0};

void CreateMap(int v,int a);

 

void CreateMap(int v,int a)

{

         int i,j;

         g.vexnum=v;

         g.arcnum=a;

         for(i=1;i<g.vexnum;++i)

    g.vex[i].number=i;

         g.vex[0].view="名称";

         g.vex[0].info="景点简介";

         g.vex[1].view="西门";

         g.vex[1].info="西门外交通便利,外是南通市近几年来的新开发地段,有繁华的商业街,购物中心等";

         g.vex[2].view="西操场";

         g.vex[2].info="含一个大型体育场,一个小型足球场和排球场,及篮球场,是通大师生锻炼身体的最佳场所";

         g.vex[3].view="一食堂";

         g.vex[3].info="位于学校西部,面积不大但菜色齐全,种类繁多,口味偏重,三楼设有独立包厢";

         g.vex[4].view="北门";

         g.vex[4].info="位于学校北部,几年刚刚改造成为与外界往来的出入口,外方便乘坐公交,附近有妇幼保健院";

         g.vex[5].view="一超市";

         g.vex[5].info="位于学校中西部,与校内自助银行,邮政,眼睛店相连,主要出售学生日常生活学习用品";

         g.vex[6].view="图书馆";

         g.vex[6].info="坐落于学校中央,面朝内湖,建筑造型独特,藏书丰富,另含校史馆及张骞艺术馆";

         g.vex[7].view="校园服务中心";

         g.vex[7].info="位于二食堂西部,是于2017年新建成的,内设有移动联通服务店,自助银行取款机,奶茶店,深受大学生青睐";

         g.vex[8].view="小北街";

         g.vex[8].info="位于学校北门,以小饭店居多,是吃饭休息的绝佳选择";

         g.vex[9].view="纺化楼";

         g.vex[9].info="位于学校西南部,是南通大学纺织学院的主要教学楼,以及生命科学学院实验研究室,造型独特,是拍照及佳的好地方";

    g.vex[10].view="二超市";

         g.vex[10].info="与二食堂同属一栋建筑,面积大,商品全,且有打印复印点,出售复习资料";

         g.vex[11].view="逸夫楼";

         g.vex[11].info="由邵逸夫先生捐献的三栋教学楼,建筑简洁大方,其中7号楼为我校行政办公楼,该楼南边有张謇先生雕像";

         g.vex[12].view="二食堂";

         g.vex[12].info="二食堂是我校综合食堂,饮食类型丰富,满足了不同地域大学生需求;含清真食堂,教工食堂,三楼是大学生活动中心";

         g.vex[13].view="范曾艺术馆";

         g.vex[13].info="该馆外观造型独特,颇具风格,于2014年开馆,国内首家范曾艺术馆,收藏范曾先生画作";

         g.vex[14].view="体育馆";

         g.vex[14].info="主要供击剑、篮球及乒乓球用的运动场,举办过许多大型赛事及宣讲活动,设施齐全";

         g.vex[15].view="东操场";

         g.vex[15].info="位于学校东部,含篮球场、网球场及其他运动设施,是许多学生活动的举办地";

         g.vex[16].view="医疗服务中心";

         g.vex[16].info="位于二食堂附近,是为通大师生服务的小型医疗中心";

         for(i=1;i<g.vexnum;++i)

         {

                   for(j=1;j<g.vexnum;++j)

                   {

                            g.arcs[i][j].adj=Max;

                            g.arcs[i][j].info=NULL;

                   }

         }

    g.arcs[1][2].adj=g.arcs[2][1].adj=200;

    g.arcs[1][3].adj=g.arcs[3][1].adj=400;

    g.arcs[1][9].adj=g.arcs[9][1].adj=600;

    g.arcs[2][4].adj=g.arcs[4][2].adj=300;

    g.arcs[3][5].adj=g.arcs[5][3].adj=500;

    g.arcs[3][6].adj=g.arcs[6][3].adj=200;

    g.arcs[4][8].adj=g.arcs[8][4].adj=30;

         g.arcs[4][5].adj=g.arcs[5][4].adj=100;

    g.arcs[5][6].adj=g.arcs[6][5].adj=50;

         g.arcs[5][7].adj=g.arcs[7][5].adj=200;

    g.arcs[6][7].adj=g.arcs[7][6].adj=100;

    g.arcs[7][10].adj=g.arcs[10][7].adj=30;

    g.arcs[9][3].adj=g.arcs[3][9].adj=500;

    g.arcs[10][12].adj=g.arcs[12][10].adj=10;

    g.arcs[10][11].adj=g.arcs[11][10].adj=300;

         g.arcs[12][16].adj=g.arcs[16][12].adj=20;

    g.arcs[12][13].adj=g.arcs[13][12].adj=700;

    g.arcs[12][14].adj=g.arcs[14][12].adj=600;

         g.arcs[13][15].adj=g.arcs[15][13].adj=400;

         g.arcs[14][15].adj=g.arcs[15][14].adj=100;

 

}

 

 

void Dijkstra(int num)

{                         //最短路径

         int v,w,i,t;

         int final[NUM];

         int min;

         for(v=1;v<NUM;v++)

         {

                   final[v]=0;     //辅助数组

                   D[v]=g.arcs[num][v].adj;  //存放v0到v的最短距离

                   for(w=1;w<NUM;w++)

                            P[v][w]=0;

                   if(D[v]<32767)

                   {

                            P[v][num]=1;

                            P[v][v]=1;

                   }

         }

         D[num]=0;

         final[num]=1;

         for(i=1;i<NUM;++i)

         {

                   min=Max;

                   for(w=1;w<NUM;++w)

                            if(!final[w])

                                     if(D[w]<min)

                                     {

                                               v=w;

                                               min=D[w];

                                     }

                                     final[v]=1;

                                     for(w=1;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 view1,int view2)

{                               //全部最短路径

         int a,b,c,d,q=0;

         a=view2;

         if(a!=view1)

         {

                   cout<<"从"<<g.vex[view1].view<<"到"<<g.vex[view2].view<<'\n'

                       <<"最短距离为" <<D[a]<<'\t' <<g.vex[view1].view;

                   d=view1;

                   for(c=0;c<NUM;++c)

                   {

            gate:;

                            P[a][view1]=0;

                            for(b=0;b<NUM;b++)

                            {

                                     if(g.arcs[d][b].adj<32767&&P[a][b])

                                     {

                                               cout<<"-->"<<g.vex[b].view;

                                               q=q+1;

                                               P[a][b]=0;

                                               d=b;

                    if(q%8==0) cout<<'\n';

                                               goto gate;

                                     }

                            }

                   }

                   cout<<'\n';

         }

}

 

void place()

{

    cout<<"   景点枚举:\n"

        <<"   1:西门      2:西操场     3:一食堂      4:北门    5:一超市\n"

        <<"   6:图书馆    7:校园服务中心      8:小北街    9:纺化楼   10:二超市\n"

        <<"   11:逸夫楼  12:二食堂  13:范曾艺术馆 14:体育馆 15:东操场  16:医疗服务中心"<<endl;

}

 

 

int main()

{

         int v0,v1;

    char ck1,ck2;

         CreateMap(NUM,17);

         do

         {

                   ck1=Menu();

                   switch(ck1)

                   {

            case '1':

                                cout<<"请选择游览方向:"

                                               <<"    1.购物  2.参观  3.饮食  4.运动  5.学习 "<<endl;

                                     cin>>ck2;

                                     switch(ck2)

                                     {

                                         case '1':

                                                        cout<<"小北街  一超市  二超市"<<'\n';

                        break;

 

                                               case '2':

                                                        cout<<"范曾艺术馆  逸夫楼  图书馆    纺化楼"<<'\n';

                                                        break;

                    case '3':

                        cout<<"一食堂  二食堂  小北街"<<'\n';

                                                        break;

                                               case '4':

                                                        cout<<"体育馆  东操场  西操场"<<'\n';

                                                   break;

                                               case '5':

                                             cout<<"图书馆 "<<'\n';

                                                        break;

                                     };

                cout<<"请按回车键返回主菜单"<<'\n';

                                     getchar();

                getchar();

                break;

 

                            case'2':

                cout<<""<<endl;

                cout<<"                                南通大学地图"<<endl;

                cout<<"   ---------------------------------------------------------------------------------------"<<endl;

                cout<<"   |           *  *  *  *  * 北门 * * * *小北街                                         |"<<endl;

                     cout<<"   |          *                  *                                                       |"<<endl;

                     cout<<"   |        *                    *                                                       |"<<endl;

                     cout<<"   |      *                      *                                                       |"<<endl;

                     cout<<"   |   西操场* * * * * * * 一超* * * * * * 校园服务中心*二超*二食堂* * * * * *  *体育馆  |"<<endl;

                     cout<<"   |      *                 * *           *           *             *       *       |"<<endl;

                     cout<<"   |      *                *   *          *            *                *        *      |"<<endl;

                     cout<<"   |      *               *    * 图书馆 *             *                 *         *     |"<<endl;

                     cout<<"   |    西门* * 一食堂*  * * * *                      *                  *          *    |"<<endl;

                     cout<<"   |       *                                         *                   *         东操场|"<<endl;

                     cout<<"   |         *                                       *                   *         *     |"<<endl;

                     cout<<"   |           *                                     *                   *        *      |"<<endl;

                     cout<<"   |         纺化楼                                逸夫楼               范增艺术馆       |"<<endl;

                cout<<"   ---------------------------------------------------------------------------------------"<<endl;

                     cout<<""<<endl;

                cout<<"请按回车键返回主菜单"<<'\n';

                           getchar();

                getchar();

                break;

 

                       case '3':

                place();

                int i,j;

                     cout<<""<<'\n';

                     cout<<"请输入景点序号(1~16):";

                     cin>>j;

                     cout<<""<<'\n';

                     for(i=1;i<NUM;i++)

                                     {

                             if(i==j)

                  cout<<i<<'\t'<<g.vex[i].view<<'\t'<<g.vex[i].info<<'\n';

                                     }

                     cout<<""<<'\n';

                cout<<"请按回车键返回主菜单"<<'\n';

                                     getchar();

                                      break;

 

                           

 

                            case '4':

                                     place();

                cout<<"请选择出发地序号(1~16):";

                                     cin>>v0;

                                     cout<<"请选择目的地序号(1~16):";

                                     cin>>v1;

                                     while(v1>16||v1<1){

                                               cout<<"输入的目的地序号错误v1 error"<<'\n';

                                               cout<<"请重新选择目的地序号(1~16):";

                                         cin>>v1;

                                     }

                                     Dijkstra(v0);

                                     output(v0,v1);

                                     cout<<"请按回车键返回主菜单"<<'\n';

                                     getchar();

                                     break;

 

            case '5':

                place();

                cout<<"请选择出发地序号(1~16):";

                                     cin>>v0;

                                     while(v0>16||v0<1){

                                               cout<<"输入的出发地序号错误v0 error"<<'\n';

                                               cout<<"请重新选择出发地序号(1~16):";

                                         cin>>v0;

                                     }

                                     Dijkstra(v0);

                for(i=1;i<17;i++)

                                        output(v0,i);

                                     cout<<"请按回车键返回主菜单"<<'\n';

                                     getchar();

                                     getchar();

                                     break;

                                     };

 

                  

         }while(ck1!='5');

    return 0;

}

 

    原文作者:学习吧TOTORO
    原文地址: https://blog.csdn.net/palm552233/article/details/86364547
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。