1. Toy模板网首页
  2. > Toy博客

数据结构课设 校园导航系统

10月前 作者：眸海不晚 分类：Toy博客 阅读(39) 违法举报

这篇具有很好参考价值的文章主要介绍了数据结构课设 校园导航系统。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1、设计目的
（1）为了进一步巩固课堂上所学到的知识，深刻把握为了进一步巩固课堂上所学到的知识，深刻掌握所学重要的数据结构类型的基本概念，逻辑结构和物理结构，以及主要应用算法。锻炼选择应用合适的数据结构解决不同实际问题的能力，使用所学的一种数据结构完成一个具体项目的分析设计和开发。
（2）设计一个校园导游程序，为来访客人提供各种信息查询任务。
（3）为来访客人提供图中任意地点相关信息的查询
（4）为来访客人提供图中任意地点的问路查询，即查询任意两个地点之间的一条最短的简单路径。
2、设计内容及要求
内容：一个校园导游程序，为来访客人提供各种信息查询任务。设计我校的校园平面图，以图中顶点表示校内各景点，存放景点名称、代号，以边表示路权，存放路径长度等相关信息。
要求：
（1）从文件中读取学校的相关简介
（2）从地图文件中读取校园主要建筑信息及建筑间的距离信息。
（3）计算出给定地点的起点到终点之间距离的行进路径
（4）输出该路径及其总距离
（5）若输入错误，则给出提示信息
一、先分析课设所给要求，仔细一想，这用到的算法：Dijkstra算法和Floyd算法。
Dijkstra算法：这是一个按路径长度递增的次序产生的最短路径的算法。基本思想：设G=（V,E）是一个带权有向图，把图中的顶点集合V分成两组，第1组为以求出最短路径的顶点集合，第2组为其余未确定最短路径的顶点集合，按最短路径长度的递增次序依次把第2组的顶点加入S中。
Floyd算法：这是求所有顶点至所有顶点的最短路径的算法。基本思想：假设有向图G=（V，E）采用邻接矩阵g表示，另外设置一个二维数组A用于存放当前顶点之间的最短路径长度，即分量A[i][j]表示当前i到j的最短路径长度,即传递产生一个矩阵序列表示路径上所有经过的顶点编号的最短路径长度。
对于所求问题，将求出当前所在地到其他所有某一个地点的最短路径，用到了最适合它的Dijkstra算法，对于之后的求出任意两点之间的最短距离时用到Floyd算法将它进行算法实现，并为它列出了对应地点的邻接矩阵，并且在实现过程中为了将最短路径权值更好地展现出来，将Dijkstra算法和Floyd算法进行了对应的优化。
二、我们在做这个课设的时候分析如下
所用学校的数据

数据结构课设 校园导航系统

