交通咨询系统-C语言.doc

CHINA
交通咨询系统

目录
一、 需求分析 2
1、 程序的功能及设计要求 2
2、 输入输出的要求 2
二、环境说明 2
三、详细设计 3
1、模块设计 3
2、画出各函数的调用关系图、主要函数的流程图。 3
2、详细代码 4
四、调试分析 4
1、测试数据： 4
2、借鉴的资料 5
五、课程总结 6
六、附录 6

一、 需求分析
1、 程序的功能及设计要求
在交通网络非常兴旺、交通工具和交通方式不断更新的今天，
人们在出差、旅游或做其他出行时，不仅关心节省交通费用，而且对里程和所需时间等问题也感兴趣。对于这样一个人们关心的问题，通过建立交通网络图的存储构造图，提供用户查询的功能，功能一：通过输入城市名及任意两个城市的距离，查询任意两个城市之间的最短距离，从而到达最省目的；功能二：通过输入城市名以及任意两个程序的距离，查询中转路线最少。程序所具有的功能特色本程序主要目的是为了给用户提供路径咨询，可以通过输入设置，延续程序的拓展性。
设计要求及分析
设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到另一城市顶点之间的中转次数最少问题或最低花费或最少时间〔最短路径〕问题。
该设计共分三个局部:一是建立交通网络图的存储构造；二是解决单源最短路径问题；最后再实现任意两个城市顶点之间的最短路径问题。
1. 建立交通网络图的存储构造
要实现设计要求，首先要定义交通图的存储构造：邻接链表和邻接矩阵；
2. 解决任意两个城市顶点之间的中转次数最少的问题；
3. 解决任意两个城市顶点之间的最短路径〔最低花费或最少时间〕问题。
2、 输入输出的要求
定义变量类型应该保持类型一致，通过键盘输入，确保输入输出一致，使最短路径途径以及最短路径能够简单明了的输出，同时保持程序简洁美观，效果明显。输入要求为输入界面直观、亲切；有利于快速输入；有利于准确输入；有利于输入、修改；方便操作。输出要求：输出要求应简单、直观，一目了然，尽量符合用户的习惯，便于用户阅读、理解与使用。输出内容应尽量汉字化，从而使输出格式醒目；各种输出设计要长考虑以利于系统开展和输出工程扩大、变动的需要；输出操作方便

二、环境说明
系统：WINDOS7
开发软件：vc6+
三、详细设计     
1、模块设计 
交通咨询系统模块图如下 

由模块图可知，该设计共分三个局部:一是建立交通网络图的存储构造；二是解决单源最短路径问题；最后再实现任意两个城市顶点之间的最短路径问题。
开场运行程序，输入命令，进入各种不同的功能区，进展各自的功能，分别运行，然后输出结果。完毕后，如果退出就完毕，不退出重复上面的功能 
2、画出各函数的调用关系图、主要函数的流程图。 
通过Mian主函数 
调用函数void creatDN(lode &g)
调用函数void ShortestPath_DIJ(lode &g,char a[],char b[]) 
调用函数void void TransferDispose(lode &G,char a[],char b[])
主流程图如上图所示

通过void creatDN(lode &g)函数
调用函数 int localvex(lode &g,char *m)

通过void ShortestPath_DIJ(lode &g,char a[],char b[])函数
调用函数 int localvex(lode &g,char *m)
调用函数 void Ppath(lode &g,int P[],int i,int v)

通过void void TransferDispose(lode &G,char a[],char b[])函数
调用函数 InitQueue(LinkQueue &Q)
调用函数 EnQueue(LinkQueue &Q,int e)
调用函数 DeQueue(LinkQueue &Q,int e)
调用函数 int localvex(lode &g,char *m)
2、详细代码
见附录六
四、调试分析 
1、测试数据： 
准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果。 
构建网络图：  

查询中转次数少：

查询最短距离并退出：

2、借鉴的资料
[1]?数据构造C语言版? 严蔚敏、吴伟民，清华大学出版社，2002

