网站首页  汉语字词  英语词汇  考试资料  写作素材  旧版资料

请输入您要查询的考试资料：

　

标题 c++查询最短路径示例
内容
    这篇文章主要介绍了c++查询最短路径示例,需要的朋友可以参考下
    代码如下:
    //shortest_path.c
    #include
    #include//用file
    #include//可用gets(),puts()
    #include"shortest_path.h"
    #define MAX 32767
    #define MENU "欢迎进入导航系统!n==========菜单===========n0、载入北外地图n1、建立地图n2、查询最短路径n3、退出n==========菜单===========n"
    struct stmap map;//无向网
    const char *filepath1="D:spots.dat";
    const char *filepath2="D:paths.dat";
    int load1()
    {
    FILE *fp;
    int i;
    fp=fopen(filepath1,"r");
    if(fp==NULL){printf("spots文件打开异常，读取失败");return -1;}
    fread(&map.spotnum,sizeof(int),1,fp);
    for(i=0;i
    {
    fread(map.spot[i].name,sizeof(char),10,fp);
    fread(map.spot[i].intro,sizeof(char),20,fp);
    }
    fclose(fp);
    return 0;
    }
    int load2()
    {
    FILE *fp;
    int i,j;
    fp=fopen(filepath2,"r");
    if(fp==NULL){printf("paths文件打开异常，读取失败");return -1;}
    fread(&map.pathmatrix,sizeof(int),1,fp);
    for(i=0;i
    for(j=0;j
    fread(&map.pathmatrix[i][j],sizeof(int),1,fp);
    fclose(fp);
    return 0;
    }
    void loadmap()
    {
    if(load1()==0)
    printf("spot读入成功n");
    else
    printf("spot读入失败n");
    if(load2()==0)
    printf("path读入成功n");
    else
    printf("path读入失败n");
    }
    void drawmap()//直接输入
    {
    int i;
    int a,b;
    char s1[10],s2[10];
    printf("共有几个景点?(<=20)");//map.spotmun
    fflush(stdin);
    scanf("%d",&map.spotnum);
    printf("共有几条景点与景点之间直接相连的路径?");//map.pathnum
    fflush(stdin);//清空键盘缓冲区，在"stdio.h"中
    scanf("%d",&map.pathnum);
    for(a=0;a
    for(b=0;b
    {
    if(a==b)map.pathmatrix[a][b]=0;
    else map.pathmatrix[a][b]=MAX;
    }
    for(i=0;i
    printf("请输入第%d个景点的名称(<=10letters)",i+1);
    fflush(stdin);
    gets(map.spot[i].name);
    printf("请输入第%d个景点的介绍(<=20letters)",i+1);
    fflush(stdin);
    gets(map.spot[i].intro);
    }//输入景点名字和简介map.spot[].name;map.spot[].intro
    for(i=0;i
    do{
    printf("请输入第%d条路径的起点",i+1);
    fflush(stdin);
    gets(s1);
    for(a=0;a
    if(!strcmp(map.spot[a].name,s1))break;//查找景点编号
    if(a==map.spotnum)printf("不存在此景点，请重新输入。n");
    }while(a==map.spotnum);
    do{
    printf("请输入第%d条路径的终点",i+1);
    fflush(stdin);
    gets(s2);
    for(b=0;b
    if(!strcmp(map.spot[b].name,s2))break;
    if(b==map.spotnum)printf("不存在此景点，请重新输入。n");
    }while(b==map.spotnum);
    printf("请输入第%d条路径的长度",i+1);
    fflush(stdin);
    scanf("%d",&map.pathmatrix[a][b]);
    map.pathmatrix[b][a]=map.pathmatrix[a][b];//输入路径长度
    }
    }
    void shortestpath()//最短路径，输入起点终点输出路径和路程
    {
    struct stspath spath[20];
    int s,t,v,w,min;
    char s1[10],s2[10];
    int pathorder[20];
    struct stspath *p;//pathorder
    do{
    printf("请输入起点");//查找起点的景点编号
    fflush(stdin);
    gets(s1);
    for(s=0;s
    if(!strcmp(map.spot[s].name,s1))break;
    if(s==map.spotnum)printf("不存在此景点，请重新输入。n");
    }while(s==map.spotnum);
    do{
    printf("请输入终点");//查找终点的景点编号
    fflush(stdin);
    gets(s2);
    for(t=0;t
    if(!strcmp(map.spot[t].name,s2))break;
    if(t==map.spotnum)printf("不存在此景点，请重新输入。n");
    }while(t==map.spotnum);
    for(v=0;v
    {
    spath[v].length=MAX;
    spath[v].in=0;
    }
    spath[s].in=1;
    spath[s].length=0;
    spath[s].pior=NULL;
    v=s;
    while(v!=t){
    for(w=0;w
    if((!spath[w].in)&&(spath[w].length>spath[v].length+map.pathmatrix[v][w])){
    spath[w].length=spath[v].length+map.pathmatrix[v][w];
    spath[w].pior=&spath[v];
    }
    min=MAX;
    for(w=0;w
    if((!spath[w].in)&&(spath[w].length
    min=spath[w].length;
    v=w;
    }
    spath[v].in=1;
    }
    printf("最短路径长度为%d,最短路径为：n",spath[t].length);//print path
    for(v=0,p=&spath[t];p->pior!=NULL;p=p->pior)
    {
    pathorder[v]=p-spath;
    v++;
    }
    pathorder[v]=s;
    for(;v>=0;v--)
    printf("%10s",map.spot[pathorder[v]].name);
    }
    void main()
    {
    int menu=1;
    printf(MENU);
    while(menu!=3)
    {
    printf("n请输入您的选项(数字)n");
    fflush(stdin);
    scanf("%d",&menu);
    switch (menu)
    {
    case 0: loadmap();printf("n北外地图载入完成n");break;
    case 1: drawmap();printf("n新建完成n");break;
    case 2: shortestpath();printf("n查询完成完成n");break;
    }
    }
    printf("谢谢使用!");
    }
    2. [文件] shortest_path.h ~ 430B 下载(2)
    #ifndef _SHORTEST_PATH_H_
    #define _SHORTEST_PATH_H_
    struct stspot{//景点的顶点
    char name[11];//景点名称no more than 10
    char intro[20];//景点介绍no more than 20
    };
    struct stmap{//整个无向网
    stspot spot[20];//点，景点向量
    int pathmatrix[20][20];//边，路径的邻接矩阵
    int spotnum;
    int pathnum;
    };
    struct stspath//求最短路径时的景点数组
    {
    stspath * pior;
    int in;// can be boolen
    int length;
    };
    #endif
    名单
随便看

　

在线学习网考试资料包含高考、自考、专升本考试、人事考试、公务员考试、大学生村官考试、特岗教师招聘考试、事业单位招聘考试、企业人才招聘、银行招聘、教师招聘、农村信用社招聘、各类资格证书考试等各类考试资料。

　

Copyright © 2002-2024 cuapp.net All Rights Reserved
更新时间：2025/5/19 19:37:10