数据结构课程设计全国交通咨询系统gerr.docx

郑州工业业应用技技术学院院课程设计计任务书书题目全国国交通资资询系统主要内容容：设计了一一个方便便用户查查询交通通咨询系系统。该该系统所所做的工工作的是是模拟全全国交通通咨询，为为旅客提提供三种种最优决决策的交交通咨询询。该系系统可以以进行城城市，列列车车次次和飞机机航班的的编辑的的基本信信息输入入操作。程序的输出信息主要是：最快需要多少时间才能到达，或最少需要多少旅费才能到达，或最少需要多少次中转到达，并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。程序的功能包括：提供对城市信息的编辑，提供列车时刻表和飞机航班表的编辑，提供三种最优决策：最快到达、最省钱到达、最少中转次数到达。基本要求求：1、掌握握C语言言的变量量及函数数的灵活活使用；2、熟练练掌握图图的深度度、广度度优先遍遍历算法法思想及及其程序序实现；3、掌握握C语言言中文件件的基本本操作；4、掌握握VC+6.0软件件的熟练练使用。主要参考考资料：1 李春葆葆.数据据结构程程序设计计M.北京京:清华华大学出出版社,20002,0032 王黎,袁永康康.Miicroosofft.NNET战战略MM.北北京:清清华大学学出版社社,20002,0013 谭浩强强.C程程序设计计第二版版M.北京京:清华华大学出出版社,20003,034 任哲.MMFC Winndowws程序序设计M.北京:清华大大学出版版社,20004,06  完完 成成 期期 限限：20016.12.05220177.011.055 指指导教师师签名： 课课程负责责人签名名：摘要随着高科科技的飞飞速发展展，列车车、飞机机、动车车、高铁铁的出现现极大的的减少了了人们花花在旅途途上的时时间。对对于城市市间错综综复杂交交通网的的管理，是是一项庞庞大而复复杂的工工作。在在此基础础上，如如何实现现交通网网智能化化的管理理达到帮帮助乘客客选择经经济高效效的交通通工具是是目前仍仍处空白白。尤其其乘客交交通工具具的择优优选择是是一个令令人懊恼恼的工作作，一个个原因就就是各种种交通工工具的查查询十分分分散和和繁琐。即即使有互互联网的的帮忙，但但是没有有一个统统一的归归类、没没有一个个精细的的算法、系系统的软软件帮助助，人们们仍然无无法获得得最优方方式。为为此开发发一个交交通择优优系统是是十分必必要的。采采用计算算机对城城市间的的交通工工具进行行系统录录入和管管理，进进一步提提高了交交通部门门针对城城市间客客运网络络的管理理效率，实实现交通通运营网网络的系系统化、规规范化和和自动化化。同时时使乘客客能通过过网络进进行称心心的交通通工具的的选择，这这也是交交通网络络优选智智能决策策的体现现。交通通信息的的咨询和和管理是是交通部部门管理理工作中中异常重重要的一一个环节节，因此此，运用用交通资资询管理理系统对对春运时时减轻乘乘客购票票压力、舒舒缓紧张张的城际际拥堵有有重要意意义。关键字：错综复复杂；智能化化；最优方方式；择优系系统目录摘要I目录III第一章概概述11.1 性能能需求111.2 功能能需求22第二章概概要设计计32.1 功能能模块设设计32.2 算法法分析与与设计33第三章详详细设计计53.1 管理理员功能能模块设设计53.2 计算算最少费费用功能能模块设设计93.3 测试试与分析析17第四章全全国交通通咨询系系统的运运行2004.1 程序序主界面面204.2 管理理员登录录主界面面204.3 用户户界面登登录界面面234.4 显示示交通系系统界面面26结束语229参考文献献30附录311全国交通咨询系统第一章 概述第一章概概述数据结构构作为一一门学科科主要研研究数据据的各种种逻辑结结构和存存储结构构，以及及对数据据的各种种操作。因因此，主主要有三三个方面面的内容容：数据据的逻辑辑结构；数据的的物理存存储结构构；对数数据的操操作（或或算法）。通通常，算算法的设设计取决决于数据据的逻辑辑结构，算算法的实实现取决决于数据据的物理理存储结结构。数数据结构构是信息息的一种种组织方方式，其其目的是是为了提提高算法法的效率率，它通通常与一一组算法法的集合合相对应应，通过过这组算算法集合合可以对对数据结结构中的的数据进进行某种种操作。 在当今今信息时时代，信信息技术术己成为为当代知知识经济济的核心心技术。我我们时刻刻都在和和数据打打交道。比比如人们们在外出出工作时时找最短短路径，在在银行查查询存款款、通过过互联网网查新闻闻、以及及远程教教育报名名等，所所有这些些都在与与数据发发生关系系。实际际上，现现实世界界中的实实体经过过抽象以以后，就就可以成成为计算算机上所所处理的的数据。 数据结结构课程程主要是是研究非非数值计计算的程程序设计计问题中中所出现现的计算算机操作作对象以以及它们们之间的的关系和和操作的的学科。数数据结构构是介于于数学、计计算机软软件和计计算机硬硬件之间间的一门门计算机机专业的的核心课课程，它它是计算算机程序序设计、数数据库、操操作系统统、编译译原理及及人工智智能等的的重要基基础，广广泛的应应用于信信息学、系系统工程程等各种种领域。 学习数数据结构构是为了了将实际际问题中中所涉及及的对象象在计算算机中表表示出来来并对它它们进行行处理。通通过课程程设计可可以提高高学生的的思维能能力，促促进学生生的综合合应用能能力和专专业素质质的提高高。通过过此次课课程设计计主要达达到以下下目的：1、了解解并掌握握数据结结构与算算法的设设计方法法，具备备初步的的独立分分析和设设计能力力；2、初步步掌握软软件开发发过程的的问题分分析、系系统设计计、程序序编码、测测试等基基本方法法和技能能；3、提高高综合运运用所学学的理论论知识和和方法独独立分析析和解决决问题的的能力；4、训练练用系统统的观点点和软件件开发一一般规范范进行软软件开发发，培养养软件工工作者所所应具备备的科学学的工作作方法和和作风。1.1性性能需求求在现代，随随着高科科技的飞飞速发展展，列车车、飞机机、动车车、高铁铁的出现现极大的的减少了了人们花花在旅途途上的时时间。对对于城市市间错综综复杂交交通网的的管理，是是一项庞庞大而复复杂的工工作，况况且，受受经济危危机的影影响，也也使人们们愈发珍珍惜包里里的人民民币。在在此基础础上，如如何实现现交通网网智能化化的管理理达到帮帮助乘客客选择经经济高效效的交通通工具是是目前仍仍处空白白。尤其其乘客交交通工具具的择优优选择是是一个令令人懊恼恼的工作作，一个个原因就就是各种种交通工工具的查查询十分分分散和和繁琐。即即使有互互联网的的帮忙，但但是没有有一个统统一的归归类、没没有一个个精细的的算法、系系统的软软件帮助助，人们们仍然无无法获得得最优方方式。显然，靠靠传统的的交通信信息咨询询、管理理方式已已不能适适应时代代的发展展，同时时也很难难旅客的的需求。今今天这种种传统的的管理方方法必然然会被以以计算机机为基础础的交通通信息总总揽、智智能咨询询所代替替。同时时这种传传统的管管理方式式反映出出很多问问题：第一，当当要查询询某两个个城市之之间的全全部交通通方式要要各种查查找，很很繁琐；第二，随随着周围围经济环环境的变变化，每每次查询询的票价价和线路路又会由由于各种种原因而而产生变变化，网网站更新新的不及及时或者者票价的的错误都都会造成成乘客陷陷入麻烦烦；第三，随随着动车车、高铁铁等各种种新型交交通方式式的加入入，一个个庞大的的信息统统计如果果占用大大量人力力、物力力、存储储资源，显显然不能能适应时时代需要要。基于以上上情况，开开发一个个交通择择优系统统是十分分必要的的。开发发一个交交通择优优系统，采采用计算算机对城城市间的的交通工工具进行行系统录录入和管管理，进进一步提提高了交交通部门门针对城城市间客客运网络络的管理理效率，实实现交通通运营网网络的系系统化、规规范化和和自动化化。同时时使乘客客能通过过网络进进行称心心的交通通工具的的选择，这这也是交交通网络络优选智智能决策策的体现现。交通通信息的的咨询和和管理是是交通部部门管理理工作中中异常重重要的一一个环节节，因此此，运用用交通资资询管理系系统对春春运时减减轻乘客客购票压压力、舒舒缓紧张张的城际际拥堵有有重要意意义。1.2 功能需需求设计了一一个方便便用户查查询交通通咨询系系统，这这个系统统功能比比较强大大。该程程序所做做的工作作的是模模拟全国国交通咨咨询，为为旅客提提供三种种最优决决策的交交通咨询询。1、在程程序中输输入城市市名称时时，需输输入100个字母母以内的的字母串串；输入入列车或或飞机编编号时需需输入一一个整型型数据；输入列列车或飞飞机的费费用时需需输入一一个实型型数据；输入列列车或飞飞机开始始时间和和到达时时间时均均需输入入两个整整型数据据（以hhh：mmm的形形式）；在选择择功能时时，应输输入与所所选功能能对应的的一个整整型数据据；2、程序序的输出出信息主主要是：最快需需要多少少时间才才能到达达，或最最少需要要多少旅旅费才能能到达，或或最少需需要多少少次中转转到达，并并详细说说明依次次于何时时乘坐哪哪一趟列列车或哪哪一次班班机到何何地；3、程序序的功能能包括：提供对对城市信信息的编编辑，提提供列车车时刻表表和飞机机航班表表的编辑辑，提供供三种最最优决策策：最快快到达、最最省钱到到达、最最少中转转次数到到达。130全国交通咨询系统第二章 概要设计第二章概概要设计计2.1 功能模模块设计计交通咨询询管理系系统通过过主控模模块进入入系统并并提示相相应功能能供用户户选择。用用户选择择后进入入到各个个功能模模块，实实现管理理员管理理、用户户咨询、交交通信息息总览功功能，管管理员管管理时可可依据不不同对系系统信息息进行增增减，使使用户在在咨询时时得到依依据最少少旅行时时间、旅旅行费用用、最少少中转站站的购票票依据，为为用户购购票选择择提供智智能决策策。也可可通过显显示模块块对系统统中存储储的全部部信息进进行总览览和查询询。基于于此，提提供以上上功能。如如下图22.1所所示： 最少中转站 主控模块系统初始化城市编辑飞机航班编辑显示飞机航班显示城市交通咨询管理系统用户资询模块管理员管理模块交通信息总览模块最少旅行时间最少旅行费用列车车次编辑显示列车车次图2.11 交通通咨询查查询系统统模块图图2.2算算法分析析与设计计系统用到到的抽象象数据类类型定义义：1ADDT GGrapph数据对象象V：一个个集合，该该集合中中的所有有元素具具有相同同的特性性数据关系系R：R=VR VR=<xx,y>>|P(x,yy)(x,yy属于V)基本操作作：（1）iinittgraaph(&G)；（2）CCreaateGGrapph(&&G)；（3）EEnteerVeerteex(&&G)；（4）DDeleeteVVerttex(&G)；（5）EEnteerpllaneeArcc(&GG)；（6）DDeleetepplannArcc(&GG)；（7）EEnteertrrainnArcc(&GG)；（8）DDeleetettraiinArrc(&&G)；ADTT Grraphh2ADDT LLinkkQueeue数据元素素：可以以是任意意类型的的数据，但但必须属属于同一一个数据据对象关系：队队列中数数据元素素之间是是线性关关系。基本操作作：（1）IInittQueeue(&Q)；（2）IIsEmmptyy(&QQ)；（3）EEnteerQuueuee(&QQ,x)；（4）DDeleeteQQueuue(&&Q,&&y)； AADT LinnkQuueuee3ADDT TTimeeTreee数据对象象D：一个个集合，该该集合中中的所有有元素具具有相同同的特性性数据关系系R：若D为空，则则为空树树。若DD中仅含含有一个个数据元元素，则则R为空集集，否则则R=H，H为如下下二元关关系：（1）在在D中存在在唯一的的称为根根的数据据元素rroott，它在在关系HH中没有有前驱；（2）除除rooot以外外，D中每个个结点在在关系HH下有且且仅有一一个前驱驱；（3）CCreaateTTimeeTreee(pp,i,j,&&Q,iinfoolisst aarcss)；（4）CCopyyTimmeTrree(p,qq)；（5）VVisiitTiimeTTreee(p)；ADTT TiimeTTreee全国交通咨询系统第三章 详细设计第三章详详细设计计3.1管管理员功功能模块块设计设计思想想：本系统的的管理员员模块，当当我们从从键盘输输入有关关图的顶顶点及弧弧的信息息后,用用显示图图的函数数验证,DOSS中显示示的图的的信息与与从键盘盘输入的的信息相相同,表表明交通通系统可可以从键键盘正确确输入信信息。通通过管理理员模块块的操作作，我们们可以对对系统的的相关信信息进行行修改与与添加。如下图3.1所示：开始进入管理员界面是否进行初始化进入主菜单选择编辑项目进入编辑子菜单是否增加城市，航班或车次是否删除信息删除信息输入添加信息返回上一级菜单结束图3.11 管管理员模模块流程程图详细功能能：本系统实实现并建立了了有关图图的3个个文本文文件(ccityy.txxt,pplann.txxt,ttraiin.ttxt),在交交通系统统程序中中,选择择从文本本文件输输入图的的信息后后,用显显示操作作验证,表明文文本文件件的内容容可以正正确调入入图的结结构体中中,说明明交通系系统可以以从文本本文件中中读取信信息。当当从键盘盘或文本本文件初初始化交交通图后后,测试试增加或或删除城城市结点点,增加加或删除除航班或或列车弧弧,修改改信息完完毕后返返回上一一级菜单单。以下下是管理理员模块块的主要要代码：Admiinissterr(ALLGraaph *G) innt ii; prrinttf("" n""); prrinttf("" 请选择择管理员员管理项项目n""); prrinttf("" n""); prrinttf("" 1 初初始化交交通系统统n""); prrinttf("" 2 城城市编辑辑n""); prrinttf("" 3 飞飞机航班班编辑n""); prrinttf("" 4 列列车车次次编辑n""); prrinttf("" 5 返返回上一一级菜单单n""); prrinttf("" n""); prrinttf("" 你的的选择是是："); scaanf("%dd",&&i); sysstemm("ccls""); gettchaar(); whiile(i!=5) swwitcch(ii) ccasee 1:iniitgrraphh(G); breeak; ccasee 2:cittyeddit(G); breeak; ccasee 3:fliighttediit(GG); breeak; ccasee 4:traaineeditt(G); breeak; prinntf(" nn");prinntf(" 请选择择管理员员管理项项目n"");prinntf(" n"");prinntf(" 1 初初始化交交通系统统n"");prinntf(" 2 城城市编辑辑n"");prinntf(" 3 飞飞机航班班编辑n"");prinntf(" 4 列列车车次次编辑n"");prinntf(" 5 返返回上一一级菜单单n"");prinntf(" nn"); pprinntf(" 你的选选择是："); sscannf(""%d"",&ii); ssysttem("clls"); ggetccharr(); inittgraaph(ALGGrapph *G)intt i; priintff(" n""); priintff(" 请选择择初始化化方式n""); priintff(" 11 键盘盘n""); priintff(" 22 文档档n""); priintff(" n""); priintff(" 你的选选择是："); sscannf(""%d"",&ii); ssysttem("clls"); gettchaar(); swiitchh(i) caase 1:ccreaateccityyfille(); ccreaatepplannefiile(); ccreaatettraiinfiile(); CCreaateGGrapph(GG); bbreaak; caase 2:CCreaateGGrapph(GG); bbreaak; cityyediit(AALGrraphh *GG)intt i; chaar qq; priintff(" n"); priintff(" 请选择择城市编编辑项目目n""); priintff(" n""); priintff(" 1 增增加城市市n""); priintff(" 2 删删除城市市n""); priintff(" n"); priintff(" 你的选选择是："); scaanf("%dd",&&i); sysstemm("ccls""); gettchaar(); if(i=1) EnnterrVerrtexx(G); if(i=2) DeeletteVeerteex(GG);fligghteeditt(ALLGraaph *G)intt i; chaar qq; prrinttf("" n""); prrinttf("" 请选择择飞机航航班编辑辑项目n""); prrinttf("" n""); prrinttf("" 1 新新增航班班n""); prrinttf("" 2 删删除航班班n""); prrinttf("" n""); prrinttf("" 你的的选择是是："); scaanf("%dd",&&i); sysstemm("ccls""); gettchaar(); if(i=1) EnnterrplaaneAArc(G); if(i=2) DeelettepllaneeArcc(G);traiineddit(ALGGrapph *G)intt i; chaar qq;prinntf(" nn");prinntf(" 请选择择列车车车次编辑辑项目n"");prinntf(" n"");prinntf(" 1 新新增车次次n"");prinntf(" 2 删删除车次次n"");prinntf(" nn"); priintff(" 你的选选择是："); scaanf("%dd",&&i); sysstemm("ccls""); gettchaar(); if(i=1) EnnterrtraainAArc(G); if(i=2) DeelettetrrainnArcc(G);3.2计计算最少少费用功功能模块块设计设计思想想：本系统设设计计算算最少费费用功能能模块，是是根据图图的广度度遍历算算法来实实现整个个功能的的。并通通过键盘盘输入所所要查询询的起始始地与目目的地，并并选择交交通方式式，算出出最佳路路径，可可以以费费用为权权值计算算最少费费用。如如下图33.2所所示：开始输入起始地输入目的地是否为文档中的城市提示输入错误选择交通方式返回上一级菜单是否存在两地车次提示不存在车次显示最佳路径结束图3.22 计算算最少费费用模块块流程图图详细功能能：计算最少少中转次次数、费费用功能能实现是是依据克克鲁斯卡卡尔算法法，以费费用为权权值来得得出最佳佳路径。根根据管理理员输入入的城市市信息构构建网状状结构，以以起始地地作为第第一个连连通分量量，然后后寻找到到其他连连通分量量的最少少费用，连连通城市市并列入入队列，连连通目的的地后，输输入队列列（即费费用最少少的路径径）。以下是信信息总览览模块的的主要代代码：TrannsfeerDiispoose(intt k,inffoliist (*aarcss)MMAX_VERRTEXX_NUUM,ALGGrapph GG,innt vv0,iint v1)intt viisittedMAXX_VEERTEEX_NNUM,v,w,nn=1; LinnkQuueuee Q; ArccNodde *t; Nodde *p,*q,*r,*s; p=(Nodde *)maallooc(GG.veexnuum*ssizeeof(Nodde); forr(v=0;vv<G.vexxnumm;v+) viisittedv=0; pv.nexxt=NNULLL; IniitQuueuee(&QQ); vissiteedvv0=1; q=(Nodde *)maallooc(ssizeeof(Nodde); q->>adjjvexx=v00; q->>nexxt=NNULLL; pvv0.nexxt=qq; EntterQQueuue(&&Q,vv0); whiile(!IssEmppty(&Q) DeeletteQuueuee(&QQ,&vv); iff(k=1) tt=G.verrticcesv.traainffirsstarrc; ellse tt=G.verrticcesv.plaaneffirsstarrc; whhilee(t!=NUULL) ww=t->addjveex; iif(!vissiteedww) vissiteedww=11; q=&&pww; s=ppv.neext; whiile(s!=NULLL) r=(Noode *)mmallloc(sizzeoff(Noode); r->addjveex=ss->aadjvvex; q->neext=r; q=r; s=s->>nexxt; r=(Nodde *)maallooc(ssizeeof(Nodde); r->>adjjvexx=w; r->>nexxt=NNULLL; q->>nexxt=rr; if(w=v1) q=pww.nnextt; r=q->>nexxt; prrinttf(""n旅旅行路线线是:n"); whhilee(r!=NUULL) iif(kk=11) priintff("乘乘坐Noo.%dd列车车车次在%d:%d从%s到%sn",(*(*(aarcss+q->addjveex)+r->>adjjvexx).staata0.nummberr,(*(*(arccs+qq->aadjvvex)+r->addjveex).sttataa0.beeginntimme00,(*(*(arrcs+q->>adjjvexx)+rr->aadjvvex).sstatta00.bbegiintiime1,G.vvertticeesqq->aadjvvex.ciitynnamee,G.verrticcesr->>adjjvexx.ccityynamme); eelsee priintff("乘乘坐Noo.%dd飞机航航班在%d:%d从%s到%sn",(*(*(aarcss+q->addjveex)+r->>adjjvexx).staata0.nummberr,(*(*(arccs+qq->aadjvvex)+r->addjveex).sttataa0.beeginntimme00,(*(*(arrcs+q->>adjjvexx)+rr->aadjvvex).sstatta00.bbegiintiime1,G.vvertticeesqq->aadjvvex.ciitynnamee,G.verrticcesr->>adjjvexx.ccityynamme); qq=r; rr=r->neext; nn+; prrinttf(""最少中中转次数数是%dd次nn",n-22); foor(vv=0;v<GG.veexnuum;vv+) qq=pv.nexxt; wwhille(qq!=NNULLL) s=qq; q=qq->nnextt; freee(ss); ppv.neext=NULLL; frree(p); reeturrn; EntterQQueuue(&&Q,ww); tt=t->neextaarc; forr(v=0;vv<G.vexxnumm;v+) q=pvv.nnextt; whhilee(q!=NUULL) ss=q; qq=q->neext; ffreee(s); pv.nexxt=NNULLL; freee(pp); if(k=1) prrinttf(""n不不存在列列车车次次从%ss到%snnn",GG.veertiicessv00.ccityynamme,G.veertiicessv11.ccityynamme); elsse prrinttf(""n不不存在飞飞机航班班从%ss到%snnn",GG.veertiicessv00.ccityynamme,G.veertiicessv11.ccityynamme);MinEExpeendiiturre(iinfoolisst aarcss,flloatt *eexpeendiiturre,iint *rooutee)intt i; *exxpennditturee=arrcs.staata0.exppenddituure; if(*exxpennditturee<INNFINNITYY) *rroutte=00; elsse *rroutte=-1; forr(i=1;ii<=aarcss.laast;i+) iff(arrcs.staatai.exppenddituure<<*exxpennditturee) *exppenddituure=arccs.sstattaii.eexpeendiiturre; *rouute=i; ExpeendiiturreDiispoose(intt k,inffoliist (*aarcss)MMAX_VERRTEXX_NUUM,ALGGrapph GG,innt vv0,iint v1,flooat *M,intt *ffinaal)intt v=-1,w,ii,rooutee; flooat m,eexpeendiiturre; Nodde *p,*q,*r,*s; p=(Nodde *)maallooc(GG.veexnuum*ssizeeof(Nodde); forr(v=0;vv<G.vexxnumm;v+) *(finnal+v)=Fallse; MiinExxpennditturee(*(*(aarcss+v00)+vv),MM+v,&rooutee); pv.nexxt=NNULLL; iff(*(M+vv)<IINFIINITTY) qq=(NNodee *)malllocc(siizeoof(NNodee); ss=(NNodee *)malllocc(siizeoof(NNodee); qq->aadjvvex=v0; ss->aadjvvex=v; ss->rroutte=rroutte; ppv.neext=q; qq->nnextt=s; ss->nnextt=NUULL; *(MM+v00)=00; *(ffinaal+vv0)=Truue; forr(i=1;ii<G.vexxnumm;i+) m=INFFINIITY; v=-1; foor(ww=0;w<GG.veexnuum;ww+) iif(*(fiinall+w)=FFalsse) if(*(MM+w)<m) v=w; m=*(MM+w); iff(v=v11) qq=pv.nexxt; rr=q->neext; pprinntf("nn旅行路路线是:n""); wwhille(rr!=NNULLL) if(k=1) prrinttf(""乘坐Noo.%dd列车车车次在%d:%d从%s到%sn",(*(*(aarcss+q->addjveex)+r->>adjjvexx).staatar->>rouute.nuumbeer,(*(*(arrcs+q->>adjjvexx)+rr->aadjvvex).sstattarr->rroutte.begginttimee0,(*(*(arccs+qq->aadjvvex