交通图咨询查询系统数据结构培训资料drva.docx

《交通图咨询查询系统数据结构培训资料drva.docx》由会员分享，可在线阅读，更多相关《交通图咨询查询系统数据结构培训资料drva.docx（59页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、信息科学学与工程程学院结构数数据课 程 设 计计 报 告课程设计计名称：交通咨咨询系统统 专 业 班 级级 ： 计算算机xxxx学 生 姓 名名 ：xxxx学 号 ：20115xxxxx指 导 教 师师 ：xxx课程设计计时间：20116.007.00420116.007.008 IV 计算机机应用技技术 专专业课程程设计任任务书学生姓名名Xxx专业班级级学号题 目交通咨询询系统课题性质质A课题来源源D指导教师师白浩同组姓名名无主要内容容1. 建立交通通网络图图的存储储结构。2. 某个城市市到达其其余各城城市的最最短路径径。3. 实现两个个城市之之间最短短路径的的问题。4. 主要目的的是给用用

2、户提供供路径咨咨询任务要求求5. 根据需求求分析给给出概要要设计，本本系统包包括以下下功能模模块：添添加信息息、查询询信息、删删除信息息、修改改信息、退退出和保保存信息息；6. 结合课题题利用数数据结构构相关知知识，利利用C语语言实现现该系统统的所有有上述功功能，要要求界面面友善，程程序运行行正常；7. 提交课程程设计报报告1份份（具体体写作要要求参考考样例），可可运行的的系统和和源代码码电子版版一套。参考文献献严蔚敏.数据据结构（CC语言版版）.北京：清华大大学出版版社谭浩强.C语语言程序序设计.（第三三版）北北京：清清华大学学出版社社审查意见见指导教师师签字：xx教研室主主任签字字：xxx

3、20166年 066月27日说明：本本表由指指导教师师填写，由由教研室室主任审审核后下下达给选选题学生生，装订订在设计计（论文文）首页页填 表 说 明明1“课课题性质质”一栏：A工程程设计；B工程程技术研研究；C软件件工程（如如CAII课题等等）；D文献献型综述述；E其它它。2“课课题来源源”一栏：A自然然科学基基金与部部、省、市市级以上上科研课课题；B企、事事业单位位委托课课题；C校、院院（系、部）级基基金课题题；D自拟拟课题。目录1需求分分析11.1 添加交交通图信信息11.2 查询单单源最短短路径111.3 查询多多源最短短路径111.4 更新交交通图信信息21.6 读取、保保存信息息2

4、2概要设设计32.1 数据类类型的定定义32.2 功能模模块结构构图43运行环环境64开发工工具和编编程语言言65详细设设计75.1 图结构构的基本本操作775.1.1添加加城市结结点和路路径结点点85.1.2修改改城市结结点和路路径结点点85.1.3删除除城市结结点和路路径结点点85.1.4退出出保存885.2 迪杰斯斯特拉算算法的实实现85.2.1 迪迪杰斯特特拉算法法函数885.2.2 提提取迪杰杰斯特拉拉函数信信息85.2.3 求求多源最最短路径径86程序编编码97运行结结果4118 心得得体会4469参考文文献4771 需求分析析本系统中中的数据据来源于于标准输输入设备备（如键键盘）

5、和和文件，可可以实现现对交通通图城市市、城市市到其余余城市的的距离的的操作，根根据需要要可查询询某两个个城市之之间的最最短距离离、城市到到各城市市的最短短距离，各各个城市市到各个个城市的的最短距距离，以以及路径径。本系统统要实现现的功能能有：添添加城市市和城市市间距离离，删除除城市及及城市间间距离，修修改城市市间距离离，查询询城市间间的最短短路径，查查询某个个城市到到某个城城市的最最短路径径。具体体如下：1.1 添加交通通图信息息能录入新新数据（城市和路径）。当录入了重复的城市和路径时，则提示数据录入重复并取消录入；当交通图中超过15个城市时，存储空间已满，不能再录入新数据；录入的新数据能按递

