主函数运行的时候不会进入Dijkstra函数,莫名其妙就结束啦。
#include <stdio.h>
#include<malloc.h>
#include <string.h>
#include <stdbool.h>
#define MVNum 100
#define INFINE 666666
#define MAXLEN 20
struct transportation //边的数据
{
float gotimehour;
float gotimemin;
float intimehour;
float intimemin;
int price;
float time;
float weight;
char range[20];
};
typedef struct ArcNode //边集
{
int adjvex;
struct ArcNode *nextarc;
struct transportation info;
} ArcNode;
typedef struct VNode //顶点集
{
int NO;
char name[20];
ArcNode *firstarc;
}VNode,AdjList[MVNum];
typedef struct TransGraph//图
{
AdjList vertices;
int vexnum,arcnum;
}TransGraph;
int getPosition(TransGraph *G, int c)
{
int m;
for (m = 1; m <= G->vexnum; m++)
{
G->vertices[m].NO=m;
if (G->vertices[m].NO == c)
{
return m;
}
}
return 1;
}
//or
int LocateVex(TransGraph *G,int v)//查找元素v在一维数组 Vertex[] 中的下标,并返回下标
{
int i;
for(i=0;i<G->vexnum;i++)
{
G->vertices[i].NO=i;
if(v==G->vertices[i].NO)
{
return i;
}
}
printf("No Such Vertex!\n");
return -1;
}
void Create(TransGraph *G)
{
int i,j,k;
int v1,v2;
scanf("%d %d",&G->vexnum,&G->arcnum);
printf("%d %d\n",G->vexnum,G->arcnum);
for(i=0;i<G->vexnum;i++)
{
scanf("%s",G->vertices[i].name);
printf("%s",G->vertices[i].name);
G->vertices[i].NO=i;
G->vertices[i].firstarc=NULL;
}
for(k=-0;k<G->arcnum;k++)
{
scanf("%d %d",&v1,&v2);
printf("%d %d\n",v1,v2);
i=LocateVex(G,v1);
j=LocateVex(G,v2);
ArcNode* p1=(ArcNode*)malloc(sizeof(ArcNode));
scanf("%f %f %f %f %d",&p1->info.gotimehour,&p1->info.gotimemin,&p1->info.intimehour,&p1->info.intimemin,&p1->info.price);
printf("%f %f %f %f %d",p1->info.gotimehour,p1->info.gotimemin,p1->info.intimehour,p1->info.intimemin,p1->info.price);
p1->info.time=p1->info.intimehour-p1->info.gotimehour+(p1->info.intimemin-p1->info.gotimemin)/60.0;
scanf("%s",&p1->info.range);
printf(" %s\n",p1->info.range);
p1->adjvex=j;
p1->nextarc=G->vertices[i].firstarc;
G->vertices[i].firstarc=p1;
}
}
void SeeAll(TransGraph *G)
{
int i;
for(i=0;i<MVNum;i++)
{
struct ArcNode* p1=(struct ArcNode*)malloc(sizeof(struct ArcNode));
p1=G->vertices[i].firstarc;
while(p1!=NULL)
{
printf("交通方式:%s ",p1->info.range);
printf("出发时间:%0.f:%0.f 到达时间:%0.f:%0.f 票价格:%d 总时间:%f \n",p1->info.gotimehour,p1->info.gotimemin,p1->info.intimehour,p1->info.intimemin,p1->info.price,p1->info.time);
p1=p1->nextarc;
}
}
}
int get_weight(TransGraph *G, int start, int end,float a,float b)
{
ArcNode* node=(ArcNode*)malloc(sizeof(ArcNode));
if (start == end)
return 0;
node=G->vertices[start].firstarc;
while (node != NULL)
{
node->info.weight=(a*(node->info.time)+b*(node->info.price));
if (end == node->adjvex)
return node->info.weight;
node = node->nextarc;
}
return INFINE;
}
void Dijkstra(TransGraph *G, int vs,int final, int prev[], int dist[])
{
printf("%d\n",prev[1]);
int i, j, k, t,m,q;
float a,b;
int min;
int tmp;
int flag[INFINE];
int path[MAXLEN][MAXLEN]={0};
printf("请输入时间与价格的权重:");
scanf("%d %d",&a,&b);
for (i = 1; i <= G->vexnum; i++)
{
flag[i] = 0;
prev[i] = 0;
dist[i] = get_weight(G, vs, i,a,b);
path[i][0] = 0;
}
flag[vs] = 1;
dist[vs] = 0;
path[vs][0] =1;
for (i = 2; i <= G->vexnum; i++)
{
t = 0;
min = INFINE;
for (j = 1; j <= G->vexnum; j++)
{
if (flag[j] == 0 && dist[j]<min)
{
min = dist[j];
k = j;
}
}
flag[k] = 1;
for (j = 1; j <= G->vexnum; j++)
{
tmp = get_weight(G, k, j,a,b);
tmp = (tmp == INFINE ? INFINE : (min + tmp));
if (flag[j] == 0 && (tmp < dist[j]))
{
dist[j] = tmp;
prev[j] = k;
path[j][t] = k;
t++;
}
}
}
printf("当前出发站:");
printf("%s",G->vertices[vs].name);
i=final;
int showpath[MAXLEN] = {0};
for (m = 0; m < G->vexnum; m++)
{
if (path[i][m] == 0|| G->vertices[path[i][m]].NO == G->vertices[vs].NO)
{
break;
}
showpath[m] = path[i][m];
}
printf("根据您的期待权重所选择的从");
printf("%s",G->vertices[vs].name);
printf("前往");
printf("%s",G->vertices[i].name);
printf("的最合适路线时间为%d小时,价格为%d元",((a*dist[i])/(a+b)), (b*dist[i])/(a+b));
if (dist[i]!= INFINE)
{
printf("\t当前最合适路线为");
puts(G->vertices[vs].name);
int z=0;
for (q = MAXLEN - 1; q >= 0; q--)
{
if (showpath[q] == 0) { continue; }
printf("%s",G->vertices[showpath[q]].name);
printf("(");
printf("%s",G->vertices[showpath[q]].firstarc->info.range);
printf(")->");
z++;
}
printf("%s",G->vertices[i].name);
printf("\n共需换乘%d次。",z);
}
else
{
printf("很抱歉,目前无法前往目的地");
}
}
void GetNext(char ch[],int cLen,int next[]){//cLen为串ch的长度
next[0] = -1;
int k = -1,j = 0;
while(j<=cLen-1){
if(k==-1||ch[j]==ch[k])
{
j++;
k++;
next[j]=k;
}
else k = next[k];
}
}
int KMP(char ch[],char b[],int next[])
{
int i=0,j=0,pos,len;
len=strlen(b);
while(i<15 && j<len)
{
if(j==-1 || ch[i]==b[j])
{
i++;j++;
}
else
{
j=next[j];
}
}
if(j>len-1)
{
printf("匹配成功\n");
return 1;
}
else
{
printf("匹配未成功\n");
return 0;
}
}
int main()
{
int i,m,n,o,f,g;
int vs=-1,final=-1;
int dist[MAXLEN], prev[MAXLEN];
int next1[50],next2[50];
char leave[10],arrive[10];
struct TransGraph* G=(struct TransGraph*)malloc(sizeof(struct TransGraph));
Create(G);
printf("v[0].firstarc:%d\n",G->vertices[0].firstarc);
printf("arc:%f\n",G->vertices[0].firstarc->info.gotimehour);
printf("全部交通行程表为:\n");
SeeAll(G);
printf("请输入您的出发地与目的地\n");
scanf("%s",&leave);
printf("%s\n",leave);
m=strlen(leave);
scanf("%s",&arrive);
printf("%s\n",arrive);
n=strlen(arrive);
for(i=0;i<G->vexnum;i++)
{
o=strlen(G->vertices[i].name);
GetNext(leave,m,next1);
GetNext(arrive,n,next2);
f=KMP(leave,G->vertices[i].name,next1);
if(f==1)
{
vs=getPosition(G,G->vertices[i].NO);
printf("\n%d\n",vs);
}
g=KMP(arrive,G->vertices[i].name,next2);
if(g==1)
{
final=getPosition(G,G->vertices[i].NO);
printf("\n%d\n",final);
}
}
if(vs==-1 || final==-1)
printf("您的出发地/目的地不在当前服务范围内");
else Dijkstra(G,vs,final,prev,dist);
system("pause");
return 0;
}
就是倒数第三行那个.