模拟一个全国城市间的交通咨询程序数据结构课程设计报告.doc

分类号 编号 华北水利水电学院 North China Institute of Water Conservancy and Hydroelectric Power 课 程 设 计题目:全国交通资讯系统 院 系 信息工程学院 专 业 计算机科学与技术专业 姓 名 指 导 教 师 杨彬 2013年6月28日 目录1.需求分析1问题描述11.1基本要求22概要设计32.1 数据结构32.2 程序模块53.详细设计63.1用到的各种函数63.2函数调用关系图83.3测试与分析84.用户说明书135.总结165.1李明月的总结165.2刘璐璐的总结175.3吕竹青的总结18参考文献：19附录：程序源代码191.需求分析 问题描述设计、模拟一个全国城市间的交通咨询程序，为旅客提供三种最优咨询方案：（1）时间最短；（2）费用最小；（3）中转次数最少。 1.1基本要求1.1.1输入输出的形式和输入值的范围 在程序中输入城市名称时，需输入10个字母以内的字母串；输入列车或飞机编号时需输入一个整型数据；输入列车或飞机的费用时需输入一个实型数据；输入列车或飞机开始时间和到达时间时均需输入两个整型数据（以hh：mm的形式）；在选择功能时，应输入与所选功能对应的一个整型数据。1.1.2 输出形式程序的输出信息主要是：最快需要多少时间才能到达，或最少需要多少旅费才能到达，或最少需要多少次中转到达，并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。 1.1.3程序所能达到的功能程序的功能包括：提供对城市信息的编辑，提供列车时刻表和飞机航班表的编辑，提供三种最优决策：最快到达、最省钱到达、最少中转次数到达，显示编辑的全国交通系统。1.1.4任务分配 在本程序中，我们一共划分了三个模块。管理员模块的初始化数据，城市信息的编辑，以及显示交通系统和整体的界面由李明月完成。航班班次以及列车车次添加删除以及数据结构的初步实现由吕竹青完成。对于最少时间，最少花费以及最少的中转次数这三个函数的实现由刘璐璐进行完成。 2概要设计2.1 数据结构#define MAX_VERTEX_NUM 18/城市节点数#define MAX_ARC_SIZE 100#define MAX_ROUTE_NUM 5/路线数#define False 0#define True 1#define INFINITY 10000struct Vehide int number;/航班号,火车号 float expenditure;/费用 int begintime2;/出发时间 int arrivetime2;/到达时间;/航班、列车信息节点 struct infolist Vehide stataMAX_ROUTE_NUM;/一个出发地到达目的地所对应的航班数或列车车次数 int last;/顺序表所对应的下标，从0开始;/顺序表表示struct ArcNodeint adjvex;/节点下标 ArcNode *nextarc; /节点的下一个指针域 infolist info;/节点的数据域;/邻接表中各个节点信息typedef struct VNode char cityname10;/城市名 ArcNode *planefirstarc,*trainfirstarc;/航班链、列车链 VNode,AdjListMAX_VERTEX_NUM;struct ALGraphAdjList vertices; int vexnum,planearcnum,trainarcnum;/城市数、航班数、列车数;struct Nodeint adjvex; int route; Node *next;/临时建立的一个邻接表，用来求最少中转次数和最少费用struct QNodeint adjvex; struct QNode *next;/链队节点信息struct LinkQueueQNode *front; QNode *rear;/链队信息typedef struct TimeNodeint adjvex; int route; int begintime2; int arrivetime2; struct TimeNode *childMAX_ROUTE_NUM;TimeNode,*TimeTree;struct arcint co; char vt10;/出发地名字 char vh10;/目的地名字 int bt2;/出发时间 int at2;/到达时间 float mo;/费用aMAX_ARC_SIZE;char cityMAX_VERTEX_NUM10;int TTime2;int time2;int time12;int time22;int cMAX_VERTEX_NUM;int dMAX_VERTEX_NUM;2.2 程序模块主要包括管理员编辑模块和用户查询模块以及显示全国交通信息模块。 2.2.1各模块之间的调用关系以及算法设计3.详细设计3.1用到的各种函数void Administer(ALGraph *G); /void CityEdit(ALGraph *G); /城市编辑void CreateCityFile();void CreateGraph(ALGraph *G);void CreatePlaneFile();void CreateTrainFile();int DeleteplaneArc(ALGraph *G);void DeleteQueue(LinkQueue *Q,int *x);int DeletetrainArc(ALGraph *G);void DeleteVertex(ALGraph *G);void DemandDispose(int n,ALGraph G);void EnterplaneArc(ALGraph *G);void EnterQueue(LinkQueue *Q,int x);void EntertrainArc(ALGraph *G);void EnterVertex(ALGraph *G);void ExpenditureDispose(int k,infolist (*arcs)MAX_VERTEX_NUM,ALGraph G,int v0,int v1,float *M,int *final);void flightedit(ALGraph *G);void InitGraph(ALGraph *G);void InitQueue(LinkQueue *Q);int IsEmpty(LinkQueue *Q);int LocateVertex(ALGraph *G,char *v);void MinExpenditure(infolist arcs,float *expenditure,int *route);void PrintGraph(ALGraph *G);int save(ALGraph *G);void trainedit(ALGraph *G);void TransferDispose(int k,infolist (*arcs)MAX_VERTEX_NUM,ALGraph G,int v0,int v1);void CopyTimeTree(TimeTree p,TimeTree q);void DestoryTimeTree(TimeTree p);void MinTime(infolist arcs,int *time,int *route);void VisitTimeTree(TimeTree p);void TimeDispose(int k,infolist (*arcs)MAX_VERTEX_NUM,ALGraph G,int v0,int v1,int (*T)2,int *final);void TimeTreeDispose(Node *head,infolist (*arcs)MAX_VERTEX_NUM);void trainedit(ALGraph *G);void CreateTimeTree(TimeTree p,int i,int j,LinkQueue *Q,infolist (*arcs)MAX_VERTEX_NUM);void UserDemand(ALGraph G);3.2函数调用关系图3.3测试与分析3.3.1测试数据与截图1.管理员操作界面2.对整个结构进行初始化3.对城市，飞机班次，列车车次的编辑对城市的编辑：对航班的编辑：对列车的编辑：1.用户操作界面1.查询最少费用2.查询最短时间3.查询最少的中转次数3.3.2测试分析1.1.1 考虑到道路网多是稀疏网，故采用了邻接表作存储结构，其空间复杂度位O(e)，此时的时间复杂度也为O（e）。构建邻接表的时间复杂度位O(n+e)，输出路径的时间复杂度为O（n2）。由此，本交通资讯系统的时间复杂度位O（n2）。1.1.2 本程序在求最短路径时使用了迪杰斯特拉算法，主要考虑在本程序的初级阶段，并不需要大量的查询，更多会是图信息的添加和修改，重在算法的理解和掌握，因此采用了算法复杂度相对较低的迪杰斯特拉算法。当然，从性能上来说，当交通图基本稳定，而且城市信息基本完善的时候，使用佛洛伊德把所有的最短路径信息存储起来可能会更方便一点，后续的查询的时间复杂度也会相对降低。由此可见，在选用算法时，不能单纯地只考虑算法的时间复杂度，有时还必须综合考虑各种因素。航班时刻表 机 号 出 发 地 到 达 地出发时间到达时间费 用 6320北京上海上海北京16：2018：00 17：2519：05680元2104北京乌鲁木齐乌鲁木齐 北京8：0010：459：5511：401150元201北京西安 西安 北京15：2512：3517：0014：15930元2323西安广州 广州 西安7：1510：159：3511：351320元173拉萨昆明 昆明拉萨10：2012：3511：4514：00830元3304拉萨武汉 武汉拉萨14：1516：2515：4517：55890元82乌鲁木齐昆明 昆明乌鲁木齐 9：3013：0512：1515：501480元4723武汉广州广州武汉 7：0511：258：4513 ：05810元列车时刻表车 次出 发 地 到 达 地出发时间到达时间车 费27北京郑州西安郑州郑州西安郑州北京13：1521：2405：4113：4221：1205：1313：3021：3978元82元82元78元41北京郑州上海郑州郑州上海郑州北京7：1115：2000：3509：4015：0800：1309：2817：3790元100元100元90元59上海广州广州上海08：2003：3903：1622：53182元134兰州北京北京兰州03：5219：2418：5610：28162元323广州昆明昆明广州06：1816：3116：1402：27102元873武汉昆明昆明武汉07：1321：4221：1711：46134元116武汉长沙长沙武汉9：3618：5418：3203：4898元373长沙广州广州长沙13：1500：3500：1511：35116元747兰州武汉武汉兰州17：4115：1314：4712：19210元371兰州乌鲁木齐乌鲁木齐 兰州11：4200：3523：5411：23114元218武汉西安西安武汉18：5001：3411：5118：35178元4.用户说明书1.2 本程序运行在Windows系统下，执行文件为：全国交通资讯系统.exe；1.3 双击运行程序后会显示控制台窗口，如图所示：1.4 输入操作命令“1”，进入管理员操作界面，输入1-5的操作命令可以执行相应的操作，如图所示：1.5 输入“2”操作命令则进入用户查询窗口，如图所示：1.6 输入“3”命令则显示整个交通网络.5.总结5.1李明月的总结在这次的课程设计中，我们抽中了这个全国交通咨询系统，刚看完题目真的感觉无从下手，最后经过我们的讨论以及需求分析，我们这个系统所要用的结构主要是图，我被分到的模块主要是对整个这个交通系统的初始化，以及对城市信息的编辑，也就是对城市的添加和删除，还有对整个系统的界面的操作。虽然看似简单，但是对于我来说实际上很困难，因为我们这个要存储的信息比较复杂，所以不能单纯的每次都要进行由键盘进行输入，进行初始化，那么这就势必要用到文件操作。所以通过这次的时间让我对于文件的操作有了很大的提高。并且城市的信息的编辑也不是那么的简单，当然添加还相对简单一点，但是在做删除的时候真的很困难，要删除这个城市到别的地方的弧，还要删除别的城市到这个城市的航班链以及列车链。 在真的下手去做的时候，我真的遇到了好多问题。首先就是在用文件对系统进行初始化的时候，一开始选错了函数，我选用的是fprintf进行由电脑输入到文件，但是在进行对航班和列车的信息添加的时候就没那么方便了，因为这个函数只能对简单的类型进行操作，于是我改成了fwrite这个函数，经过无数次的尝试，以及上网搜集资料，终于可以成功的把我从键盘输入的信息传入到文件中了。然后开始尝试将自己存入到文件中的数据对建立的图的结构进行初始化，在这一步上我先把文件中存入的信息都依次读入到一个结构体数组中，然后再用这个结构体数组对图的相应的结构以及弧进行赋值，将相关的城市信息，列车信息以及飞机信息都存入到这个整个的结构中。在对城市进行删除的时候，一开始认为只要我把这个节点的相关信息删除掉，就是把这个城市的信息从这个交通网中删除掉了，但是当调试的时候才发现，这样是不对的，如果我只是删除了这个节点的信息，只是把这个城市到其他的地方的航班和列车信息删除了，但是并没有将别的城市到这个城市的一些航班，列车进行删除，怎么做都做不对，吕竹青和我做的功能想类似，经过我们两个的讨论以及搜集资料，最后功夫不负有心人，我们终于成功的把删除这一块给做了出来。当然在最后的调试中我们也遇到了各种各样的问题，因为各人都是分模块写的所以调试的时候有很大的困难，但是经过我们三个人不懈的努力，终于把各自写的模块像融合，这个系统成功的调试出来了，在这两周的课程设计中，我相信我们都收益良多。5.2刘璐璐的总结 开始抽到我们做的题，题目是全国交通咨询系统，主要实现城市以及航班的编辑以及最短时间，最少费用，最少中转次数。我是该小组的负责人，在抽到题目的前两天，我们做了详细的需求分析与分工，我们做的题目中主要用到的是第七章图的知识，实现各种功能的时候，用的算法都是书中的，只是结构很负责，我对第七章的算法比较熟悉，所以主要实现的是最小费用、最短时间、以及最少中转次数。最少时间和最少费用用到的算法是迪杰斯特拉算法。最少中转次数使用的是广度优先遍历。刚开始时我以为只是函数的简单整合，但是在实验过程中，有很多函数的传递参数，在传参的时候出现了很多错误。在实现最少费用的时候权值是费用，但是在最少时间的时候权值是时间，题目的要求中时间是用两个整形进行存储的，要用用两点间的时间作为权值（需经过一些简单的运算，用到达的时间减去刚开始的时间，但是时间不能简单的相减，当小时不够减时和当分钟不够减时，应该进行相关的转化）。通过本次实验，我对网（带权图）的操作有了更深刻的理解。也对数据结构这门课在实际中的应用有了深刻的体会。同时，我也明白了要学好任何一门语言，基础要打牢，只有在坚实的基础上，以后在应用时才可以进行变通。最后，感谢杨老师在这学期的指导。5.3吕竹青的总结 该课程设计我主要负责数据结构的构建，飞机航班的添加、删除，火车车次的添加、删除。（1）、数据结构的设计：首先拿到题目就考虑到，必须有存储航班及车次信息的结构体(struct Vehide),主要包括航班或车次号、费用、出发到达的时间。又考虑到每一个城市也许具有一个或多个航班，又创建了struct infolist 里面包括：与城市相邻的城市之间的航班信息及与该城市相连接的航班数目。然后总的结点为struct ArcNode 里面包括结点的下标，一个结点指针，还有一个infolist 变量。最后是存储城市的信息，struct VNode 里面包括：城市的名称，两个结点指针（航班结点，车次结点）。紧接着创建交通系统图struct ALGraph （以邻接表为存储结构），里面包括：结点数组，城市的个数，航班的个数，列车的个数。Struct arc 用于写入文档。其他的还有临时建立的邻接表的结点结构，链队列结点结构，链队列信息结构，struct LinkQueue 里面包括：指向链对结点类型的两个指针（尾指针，头指针）。（2）、添加航班或车次：存储结构由同组人员完成，邻接表。输入要加入的车次或航班的编号，起始城市，目的城市，费用及出发到达的时间，利用广度遍历遍历邻接表，如果原先起始城市，目的城市无航班到达则直接插入到两则的next位置即可，若有就插入到最后的一个邻接的后面，last(通往该结点的航班的个数)分别加1。（3）、删除航班或车次：重复上面的输入，以广度优先遍历邻接表，找到要删除的航班或车次的下标（即找到了起始城市和目的城市），找到起始城市的那个航班或列车链，遍历到目的城市，从这个位置开始，后边的链结点向前移动一位，被删除的航班被覆盖，释放最后那各结点。经过两周的努力，小组查阅资料，向杨老师咨询，终于把自己的系统完成了，感触最深的是小组协作，虽然我们各自都分了模块，但是完成的过程中我们都是在商量其实现的思想，其中又把数据结构这门课程系统的复习了一下，把整个学期学习的知识汇总了。参考文献：1数据结构C语言版 严蔚敏、吴伟民，清华大学出版社，20022数据结构课程实验 徐孝凯，清华大学出版社， 20023数据结构程序设计题典 李春葆，清华大学出版社，2002附录：程序源代码2int main()/程序功能选择界面ALGraph G; int i; printf(tt*tt);printf(nnnnn); printf( 尊敬的用户，你好！nnn); printf( 欢迎进入全国交通咨询系统.nnn);printf( 在这里我们将为您提供最便捷，最优惠的出行方案.nnn);printf(nnn);printf(tt*tt);printf(n 请您按任意键进入查询系统！nn);system(pause);system(cls);printf(ttttn);printf(tt 1、管理员登陆 ttn);printf(tt 2、用户查询 ttn);printf(tt 3、显示交通系统 ttn);printf(tt 4、退出系统 ttn);printf(ttttn);printf(tt 请输入您要进行的操作：);scanf(%d,&i);getchar();system(cls);while(i!=4) /只要没有退出选择退出系统就可以一直执行下去 switch(i) case 1:Administer(&G);break; case 2:UserDemand(G);break; case 3:PrintGraph(&G);break; printf(ttttn);printf(tt 1、管理员登陆 ttn);printf(tt 2、用户查询 ttn);printf(tt 3、显示交通系统 ttn);printf(tt 4、退出系统 ttn);printf(ttttn);printf(tt 请您正确输入您要进行的操作：);scanf(%d,&i); getchar( );system(cls);return 1;void Administer(ALGraph *G)/管理员管理项目选择界面int i; printf(nnn);printf(tt 尊敬的管理员,请您选择您要进行的操作: ttnn); printf(tt*ttn);printf(tt 1、初始化交通系统; ttn);printf(tt 2、城市信息编辑; ttn);printf(tt 3、航班班次编辑; ttn);printf(tt 4、列车车次编辑; ttn);printf(tt 5、退出管理员登录; ttn);printf(tt*ttn);printf(tt 请您输入您要进行的操作：);scanf(%d,&i); getchar();system(cls); 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(请您按回车键继续：);getchar( ); printf(nnn); printf(nnn); printf(tt*ttn);printf(tt 请选择操作: ttn);printf(tt 1、初始化交通系统; ttn);printf(tt 2、城市信息编辑; ttn);printf(tt 3、航班航班编辑; ttn);printf(tt 4、列车车次编辑; ttn);printf(tt 5、退出管理员登录; ttn);printf(tt*ttn);printf(tt 请您输入您要进行的操作：);scanf(%d,&i); getchar();system(cls);void InitGraph(ALGraph *G) /初始化交通系统int i;system(cls); printf(nnn);printf(nnn);printf(ttttn);printf(tt 1、用键盘输入 ttnn);printf(tt 2、用文件导入 ttn);printf(ttttn);printf(tt 请您输入您要进行的操作：); scanf(%d,&i); getchar();system(cls); switch(i) case 1: CreateCityFile(); CreatePlaneFile(); CreateTrainFile(); CreateGraph(G); break; case 2:CreateGraph(G); break;void CreateCityFile()/创建城市名称文档int i=0; int j; char flag=y; FILE *fp;/定义一个指向文件型数据的指针变量 printf(n请输入城市名称的信息:n); while(flag=y|flag=Y)printf(城市名称:); gets(cityi);/输入一个城市名 i+; printf(继续输入?(Y/N); scanf(%c,&flag); getchar(); printf(n); if(fp=fopen(city.txt,wb)=NULL) printf(无法打开文件!n); return ; for(j=0;ji;j+) fprintf(fp,%10s,cityj);/把用键盘输入的城市名输出到fp所指向的文件中 fclose(fp);/关闭文件void CreatePlaneFile()/创建飞机航班文档int i,count,code,bt2,at2; /code航班编号，bt出发时间，at到达时间 float money;/费用 char vt10,vh10,flag; /vt起始城市，vh目标城市 FILE *fp; flag=y; count=0; while(flag=Y|flag=y) /*flag为标志位,初值为1*/printf(请输入飞机航班的信息:n); /提示输入航班信息 printf(飞机航班编号:); /输入航班code scanf(%d,&code); getchar(); printf(起始城市:); /输入航班的出发城市vt gets(vt); printf(目的城市:); /输入航班的到达城市vh gets(vh); printf(航班费用:); /输入机票价格money scanf(%f,&money); getchar(); printf(起飞时间:); /输入航班的出发时间bt scanf(%d:%d,&bt0,&bt1); getchar(); while(bt0=24|bt1=60)printf(n时间输入有误，请重新输入n); scanf(%d:%d,&bt0,&bt1); getchar(); printf(到达时间:); /输入航班的到达时间at scanf(%d:%d,&at0,&at1); getchar(); while(at0=24|at1=60) printf(n时间输入有误，请重新输入n); scanf(%d:%d,&at0,&at1); getchar(); acount.co=code; / a 为程序头部定义的结构体 strcpy(acount.vt,vt); strcpy(acount.vh,vh); acount.bt0=bt0; acount.bt1=bt1; acount.at0=at0; acount.at1=at1; acount.mo=money; count+; /计数值count+1 printf(继续输入?(Y/N); /提示是否要继续输入航班信息： scanf(%c,&flag); getchar(); printf