数据结构课程设计报告 页.docx

《数据结构课程设计报告 页.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计报告 页.docx（67页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、n数据结构构课程设设计报告告题目：全全国交通通咨询模模拟学 院 信息 专 业 计计算机科科学与技技术 年级班别别 计科科09002 学 号 0911230002113 学生姓名名 陈佳佳丽 指导教师师 章志志勇 一需求求分析1程序序设计任任务：从中国地地图平面面图中选选取部分分城市，抽象为为程序所所需要图图的结点点，并以以城市间间的列车车路线和和飞机路路线，作作为图结结点中的的弧信息息，设计计一个全全国交通通咨询模模拟系统统。利用用该系统统实现两两种最优优决策：最快到到达或最最省钱到到达。2.明确确规定：(1)输输入形式式和输入入值的范范围： 每条飞飞机弧或或者火车车弧涉及及的信息息量很多多，

2、包括括：起始始城市、目的城城市、出出发时间间、到达达时间、班次以以及费用用。作为为管理员员要输入入的信息息包括以以上信息息，而作作为用户户或者客客户，要要输入的的信息有有起始城城市和目目的城市市，并选选择何种种最优决决策。(2)输输出形式式：按用户提提供的最最优决策策的不同同而输出出不同的的信息，其中输输出的所所搭飞机机或火车车的班次次及其起起始地点点和终点点、起始始时间和和出发时时间还有有相关的的最优信信息，比比如最快快经多少少时间到到达、最最省钱多多少钱到到达和最最少经多多少中转转站到达达。(3)程程序所能能达到的的功能a.该系系统有供供用户选选择的菜菜单和交交互性。可以对对城市、列车车车

3、次和飞飞机航班班进行编编辑，添添加或删删除。b.建立立一个全全国交通通咨询系系统，该该系统具具备自动动查找任任意两城城市间铁铁路、飞飞机交通通的最短短路径和和最少花花费及中中转次数数最少等等功能。c.初始始化交通通系统有有两种方方式，键键盘和文文档。二设计计概要1.抽象象数据类类型本程序运运用了关关于图这这种数据据结构。ADT Graaph数据对象象V：VV是具有有相同特特性的数数据元素素的集合合，称为为顶点集集。数据关系系R： RR=VVR VVR=|v,wwV且PP(v,w),表表示从vv到w的的弧。 谓词PP(v,w)定定义了弧弧的的意义或或信息基本操作作P： CCreaateGGrap

4、ph(&G,VV,VRR); 初始条条件：VV是图的的顶点集集，VRR是图中中弧的集集合。 操作结结果：按按V和VVR的定定义构造造图G。 DeestrroyGGrapph(&G);初始条件件：图GG存在。 操作结结果：销销毁图GG。 LoocatteVeet(GG,u); 初始条条件：图图G存在在，u和和G中顶顶点有相相同的特特征。 操作结结果：若若G中存存在顶点点u，则则返回该该顶点在在图中的的位置， 否则则返回其其他信息息。GetVVex(G,vv); 初始条条件：图图G存在在，v是是G中某某个顶点点。 操作结结果：返返回v的的值。PutVVex(&G,v,vvaluue); 初初始条件

5、件：图GG存在，v是GG中某个个顶点。 操操作结果果：对vv赋值vvaluue。FirsstAddjVeex(GG,v); 初初始条件件：图GG存在，v是GG中某个个顶点。 操操作结果果：返回回v的第第一个邻邻接顶点点。若顶顶点在GG中没有有邻接 顶点，则返回回“空”。NexttAdjjVexx(G,v,ww); 初初始条件件：图GG存在，v是GG中某个个顶点，w是vv的邻接接顶点， 操操作结果果：返回回v的(相对于于w的)下一个个邻接顶顶点。若若w是vv 的的最后一一个邻接接点，则则返回“空”。InseertVVex(&G,v); 初初始条件件：图GG存在，v和图图中顶点点有相同同特征。 操

