数据结构课程设计汇本报告

1、洛阳理工学院课程设计说明书课程名称数据构造课程设计设计课题校园导游程序 专业计算机科学与技术班级 学号某完成日期课程设计任务书设计题目：校园导游程序设计容与要求：问题描述用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景 点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路， 存放路径长度等信息。要求能够答复有关景点介绍、游览路径等问题。根本要求1查询各景点的相关信息；2查询图中任意两个景点间的最短路径。3查询图中任意两个景点间的所有路径。4增加、删除、更新有关景点和道路的信息。指导教师：2016年12月20日课程设计评语成绩：指导教师：年 月 日目录一、问题描述1二、根本要

2、求1三、测试数据2四、算法思想3五、模块划分45.1应用函数4521主函数6522查询景点信息函数7523查询两景点之间最短路径函数 9查询两景点之间所有路径函数 9删除已有的顶点和路径10修改已有的顶点和路径12六、数据构造14七、测试16八、心得28九、源程序30问题描述用无向网表示你所在学校的校园景点平面图， 图中顶点表示主要景点，存放 景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等 信息。要求能够答复有关景点介绍、游览路径等问题。根本要求1查询各景点的相关信息；2查询图中任意两个景点间的最短路径。3查询图中任意两个景点间的所有路径。4增加、删除、更新有关景点和道

3、路的信息三、测试数据菜单函数：依次输入：1, 2 , 3 , 4, 5 , 6, 0分别对应景点信息查询，最短路径查询，所有路径查询，添加景点及路径 信息，删除景点及路径信息，修改景点及路径信息，退出。查询景点信息：输入：1，2分别对应按编号查询，按景点名称查询按编号查询：输入编号：1按景点名称查询：输入名称：大明桥最短路径查询：输入起始景点和终点景点编号：1，7所有路径查询：输入起始景点和终点景点编号：2，8添加景点及路径信息：输入新景点序号：9输入新景点名称：南门输入新景点相关信息：充满古韵的门，适合拍照 输入到其余各景点的距离：50, 100, 20删除景点及路径信息：输入：1, 2分别

4、对应按编号查询，按景点名称查询按编号查询：输入需要删除的景点编号：8修改景点及路径信息：输入：1，2分别对应修改景点信息，修改道路信息修改景点信息：输入1，2分别对应修改景点名称，修改景点描述修改景点信息：输入修改序号：1输入修改后的名称：图书馆123四、算法思想先利用CreateUDN 创立初始无向网，通过ma in主函数调用显示，操作功 能的选择通过Menu函数输出，根据游客需求选择景点信息查询、景点之间最 短路径查询、景点之间所有路径查询、添加景点信息、删除景点信息或者修改信 息。如果是景点信息查询，在search中完成，再调用SearchMenu选择是按照景点编号或者景点名称查询，游客

5、输入相应容。如果是景点之间最短路径查询 或是景点之间所有路径查询那么游客输入起始景点和完毕景点；最短路径是用 ShortestPath实现，其中运用了迪杰斯特拉算法；所有路径由 Searchpathl调 用disppath再调用path，在path过递归算法实现寻找每一条路并输出。如果 是添加景点信息调用Addnewsight函数，游客按照提示依次输入信息容。如果 是删除景点信息，选择按照名称删除或是按照序号删除，再调用Deletesight函数，游客输入相应容进展删除。如果是修改信息，调用Cha ngesight ，Chan geme nu两个函数，游客按提示选择修改景点信息或者道路信息，再

6、按提 示输入修改后得容。输出使用调用的相应函数。信息保存于文件中。五、模块划分5.1应用函数void CreateUDN(i nt v,i nt a);void n arrate();void ShortestPath(i nt nu m);void output(i nt sight1,i nt sight2);in t Men u();void search();int SearchMe nu();void HaMiTo nian(in t);void Searchpath1(MGraph g);*/void disppath(MGraph g,i nt i,i nt j);void pa

7、th(MGraph g,i nt i,i nt j,i nt k);/*void NextValue(i nt);/*造图函数*/*说明函数*/*最短路径函数*/*输出函数*/*主菜单*/*查询景点信息*/*查询子菜单*/*图的遍历*/*查询两个景点间的所有路径确定路径上第k+1个顶点的序号*/void display。;/*显示遍历结果*/int Add newsight(i nt n); int Deletesight(); void Chan gesight();int Chan geme nu();int Sightme nu();/*添加新的景点和路径*/*删除景点和路径*/*修改景

8、点和路径*/*修改路径或顶点的选择菜单*/*选择需该景点的菜单*/521主函数1. 功能：初始图通过main主函数调用显示，操作功能的选择通过Menu函数输 出，显示为菜单形式提醒用户进展操作， 用户选择后在main主函数中调用各个 函数实现各种功能。2. 流程图：522查询景点信息函数1.功能：在main主函数中调用search,翻开存储了信息的文件，在显示界面显示已有的景点名称和序号，游客按需求进展序号查询或者名称查询，输入需要查询的序号或者名称后会显示该景点的名称及简介，而后按任意键返回上级菜单项 选择择继续查询或者返回主界面，在查询景点信息函数中实现2.流程图：按编号查询按景点查询ye

9、s输出景点信息没有找到!完毕523查询两景点之间最短路径函数1.功能：在main函数中调用narrate函数，翻开存储了信息的文件，游客 输入起点编号或者终点编号，利用迪杰斯特拉算法由ShortestPath最短路径函数选择一条两点之间的最短路径展示给游客，关闭文件。查询两景点之间所有路径函数1.功能：当游客输入完毕后，根据之前构建的无向图，执行过程为进层和退层两个阶段。首先开场递归进层，考虑使用基于深度优先思想，在搜素过程中， 按照景点编号大小依次访问每一个节点，假设访问到一个未被访问且有路径相通 的点那么将其参加数组P,直到找到目的地，输出第一条路径，然后开场递归退 层，按照之前的方式递归

10、访问它的所有未被访问的相邻节点。并通过相应的设置标志visited的方式使最终能不重复地走遍所有的简单路径。最后输出这些路径 即可。添加新的顶点和路径1.功能：在Addnewsight 添加新的景点和路径函数 中实现，翻开存储了信息的文件，输入需要新添加的景点名称，根本信息介绍并依次输入它到原有各 景点的距离，将新信息存储到文件中并保存526删除已有的顶点和路径1.功能：删除不需要的景点信息，并保存删除后的文件，方便下一次浏览2 流程图：开场10 / 6按景点名称按 景 点 八、 编 号11 / 67527修改已有的顶点和路径1.功能：修改有误的景点信息，并保存修改后的文件，方便下一次浏览。2

11、 流程图:I1*1开场1 221II修改景点信息修改道路信息13 / 67六、数据构造MGraph疋义图的类型，其中包含景点，景点之间的距离，景点数和边数。VertexType是景点的构造体，里面包含了景点编号，景点名称，景点描述ArcCell是边的构造体，其中包含了边的长度即景点之间的距离。typedef struct ArcCellint adj;/*相邻接的景点之间的路程*/ArcCell;/*定义边的类型*/typedef struct VertexTypeint nu mber;/*景点编号*/char sight100;char descriptio n1000;VertexTyp

12、e;/*景点名称*/*景点描述*/*定义顶点的类型*/typedef structVertexType vex20;/*图中的顶点，即为景点*/ArcCell arcs2020;/*图中的边，即为景点间的距离*/int vex nu m,arum;/*顶点数，边数*/MGraph;/*定义图的类型*/七、测试7.1.测试数据输入：根据游客需求选择景点信息查询、景点之间最短路径查询、景点之间 所有路径查询、添加景点信息、删除景点信息或者修改信息。如果是景点信息查 询，再选择是按照景点编号或者景点名称查询， 游客输入相应容；如果是景点之 间最短路径查询或是景点之间所有路径查询那么游客输入起始景点和