我们将所有的边赋予权值，将每一个点当做邻接矩阵的一个点进行赋值，在处理时要考虑到需要求出当前所在者到校园任意一个地点的最短路径，这时便会想到排序中找最短路径的Dijkstra算法和Floyd算法，而这两者如果是单源点正权图，就用Dijkstra算法，如果是任意两点之间的最短路径或者是赋权图则用Floyd算法，而求当前所在者到校园任意一个地点的最短路径，就是单源点正权图，所以用Dijkstra算法，而后面加入的任意两个地点的最短路径问题则用Floyd算法。用到Floyd算法时需要将每个地点进行一次赋值到邻接矩阵中去。
程序整体逻辑图
数据结构课设 校园导航系统
但是在最后很遗憾我们并未使用文件的方法来将地图存入，而是直接画在了程序之中

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#define MaxVerNum 100 //最大景点数
#define INF 99999//表示无穷 即没有路径
typedef struct
{
    char name[MaxVerNum];//地点名字
    char features[1000];//地点信息
} VertexType;
//图的存储结构
typedef struct
{
    VertexType vexs[MaxVerNum];//每一个地点的信息
    int edges[MaxVerNum][MaxVerNum];//每一个地点的邻接边的权值
    int v, e;//顶点数和边数
} MGraph;
static MGraph map;
void menu1();//导航菜单
void ListSpots();//烟理工地点
void create();//创建邻接链表
void Introduce();//地点介绍函数
void Dijkstra();//查找当前地点到其他地点的最短路径
void Floyd();//查找任意两个地点之间的最短路径
void Exit();//退出系统的函数
void changepassword();
void printmap();
//主函数
int main()
{
    while(1)
    {
        create();
        printf("\n\n");
        system("cls");
        printf("\n\n\n\n\n");
        printf("\t\t\t\t    ******************************************************\n");
        printf("\t\t\t\t    *----------------------主界面------------------------*\n");
        printf("\t\t\t\t    *----------------------------------------------------*\n");
        printf("\t\t\t\t    *----------------1、进入导航系统---------------------*\n");
        printf("\t\t\t\t    *----------------------------------------------------*\n");
        printf("\t\t\t\t    *----------------2、退出程序-------------------------*\n");
        printf("\t\t\t\t    *----------------------------------------------------*\n");
        printf("\t\t\t\t    *----------------3、制作人---------------------------*\n");
        printf("\t\t\t\t    *----------------------------------------------------*\n");
        printf("\t\t\t\t    *----------------4、xxxx校园地图-------------*\n");
        printf("\t\t\t\t    *----------------------------------------------------*\n");
        printf("\t\t\t\t    ******************************************************\n");
        int n;
        printf("\n\n");
        printf("请输入代号选择您的操作：\n\n");
        scanf("%d",&n);
        if(n==1)
        {
            menu1();
        }
        else if(n==2)
        {
            Exit();
        }
        else if(n==3)
        {
            system("cls");		//清屏
            printf("制作人:\n");
            printf("按回车键返回主界面\n");
            system("pause");
            getchar();
            getchar();
            main();
            break;
        }
        else if(n==4)
        {
            printmap();
        }
    }
    return 0;
}
//导航菜单
void menu1()
{
    while(1)
    {
        system("cls");
        printf("\t当前为操作者操作界面\n\n");
        printf("\t<1>查看地点介绍\n\n");
        printf("\t<2>查找当前地点到其他地点的最短路径\n\n");
        printf("\t<3>查找任一两个地点之间的最短路径\n\n");
        printf("\t<4>返回主界面\n\n");
        printf("\t<5>退出系统！\n\n");
        int n;
        scanf("%d",&n);
        if(n==1)
        {
            Introduce();
        }
        else if(n==2)
        {
            Dijkstra();
        }
        else if(n==3)
        {
            Floyd();
        }
        else if(n==4)
        {
            main();
        }
        else if(n==5)
        {
            Exit();
        }
        else
        {
            printf("您的输入有误，请重新输入！\n");
            system("pause");
        }
    }
}
//地点介绍函数
void Introduce()
{
    system("cls");
    if(map.v==0)
    {
        printf("该地图暂时没有景点！\n\n");
        system("pause");
        return ;
    }
    ListSpots();
    printf("\n请输入你要查看的景点代号：\n");
    int n;
    while(1)
    {
        scanf("%d",&n);
        if(n<1||n>map.v)
        {
            printf("您的输入有误，请重新输入！\n");
        }
        else
            break;
    }
    printf("%s：",map.vexs[n-1].name);
    printf("%s\n",map.vexs[n-1].features);
    int flag;
    printf("\n再次查询请按1，退出查询请按任意键\n");
    scanf("%d",&flag);
    if(flag==1)
        Introduce();
}
//查找当前景点到其他景点的最短路径
void Dijkstra()
{
    system("cls");
    if(map.v<=0)
    {
        printf("地图中没有地点，无法查询最短路径！\n");
        system("pause");
        return ;
    }
    if(map.v==1)
    {
        printf("地图中只有一个地点，无法查询最短路径！\n");
        system("pause");
        return ;
    }
    if(map.e<=0)
    {
        printf("地图中没有道路，无法查询最短路径！\n");
        system("pause");
        return ;
    }
    ListSpots();
    int a;
    printf("请输入您所在地点位置的代号：\n");
    scanf("%d",&a);
    while(a<1||a>map.v)
    {
        printf("您的输入有误，请重新输入！范围在1~%d之间。\n",map.v);
        scanf("%d",&a);
    }
    int s[MaxVerNum];//存放源点和已生成的终点
    int dist[MaxVerNum];//存放最短路径的长度
    int path[MaxVerNum];//存放上一个路径的位置
    int i,j,k,min,pre;
    s[a-1]=1;
    //初始化
    for(i=0; i<map.v; i++)
    {
        dist[i]=map.edges[a-1][i];
        path[i]=a-1;
        s[i]=0;//这个看网上的答案是没有的 我自己加上去的，这样就正确了
    }
    //对当前位置进行信息更改
    dist[a-1]=0;
    s[a-1]=1;
    path[a-1]=-1;
    for(i=0; i<map.v; i++)
    {
        min=INF+1;
        for(k=1; k<map.v; k++)
        {
            if(s[k]==0&&dist[k]<min)
            {
                j=k;
                min=dist[k];
            }
        }
        s[j]=1;
        for(k=0; k<map.v; k++)
        {
            if(s[k]==0&&(dist[j]+map.edges[j][k]<dist[k]))
            {
                dist[k]=dist[j]+map.edges[j][k];
                path[k]=j;
            }
        }
    }
    int flag=1;
    int mid;
    for(i=0; i<map.v; i++)
    {
        if(i!=a-1)
        {
            if(dist[i]!=INF)
            {
                flag=0;
                printf("%d米: %s",dist[i],map.vexs[i].name);
                pre=path[i];
                mid=i;
                while(pre>=0)
                {
                    if(map.edges[mid][pre]!=INF)
                    {
                        printf(" <-%s(%d)",map.vexs[pre].name,map.edges[mid][pre]);
                        mid=pre;
                        pre=path[pre];
                    }
                    else
                    {
                        printf(" (%d)<-%s",map.edges[i][pre],map.vexs[pre].name);
                        mid=pre;
                        pre=path[pre];
                    }
                }
                printf("\n");
            }
        }
    }
    if(flag)
        printf("【%s】与任何地点之间都没有可通道路！\n",map.vexs[a-1].name);
    system("pause");
}
//查找任一两个地点之间的最短路径
void Floyd()
{
    system("cls");
    if(map.v<=0)
    {
        printf("地图中没有地点，无法查询最短路径！\n");
        system("pause");
        return ;
    }
    if(map.v==1)
    {
        printf("地图中只有一个地点，无法查询最短路径！\n");
        system("pause");
        return ;
    }
    if(map.e<=0)
    {
        printf("地图中没有道路，无法查询最短路径！\n");
        system("pause");
        return ;
    }
    ListSpots();
    int a,b;
    printf("请输入您要查询距离的两个地点代号,中间用空格隔开：\n");
    scanf("%d %d",&a,&b);
    while(a<1||a>map.v||b<1||b>map.v)
    {
        printf("您的输入有误，请重新输入！范围在1~%d之间。\n",map.v);
        scanf("%d %d",&a,&b);
    }
    int s[MaxVerNum];//存放源点和已生成的终点
    int dist[MaxVerNum];//存放最短路径的长度
    int path[MaxVerNum];//存放上一个路径的位置
    int i,j,k,min,pre;
    s[a-1]=1;
    //初始化
    for(i=0; i<map.v; i++)
    {
        dist[i]=map.edges[a-1][i];
        path[i]=a-1;
        s[i]=0;
    }
    //对当前位置进行信息更改
    dist[a-1]=0;
    s[a-1]=1;
    path[a-1]=-1;
    int K=0,mid=a-1;
    for(i=0; i<map.v; i++)
    {
        min=INF+1;
        for(k=1; k<map.v; k++)
        {
            if(s[k]==0&&dist[k]<min)
            {
                j=k;
                min=dist[k];
            }
        }
        s[j]=1;
        for(k=0; k<map.v; k++)
        {
            if(s[k]==0&&(dist[j]+map.edges[j][k]<dist[k]))
            {
                dist[k]=dist[j]+map.edges[j][k];
                path[k]=j;
            }
        }
    }
    if(dist[b-1]==INF)
        printf("【%s】与【%s】任何地点之间都没有可通道路！\n",map.vexs[a-1].name,map.vexs[b-1].name);
    else
    {
        printf("【%s】->【%s】的最短距离是%d米。 \n",map.vexs[b-1].name,map.vexs[a-1].name,dist[b-1]);
        pre=path[b-1];
        printf("路径为：%s",map.vexs[b-1].name);
        int pre1=pre;
        while(pre>=0)
        {
            if(pre!=pre1)
            {
                printf(" <-%s(%d)",map.vexs[pre].name,map.edges[mid][pre]);
                mid=pre;
                pre=path[pre];
            }
            else
            {
                printf(" (%d)<-%s",map.edges[b-1][pre],map.vexs[pre].name);
                mid=pre;
                pre=path[pre];
            }
        }
    }
    printf("\n");
    system("pause");

}
//烟理工地点列表
void ListSpots()
{
    if(map.v==0)
    {
        printf("当前地图中没有地点！\n\n");
        system("pause");
        return ;
    }
    if(map.v>0)
        printf("xxxx有当前地点：\n\n");
    int i;
    for(i=0; i<map.v; i++)
    {
        printf("\t<%d>%s\n",i+1,map.vexs[i].name);
    }
}
//创建邻接链表
void create()
{
    map.v=13;
    map.e=22;
    int i,j,k;
    for(i=0; i<MaxVerNum; i++)
    {
        for(j=0; j<MaxVerNum; j++)
        {
            map.edges[i][j]=INF;
        }
    }
    //顶点的名字 介绍赋值
    strcpy(map.vexs[0].name, "北门口");
    strcpy(map.vexs[0].features, "地点的描述，下列相同");
    strcpy(map.vexs[1].name, "二号教学楼");
    strcpy(map.vexs[1].features, "上课的地点，包括图书馆，自修区");
    strcpy(map.vexs[2].name, "三号教学楼");
    strcpy(map.vexs[2].features, "新建教学楼，里面有各种实验室以及老师办公室，湖景房");
    strcpy(map.vexs[3].name, "一号教学楼");
    strcpy(map.vexs[3].features, "上课的地点，旁边就是菜鸟驿站 ");
    strcpy(map.vexs[4].name, "田径场");
    strcpy(map.vexs[4].features, "学生跑步散步的地点，部分体育课的地点以及体测的地方");
    strcpy(map.vexs[5].name, "湖");
    strcpy(map.vexs[5].features, "人造湖，禁止垂钓，可以在旁边散步");
    strcpy(map.vexs[6].name, "文体中心");
    strcpy(map.vexs[6].features, "各种表彰大会等会议的地点，部分体育课的地点");
    strcpy(map.vexs[7].name, "西门口");
    strcpy(map.vexs[7].features, "重建之后的门口，旁边可以直达小吃街");
    strcpy(map.vexs[8].name, "男宿舍");
    strcpy(map.vexs[8].features, "学生就寝的地点");
    strcpy(map.vexs[9].name, "三餐");
    strcpy(map.vexs[9].features, "分为一二楼，旁边有711便利店");
    strcpy(map.vexs[10].name, "女宿舍");
    strcpy(map.vexs[10].features, "学生就寝的地点");
    strcpy(map.vexs[11].name, "校医院");
    strcpy(map.vexs[11].features, "学校的医院，旁边有天猫超市，洗浴中心");
    strcpy(map.vexs[12].name, "第一二餐");
    strcpy(map.vexs[12].features, "分为一二楼，一餐一楼，二餐二楼");
    //边的权重赋值
    map.edges[0][1]=map.edges[1][0]=350;
    map.edges[0][2]=map.edges[2][0]=100;
    map.edges[0][3]=map.edges[3][0]=350;
    map.edges[1][2]=map.edges[2][1]=200;
    map.edges[1][4]=map.edges[4][1]=200;
    map.edges[2][3]=map.edges[3][2]=200;
    map.edges[2][5]=map.edges[5][2]=200;
    map.edges[3][6]=map.edges[6][3]=300;
    map.edges[4][7]=map.edges[7][4]=60;
    map.edges[4][5]=map.edges[5][4]=500;
    map.edges[4][8]=map.edges[8][4]=200;
    map.edges[5][9]=map.edges[9][5]=600;
    map.edges[5][6]=map.edges[6][5]=100;
    map.edges[6][10]=map.edges[10][6]=100;
    map.edges[6][11]=map.edges[11][6]=300;
    map.edges[7][8]=map.edges[8][7]=50;
    map.edges[8][9]=map.edges[9][8]=800;
    map.edges[8][12]=map.edges[12][8]=850;
    map.edges[9][12]=map.edges[12][9]=50;
    map.edges[9][10]=map.edges[10][9]=300;
    map.edges[10][12]=map.edges[12][10]=400;
    map.edges[10][11]=map.edges[11][10]=200;
}
void Exit()
{
    printf("\n【警告】：\n退出系统之后，当前的所有操作将会恢复默认值。\n");
    printf("确认退出请按1，按任意键停止当前退出操作。\n");
    int flag;
    scanf("%d",&flag);
    if(flag==1)
    {
        system("cls");
        exit(0);
    }
}
void printmap()
{
    system("cls");
    printf("\n                              *地图一览*\n\n");
    printf("                                @0北校门                                         \n");
    printf("                           .      |       .                                \n");
    printf("                  350   .         |            .  350                           \n");
    printf("                   .              |100             .                         \n");
    printf("               .      200         |       200           .                    \n");
    printf("  (图书馆)@1二教----------------@2三教---------------@3一教(菜鸟驿站)              \n");
    printf("              |300               | 200                 |300                   \n");
    printf("              |       500        |          100        |                     \n");
    printf("          @4田径场--------------@5湖-------------@6文体中心              \n");
    printf("     60  .    |200               |                     |       .  300          \n");
    printf("       .      |         800      | 600    300          |100        .          \n");
    printf("  @7西门口---@8男宿舍-----------@9一二餐----------@10女宿舍----@11校医院         \n");
    printf("          50    .                 |                    .    200             \n");
    printf("                     .            | 50          .                             \n");
    printf("                  850      .      |       .     400                         \n");
    printf("                                @12三餐                                           \n");
    printf("\n\n\n\n\n");
    printf("按回车键返回主界面\n");
    system("pause");
    getchar();
    getchar();
    main();
}