6、操作结果果：在图图G中添添加新顶顶点v。DeleeteVVex(&G,v); 初初始条件件：图GG存在，v是GG中某个个顶点。 操操作结果果：删除除G中顶顶点v及及相关弧弧。InseertAArc(&G,v,ww); 初初始条件件：图GG存在，v和ww是G中中两个顶顶点。 操操作结果果：在GG中增添添弧，若GG是无向向的则还还增加对对称弧。DeleeteAArc(&G,v,ww);初始条件件：图GG存在，v和ww是G中中两个顶顶点。 操操作结果果：在GG中删除除弧，若GG是无向向的，则则还删除除对称 弧。DFSTTravversse(GG,Viisitt(); 初初始条件件：图GG存在，Vis

7、sit是是顶点的的应用函函数。 操操作结果果：对图图进行深深度优先先遍历。在遍历历过程中中对每个个顶点调调用函数Vissit一一次且仅仅一次。一旦vvisiit()失败，则操作作失败。BFSTTravversse(GG,Viisitt(); 初初始条件件：图GG存在，Vissit是是顶点的的应用函函数。 操操作结果果：对图图进行广广度优先先遍历。在遍历历过程中中对每个个顶点调调用函数Vissit一一次且仅仅一次。一旦vvisiit()失败，则操作作失败。 ADTT Grraphh其他的抽抽象数据据类型定定义如下下：typeedeff sttrucctintt nuumbeer; flooat

8、exppenddituure; intt beeginntimme22; intt arrrivvetiime2;Vehhidee;typeedeff sttrucctVehhidee sttataaMAAX_RROUTTE_NNUM; intt laast;inffoliist;typeedeff sttrucct AArcNNodeeintt addjveex; strructt ArrcNoode *neextaarc; inffoliist inffo;ArccNodde;typeedeff sttrucct VVNoddechaar ccityynamme110; ArccNodde

9、 *plaaneffirsstarrc,*traainffirsstarrc;VNoode,AdjjLisstMMAX_VERRTEXX_NUUM;typeedeff sttrucctAdjjLisst vvertticees; intt veexnuum,pplannearrcnuum,ttraiinarrcnuum;ALGGrapph;typeedeff sttrucct NNodeeintt addjveex; intt rooutee; strructt Noode *neext;Nodde;typeedeff sttrucct QQNoddeintt addjveex; strruc

10、tt QNNodee *nnextt;QNoode;typeedeff sttrucctQNoode *frrontt; QNoode *reear;LinnkQuueuee;typeedeff sttrucct TTimeeNoddeintt addjveex; intt rooutee; intt beeginntimme22; intt arrrivvetiime2; strructt TiimeNNodee *cchilldMMAX_ROUUTE_NUMM;TimmeNoode,*TiimeTTreee;struuct arccintt coo; chaar vvt110; chaar

11、 vvh110; intt btt2; intt att2;floaat mmo;aMMAX_ARCC_SIIZE;基本操作作：voidd Addminnistter(ALGGrapph *G);voidd ciityeeditt(ALLGraaph *G);voidd CoopyTTimeeTreee(TTimeeTreee pp,TiimeTTreee q);voidd crreatteciityffilee();voidd CrreatteGrraphh(ALLGraaph *G);voidd crreattepllaneefille();voidd CrreatteTiimeTTree

12、e(TiimeTTreee p,intt i,intt j,LinnkQuueuee *QQ,innfollistt (*arccs)MAXX_VEERTEEX_NNUM);voidd crreattetrrainnfille();int DelleteeplaaneAArc(ALGGrapph *G);voidd DeeletteQuueuee(LiinkQQueuue *Q,iint *x);int DelleteetraainAArc(ALGGrapph *G);voidd DeeletteVeerteex(AALGrraphh *GG);voidd DeemanndDiispoose(

13、intt n,ALGGrapph GG);voidd DeestooryTTimeeTreee(TTimeeTreee pp);voidd EnnterrplaaneAArc(ALGGrapph *G);voidd EnnterrQueeue(LinnkQuueuee *QQ,innt xx);voidd EnnterrtraainAArc(ALGGrapph *G);voidd EnnterrVerrtexx(ALLGraaph *G);voidd ExxpenndittureeDissposse(iint k,iinfoolisst (*arrcs)MAAX_VVERTTEX_NUMM,A

14、ALGrraphh G,intt v00,innt vv1,ffloaat *M,iint *fiinall);voidd fllighhteddit(ALGGrapph *G);voidd innitggrapph(AALGrraphh *GG);voidd InnitQQueuue(LLinkkQueeue *Q);int IsEEmptty(LLinkkQueeue *Q);int LoccateeVerrtexx(ALLGraaph *G,chaar *v);voidd MiinExxpennditturee(innfollistt arrcs,flooat *exxpenndittu

15、ree,innt *rouute);voidd MiinTiime(inffoliist arccs,iint *tiime,intt *rroutte);voidd PrrinttGraaph(ALGGrapph *G);int savve(AALGrraphh *GG);voidd TiimeDDispposee(innt kk,innfollistt (*arccs)MAXX_VEERTEEX_NNUM,ALLGraaph G,iint v0,intt v11,innt (*T)2,innt *finnal);voidd TiimeTTreeeDissposse(NNodee *hhea

16、dd,innfollistt (*arccs)MAXX_VEERTEEX_NNUM);voidd trrainnediit(AALGrraphh *GG);voidd TrranssferrDissposse(iint k,iinfoolisst (*arrcs)MAAX_VVERTTEX_NUMM,AALGrraphh G,intt v00,innt vv1);voidd UsserDDemaand(ALGGrapph GG);voidd ViisittTimmeTrree(TimmeTrree p);主程序的的流程以以及各程程序模块块之间的的调用关关系退出显示交通系统PrintGraph用

17、户咨询UserDemand管理员管理Administer主函数main（）返回上一级菜单列车车次编辑Administer飞机航班编辑Administer城市编辑cityedit管理员管理Administer初始化交通系统initgraph返回上一级菜单最少中转次数TransferDispose最少旅行时间TimeDispose用户咨询UserDemand最少旅行费用ExpenditureDisposeUserDemand显示城市显示飞机航班显示列车车次返回上一级菜单显示交通系统PrintGraph文档键盘初始化交通系统initgraph删除城市新增城市城市编辑cityedit删除航班新增航班飞

18、机航班编辑planeedit删除车次新增车次火车列次编辑trainedit三详细细设计1.主程程序伪代代码int maiin() 界面面初始化化； 输入入操作命命令；Whille（“命令” ！= “退出”） 接受命命令（用用户输入入要实现现功能）； 进入各各个处理理命令函函数；2. 函函数和过过程的调调用关系系图DeleteQueueEnterQueueInitQueueMinTimeTimeTreeDisposeEnterplaneArcDeleteplaneArcEntertrainArcDeletetrainArcTransferDisposeTimeDisposeMinExpendit

19、ureExpenditureDisposecreateplanefilecreatetrainfileCreateGraphinitgraphcityeditAdministerPrintGraphEnterVertextraineditDeleteVertexcreatecityfileflighteditUserDemandMain()InitQueueEnterQueueDeleteQueueCreateTimeTreeCopyTimeTreeTimeTreeDisposeVisitTimeTreeDestoryTimeTree四调试试分析：调试过过程中遇遇到的问问题是如如何解决决的以及

20、及对设计计与实现现的回顾顾讨论和和分析： 在调调试的过过程中碰碰到了一一下问题题：a. 引引用形参参应用不不当；b. 文文件操作作中遇到到读入错错误或找找不到文文件；解决方案案：a. 对对引用形形参了解解的不是是很透彻彻，导致致错误，通过查查阅相关关书籍如如C+ PPrimmer和请教教编程能能力较高高的人，最终解解决问题题。b. 通通过参考考谭浩强强编著的的C程程序设计计中的的文件操操作，文文件格式式和相关关文件路路径的设设置，最最终解决决问题。算法的的时空分分析（包包括基本本操作和和其他算算法的时时间复杂杂度和空空间复杂杂度的分分析）和和改进设设想：基本操作作时间复杂杂度空间复杂杂度voi

21、dd Addminnistter(ALGGrapph *G)O(1)O(1)voidd ciityeeditt(ALLGraaph *G)O(n)O(n)voidd CoopyTTimeeTreee(TTimeeTreee pp,TiimeTTreee q)O(n)O(1)voidd crreatteciityffilee()O(n)O(n)voidd CrreatteGrraphh(ALLGraaph *G)O(n)O(n)voidd crreattepllaneefille()O(1)O(1)voidd CrreatteTiimeTTreee(TiimeTTreee p,intt i,in

22、tt j,LinnkQuueuee *QQ,innfollistt (*arccs)MAXX_VEERTEEX_NNUM)O(n)O(n)voidd crreattetrrainnfille()O(1)O(1)int DelleteeplaaneAArc(ALGGrapph *G)O(n)O(n)voidd DeeletteQuueuee(LiinkQQueuue *Q,iint *x)O(1)O(1)int DelleteetraainAArc(ALGGrapph *G)O(n)O(n)voidd DeeletteVeerteex(AALGrraphh *GG)O(n)O(n)voidd D

23、eemanndDiispoose(intt n,ALGGrapph GG)O(1)O(1)voidd DeestooryTTimeeTreee(TTimeeTreee pp)O(n)O(1)voidd EnnterrplaaneAArc(ALGGrapph *G)O(n)O(n)voidd EnnterrQueeue(LinnkQuueuee *QQ,innt xx)O(1)O(1)voidd EnnterrtraainAArc(ALGGrapph *G)O(1)O(1)voidd EnnterrVerrtexx(ALLGraaph *G)O(n)O(n)voidd Exxpenndittur

24、eeDissposse(iint k,iinfoolisst (*arrcs)MAAX_VVERTTEX_NUMM,AALGrraphh G,intt v00,innt vv1,ffloaat *M,iint *fiinall)O(n)O(1)voidd fllighhteddit(ALGGrapph *G)O(1)O(1)voidd innitggrapph(AALGrraphh *GG)O(1)O(n)voidd InnitQQueuue(LLinkkQueeue *Q)O(1)O(1)int IsEEmptty(LLinkkQueeue *Q)O(1)O(1)int LoccateeVe

25、rrtexx(ALLGraaph *G,chaar *v)O(n)O(1)voidd MiinExxpennditturee(innfollistt arrcs,flooat *exxpennditturee,innt *rouute)O(n)O(n)voidd MiinTiime(inffoliist arccs,iint *tiime,intt *rroutte)O(n)O(n)voidd PrrinttGraaph(ALGGrapph *G)O(1)O(n)int savve(AALGrraphh *GG)O(1)O(1)voidd TiimeDDispposee(innt kk,inn

26、follistt (*arccs)MAXX_VEERTEEX_NNUM,ALLGraaph G,iint v0,intt v11,innt (*T)2,innt *finnal)O(n)O(n)voidd TiimeTTreeeDissposse(NNodee *hheadd,innfollistt (*arccs)MAXX_VEERTEEX_NNUM)O(n)O(n)voidd trrainnediit(AALGrraphh *GG)O(1)O(1)voidd TrranssferrDissposse(iint k,iinfoolisst (*arrcs)MAAX_VVERTTEX_NUMM

27、,AALGrraphh G,intt v00,innt vv1)O(n)O(n)voidd UsserDDemaand(ALGGrapph GG)O(1)O(1)voidd ViisittTimmeTrree(TimmeTrree p)O(n)O(n)经验和和体会：通过本次次课程设设计，我我学到了了一种程程序设计计方法，就是结结构化程程序设计计方法，在程序序设计过过程中，我尝试试按如下下方法进进行结构构化程序序设计：(1)自自顶向下下；(22)逐步步细化；(3)模块化化设计(4)结构化化编码。这种设设计方法法的过程程是将问问题求解解由抽象象逐步具具体化的的过程，而且，用这种种方法便便于验证证算

28、法的的正确性性。 本次次课程设设计所使使用的是是较为复复杂的抽抽象数据据类型图，而且在在弧的基基础上增增加了许许多信息息，如添添加了时时间，费费用等等等，这无无疑给编编程加大大了难度度，同时时也是相当当的具有有挑战性性。在编程的的过程中中，我用用到了全全局数组组，我将将数组放放在工程程的头文文件里面面，编译译的时候候报错，说是多多重定义义。最终终放弃了了创建工工程，而而选择了了单个文文件进行行编译和和运行，结果顺顺利通过过。同时，在在文件操操作方面面我也曾曾遇到问问题，就就是在程程序对文文件进行行读取的的时候报报错，无无法读取取文件，最后查查询有关关C的工工具书，原来是是文件路路径问题题，借助

29、助工具书书最终解解决了文文件操作作方面的的问题。总之，这这次课程程设计是是对这一一个学期期以来对对数据结结构学习习成果的的一个验验证，同同时也是是理论与与实践很很好的结结合，既既对学过过的数据据结构进进行了巩巩固，也也对我的的编程能能力奠定定了坚实实的基础础。五用户户使用说说明：1) 打开并运运行程序序，按任任意键进进入操作作主界面面，按提提示进行行相关操操作；2) 按“1”进入管管理员界界面，按按“2”进入用用户咨询询界面，按“3”显示交交通系统统，按“4”则退出出。3) 进入管理理员界面面可键入入“1”初始化化交通系系统，并并选择文文档初始始化方式式(如果果是第一一次使用用该系统统建议使使

30、用文档档初始化化交通系系统，免免得自己己进行繁繁冗的初初始化操操作)。其余可可按提示示进行相相关操作作，不难难掌握。4) 进入用户户咨询界界面，可可根据用用户需要要进行相相关的选选择，或或是选择择“1”(最少少旅行费费用)；或是选选择“2”(最少少旅行时时间)，又或者者是选择择“3”(最少少旅行中中转次数数)等。5) 进入显示示交通系系统界面面，根据据用户选选择则可可显示城城市、飞飞机航班班、列车车车次等等信息。或者返返回上一一级菜单单。六测试试结果：1. 个个人信息息界面：2. 操操作主界界面：3. 管管理员界界面：4. 交交通系统统初始化化方式选选择界面面：5. 城城市编辑辑界面：6. 飞