13、完毕景点； 如果是添加景点信息那么按照提示依次输入信息容；如果是删除景点信息，选择按照名称删除或是按照序号删除，再输入相应容进展删除；如果是修改信息，按 提示选择修改景点信息或者道路信息，再按提示输入修改后得容预期的输出结果：运行程序直接出现各景点及其编号，同时出现操作菜单，明书.注齧常阳 11/ (J- sr- o 1 ni 3 4 s 6 ffc- (- -( c /11一 HL 一二匚匚一匚I一一蛊“电栓 岂阊I'fil占苫点 曙羡SW 壬两两sir已已 询询询1 HJG 3 4- 5 6 n-其他结果依使用者需求而定，请参见程序后的运行结果1.菜单函数半半半*林半林半半半半欢迎

14、使用洛阳 理工学 院开元校 区校13导游程序半半半林半+4林 榴*审JH-ftrlR7尺、恵令称 幡lg SW赛验验院院 大團教士头r头隽 >JT TJ- IJr J- XJ- KI/ 0-12345678 请输入您要查拔的景点编号I 1您娶查找景点信息如下：图书馆；环境优雅，充满书香气息，呈环形按任意键返回2查询景点信息按编号3查询景点信息按名称4.查询两景点之间的最短路径您要查找景点信息如下：大明桥:落于小河上，风景优美请输入您要查拔的景点名称：大明桥:俅枠+村梅*衬 欢迎使闰 洛阳理工学 院开元松区校园导 游程序+林林杠林*杠*耳冰*尢弃林*欢迎使用 洛阳理 工学 院幵TC校区校园

15、导游程序+*衬*弃*申爭点名称大图教士头实实縈012345678if选争起点署点(08) : 1it遥律寒点熹点(0-8) . 7从图书馆到璞院餐厅的最短路径是(最短距离为380m ) 图书馆一实验A楼一璞院餐厅请按任意键继续5.查询两点之间的所有路径> >181111口二 口呛 E 口W 图实犬买* :怦*欢迎使用洛阳理工学院开7E校区校园导沸禾呈序*忖枠* * * *景点名秫充满古韵的门适春请祁！I入新景点的序号冃自ft大图教士头012345 6 7006添加新的景点及其路径添加过程添加后巒入此豁到第作点跳离（现（硏酣或和到达胶U0嚴锁大值）:nw(2)教享技(4) 买滋业(5

16、) 实萼( 9)南门12 3 4 5 6 0I短白心间间-Q"占皿占宀 占筑臺沪的W-祐 景已已 询询询加杳请输入您的选择】7删除景点删除过程桶宋*栩*補 材*欢迎使屈 洛 阳理工学院开兀校 区校园 导 游程序*岀+岀林*衬* $+谙输人您要删除景点的编号：8删除成功！按任意键返回、删除后启大图教盂实宀南 lint X17 17J XJ 17 寿 0123456789 r -fkzL- /L /rk8修改景点信息娄新 学峯養皆 教i头实欝 0 12 3 4 5 f - 7 9i路 #.-咸 息 占xlx 章昱昼.?.占堂堅导 景两两新己已 询询词九 s_n w w w>%*%,

17、123 4 5 G o请输入您的选择!*：*#归0*辿使用洛阳玉里丁%宗开RL校区"丰专园导薰呈序水水除归1*母才*沐*最点名称$8 改改回 修修晅5 * 512 0请输入您的迪择，1修改成切!靡篦彎景点细修改后32丈黑子其其-IJ- -ij-kn- .1- li- J-lr-lr-lJ.o 1 2 3 4 s 6 ¥ 9匚口匚義 血有路踊筋 息Rlfi古古. 一点吕：41害. 占 ulwslan U協曲抽己己 询询询 查查查 2-,3.4.艮乩0.洁辅入您的诜梓;落于15,风景优美 棊境彳驢每满书香气息，呈坏形自习的地方，临近图书馆9.文件容巳餐評爲采修过的餐厅，临近实验

18、機是男女比例最适中的餐厅甯二蟲睡男生宿舍，食物种类比较多 瞬三錚镰女生宿舍楼, 比较便宜count -记事本文除艮輛（口格式Q】直看巴 g八、心得通过对这次对校园导游系统程序编写，我切实体会到了如何编写一个较大的 程序。这是我自己相对独立做的最大的一个程序，过程中遇到了各种各样的问题。 但同时稳固了课堂上所学的知识，也学到了很多新的东西，也收获了很多。拿到题目，第一步就是构思，分析，创立。题目要求用无向网完成，所以我考虑的是用邻接矩阵存储这个无向网，参考了书上的无向网的邻接矩阵存储程序写了 CreatUDN。查询两个景点之间的最短路径刚开场我参考的是书上的迪杰斯特拉算法， 后 来发现书上定义的

19、顶点的构造体数组容太简单， 程序考虑的情况也很简单，无法 满足我题目的需求，于是我又把迪杰斯特拉算法研读了一遍，自己做了改良。查找所有路径的Searchpathl函数刚开场一直没有写出来，我和同学先在纸上画出顶点，参考深度优先遍历把整个路径走了一遍，但是编程没有什么思路， 上网查找了关于这个算法的资料，看到有人说可以考虑用递归实现，就试着用递 归实现，同时参照迪杰斯特拉算法用一个数组收集访问过的顶点， 还设置了一个 标志量标记顶点是否被访问。文件在上学期的课设中我写过，当时学习了一些关于文件的知识，所以运用 并没有遇到太多问题，利用文件保存数据，需要fope n翻开文件进展读写，还要fclos

20、e函数进展关闭操作，可能还会用到fread读取文件。后来知道a+可以 继续录入，于是我通过参加一个 a+形式的语句，实现了可不定时地增加景点数据的功能所有框架写查找、删除、修改和添加函数本身并不太难，写好以后用main函数调用可以了。写出框架后，冈寸开场运行也是没什么问题的，但是多做几步就遇到了问题。在添加的时候，刚开场没有考虑序号，程序自动生成的序号和我想。要的并不是 一种，于是我在添加景点里面让游客自己输入序号。 后来又发现删除没有考虑找 不到需要删除的目标的可能性，用一个判断符a来判断是否删除成功。接下来整 个运行都没有错但是如果删除两个景点就会出现问题了，试了很久发现是循环条件有问题，

21、虽然固定了景点编号number，但是循环的num和number不能对 应，于是去询问教师，教师说可以把整个邻接矩阵重新修改或者设置特殊符号控 制输出，我选择了相对简便的修改方法。这个程序很长，编写花了很多时间，在程序编写过程中，我不断遇到困难，调试时更是出现了很多问题，一个个的修改，有的花了很长的时间。但我的努力 和辛苦没有白费，在教师的指导，同学的帮助，和自己的努力下我终于完成了这 个程序。很感教师最后的点睛之笔，在我和同学冥思苦想很长时间都没有解决方 案的时候是教师帮助我们解决了问题。同时也反映出我思考问题的不全面和经历 的欠缺。在程序编写和解决问题时，每一个细节都很重要，既要防止功能的重

22、复也要 防止功能疏漏的地方。理论和实践相结合是学好数据构造的关键，这次的课设既 培养了我们的自学能力，也提高了我们的学习兴趣。九、源程序#in elude <stri ng.h>#i nclude <stdio.h>#i nclude <malloc.h>#i nclude <stdlib.h>/*相邻接的景点之间的路程*/*定义边的类型 */#defi ne Max 20000 typedef struct ArcCell int adj;ArcCell;/*图中的顶点，即为景点 */typedef struct VertexTypeint n

23、u mber;char sight100;char descripti on1000; VertexType;typedef structVertexType vex20;/*景点编号*/*景点名称*/*景点描述*/*定义顶点的类型*/ArcCell arcs2020;/*图中的边，即为景点间的距离*/int vexnu m,arum;/*顶点数，边数 */MGraph;/*定义图的类型 */FILE *fp,*cou nt ;/*变量类型声明，声明fp是FILE型指针，用于指向file类型*/MGraph G;/*把图定义为全局变量*/char n ameofschool100;/*学校名称

24、*/int NUM=9;int P2020;/*用来存放图中的边*/int p20;/*全局数组，用来存放路径上的各顶点*/in t visited20;/*全局数组，用来记录各顶点被访问的情况*/int a=0;/*全局变量，用来记录每对顶点之间的所有路径的条数*/long int D20;/*辅助变量存储最短路径长度*/void CreateUDN(i nt v,i nt a);/*造图函数*/void n arrate();/*说明函数*/void ShortestPath(i nt nu m);/*最短路径函数*/void output(i nt sight1,i nt sight2)

25、;/*输出函数*/int Men u();void search();int SearchMe nu();void HaMiTo nian (i nt);void Searchpath1(MGraph g);void disppath(MGraph g,i nt i,i nt j);void path(MGraph g,int i,int j,int k);void NextValue(i nt);void display();int Add newsight(i nt n);int Deletesight();void Chan gesight();int Chan geme nu();in

26、t Sightme nu();/*主菜单*/ /*查询景点信息*/*查询子菜单 */*图的遍历*/*查询两个景点间的所有路径*/*确定路径上第k+1个顶点的序号*/*显示遍历结果*/*添加新的景点和路径*/*删除景点和路径*/*修改景点和路径*/*修改路径或顶点的选择菜单*/*选择需该景点的菜单*/void main()/* 主函数 */in t v0,v1;int ck;CreateUDN(NUM,11);dock=Me nu();switch(ck)case 1:search。；break;case 2:system("cls");n arrate();printf(&

27、quot;nnttt请选择起点景点0%d： ",NUM-1);scan f("%d",&v0);printf("ttt请选择终点景点0 %d： ",NUM-1);scan f("%d"，&v1);ShortestPath(v0);/*计算两个景点之间的最短路径*/output(v0,v1);/* 输出结果 */printf("nntttt请按任意键继续.n");getchar();getchar();break;case 3:system("cls"); n arrat

28、e();Searchpathl(G);printf("nntttt请按任意键继续.n");getchar();getchar();break;case 4:system("cls");n arrate();NUM=Add newsight(NUM);system("cls");n arrate();break;case 5:NUM=Deletesight();break;case 6:Chan gesight();break;while(ck!=O);int Me nu()int c;int flag; do flag=1;/*主菜单

29、*/system("cls");n arrate();prin tf("ntttprin tf("tttn");prin tf("ttt1、查询景点信息prin tf("ttt2、查询两景点间最短路径prin tf("ttt3、查询两景点间所有路线prin tf("ttt4、添加新的景点和路径prin tf("ttt5、删除已有景点和路径prin tf("ttt6、修改已有景点或路径prin tf("ttt0、退出prin tf("tttn");prin

30、tf("tttprin tf("tttt请输入您的选择：");scan f("%d",&c);if(c=1|c=2|c=3|c=4|c=5|c=6|c=0)flag=O;while(flag);return c;int SearchMenu()/*查询子菜单函数 */int c;int flag;doflag=1;system("cls");n arrate();prin tf("ntttin)1prin tf("ttt|n ”);prin tf("ttt|1、按照景点编号查询|n&qu

31、ot;);prin tf("ttt|2、按照景点名称查询|n");prin tf("ttt|0、返回|n");prin tf("ttt|prin tf("ttt1n ”);1n)1prin tf("tttt请输入您的选择：”);scan f("%d",&c);if(c=1|c=2|c=0)flag=O;while(flag);return c; void search()int num;int i;int c;char n ame20;fp=fope n( "guide.txt"

32、;,"r+");coun t=fope n("co un t.txt","r+"); dosystem("cls");c=SearchMe nu();switch (c)/*查询景点信息函数 */*读翻开原文件book.txt*/*读写count文件*/case 1:system("cls");n arrate();prin tf("nntt请输入您要查找的景点编号：”)；sca nf("%d",&n um);for(i=0;i<NUM;i+)if(n

33、um=G.vexi. nu mber)prin tf("nnttt您要查找景点信息如下：”)；prin tf("nnttt%s: %-25snn",G.vexi.sight,G.vexi.descriptio n);printf("nttt 按任意键返回.");getchar();getchar();break;if(i=NUM)prin tf("nnttt没有找到！");printf("nnttt按任意键返回.");getchar();getchar();break;case 2:system(&quo

34、t;cls");n arrate();prin tf("nntt请输入您要查找的景点名称：”)；sca nf("%s", name);for(i=0;i<NUM;i+)if(!strcmp( name,G.vexi.sight)prin tf("nnttt您要查找景点信息如下：”)；prin tf("nnttt%s:%-25snn",G.vexi.sight,G.vexi.descriptio n);printf("nttt按任意键返回.");getchar();getchar();break;if

35、(i=NUM)prin tf("nnttt没有找到！ ”);printf("nnttt按任意键返回.");getchar();getchar();break;while(c!=O);fwrite(&G,sizeof(MGraph),1,fp);/* 保存到文件中 */fclose(fp);fprin tf(cou nt,"%d",NUM);fclose(co un t);void CreateUDN(i nt v,i nt a)/*创立初始图函数 */int i,j;/调用了 fopen,要用fclose关闭if(fp=fope n(

36、"guide.txt","a+")=NULL)ticket文件保存记录的详细信息printf("文件未找到n");if(cou nt=fope n( "cou nt.txt","w+ ")=NULL)cou nt文件保存记录的条数fprin tf(cou nt,"0");elsefscan f(cou nt,"%d",&NU M);strcpy( nameofschool,"理工学院开元校区");G.vex num=v;边数*/

37、G.arum=a;for(i=0;i<20;+i) G.vexi. number=i;/*初始化构造中的景点数和/*初始化每一个景点的编号*/*初始化每一个景点名及其景点描述*/strcpy(G.vexO.sight," 大明桥");strcpy(G.vex0.descriptio n,"落于小河上，风景优美");strcpy(G.vex1.sight,"图书馆");strcpy(G.vex1.descriptio n,"环境优雅，充满书香气息，呈环形 ");strcpy(G.vex2.sight,"

38、;教学楼");strcpy（G.vex2.description," 上课和自习的地方，临近图书馆”）;strcpy（G.vex3.sight,"子衿餐厅"）;strcpy（G.vex3.descriptio n,"餐厅，新装修过的餐厅，临近实验楼，是男女比例最适中的餐厅"）;strcpy（G.vex4.sight,"实验 A 楼"）;strcpy（G.vex4.description,"教师办公室"）;strcpy（G.vex5.sight,"实验 B 楼"）;strcpy

39、（G.vex5.description,"计算机机房"）;strcpy（G.vex6.sight,"实验 C 楼"）;strcpy（G.vex6.description,"电气实验楼"）;strcpy（G.vex7.sight,"璞院餐厅"）;strcpy（G.vex7.descriptio n,"第二餐厅，临近男生宿舍，食物种类比拟多”）；strcpy（G.vex8.sight,"琇院餐厅"）;strcpy（G.vex8.descriptio n,"第三餐厅，临近女生宿舍楼

40、，比拟廉价”）；/*这里把所有的边假定为20000，含义是这两个景点之间是不可到达，极大值*/for（i=0;i<20;+i）for（j=0;j<20;+j）G.arcsi j.adj=Max;/*下边是可直接到达的景点间的距离，由于两个景点间距离是互相的，所以要对图中对称的边同时赋值。*/G.arcs01.adj=G.arcs10.adj=50;G.arcs13.adj=G.arcs31.adj=70;G.arcs06.adj=G.arcs60.adj=250;G.arcs14.adj=G.arcs41.adj=80;G.arcs24.adj=G.arcs42.adj=100;G.arcs35.adj=G.arcs53.adj=90;G.arcs52.adj=G.arcs25.adj=100;G.arcs46.adj=G.arcs64.adj=75;G.arcs47.adj=G.arcs74.adj=300;G.arcs27.adj=G.arcs72.adj=400;G.arcs78.adj=G.arcs87.adj=40;/保存到文件中fWrite(&G,sizeof(MGraph),1,fp);fclose(fp);/关闭文