6、增的顺序自动进行条目编号。1.2 查询单源源最短路路径能够实现现输入起起点城市市名后，查询出其到各个城市的最短路径，输出该城市到的其他所有的城市的最短路径。1.3 查询多源源最短路路径 输入入起点城城市名和和终点城城市名，查询出两个城市的最短路径，并输出该最短路径。1.4 更新交通通图信息息根据给定定的城市市名能够够修改该该城市的名字。或者输输入两个个城市，修修改一条条路径的的距离。 1.55 删除除交通图图信息 根根据输入入的城市市名 ，删删除与该该城市有有关的所所有路径径。输入入两个城城市可以以删除一一条路径径。 1.6 读取、保存信息能够实现现退出系系统时把把交通图图中的信信息保存存在一

7、个个文件中中，在程序序瑕疵运运行时能能够读取取出来。2 概要设计计2.1 数据类型型的定义义1. 定义交通通图城市市的元素素类型 typeedeff sttrucct _ciitycharr naame10;城市市名struuct _paath * ffirsstpaath；/第第一个路路径AdjjLisst115,CittyNoode;2. 定义交通通图的路径元元素类型型 typeedeff sttrucct _patthint adjjcitty/邻接点点域int disstannce；/距距离struuct _paath *neextppathh；/下一个个路径PatthNoode,*P

8、aathPPtr;3. 定义交通通图类型型 typeedeff sttrucct int cittiess;intppathhs; AAdjLListt liist；Graaph;4. 全局变量量PLisst hheadd;typeedeff innt PPathhMattrixx;typeedeff innt SShorrtPaathTTablle;PathhMattrixx PMAXX_CIITIEESMAXX_CIITIEES;ShorrtPaathTTablle DDMAAX_CCITIIES;2.2 功能模块块结构图图根据需求求分析，为为了满足足用户的的功能需需求，按按照软件件开发方

9、方法学中中的模块块划分原原则，我我将本系系统主要要划分为为如下模模块：操操作交通通图信息息，和查询询交通图图路径两两大模块块。各模模块之间间的关系系如图11所示。图 1模模块结构构图为了实现现上述功功能模块块，分别别在顺序序表和单单链表物物理结构构上定义义了多个个函数，本本系统定定义的函函数和功功能如下下：1. 数据结构构部分部部分 voidd innitaalizze_ggrapph(GGrapph *G)功能为：图初始化化，即生生成一个个空图。int CreeatAAdjLListt(Grraphh *GG)/初始化化交通图图功能为：图的创创建，用图存存储数据据。voidd ADDD_CC

10、ITYY(Grraphh *GG)功能为：往图GG中插入入一个城城市结点点。voidd ADDD_PPATHH(Grraphh *GG,innt oori,intt addd,PPathhNodde *p)功能为：往图GG中插入入一个路路径结点点。voidd DEELETTE_CCITYY(Grraphh *GG,innt ccityy)功能为：删除图图G中的的指定的的城市及及其相关关的路径径。voidd DEELETTE_PPATHH(Grraphh *GG,innt lleftt,innt rrighht)功能为：删除图GG中一条指指定的路路径。voidd UPPDATTE_PPATHH(

11、Grraphh *GG,innt lleftt,innt rrighht)功能为：更新图图G中的的一个路路径信息息 。Stattus SqLListtSeaarchhByNNamee(SqqLisst *L,ccharr *nnamee) ;功能为：通过姓姓名查找找顺序表表中,返返回值为为其在通通讯录中中的位置置 。voidd UPPDATTE_CCITYY(Grraphh *GG,innt ccityy,chhar *naame)功能为：更新图图G中的的一个城城市信息息 。Stattus SqLListtSeaarchhByNNamee(SqqLisst *L,ccharr *pphonne

12、) ;功能为：通过电电话号码码查找顺顺序表中中,返回回值为其其在通讯讯录中的的位置。 2.程序序功能部部分 voidd MOODE_CLIIENTT(Grraphh *GG)功能为：客户端端界面函函数。 voidd MOODE_ADMMIN(Graaph *G)功能为：管理员员端界面面函数。 int ReaadAddjLiist(Graaph *G)功能为：从文件件中读取取交通图图。 int WriiteAAdjLListt(Grraphh *GG)功能为：在文件件中存储储交通图图。 voidd meenu(intt i)功能为：各种的的端界面面打印。3.算法法实现部部分voidd Shhor