31、飞机航班班编辑：7. 列列车车次次编辑：8. 显显示交通通系统主主界面：9. 显显示城市市：10. 显示飞飞机航班班：11. 显示列列车车次次：12 用户咨咨询：13. 选择旅旅行起始始城市：14. 选择旅旅行到达达城市：15. 选择旅旅行的交交通工具具：16. 最少旅旅行费用用：17最最少旅行行时间：18. 最少中中转次数数：七附录录源程程序#deffinee MAAX_VVERTTEX_NUMM 188#deffinee NUULL 0#deffinee MAAX_AARC_SIZZE 1100#deffinee MAAX_RROUTTE_NNUM 5#inccludde#inccludd

32、e#inccludde#inccludde#deffinee Faalsee 0#deffinee Trrue 1#deffinee INNFINNITYY 1000000typeedeff sttrucctintt nuumbeer;flooat exppenddituure; intt beeginntimme22; intt arrrivvetiime2;Vehhidee;typeedeff sttrucctVehhidee sttataaMAAX_RROUTTE_NNUM; intt laast;inffoliist;typeedeff sttrucct AArcNNodeeintt

33、addjveex;strructt ArrcNoode *neextaarc; inffoliist inffo;ArccNodde;typeedeff sttrucct VVNoddechaar ccityynamme110;ArccNodde *plaaneffirsstarrc,*traainffirsstarrc;VNoode,AdjjLisstMMAX_VERRTEXX_NUUM;typeedeff sttrucctAdjjLisst vvertticees; intt veexnuum,pplannearrcnuum,ttraiinarrcnuum;ALGGrapph;typeed