测试结果就不放了，将代码的部分程序修改修改就可以了。文章来源地址https://www.toymoban.com/news/detail-459222.html

到了这里，关于数据结构课设 校园导航系统的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【数据库课设】图书馆资源管理系统 源码+流程图+结构设计（借还图书 逾期罚款 图书管理 读者管理 信息查询）python实现

    【数据库课设】图书馆资源管理系统 源码+流程图+结构设计（借还图书 逾期罚款 图书管理 读者管理 信息查询）python实现

    一个管理员编号对应一个密码，且需要有管理员注册密匙。 可以在图书信息表中录入、修改、删除图书。 可以在图书信息表中查询书籍。 可以编辑图书借阅、归还信息。 可以编辑欠款信息。 可以编辑读者信息表。 图书馆注册，获得读者编号。 可以在图书信息表中查阅书籍

    2024年02月10日
    浏览(53)
  • 数据结构课设--图书管理系统（含泪版）

    数据结构课设--图书管理系统（含泪版）

    设计一个计算机管理系统完成图书管理基本业务。 【基本要求】 （1）每种书的登记内容包括书号、书名、著作者、现存量和库存量； （2）对书号建立索引表（线性表）以提高查找效率； （3）采编入库：新购一种书，确定书号后，登记到图书帐目表中，如果表中已有，则只

    2024年02月08日
    浏览(47)
  • 交通咨询系统源代码（数据结构课设）

    交通咨询系统源代码（数据结构课设）

      系统的展示和选题在这篇博客：点击这里        （就没有详解啦，代码中的注释已经写的很详细了）          直说了，我使用的软件是vs，但是dev也可以运行，反倒是初次使用vs的同学，没有关掉sdl检查的话运行会报错，说是scanf啥的出问题。解决方法：项目-属性-

    2024年02月11日
    浏览(42)
  • 数据结构课设----运动会分数统计系统（C++版）

    数据结构课设----运动会分数统计系统（C++版）

    1.1② 运动会分数统计 【问题描述】 参加运动会的n个学校编号为1~n。比赛分成m个男子项目和w个女子项目，项目编号分别为1~m和m+1~m+w。由于各项目参加人数差别较大，有些项目取前五名，得分顺序为7，5，3，2，1；还有些项目只取前三名，得分顺序为5；3，2。写一个统计程序

    2024年02月03日
    浏览(43)
  • 数据结构课设—C语言实现通讯录管理系统（顺序表实现）

    数据结构课设—C语言实现通讯录管理系统（顺序表实现）

    这个项目是我大一时期数据结构的课程设计，在我潜心研究下出来的，对于当时的我来说算是非常满意啦，哈哈哈哈哈哈哈哈哈哈☆*: .｡. o(≧▽≦)o .｡.:*☆ 目录 一、引言 1.目的： 2.意义： 3.主要任务： 4.程序功能： 5.编译工具： 二、正文 1.系统模块： 2.算法流程图： 3.各

    2024年02月02日
    浏览(79)
  • 数据结构课程设计——项目2：校园导游咨询

    数据结构课程设计——项目2：校园导游咨询

    【问题描述】 设计一个校园导游程序,为来访的客人提供各种信息查询服务。 【基本要求】 设计你所在学校的校园平面图,所含景点不少于10个.以图中顶点表示校 内各景点,存放景点名称、代号、简介 等信息；以边表示路径，存放路径长度等相关信息。 为来访客人提供图中任

    2024年02月02日
    浏览(69)
  • 数据结构——校园导游系统

    数据结构——校园导游系统

    大二下学期修了数据结构这门课，课设的要求是做一个校园导航系统。详细的要求如下 问题描述： 当我们参观校园时，会遇到如下问题：从当前所处位置去校园另外一个位置，要走什么样的路线距离最短？本课程设计任务要求，在给出校园各主要建筑的名称信息及有路线连

    2024年02月04日
    浏览(39)
  • 数据结构课设——成绩分析问题

    数据结构课设——成绩分析问题

    一、实验 题目 【问题描述】 录入、保存一个班级学生多门课程的成绩，并对成绩进行分析。 【基本要求】 （1）通过键盘输入各学生的多门课程的成绩，建立相应的文件 input.dat。 （2）对文件 input.dat 中的数据进行处理，要求具有如下功能：         1) 按各门课程成绩排

    2024年02月07日
    浏览(44)

  • 内部排序算法比较-数据结构C语言课设

    名称： 内部排序算法比较 内容： 在教科书中，各种内部排序算法的时间复杂的分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机数据比较各种算法的比较次数和移动次数，以取得直观感受。 任务： (1)对以下7中常会用的内部排序算法进行比较

    2024年02月12日
    浏览(55)
  • 数据结构课设：图书信息管理--顺序存储和链式存储

    数据结构课设：图书信息管理--顺序存储和链式存储

    在本实验中，我选择了两种存储结构（顺序存储和链式存储）来对图书信息表的修改问题进行描述，即：3．基于顺序存储结构的图书信息表的修改问题描述 和 13．基于链式存储结构的图书信息表的修改问题描述。 3．基于顺序存储结构的图书信息表的修改问题描述 首先，定

    2024年02月08日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包