数据结构课程设计全国交通咨询系统(3)

全国交通咨询系统 第三章详细设计

cityedit(ALGraph *G) {int i; char q;

printf(\ ┏━━━━━━━━━━━━━━━━━┓\\n\ printf(\ ┃请选择城市编辑项目┃\\n\ printf(\ ┃┃\\n\

printf(\ ┃ 1 增加城市┃\\n\ printf(\ ┃ 2 删除城市┃\\n\

printf(\ ┗━━━━━━━━━━━━━━━━━┛\\n\ printf(\ 你的选择是：\ scanf(\ system(\ getchar(); if(i==1) EnterVertex(G); if(i==2)

DeleteVertex(G); }

flightedit(ALGraph *G) {int i; char q;

printf(\ ┏━━━━━━━━━━━━━━━━━┓\\n\ printf(\ ┃请选择飞机航班编辑项目┃\\n\ printf(\ ┃┃\\n\

printf(\ ┃ 1 新增航班┃\\n\ printf(\ ┃ 2 删除航班┃\\n\

printf(\ ┗━━━━━━━━━━━━━━━━━┛\\n\ printf(\ 你的选择是：\ scanf(\ system(\ getchar(); if(i==1)

EnterplaneArc(G); if(i==2)

8

全国交通咨询系统 第三章详细设计

DeleteplaneArc(G); }

trainedit(ALGraph *G) {int i; char q;

printf(\ ┏━━━━━━━━━━━━━━━━━┓\\n\printf(\ ┃请选择列车车次编辑项目┃\\n\printf(\ ┃┃\\n\

printf(\ ┃ 1 新增车次┃\\n\printf(\ ┃ 2 删除车次┃\\n\

printf(\ ┗━━━━━━━━━━━━━━━━━┛\\n\ printf(\ 你的选择是：\ scanf(\ system(\ getchar(); if(i==1)

EntertrainArc(G); if(i==2)

DeletetrainArc(G); }

3.2计算最少费用功能模块设计

设计思想：

本系统设计计算最少费用功能模块，是根据图的广度遍历算法来实现整个功能的。并通过键盘输入所要查询的起始地与目的地，并选择交通方式，算出最佳路径，可以以费用为权值计算最少费用。如下图3.2所示：

9

全国交通咨询系统 第三章详细设计

开始 输入起始地 输入目的地 是否为文档中的城市 提示输入错误 选择交通方式 返回上一级菜单 是否存在两地车次 提示不存在车次 显示最佳路径 结束 图3.2 计算最少费用模块流程图

详细功能：

计算最少中转次数、费用功能实现是依据克鲁斯卡尔算法，以费用为权值来得出最佳路径。根据管理员输入的城市信息构建网状结构，以起始地作为第一个连通分量，然后寻找到其他连通分量的最少费用，连通城市并列入队列，连通目的地后，输入队列（即费用最少的路径）。 以下是信息总览模块的主要代码：

TransferDispose(int k,infolist (*arcs)[MAX_VERTEX_NUM],ALGraph G,int v0,int v1)

{int visited[MAX_VERTEX_NUM],v,w,n=1; LinkQueue Q; ArcNode *t;

10

全国交通咨询系统 第三章详细设计

Node *p,*q,*r,*s;

p=(Node *)malloc(G.vexnum*sizeof(Node)); for(v=0;v

InitQueue(&Q); visited[v0]=1;

q=(Node *)malloc(sizeof(Node)); q->adjvex=v0; q->next=NULL; p[v0].next=q; EnterQueue(&Q,v0); while(!IsEmpty(&Q)) {DeleteQueue(&Q,&v); if(k==1)

t=G.vertices[v].trainfirstarc; else

t=G.vertices[v].planefirstarc; while(t!=NULL) {w=t->adjvex; if(!visited[w]) {visited[w]=1; q=&p[w]; s=p[v].next; while(s!=NULL)

{r=(Node *)malloc(sizeof(Node)); r->adjvex=s->adjvex; q->next=r; q=r; s=s->next; }

r=(Node *)malloc(sizeof(Node)); r->adjvex=w;

11

全国交通咨询系统 第三章详细设计

r->next=NULL; q->next=r; if(w==v1) {q=p[w].next; r=q->next;

printf(\旅行路线是:\\n\ while(r!=NULL) {if(k==1)

printf(\乘坐No.%d列车车次在%d:%d从%s到%s\\n\+r->adjvex)).stata[0].number,(*(*(arcs+q->adjvex)+r->adjvex)).stata[0].begintime[0],(*(*(arcs+q->adjvex)+r->adjvex)).stata[0].begintime[1],G.vertices[q->adjvex].cityname,G.vertices[r->adjvex].cityname); else

printf(\乘坐No.%d飞机航班在%d:%d从%s到%s\\n\+r->adjvex)).stata[0].number,(*(*(arcs+q->adjvex)+r->adjvex)).stata[0].begintime[0],(*(*(arcs+q->adjvex)+r->adjvex)).stata[0].begintime[1],G.vertices[q->adjvex].cityname,G.vertices[r->adjvex].cityname); q=r; r=r->next; n++; }

printf(\最少中转次数是%d次\\n\\n\ for(v=0;vnext; free(s); }

p[v].next=NULL; } free(p); return; }

12