程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> c++查詢最短途徑示例

c++查詢最短途徑示例

編輯:關於C++

c++查詢最短途徑示例。本站提示廣大學習愛好者:(c++查詢最短途徑示例)文章只能為提供參考,不一定能成為您想要的結果。以下是c++查詢最短途徑示例正文



//shortest_path.c
#include<stdio.h>
#include<stdlib.h>//用file
#include<string.h>//可用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<map.spotnum;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<map.spotnum;i++)
  for(j=0;j<map.spotnum;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<map.spotnum;a++)//initialize map
  for(b=0;b<map.spotnum;b++)
  {
   if(a==b)map.pathmatrix[a][b]=0;
   else map.pathmatrix[a][b]=MAX;
  }

 for(i=0;i<map.spotnum;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<map.pathnum;i++){
  do{
   printf("請輸出第%d條途徑的終點",i+1);
   fflush(stdin);
   gets(s1);
   for(a=0;a<map.spotnum;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<map.spotnum;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<map.spotnum;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<map.spotnum;t++)
   if(!strcmp(map.spot[t].name,s2))break;
  if(t==map.spotnum)printf("不存在此景點,請從新輸出。\n");
 }while(t==map.spotnum);
 for(v=0;v<map.spotnum;v++)//initialize spath
 {
  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<map.spotnum;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<map.spotnum;w++)
   if((!spath[w].in)&&(spath[w].length<min)){
    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


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved