数据结构课程设计交通咨询系统.doc

目 录

第1章 概述 1
1.1 性能需求 2
1.2 功能需求 2
第2章 概要设计 3
2.1功能模块设计 3
2.2算法分析与设计 4
第3章 详细设计 5
3.1 管理员功能模块设计 5
3.2计算最少费用功能模块设计 9
第4章 调试分析与测试结果 16
4.1调试分析 16
4.2测试结果 17
第5章 总结 19
参考文献 20
附录 21

65

第1章 概述
数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。因此，主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。
在当今信息时代，信息技术己成为当代知识经济的核心技术。我们时刻都在和数据打交道。比如人们在外出工作时找最短路径，在银行查询存款、通过互联网查新闻、以及远程教育报名等，所有这些都在与数据发生关系。实际上，现实世界中的实体经过抽象以后，就可以成为计算机上所处理的数据。
数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。
学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。通过此次课程设计主要达到以下目的：
1.了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；
2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；
3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；
4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。

1.1 性能需求
在现代，随着高科技的飞速发展，列车、飞机、动车、高铁的出现极大的减少了人们花在旅途上的时间。对于城市间错综复杂交通网的管理，是一项庞大而复杂的工作，况且，受经济危机的影响，也使人们愈发珍惜包里的人民币。在此基础上，如何实现交通网智能化的管理达到帮助乘客选择经济高效的交通工具是目前仍处空白。尤其乘客交通工具的择优选择是一个令人懊恼的工作，一个原因就是各种交通工具的查询十分分散和繁琐。即使有互联网的帮忙，但是没有一个统一的归类、没有一个精细的算法、系统的软件帮助，人们仍然无法获得最优方式。
显然，靠传统的交通信息咨询、管理方式已不能适应时代的发展，同时也很难旅客的需求。今天这种传统的管理方法必然会被以计算机为基础的交通信息总揽、智能咨询所代替。同时这种传统的管理方式反映出很多问题：
第一，当要查询某两个城市之间的全部交通方式要各种查找，很繁琐。
第二，随着周围经济环境的变化，每次查询的票价和线路又会由于各种原因而产生变化，网站更新的不及时或者票价的错误都会造成乘客陷入麻烦。
第三，随着动车、高铁等各种新型交通方式的加入，一个庞大的信息统计如果占用大量人力、物力、存储资源，显然不能适应时代需要。
基于以上情况，开发一个交通择优系统是十分必要的。开发一个交通择优系统，采用计算机对城市间的交通工具进行系统录入和管理，进一步提高了交通部门针对城市间客运网络的管理效率，实现交通运营网络的系统化、规范化和自动化。同时使乘客能通过网络进行称心的交通工具的选择，这也是交通网络优选智能决策的体现。交通信息的咨询和管理是交通部门管理工作中异常重要的一个环节，因此，运用交通资讯管理系统对春运时减轻乘客购票压力、舒缓紧张的城际拥堵有重要意义。
1.2 功能需求
我们设计了一个方便用户查询交通咨询系统，这个系统功能比较强大。该程序所做的工作的是模拟全国交通咨询，为旅客提供三种最优决策的交通咨询。（1）在程序中输入城市名称时，需输入10个字母以内的字母串；输入列车或飞机编号时需输入一个整型数据；输入列车或飞机的费用时需输入一个实型数据；输入列车或飞机开始时间和到达时间时均需输入两个整型数据（以hh：mm的形式）；在选择功能时，应输入与所选功能对应的一个整型数据。（2）程序的输出信息主要是：最快需要多少时间才能到达，或最少需要多少旅费才能到达，或最少需要多少次中转到达，并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。（3）程序的功能包括：提供对城市信息的编辑，提供列车时刻表和飞机航班表的编辑，提供三种最优决策：最快到达、最省钱到达、最少中转次数到达。

第2章 概要设计
2.1功能模块设计

最少中转站

主控模块
系统初始化
城市编辑
飞机航班编辑
显示飞机航班
显示城市
交通咨询管理系统
用户资讯模块
管理员管理模块
交通信息总览模块
最少旅行时间

最少旅行费用

列车车次编辑
显示列车车次

图2.1.1--交通咨询查询系统模块图

交通咨询管理系统通过主控模块进入系统并提示相应功能供用户选择。用户选择后进入到各个功能模块，实现管理员管理、用户咨询、交通信息总览功能，管理员管理时可依据不同对系统信息进行增减，使用户在咨询时得到依据最少旅行时间、旅行费用、最少中转站的购票依据，为用户购票选择提供智能决策。也可通过显示模块对系统中存储的全部信息进行总览和查询。基于此，提供以上功能。

2.2算法分析与设计
1.抽象数据类型的定义如下：
系统用到的抽象数据类型定义：
1．ADT Graph{
数据对象V：一个集合，该集合中的所有元素具有相同的特性
数据关系R：R={VR} VR={<x,y>|P(x,y)^(x,y属于V)}
基本操作：
（1） initgraph(&G)；
（2） CreateGraph(&G)；
（3） EnterVertex(&G)；
（4） DeleteVertex(&G)；
（5） EnterplaneArc(&G)；
（6） DeleteplanArc(&G)；
（7） EntertrainArc(&G)；
（8） DeletetrainArc(&G)；
}ADT Graph
2．ADT LinkQueue{
数据元素：可以是任意类型的数据，但必须属于同一个数据对象
关系：队列中数据元素之间是线性关系。
基本操作：
（1） InitQueue(&Q)；
（2） IsEmpty(&Q)；
（3） EnterQueue(&Q,x)；
（4） DeleteQueue(&Q,&y)；
}ADT LinkQueue

3．ADT TimeTree{
数据对象D：一个集合，该集合中的所有元素具有相同的特性
数据关系R：若D为空，则为空树。若D中仅含有一个数据元素，则R为空集，否则R={H}，H为如下二元关系：
（1） 在D中存在唯一的称为根的数据元素root，它在关系H中没有前驱
（2） 除root以外，D中每个结点在关系H下有且仅有一个前驱。
基本操作：
（1） CreateTimeTree(p,i,j,&Q,infolist arcs)；
（2） CopyTimeTree(p,q)；
（3） VisitTimeTree(p)；
}ADT TimeTree
第3章 详细设计
3.1 管理员功能模块设计
设计思想：
我设计的管理员模块，当我们从键盘输入有关图的顶点及弧的信息后,用显示图的函数验证,DOS中显示的图的信息与从键盘输入的信息相同,表明交通系统可以从键盘正确输入信息。通过管理员模块的操作，我们可以对系统的相关信息进行修改与添加。

以下是管理员模块的流程图：

图3.1.1-- 管理员模块流程图
详细功能：
我们实现建立了有关图的3个文本文件(city.txt,plan.txt,train.txt),在交通系统程序中,选择从文本文件输入图的信息后,用显示操作验证,表明文本文件的内容可以正确调入图的结构体中,说明交通系统可以从文本文件中读取信息。当从键盘或文本文件初始化交通图后,测试增加或删除城市结点,增加或删除航班或列车弧,修改信息完毕后返回上一级菜单。

以下是管理员模块的主要代码：
Administer(ALGraph *G)
{ int i;
printf(" ┏━━━━━━━━━━━━━━━━━┓\n");
printf(" ┃ 请选择管理员管理项目 ┃\n");
printf(" ┃ ┃\n");
printf(" ┃ 1 初始化交通系统 ┃\n");
printf(" ┃ 2 城市编辑 ┃\n");
printf(" ┃ 3 飞机航班编辑 ┃\n");
printf(" ┃ 4 列车车次编辑 ┃\n");
printf(" ┃ 5 返回上一级菜单 ┃\n");
printf(" ┗━━━━━━━━━━━━━━━━━┛\n");
printf(" 你的选择是：");
scanf("%d",&i);
system("cls");
getchar();
while(i!=5)
{switch(i)
{case 1:initgraph(G);
break;
case 2:cityedit(G);
break;
case 3:flightedit(G);
break;
case 4:trainedit(G);
break;
}
printf(" ┏━━━━━━━━━━━━━━━━━┓\n");
printf(" ┃ 请选择管理员管理项目 ┃\n");
printf(" ┃ ┃\n");
printf(" ┃ 1 初始化交通系统 ┃\n");
printf(" ┃ 2 城市编辑 ┃\n");
printf(" ┃ 3 飞机航班编辑 ┃\n");
printf(" ┃ 4 列车车次编辑 ┃\n");
printf(" ┃ 5 返回上一级菜单 ┃\n");
printf(" ┗━━━━━━━━━━━━━━━━━┛\n");
printf(" 你的选择是：");
scanf("%d",&i);
system("cls");
getchar();
}
}
initgraph(ALGraph *G)
{int i;
printf(" ┏━━━━━━━━━━━━━━━┓\n");
printf(" ┃ 请选择初始化方式 ┃\n");
printf(" ┃ 1 键盘 ┃\n");
printf(" ┃ 2 文档 ┃\n");
printf(" ┗━━━━━━━━━━━━━━━┛\n");
printf(" 你的选择是：");
scanf("%d",&i);
system("cls");
getchar();
switch(i)
{case 1:createcityfile();
createplanefile();
createtrainfile();
CreateGraph(G);
break;
case 2:CreateGraph(G);
break;
}
}
cityedit(ALGraph *G)
{int i;
char q;
printf(" ┏━━━━━━━━━━━━━━━━━┓\n");
printf(" ┃ 请选择城市编辑项目 ┃\n");
printf(" ┃ ┃\n");
printf(" ┃ 1 增加城市 ┃\n");
printf(" ┃ 2 删除城市 ┃\n");
printf(" ┗━━━━━━━━━━━━━━━━━┛\n");
printf(" 你的选择是：");
scanf("%d",&i);
system("cls");
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("%d",&i);
system("cls");
getchar();
if(i==1)
EnterplaneArc(G);
if(i==2)
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("%d",&i);
system("cls");
getchar();
if(i==1)
EntertrainArc(G);
if(i==2)
DeletetrainArc(G);
}

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