13、ttesttPatth(GGrapph *G,iint v0)功能为：迪杰斯斯特拉算算法，求求出对VV0单源源最短路路径。voidd Prrintt(Grraphh *GG,innt vv0)功能为：根据迪迪杰斯特特拉算法法，打印印出V00单源最最短路径径。voidd Prrintt2(GGrapph *G,iint v1,intt v22)功能为：根据迪迪杰斯特特拉算法法，打印印出V11和V22的最短短路径。voidd FiindPPathh(Grraphh *GG,innt vv)功能为：打印出出V1到到V2的的经过路路径。int diss(Grraphh *GG,innt lleftt,

14、innt rrighht)功能为：返回指指定路径径的距离离。3 运行环境境1. 硬件环境境:PCC机内存存 4GG；硬盘盘5000G2. 软件环境境：操作系系统：wwinddowss104 开发工具具和编程程语言开发环境境：CoodeBBloccks 、Deev CC+编程语言言：C语语言5 详细设计计在概要设设计的基基础上，对对每个模模块进行行内部逻逻辑处理理部分详详细设计计。下面面分别列列出各个个模块具具体实现现流程图图：5.1 图结构的的基本操操作观察了数数据对象象后，我我选择用用一个邻邻接表用用来存储储图2信信息，则则数据结结构的基基本操作作也就确确定了，分分别为图图的添加加、删除除、

15、更新新。图 2模模拟交通通图5.1.1添加加城市结结点和路路径结点点 和图的的基本操操作相同同，只是是该城市市每增加加一个城城市结点点要在弧弧的邻接接点对应应的城市市上也增增加一条条弧。5.1.2修改改城市结结点和路路径结点点 和图的的基本操操作相同同。5.1.3删除除城市结结点和路路径结点点 和图的的基本操操作相同同，只是是该城市市每删除除一个城城市结点点要在弧弧的邻接接点对应应的城市市上也删删除那条条弧。5.1.4退出出保存 在主函函数的开开始部分分添加RReadd函数，在在管理员员修改模模式添加加Wriite函函数。实实现对图图结构的的读取保保存。5.2 迪杰斯斯特拉算算法的实实现把算法

16、实实现得到到不仅仅仅是一系系列数组组，而是是将这些些数组的的信息提提炼成有有用的信信息输出出出来，将将抽象的的数据转转换为具具象的信信息。5.2.1 迪迪杰斯特特拉算法法函数定义了若若干个全全局辅助助变量，如如路径矩矩阵P和距离离数组DD，ffinaal用来来标记是是否找到到了点的的最短路路径在函函数的初初始阶段段进行对对个辅助助变量的的初始化化，第一一趟把VV0相邻邻的路径径距离保保存下来来。选择择一个最最小的用用finnal记记录下来来，记录录下最终终的D和和P值。再再遍历其其他结点点，如果果出现新新的路径径，且路路径小于于最大值值INFFINIITY，则则保存路路径和距距离以便便下次比比

17、较。循循环n-1次得得到V00到各结结点的最最短距离离和路径径。5.2.2 提提取迪杰杰斯特拉拉函数信信息根据P函函数与DD函数，可可以将VV0到每每个终点点的经过过结点和和最终路路径求出出，利用用Priint函函数打印印出V00和V，再再调用FFinddPatth函数数，打印印经过的的结点。最最后打印印出距离离，便可可在屏幕幕上打印印出单源源最短路路径。5.2.3 求求多源最最短路径径对每个结结点循环环调用便便可打印印出每个个结点到到其他结结点的最最短路径径，通过过改变PPrinnt函数数的形参参，便可可以求出出两点间间的最短短路径。6 程序编码码根据详细细设计转转化为如如下代码码，下面面列

18、出部部分代码码：#inccludde#inccludde #inccludde#deffinee OVVERFFLOWW 0#deffinee MAAX_CCITIIES 15#deffinee INNFINNITYY 9999#deffinee FAALSEE 0#deffinee TRRUE 1typeedeff sttrucct _patth intt addjciity;/邻邻接点域域 intt diistaancee;/距离 strructt _ppathh *nnexttpatth;/下一一个路径径 PaathNNodee,*PPLisstMMAX_CITTIESS;typeede

