图的最短路径算法的实现.doc

图的最短路径算法的实现C语言#include#include#include#define INF 32767#define MAXV 100#define BUFLEN 1024typedef struct char name100;char info1000; VertexType;typedef struct VertexType vexs10; int arcs100100;int vexnum,arcnum; MGraph;/图结构 char* getFile(char fileName,char *array,int &count)FILE *file;char bufBUFLEN;int len=0;/文件读取的长度 file=fopen(fileName,rt);/打开graph.txt的信息 if(file=NULL)/文件为空的处理办法 printf(Cannot open file strike any key exit!n);exit(1);while(fgets(buf,BUFLEN,file) len=strlen(buf); arraycount=(char*)malloc(len+1); if(!arraycount) break; strcpy(arraycount+,buf);fclose(file);return array;void getInfo(int &vex,int &arc,char *array)char buf_ch100;char *ch100; char *tokenp;int str_count=0,str_len=0;tokenp=strtok(array, );strcpy(buf_ch,tokenp);while(tokenp!=NULL)str_len=strlen(tokenp); chstr_count=(char*)malloc(str_len+1); strcpy(chstr_count+,tokenp); tokenp=strtok(NULL, );for(int i=0;istr_count;i+)if(i%2=1)chistrlen(chi)-1=0;sscanf(chi,%d,&arc);elsesscanf(chi,%d,&vex); MGraph setVertexTypeInfo(MGraph g,char *arrayVer)int str_count=0;char buf_ch100;char *ch100;char *tokenp;for(int i=0;ig.vexnum+1&arrayVerg.vexnum;i+)int str_len=0;tokenp=strtok(arrayVeri, );strcpy(buf_ch,tokenp);while(tokenp!=NULL) str_len=strlen(tokenp); chstr_count=(char*)malloc(str_len+1); strcpy(chstr_count+,tokenp);tokenp=strtok(NULL, );for(int i1=2;i1str_count;i1+)if(i1%2=1)chi1strlen(chi1)-1=0;strcpy(g.vexsi1/2-1.info,chi1);elsestrcpy(g.vexsi1/2-1.name,chi1);return g;/设置无向图的基本信息 MGraph setMGraphInfo(MGraph g,char *arrayMGraph,int &count)int str_count=0;char buf_ch100;char *ch100;char *tokenp;for(int i4=g.vexnum+1;i4count;i4+)int str_len=0;tokenp=strtok(arrayMGraphi4, );strcpy(buf_ch,tokenp);while(tokenp!=NULL) str_len=strlen(tokenp); chstr_count=(char*)malloc(str_len+1); strcpy(chstr_count+,tokenp);tokenp=strtok(NULL, );char *info8;/需要匹配的字符串集合 for(int i2=0;i2g.vexnum;i2+)infoi2=;int G5050;/邻接矩阵初始化 for(int i3=0;i3g.vexnum;i3+)for(int j=0;jg.vexnum;j+)Gi3j=INF;int temp100=0;/存储距离信息 int temp_count=0;/距离计数器 int templeft100=0;/起始地址的代号信息 int templeft_count=0;/起始地址计数器 int tempright100=0;/终点地址的代号信息 int tempright_count=0;/终点地址的计数器 for(int k=0;kstr_count;k+)if(k%3=0)for(int m=0;mg.vexnum;m+)if(strcmp(infom,chk)=0)templefttempleft_count+=m;else if(k%3=1)for(int m=0;mg.vexnum;m+)if(strcmp(infom,chk)=0)temprighttempright_count+=m;else if(k%3=2)chkstrlen(chk)-1=0;sscanf(chk,%d,&temptemp_count+);for(int i5=0;i5temp_count;i5+)Gtemplefti5temprighti5=tempi5;for(int i6=0;i6g.vexnum;i6+)/建立图的邻接矩阵for(int j=0;jg.vexnum;j+)g.arcsi6j=Gi6j;return g;void DispMat(MGraph g)int i,j;for(i=0;ig.vexnum;i+)for (j=0;j,);ppath(g,path,k,j);void DisPath(MGraph g,int AMAXV,int pathMAXV,int i,int j)if (Aij=INF)if (i!=j) printf(从 %s 到 %s 没有路径n,,);elseprintf(%s-,);ppath(g,path,i,j);printf(%s,);printf(t路径长度为:%dn,Aij); void Floyd(MGraph g,int p,int q)/弗洛伊德算法int AMAXVMAXV,pathMAXVMAXV;int i,j,k,n=g.vexnum;for (i=0;in;i+)for (j=0;jn;j+) Aij=g.arcsij;pathij=-1;for (k=0;kn;k+) for (i=0;in;i+) for (j=0;j(Aik+Akj) Aij=Aik+Akj; pathij=k; printf(最短路径为:n);DisPath(g,A,path,p,q); /输出最短路径int main()int vex,arc;printf( 欢迎来到江西理工大学 n);printf( n);MGraph g;/图的定义char *array1;/存储顶点和边数数据信息 char *arrayVer10;/存储地点信息 char *arrayMGraphMAXV;/存储关于图的信息 int count=0;char fileName=D:数据结构shujujiegouyigraph.txt;getFile(fileName,array,count);/printf(%dn,count);count=0;getInfo(vex,arc,array0);g.vexnum=vex;g.arcnum=arc;getFile(fileName,arrayVer,count);count=0;g=setVertexTypeInfo(g,arrayVer); getFile(fileName,arrayMGraph,count);g=setMGraphInfo(g,arrayMGraph,count);DispMat(g);printf( 江西理工大学校园导向图 nn);printf( 功能选项： nn);printf( 1.查看所有景点 nn);printf( 2.查询景点信息 nn);printf( 3.查询两个景点的最短路径 nn);printf( 4.退出校园导游 nn);printf( 返回到所有景点请输入9（功能3辅助） nn);int n=0,m=0,p=0,q=0,flag=0;int i7=0;while(n!=4)flag=scanf(%d,&n);while(flag!=1) fflush(stdin); printf(对不起，您输入的有误，请重输入n); flag=scanf(%d,&n); switch(n)loop1:case 1: printf(校园的景点有：n);for(i7=0;i7g.vexnum;i7+)printf( %d.%sn,i7+1,);printf(需要继续查询请选择功能选项，否则按4退出n);break;loop2:case 2: printf(请选择您要查询的景点:(1-8)n); flag=scanf(%d,&m);while(flag!=1) fflush(stdin); printf(对不起，您输入的不是数字，请输入数字n); flag=scanf(%d,&m); if(m0)printf(%s的信息:%sn,,);printf(需要继续查询请选择功能选项，否则按4退出n);elseprintf(您输入的数字有误，请输入(1-8)n);goto loop2;break;case 3: printf(请输入您要查询第一个的景点:(1-8)n); loop3:flag=scanf(%d,&p); while(flag!=1) fflush(stdin); printf(对不起，您输入的不是数字，请输入数字n); flag=scanf(%d,&p); if(p=9) goto loop1; if(p0)printf(请输入您要查询第二个的景点:(1-8)n);elseprintf(您输入有误，请重新输入要查询的第一个景点(1-8)n);goto loop3;loop4:flag=scanf(%d,&q);while(flag!=1) fflush(stdin); printf(对不起，您