以下是计算最少费用模块的流程图：

图3.2.1 --计算最少费用模块流程图

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

以下是信息总览模块的主要代码：
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;
Node *p,*q,*r,*s;
p=(Node *)malloc(G.vexnum*sizeof(Node));
for(v=0;v<G.vexnum;v++)
{visited[v]=0;
p[v].next=NULL;
}
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;
r->next=NULL;
q->next=r;
if(w==v1)
{q=p[w].next;
r=q->next;
printf("\n旅行路线是:\n");
while(r!=NULL)
{if(k==1)
printf("乘坐No.%d列车车次在%d:%d从%s到%s\n",(*(*(arcs+q->adjvex)+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",(*(*(arcs+q->adjvex)+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",n-2);
for(v=0;v<G.vexnum;v++)
{q=p[v].next;
while(q!=NULL)
{s=q;
q=q->next;
free(s);
}
p[v].next=NULL;
}
free(p);
return;
}
EnterQueue(&Q,w);
}
t=t->nextarc;
}
}
for(v=0;v<G.vexnum;v++)
{q=p[v].next;
while(q!=NULL)
{s=q;
q=q->next;
free(s);
}
p[v].next=NULL;
}
free(p);
if(k==1)
printf("\n不存在列车车次从%s到%s\n\n",G.vertices[v0].cityname,G.vertices[v1].cityname);
else
printf("\n不存在飞机航班从%s到%s\n\n",G.vertices[v0].cityname,G.vertices[v1].cityname);
}
MinExpenditure(infolist arcs,float *expenditure,int *route)
{int i;
*expenditure=arcs.stata[0].expenditure;
if(*expenditure<INFINITY)
*route=0;
else
*route=-1;
for(i=1;i<=arcs.last;i++)
if(arcs.stata[i].expenditure<*expenditure)
{*expenditure=arcs.stata[i].expenditure;
*route=i;
}}
ExpenditureDispose(int k,infolist (*arcs)[MAX_VERTEX_NUM],ALGraph G,int v0,int v1,float *M,int *final)
{int v=-1,w,i,route;
float m,expenditure;
Node *p,*q,*r,*s;
p=(Node *)malloc(G.vexnum*sizeof(Node));
for(v=0;v<G.vexnum;v++)
{*(final+v)=False;
MinExpenditure(*(*(arcs+v0)+v),M+v,&route);
p[v].next=NULL;
if(*(M+v)<INFINITY)
{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;
}
}
*(M+v0)=0;
*(final+v0)=True;
for(i=1;i<G.vexnum;i++)
{m=INFINITY;
v=-1;
for(w=0;w<G.vexnum;w++)
if(*(final+w)==False)
if(*(M+w)<m)
{v=w;
m=*(M+w);
}
if(v==v1)
{q=p[v].next;
r=q->next;
printf("\n旅行路线是:\n");
while(r!=NULL)
{if(k==1)
printf("乘坐No.%d列车车次在%d:%d从%s到%s\n",(*(*(arcs+q->adjvex)+r->adjvex)).stata[r->route].number,(*(*(arcs+q->adjvex)+r->adjvex)).stata[r->route].begintime[0],(*(*(arcs+q->adjvex)+r->adjvex)).stata[r->route].begintime[1],G.vertices[q->adjvex].cityname,G.vertices[r->adjvex].cityname);
else
printf("乘坐No.%d飞机航班在%d:%d从%s到%s\n",(*(*(arcs+q->adjvex)+r->adjvex)).stata[r->route].number,(*(*(arcs+q->adjvex)+r->adjvex)).stata[r->route].begintime[0],(*(*(arcs+q->adjvex)+r->adjvex)).stata[r->route].begintime[1],G.vertices[q->adjvex].cityname,G.vertices[r->adjvex].cityname);
q=r;
r=r->next;
}
printf("最少旅行费用是%f元\n\n",m);
for(v=0;v<G.vexnum;v++)
{q=p[v].next;
while(q!=NULL)
{s=q;
q=q->next;
free(s);
}
p[v].next=NULL;
}
free(p);
return;
}
else if(v!=-1)
{*(final+v)=True;
for(w=0;w<G.vexnum;w++)
if(*(final+w)==False&&(*(*(arcs+v)+w)).last>-1)
{MinExpenditure(*(*(arcs+v)+w),&expenditure,&route);
if(*(M+w)>m+expenditure)
{*(M+w)=m+expenditure;
q=p[w].next;
while(q!=NULL)
{s=q;
q=q->next;
free(s);
}
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;
}}}}
for(v=0;v<G.vexnum;v++)
{q=p[v].next;
while(q!=NULL)
{s=q;
q=q->next;
free(s);
}
p[v].next=NULL;
}
free(p);
if(k==1)
printf("\n不存在列车车次从%s到%s\n\n",G.vertices[v0].cityname,G.vertices[v1].cityname);
else
printf("\n不存在飞机航班从%s到%s\n\n",G.vertices[v0].cityname,G.vertices[v1].cityname);}

