目的是要求出交通网中最短时间到达的最优路径 构造了时间树 这个只是MFC求最少时间的模块 其他的没有贴出来 第一次运行的时候正常 第二次就会出现图片的错误 查了好久 大多说是指针错误 看调用堆栈我也不太会看 而且调用堆栈里面还说user32.dll未加载符号 不知道是怎么回事 希望你们能给些建议 谢谢你们 分不多 可是我就只有这么多了
typedef struct QNode
{
int adjvex;
struct QNode *next;
}QNode;
typedef struct
{
QNode *front;
QNode *rear;
}LinkQueue;
typedef struct TimeNode
{
int adjvex;
int route;
double starttime;
double endtime;
struct TimeNode *child[MAX_PATH_NUM];
}TimeNode,*TimeTree;
typedef struct Vehide
{
int number;
double starttime;
double endtime;
double costtime;
double costmoney;
}Vehide;
typedef struct
{
Vehide stata[MAX_PATH_NUM];
int last;
}infolist;
typedef struct ArcNode
{
int adjvex;
struct ArcNode *nextarc;
infolist info;
}ArcNode;
typedef struct VNode
{
CString city;
ArcNode *planefirstarc,*trainfirstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct
{
AdjList vertices;
int vexnum,planearcnum,trainarcnum;
}ALGraph;
typedef struct Node
{
int adjvex;
int route;
struct Node *next;
}Node;
void LowTime2City(infolist arcs ,double &costtime , int &route)
{
int i;
costtime = arcs.stata[1].costtime;
if( costtime < INIFINTY)
route = 1;
else
route = -1;
for( i = 2; i <= arcs.last ;i++)
{
if (arcs.stata[i].costtime < costtime)
{
costtime = arcs.stata[i].costtime;
route = i;
}
}
}
void CreateTimeTree(TimeTree p, int i,int j,LinkQueue &Q,infolist arcs[][MAX_VERTEX_NUM])
{//创建时间树
int n , x , y;
TimeTree q;
q = (TimeNode *)malloc(sizeof(TimeNode));
q->adjvex = j;
q->starttime = arcs[i][j].stata[1].starttime;
q->endtime = arcs[i][j].stata[1].endtime;
q->route = 1;
p->child[1] = q;
for(n = 2;n <= arcs[i][j].last;n++)
{
q = (TimeNode *)malloc(sizeof(TimeNode));
q->adjvex = j;
q->starttime = arcs[i][j].stata[n].starttime;
q->endtime = arcs[i][j].stata[n].endtime;
q->route = n;
p->child[n] = q;
}
while (n < MAX_PATH_NUM)
{
p->child[n] = NULL;
n++;
}
x = j;
if ( !IsEmpty(Q))
{
DeQueue(Q,y);
CreateTimeTree(p->child[1],x,y,Q,arcs);
for(n = 2;n <= arcs[i][j].last;n++)
{
CopyTimeTree(p->child[n],p->child[1]);
}
}
else
{
for(n = 1; n<MAX_PATH_NUM;n++)
{
p->child[1]->child[n]= NULL;
}
for(n = 2; n <= arcs[i][j].last;n++)
{
CopyTimeTree(p->child[n],p->child[1]);
}
}
return ;
}
void CopyTimeTree(TimeTree p,TimeTree q)
{//复制时间树
TimeTree r;
int n = 1;
while(q->child[n] != NULL)
{
r = (TimeNode *)malloc(sizeof(TimeNode));
r->adjvex = q->child[n]->adjvex;
r->starttime = q->child[n]->starttime;
r->endtime = q->child[n]->endtime;
r->route = q->child[n]->route;
p->child[n] = r;
CopyTimeTree(p->child[n],q->child[n]);
n++;
}
while (n < MAX_PATH_NUM)
{
p->child[n] = NULL;
n++;
}
return ;
}
void VisitTimeTree(TimeTree p)
{
int n ;
int x;
double y;
x = time1;
y = time2;
int days = 1;
CString str;
CString starttime,sshour,ssmin;
int ishour,ismin;
starttime.Format(_T("%f"),p->starttime);
sshour = starttime.Mid(8,2);
ssmin = starttime.Mid(10,2);
ishour = _ttoi(sshour);
ismin = _ttoi(ssmin);
CTime start(2004,10,1,ishour,ismin,0);
CString time22,stime2hour,stime2min;
int itime2hour,itime2min;
time22.Format(_T("%f"),time2);
stime2hour = stime2hour.Mid(8,2);
stime2min = stime2min.Mid(10,2);
itime2hour = _ttoi(stime2hour);
itime2min = _ttoi(stime2min);
CTime ttime2(2004,10,1,itime2hour,itime2min,0);
CTimeSpan cost1 = start - ttime2;
time1 = int (cost1.GetTotalMinutes());
if (time1 < 0)
{
time1 += 1440;
}
CString endtime,sehour,semin,seday;
int iehour,iemin,ieday;
endtime.Format(_T("%f"),p->endtime);
seday = endtime.Mid(6,2);
sehour = endtime.Mid(8,2);
semin = endtime.Mid(10,2);
iehour = _ttoi(sehour);
iemin = _ttoi(semin);
ieday = _ttoi(seday);
CTime end(2004,10,ieday,iehour,iemin,0);
cost1 = end - start;
time1 += int(cost1.GetTotalMinutes());
time2 = p->endtime;
c[p->adjvex] = p->route;
if (p->child[1] == NULL)
{
if (time1 < time0)
{
time0 = time1;
for ( n = 1;n <= MAX_VERTEX_NUM;n++)
{
d[n] = c[n];
}
}
}
else
{
n = 1;
while (p->child[n] != NULL)
{
VisitTimeTree(p->child[n]);
n++;
}
}
time1 = x;
time2 = y;
return ;
}
void TimeTreeDispose(Node *head , infolist arcs[][MAX_VERTEX_NUM])
{//构造时间树
int n , i , j;
Node *p;
LinkQueue Q;
TimeTree root;
root = (TimeNode *)malloc(sizeof(TimeNode));
InitQueue(Q);
TTime = int(INIFINTY);
p = head->next;
while (p != NULL)
{
EnQueue(Q,p->adjvex);
p = p->next;
}
DeQueue(Q,i);
root->adjvex = i;
DeQueue(Q,j);
CreateTimeTree(root, i , j, Q , arcs);
for(n = 1;n <= arcs[i][j].last;n++)
{
time1 = 0;
time2 = root->child[n]->starttime;
time0 = int(INIFINTY);
VisitTimeTree(root->child[n]);
if(time0 < TTime)
{
TTime = time0;
p = head->next;
while(p != NULL)
{
p->route = d[p->adjvex];
p = p->next;
}
}
}
return ;
}
void LowestTime(int k , infolist arcs[][MAX_VERTEX_NUM] , ALGraph G ,int v0 ,int v1,double T[],int Final[])
{
int v , w , i , route;
double m;
Node *p , *q , *s , *t , *r;
CString str1,str2;
p = (Node *)malloc(G.vexnum*sizeof(Node));
for (v = 1;v <= G.vexnum ; v++)
{
Final[v] = FALSE;
LowTime2City(arcs[v0][v] , T[v] , route);
p[v].next = NULL;
if (T[v] < INIFINTY)
{
q = (Node *)malloc(sizeof(Node));
s = (Node *)malloc(sizeof(Node));
q->adjvex = v0;
s->adjvex = v;
s->route = route;
p[v].next = q;
q->next = s;
s->next = NULL;
}
}
T[v0] = 0;
Final[v0] = TRUE;
for ( i = 2; i <= G.vexnum; i++)
{
m = INIFINTY;
v = -1;
for (w = 1;w <= G.vexnum; w ++)
{
if (Final[w] == FALSE)
{
if (T[w] < m)
{
v = w;
m = T[w];
}
}
if (v == v1)
{
q = p[v].next;
r = q->next;
str1.Format(_T("最少时间旅行路线是:\n\n"));
str2 = str1;
while ( r != NULL)
{
if (k == 1)
{
str1.Format(_T("乘坐No.%d列车从%s到%s\n"),arcs[q->adjvex][r->adjvex].stata[r->route].number,G.vertices[q->adjvex].city,G.vertices[r->adjvex].city);
str2 += str1;
}
if (k == 2)
{
str1.Format(_T("乘坐No.%d飞机从%s到%s\n"),arcs[q->adjvex][r->adjvex].stata[r->route].number,G.vertices[q->adjvex].city,G.vertices[r->adjvex].city);
str2 += str1;
}
q = r;
r = r->next;
}
MessageBox(NULL,str2,NULL,NULL);
for (v = 1; v<= G.vexnum;v++)
{
q = p[v].next;
while (q != NULL)
{
s = q;
q = q->next;
free(s);
}
p[v].next = NULL;
}
return ;
}
else if (v != -1)
{
Final[v] = TRUE;
for (w = 1 ; w <= G.vexnum; w++)
{
if (Final[w] == FALSE&&arcs[v][w].last >0)
{
t = p[w].next;
q = &p[w];
s = p[v].next;
while (s != NULL)
{
r = (Node *)malloc(sizeof(Node));
r->adjvex = s->adjvex;
r->route = s->route;
q->next = r;
q = r;
s = s->next;
}
r = (Node *)malloc(sizeof(Node));
r->adjvex = w;
r->route = route;
r->next = NULL;
q->next = r;
TimeTreeDispose(&p[w],arcs);
if (T[w] > TTime)
{
T[w] = TTime;
while (t != NULL)
{
q = t;
t = t->next;
free(q);
}
}
else
{
q = p[w].next;
while (q != NULL)
{
r = q;
q = q->next;
free(r);
}
p[w].next = t;
}
}
}
}
}
}
for (v = 1;v <= G.vexnum;v++)
{
q = p[v].next;
while (q != NULL)
{
s = q;
q = q->next;
free(s);
}
p[v].next = NULL;
}
if ( k == 1 )
{
str1.Format(_T("不存在列车从 %s 到 %s \n"),G.vertices[v0].city,G.vertices[v1].city);
}
else
{
str1.Format(_T("不存在飞机从 %s 到 %s \n"),G.vertices[v0].city,G.vertices[v1].city);
}
MessageBox(NULL,str1,_T("查询结果"),MB_OK|MB_ICONASTERISK);
return ;
}