五、课程总结 
这次任务分配，从难度上来说，我这个交通咨询系统程序并不复杂，在书本上根本能找到一摸一样的程序，但关键是理解，虽然书上的程序能看懂，但实践设计不比理解，要是练得少，往往捉襟见肘，要学会融会贯穿，那就难上加难了。所以这次就不断演练，不断打击信心，我想还是练少了，酱油打多了，尽管这学期课听的还是很多，但效果还是不好。 
总的来说，这次变成还是学到了一些东西，尽管微乎其微，算法毕竟是死的，人的大脑是活的，只有不断的实验，才能找到信心，也才能学到东西，但还是可以学到很多东西，怎样的思考方法，怎样连接使逻辑构造语句更完善，所以在编程中和调试过程中要成认真分析和蔼于发现问题并及时解决的习惯，不懂的及时问教师或者其他同学。通过本次实验，就要掌握了最短路径问题，并结合图的储存构造、狄克斯特拉算法、广度优先遍历等解决了交通咨询系统的设计。源程序打出来后有多处错误，大小写错误、符号错误、遗漏等等，经反复检查调试后实验成功。
六、附录 
源程序清单〔带注释〕
#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#define INFINITY 65315
int visited[20];
//邻接链表
typedef struct arcnode{
int adjvex; //城市编号
struct arcnode *nextarc;
}arcnode;
typedef struct vnode {
char ctname[20];
arcnode *firstarc;
}adjlist[20]; //城市个数
//邻接邻接表
typedef struct node{
int adjvex; int route;
struct node *next;}node;
typedef struct arccell{
int adj; //两城市之间的距离
}adjmatrix[20][20];
typedef struct{
adjmatrix arcs;
adjlist vexs;

int v,a;//顶点 边数
}lode;
//定义城市在位置
typedef struct QNode{
int data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
int localvex(lode &g,char *m){
int i;

for(i=0;i<g.v;i++){
// printf("%s\n",g.vexs[i].ctname);
if(strcmp(g.vexs[i].ctname,m)==0)
break;}
return i;
}
//创立连接表
void creatDN(lode &g){
int i,j,k,w;
char v1[20],v2[20];
arcnode *p,*s;
printf("输入城市的个点和两城市之间连通的路径条数:\n");
scanf("%d%d",&g.v,&g.a);
for(i=0;i<g.v;i++){
printf("输入第%d个城市的名称:\n",i+1);
scanf("%s",g.vexs[i].ctname);
g.vexs[i].firstarc=0;
getchar();
}
for(i=0;i<g.v;i++)
for(j=0;j<g.v;j++)
g.arcs[i][j].adj=INFINITY;
for(k=0;k<g.a;k++){
printf("输入第%d条城市路径通过的两个城市以及所需的价钱：\n",k+1);
scanf("%s%s%d",&v1,&v2,&w);
i=localvex(g,v1);
// printf("i=%d",i);
j=localvex(g,v2);
// printf("j=%d",j);
g.arcs[i][j].adj=w;
g.arcs[j][i].adj=g.arcs[i][j].adj;
p=(arcnode *)malloc(sizeof(arcnode));
p->adjvex=j;
p->nextarc=g.vexs[i].firstarc;
g.vexs[i].firstarc=p;
s=(arcnode *)malloc(sizeof(arcnode));
s->adjvex=i;
s->nextarc=g.vexs[j].firstarc;
g.vexs[j].firstarc=s;
}

/* for(i=0;i<g.v;i++)
{
for(j=0;j<g.v;j++)
printf(" %d",g.arcs[i][j].adj);}*/
}
/*void printfb(lode &g){
arcnode *p;int i;
printf("%4s%6s%12s\n","编号","顶点","相邻边编号");
for(i=0;i<g.v;i++){
printf("%4d %s",i,g.vexs[i].ctname);
for(p=g.vexs[i].firstarc;p;p=p->nextarc){
printf("%4d",p->adjvex);
printf("\n");}}
/* for(i=0;i<g.v;i++)
{
for(j=0;j<g.v;j++)
printf(" %d",g.arcs[i][j].adj);}*/
void Ppath(lode &g,int P[],int i,int v){
int k;
while(k!=v){
k=P[i];
if(k!=v)
printf("%s,",g.vexs[k].ctname); /*输出顶点k*/
i=k;
}
// Ppath(P,k,v); /*找顶点k的前一个顶点*/
/*找到了起点那么返回*/
return;
}
//最短路径
void ShortestPath_DIJ(lode &g,char a[],char b[]){
int v,w,i,min,v0,x;
int final[20];
int D[20]; //最短路径长度
int P[20];//最短路径的顶点
v0=localvex(g,a);
x=localvex(g,b);
for(v=0;v<g.v;++v){
final[v]=0;
D[v]=g.arcs[v0][v].adj;
if (g.arcs[v0][v].adj<INFINITY) /*路径初始化*/
P[v]=v0;
else
P[v]=-1;
}
D[v0]=0; final[v0]=1;
P[v0]=v0;
//开场循环；
for(i=1;i<g.v;++i){
min=INFINITY;v=-1;
for(w=0;w<g.v;++w)
if(!final[w])
if(D[w]<min)
{ v=w; min=D[w];}//求出V0到W最短距离的
final[v]=1;
for(w=0;w<g.v;++w)
if(!final[w]&&(min+g.arcs[v][w].adj<D[w])&&(g.arcs[v][w].adj<INFINITY)){
D[w]=min+g.arcs[v][w].adj;
P[w]=v;
} }
/* for(v=1;v<g.v;v++){
if(final[v]){
printf("%s到%s的最短路径为",a,g.vexs[v].ctname);
printf("%s,",a);
Ppath(P,v,v0);
printf("%s\n",g.vexs[v].ctname);
printf("%s到%s的最短路径长度为%d\n",a,g.vexs[v].ctname,D[v]);}
else
printf("从%s到%s不存在路径\n",a,g.vexs[v].ctname);
}*/
if(final[x]){
printf("%s到%s用最少的钱通过的城市为:",a,b);
printf("%s,",a);
Ppath(g,P,x,v0);
printf("%s\n",b);
printf("%s到%s的所需最少价钱为:%d\n",a,b,D[x]);}
else
printf("%s不能到达%s!\n",a,b);
}
/*void printf(lode *g){
int i;arcnode *p;
for(i=0;i<g->vexnum;i++){
printf("%d",g->AdjList[i].data);
p=g->AdjList[i].firstarc;
while(p!=0){
printf(" %d",p->adjvex);
p=p->nextarc;
}
printf("\n");
}
}*/
void InitQueue(LinkQueue &Q){
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
Q.front=Q.rear;
Q.front->next=NULL;
}
LinkQueue EnQueue(LinkQueue &Q,int e){
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return Q;
}
int DeQueue(LinkQueue &Q,int e){
QueuePtr p;
if(Q.front!=Q.rear){
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p) Q.rear=Q.front;
}
free(p);
return e;
}
//最少旅行中转次数处理
void TransferDispose(lode &G,char a[],char b[])
{
int v0,v1,v,w,n=1;LinkQueue Q; arcnode *t;
node *p,*q,*r,*s;
p=(node*)malloc(G.v*sizeof(node));
for(v=0;v<G.v;v++)
{visited[v]=0;p[v].next=NULL;}
v0=localvex(G,a);
v1=localvex(G,b);
InitQueue(Q);
visited[v0]=1;
q=(node*)malloc(sizeof(node));
q->adjvex=v0;
q->next=NULL;
p[v0].next=q;
EnQueue(Q,v0);
while(Q.front!=Q.rear)//队列不空
{
v=DeQueue(Q,v);
t=G.vexs[v].firstarc;
while(t!=NULL){
w=t->adjvex;//w为与城市v相连的第一个城市
if(!visited[w])//城市w未访问
{
visited[w]=1;//将城市w设为已访问
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;r->next=NULL;q->next=r;
if(w==v1)//w等于v1
{
q=p[w].next;r=q->next;
printf("\n旅行路线是:\n");
while(r!=NULL){
printf("从%s到%s\n",G.vexs[q->adjvex].ctname,G.vexs[r->adjvex].ctname);
q=r;
r=r->next;n++;}
printf("最少中转次数是%d次\n\n",n-2);
for(v=0;v<G.v;v++)
{
q=p[v].next;
while(q!=NULL)
{s=q;
q=q->next; free(s);}
p[v].next=NULL;}
free(p);
return;}
EnQueue(Q,w);}//将城市w入队
t=t->nextarc;//w等于城市v相连的下一个城市
}}
for(v=0;v<G.v;v++){
q=p[v].next;
while(q!=NULL)
{s=q;
q=q->next;free(s);}
p[v].next=NULL;
}
free(p);
printf("不存在%s到%s的路线",a,b);
}
void main()
{
int c=1,d=1;char a[20],b[20];
lode g;
creatDN(g);
printf("欢送使用！\n");
while(d!=2){
printf("请输入你出发的城市:\n");
scanf("%s",a);
printf("请输入你到达的城市:\n");
scanf("%s",b);
printf("-----请选择你所需要的功能-----:\n");
printf("1:中转次数少的路线\n");
printf("2:两城市之间所需的钱最少\n");
//printf("3:退出系统!\n");
printf("请选择：\n");
getchar();
scanf("%d",&c);
switch(c){
case 1:
TransferDispose(g,a,b);
printf("\n");
break;
case 2:
ShortestPath_DIJ(g,a,b);
break;
}
printf("继续查询吗？\n");
printf("继续请按1\n");
printf("退出请按2\n");
scanf("%d",&d);
if(d==2)
printf("谢谢使用！\n");
}}

【本文档内容可以自由复制内容或自由编辑修改内容期待你的好评和关注，我们将会做得更好】

页脚下载后可删除，如有侵权请告知删除！