第4章 调试分析与测试结果
4.1调试分析

图4.1.1—— 错误提示

如图4.1.1，这是我们在测试中发现的一些警告，因为在程序中创建了两个图，在定义函数时没有给函数返回值，所以程序中导致一些运行的问题。经过对函数的完善之后，相应的问题得以解决。
测试程序时，也曾出现一些调用系统函数发生错误的情况，工程中没有包含"stdlib.h"头文件，之后错误也得以解决。

4.2测试结果

图4.2.1—— 主菜单

如图4.2.1，这是程序运行成功之后的主菜单。

图4.2.2—— 管理员菜单

如图4.2.2,这是程序运行成功后的管理员界面。

图4.2.3—— 用户咨询结果

如图4.2.3，这是用户咨询昆明至北京最少用费的结果，交通方式为列车，由于昆明至北京没有直达列车，系统自动列出最佳路径。

图4.2.4—— 显示界面的航班显示结果

如图4.2.4，此图为显示界面下显示所有航班的显示结果。

第5章 总结
1.遇到的问题：
主要遇到了怎样储存和读取哈夫曼树的问题，知道了应该灵活解决问题，如在建哈夫曼树时要由叶子结点向根结点的次序，而在读取时应由根结点向叶子结点的次序。文件流问题：无法读指定的文件。解决，先判断文件能否打开，若能打开，则继续操作，还要判断是否是全文结束。
2.总结：
这次实验难度很高，有许多复杂的函数和文件流问题。遇到了许多问题，在哈夫曼树的建立存储和读取方面可以参照书独立完成，但文件流方面难度较高，涉及到许多特定语句和形式，如if(!encoding.eof())，ofstream coding("CodeFile.txt");等，由于以前不经常使用，接触不多，所以使用比较困难，通过向他人请教和参考以有的例子得以解决。
通过此次实验更加巩固了树、二叉树的用法，深入理解了树和二叉树在计算机中的存储和读取方式，也增强了自学能力，并且对文件流方面的知识有更深一步的运用和了解，虽然还不能灵活的应用，但已经起到了抛砖引玉的作用。同时也更加意识到，每一次编程都是对自己学习能力和耐力的挑战，督促我去了解更有用的东西，得到进一步的提高。

参考文献
[1] 刘晓华．SQL Server2000数据库应用开发．北京：电子工业出版社，2001.6
[2] (美)微软公司著，王黎，袁永康译．Microsoft．NET 战略．北京：清华大学出版社，2002.1
[4] 谭浩强.C程序设计第二版.北京：清华大学出版社，2003
[5]任哲等.MFC Windows程序设计.北京:清华大学出版社,2004
[6]唐克.MFC程序设计.北京:北京希望电子出版社,2002
[7]严蔚敏,吴伟民.数据结构(C语言版).北京:清华大学出版社,1997
[8]求是科技.Visual C++ 6.0信息管理系统开发.北京:人民邮电出版社,2005
[9]朱晴婷,黄海鹰,陈莲君.VC++程序设计.北京:清华大学出版社,1998

附录
源程序代码：

#include"stdio.h"
#include"stdlib.h"
#include"string.h"
#include"fstream.h"
#include"iomanip.h"
#define MAX_VERTEX_NUM 18
#define NULL 0
#define MAX_ARC_SIZE 100
#define MAX_ROUTE_NUM 5
#define False 0
#define True 1
#define INFINITY 10000
typedef struct
{int number;
float expenditure;
int begintime[2];
int arrivetime[2];
}Vehide;
typedef struct
{Vehide stata[MAX_ROUTE_NUM];
int last;
}infolist;