c++查詢最短路徑示例
C++擅長面向對象程序設計的同時,還可以進行基於過程的程序設計,因而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:sp";
const char *filepath2="D:";
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]o,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(&matrix[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)matrix[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",&matrix[a][b]);
matrix[b][a]=matrix[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])&&(spath[w]th<min)){
min=spath[w]th;
v=w;
}
spath[v]=1;
}
printf("最短路徑長度為%d,最短路徑為:n",spath[t]th);//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]]);
}
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
-
在C語言中轉換時間的基本方法
本文主要介紹了在C語言中轉換時間的基本方法,分別是mktime()函數和localtime()函數的使用,供參考學習,感興趣的小夥伴們可以參考一下!想了解更多相關信息請持續關注我們應屆畢業生考試網!C語言mktime()函數:將時間轉換成經過的秒數頭文件:#include<time.h>定義函數:t...
-
C語言轉義字符和格式控制符參考
導語:字符型常量所表示的值是字符型變量所能包含的值。我們可以用ASCII表達式來表示一個字符型常量,或者用單引號內加反斜槓表示轉義字符。下面是C語言轉義字符和格式控制符參考,歡迎學習:轉義字符參考:a:蜂鳴,響鈴:回退:向後退一格f:換頁:換行,光標到下行行首:回車,光...
-
C語言自學入門技巧
學習C語言不是一朝一夕的事情,但也不需要花費很長的時間才能精通。下面小編就為大家介紹一下C語言自學入門技巧吧!C語言自學入門技巧11、程語語言其實是一個很初級的工具,但是又必須熟練的掌握它,學懂一門編程語言就好像學會了寫字,但是會寫字的人不見得會寫文章,而...
-
C/C++變量在內存中的分佈介紹
變量在內存地址的分佈為:堆-棧-代碼區-全局靜態-常量數據。同一區域的各變量按聲明的順序在內存的中依次由低到高分配空間(只有未賦值的全局變量是個例外)。本文是本站小編搜索整理的關於C/C++變量在內存中的分佈介紹,感興趣的朋友一起學習吧!!想了解更多相關信息...