19、ff sttrucct _ciity chaar nnamee100;/城市市名 strructt _ppathh *ffirsstpaath;/第第一个路路径 AddjLiist15,CiityNNodee;typeedeff sttrucct intt ciitiees; intt paathss; AdjjLisst llistt; Grraphh;PLisst hheadd;typeedeff innt PPathhMattrixx;typeedeff innt SShorrtPaathTTablle;PathhMattrixx PMAXX_CIITIEESMAXX_CIITIEES;

20、ShorrtPaathTTablle DDMAAX_CCITIIES;int CreeatAAdjLListt(Grraphh *GG)/初始化化交通图图 PatthNoode *p,*p11,*ppre; intt i=0; priintff(请请输入交交通路径径数目n); scaanf(%dd,&G-patths); priintff(请请输入城城市数目目n); scaanf(%dd,&G-cittiess); forr(i=0; iccitiies; i+) prrinttf(请输入入第%dd个城市市名称n,i+11); geetchhar(); sccanff(%s,G-lisstii

21、.nnamee); G-liisti.firrstppathh=(PPathhNodde *)maallooc(ssizeeof(PatthNoode); p=G-lisstii.ffirsstpaath; prrinttf(请输入入城市第第一条路路径的邻邻接城市市的位置置（-11表示结结束）n); sccanff(%d,&p-addjciity); prrinttf(请输入入城市第第一条路路径的距距离nn); sccanff(%d,&p-diistaancee); iff(p-addjciity=-11) ffreee(p); pp=NUULL; GG-llistti.fiirsttpatt

22、h = NUULL;/把把弧链表表的fiirstt置为NNULLL whhilee(p) pp-nnexttpatth=(PatthNoode *)mmallloc(sizzeoff(PaathNNodee); ppre=p; pp=p-neextppathh; pprinntf(请输输入城市市下一条条路径的的邻接城城市（-1表示示结束）n); sscannf(%d,&pp-aadjccityy); iif(pp-aadjccityy=-1) freee(pp); p=NNULLL; pree-nnexttpatth = NUULL;/置置pree为弧链链表结束束的节点点 breeak; pp

23、rinntf(请输输入城市市下一条条路径的的距离n); sscannf(%d,&pp-ddisttancce); retturnn 0;int ReaadAddjLiist(Graaph *G)/读读取交通通图 FILLE *fp; intt r,i; PatthNoode *p,*p11,*ppre; if( ffp=ffopeen(graaph.txtt,r)=NULLL) prrinttf(文件打打开失败败); exxit(0); r=ffscaanf(fp,%dd %dd ,&G-paathss,&GG-ccitiies); if(r=2) foor(ii=0; icittiess;

24、ii+) ffscaanf(fp,%ss,GG-llistti.naame); GG-llistti.fiirsttpatth=(PatthNoode *)mmallloc(sizzeoff(PaathNNodee); pp=G-liisti.firrstppathh; ffscaanf(fp,%dd,&p-adjjcitty); iif(pp-aadjccityy=-1) freee(pp); p=NNULLL; G-lisstii.ffirsstpaath = NNULLL;/把弧链链表的ffirsst置为为NULLL breeak; eelsee fsccanff(fpp,%d,&p-d

25、iistaancee); wwhille(11) p-nexxtpaath=(PaathNNodee *)malllocc(siizeoof(PPathhNodde); pree = p; p=pp-nnexttpatth; fsccanff(fpp,%d,&p-addjciity); if(p-adjjcitty=-1) frree(p); p=NULLL; prre-nexxtpaath = NNULLL;/置prre为弧弧链表结结束的节节点 brreakk; elsse fsscannf(ffp,%d,&pp-ddisttancce); fcllosee(fpp); retturnn 0

26、;int WriiteAAdjLListt(Grraphh *GG)/读取交交通图 FILLE *fp; intt r,i; PatthNoode *p,*p11; if( ffp=ffopeen(graaph.txtt,w)=NULLL) prrinttf(文件打打开失败败); exxit(0); fprrinttf(ffp,%d %d ,GG-ppathhs,GG-ccitiies); forr(i=0; iccitiies; i+) fpprinntf(fp,%ss ,G-lisstii.nnamee); p=G-lisstii.ffirsstpaath; whhilee(p) ffpr

27、iintff(fpp,%d %d ,p-addjciity,p-disstannce); pp=p-neextppathh; fpprinntf(fp,-11 ); fcllosee(fpp); retturnn 0;voidd ADDD_PPATHH(Grraphh *GG,innt oori,intt addd,PPathhNodde pp)/添加路路径 PatthNoode *prr; pr=(PaathNNodee *)malllocc(siizeoof(PPathhNodde); pr-addjciity=addd; pr-diistaancee=p.disstannce; pr-n

28、eextppathh=G-liistorii.ffirsstpaath; G-lisstoori.fiirsttpatth=ppr;voidd ADDD_CCITYY(Grraphh *GG)/添加城城市 intt i=0; PatthNoode *p,*prre; if(G-cittiess=MMAX_CITTIESS) rretuurn ; whiile(strrcmpp(G-liisti.namme,0)!=00) i+; G-cittiess+; priintff(请请输入%d城市市的名称称n,i+1); gettchaar(); scaanf(%ss,GG-llistti.naame

29、); G-lisstii.ffirsstpaath=(PaathNNodee *)malllocc(siizeoof(PPathhNodde); p=GG-llistti.fiirsttpatth; priintff(请请输入城城市第一一条路径径的邻接接城市的的位置（-1表示示结束）n); scaanf(%dd,&p-adjjcitty); priintff(请请输入城城市第一一条路径径的距离离n); scaanf(%dd,&p-disstannce); if(p-adjjcitty=-1) frree(p); p=NULLL; G-liisti.firrstppathh = NULLL;/把

30、弧弧链表的的firrst置置为NUULL elsse ADDD_PPATHH(G,p-adjjcitty,ii,*pp); whiile(p) p-neextppathh=(PPathhNodde *)maallooc(ssizeeof(PatthNoode); prre = p; p=p-nexxtpaath; prrinttf(请输入入城市下下一条路路径的邻邻接城市市（-11表示结结束）n); sccanff(%d,&p-addjciity); prrinttf(请输入入城市下下一条路路径的距距离nn); sccanff(%d,&p-diistaancee); iff(p-addjciit

31、y=-11) ffreee(p); pp=NUULL; ppre-neextppathh = NULLL;/置ppre为为弧链表表结束的的节点 ellse AADD_PATTH(GG,p-addjciity,i,*p); voidd UPPDATTE_CCITYY(Grraphh *GG,innt ccityy,chhar *naame) strrcpyy(G-liistcitty.namme,nnamee);int FinndCiity(Graaph *G,chaar nnamee)/返返回城市市的序号号 intt i; forr(i=0; iccitiies; i+) iff(sttrcm

32、mp(nnamee,G-liisti.namme)=0) rretuurn i; retturnn -11;voidd UPPDATTE_PPATHH(Grraphh *GG,innt lleftt,innt rrighht) PatthNoode *p; intt diis; priintff(请请输入修修改后的的路径距距离nn); scaanf(%dd,&diss); p=GG-llisttleeft.fiirsttpatth; whiile(1) iff(riightt=pp-aadjccityy) pp-ddisttancce=ddis; bbreaak; p=p-nexxtpaath

33、; p=GG-llisttriightt.ffirsstpaath; whiile(1) iff(leeft=p-addjciity) pp-ddisttancce=ddis; bbreaak; p=p-nexxtpaath; retturnn ;voidd DEELETTE_PPATHH(Grraphh *GG,innt lleftt,innt rrighht) PatthNoode *p,*prre; intt diis; p=GG-llisttleeft.fiirsttpatth; pree=p; whiile(p) iff(riightt=pp-aadjccityy) bbreaak;

34、 p=p-nexxtpaath; whiile(1) iff(p=G-liistlefft.firrstppathh) GG-llisttleeft.fiirsttpatth=pp-nnexttpatth; ffreee(p); bbreaak; iff(prre-nexxtpaath=p) ppre-neextppathh=p-neextppathh; ffreee(p); bbreaak; p=GG-llisttriightt.ffirsstpaath; pree=p; whiile(p) iff(leeft=p-addjciity) bbreaak; p=p-nexxtpaath; whiile(1) iff(p=G-liistrigght.fiirsttpatth) GG-llisttriightt.ffirsstpaath=p-nexxtpaath; ffreee(p); bbreaak; iff(prre-nexxtpaath=p) ppre-neextppathh=p-neextppathh; ffreee(p); bbreaak; retturnn ;voidd DEELETTE_CCITYY(Grraphh *GG,innt ccityy) intt i; w