34、eff sttrucct NNodeeintt addjveex; intt rooutee; strructt Noode *neext;Nodde;typeedeff sttrucct QQNoddeintt addjveex; strructt QNNodee *nnextt;QNoode;typeedeff sttrucctQNoode *frrontt; QNoode *reear;LinnkQuueuee;typeedeff sttrucct TTimeeNoddeintt addjveex; intt rooutee; intt beeginntimme22; intt arrr

35、ivvetiime2; strructt TiimeNNodee *cchilldMMAX_ROUUTE_NUMM;TimmeNoode,*TiimeTTreee;struuct arccintt coo; chaar vvt110; chaar vvh110; intt btt2; intt att2; flooat mo;aMMAX_ARCC_SIIZE;charr ciityMAXX_VEERTEEX_NNUM100;int TTiime2;int timme22;int timme12;int timme22;int cMMAX_VERRTEXX_NUUM;int dMMAX_VERR

36、TEXX_NUUM;voidd Addminnistter(ALGGrapph *G);voidd ciityeeditt(ALLGraaph *G);voidd CoopyTTimeeTreee(TTimeeTreee pp,TiimeTTreee q);voidd crreatteciityffilee();voidd CrreatteGrraphh(ALLGraaph *G);voidd crreattepllaneefille();voidd CrreatteTiimeTTreee(TiimeTTreee p,intt i,intt j,LinnkQuueuee *QQ,innfoll

37、istt (*arccs)MAXX_VEERTEEX_NNUM);voidd crreattetrrainnfille();int DelleteeplaaneAArc(ALGGrapph *G);voidd DeeletteQuueuee(LiinkQQueuue *Q,iint *x);int DelleteetraainAArc(ALGGrapph *G);voidd DeeletteVeerteex(AALGrraphh *GG);voidd DeemanndDiispoose(intt n,ALGGrapph GG);voidd DeestooryTTimeeTreee(TTimee

38、Treee pp);voidd EnnterrplaaneAArc(ALGGrapph *G);voidd EnnterrQueeue(LinnkQuueuee *QQ,innt xx);voidd EnnterrtraainAArc(ALGGrapph *G);voidd EnnterrVerrtexx(ALLGraaph *G);voidd ExxpenndittureeDissposse(iint k,iinfoolisst (*arrcs)MAAX_VVERTTEX_NUMM,AALGrraphh G,intt v00,innt vv1,ffloaat *M,iint *fiinall

39、);voidd fllighhteddit(ALGGrapph *G);voidd innitggrapph(AALGrraphh *GG);voidd InnitQQueuue(LLinkkQueeue *Q);int IsEEmptty(LLinkkQueeue *Q);int LoccateeVerrtexx(ALLGraaph *G,chaar *v);voidd MiinExxpennditturee(innfollistt arrcs,flooat *exxpennditturee,innt *rouute);voidd MiinTiime(inffoliist arccs,iin

40、t *tiime,intt *rroutte);voidd PrrinttGraaph(ALGGrapph *G);int savve(AALGrraphh *GG);voidd TiimeDDispposee(innt kk,innfollistt (*arccs)MAXX_VEERTEEX_NNUM,ALLGraaph G,iint v0,intt v11,innt (*T)2,innt *finnal);voidd TiimeTTreeeDissposse(NNodee *hheadd,innfollistt (*arccs)MAXX_VEERTEEX_NNUM);voidd trrainnediit(AALGrraphh *GG);voidd TrranssferrDissposse(iint k,iinfoolisst (*arrcs)MAAX_VVERTTEX_NUMM,AALGrraphh G,intt v00,innt vv1);voidd UsserDDemaand(ALGGrapph GG);voidd ViisittTimmeTrree(TimmeTrree p);int maiin()ALGGrapph GG; intt i; priintff(nnnnnnnnn*); prrinttf(*