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

洛阳理工学院课程设计说明书课程名称数据结构课程设计设计课题校园导游程序专 业计算机科学与技术班级学号姓名完成日期查询景点信息函数功能：在main主函数中调用search,打开存储了信息的文件，在显示界面显示已 有的景点名称和序号，游客按需求进行序号查询或者名称查询，输入需要查询的 序号或者名称后会显示该景点的名称及简介，而后按任意键返同上级菜单选择继 续查询或者返回主界面，在查询景点信息函数中实现。1. 流程图:开始12查询两景点之间最短路径函数1. 功能：在main函数中调用narrate函数，打开存储了信息的文件，游客输 入起点编号或者终点编号，利用迪杰斯特拉算法由ShortestPath最短路径函数 选择一条两点之间的最短路径展示给游客，关闭文件。查询两景点之间所有路径函数1.功能：当游客输入完毕后，根据之前构建的无向图，执行过程为进层和退层两个阶段。首先开始递归进层，考虑使用基于深度优先思想，在搜素过程中， 按照景点编号大小依次访问每一个节点，若访问到一个未被访问且有路径相通的 点则将其加入数组P,直到找到目的地，输出第一条路径，然后开始递归退层， 按照之前的方式递归访问它的所有未被访问的相邻节点。并通过相应的设置标志 visitcdf的方式使最终能不重复地走遍所有的简单路径。最后输出这些路径即可。添加新的顶点和路径1. 功能：在Addncwsight添加新的景点和路径函数中实现，打开存储了信息 的文件，输入需要新添加的景点名称，基本信息介绍并依次输入它到原有各景点 的距离，将新信息存储到文件中并保存。526删除已有的顶点和路径1.功能：删除不需要的景点信息，并保存删除后的文件，方便下一次浏览。2.流程图:史 按景点名称r按景点编号527修改已有的顶点和路径功能：修改有误的景点信息，并保存修改后的文件，方便下一次浏览。1. 流程图：修改景点描述修改景点名称六、数据结构MGraph定义图的类型，其中包含景点，景点之间的距离，景点数和边数。VertexType是景点的结构体，里面包含了景点编号，景点名称，景点描述。ArcCell 是边的结构体，其中包含了边的长度即景点之间的距离。typcdcf struct ArcCcllint adj; ArcCcll;typcdcf struct VertexTypeint number;char sight 100;char description 1000; VertexType;typedef structVertexType vex 20;ArcCell arcs2020;int vexnum,arcnum;/*相邻接的景点之间的路程*/*定义边的类型*/*景点编号*/*景点名称*/*景点描述*/*定义顶点的类型*/*图中的顶点，即为景点*/*图中的边，即为景点间的距离*/*顶点数，边数*/MGraph;/*定义图的类型*/七、测试7.1.测试数据输入：根据游客需求选择景点信息查询、景点之间最短路径查询、景点之间 所有路径查询、添加景点信息、删除景点信息或者修改信息。如果是景点信息查 询，再选择是按照景点编号或者景点名称查询，游客输入相应内容；如果是景点 之间最短路径查询或是景点之间所有路径查询则游客输入起始景点和结束景点； 如果是添加景点信息则按照提示依次输入信息内容；如果是删除景点信息，选择 按照名称删除或是按照序号删除，再输入相应内容进行删除；如果是修改信息， 按提示选择修改景点信息或者道路信息，再按提示输入修改后得内容预期的输出结果：运行程序直接出现各景点及其编号，同时出现操作菜单， 其他结果依使用者需求而定，请参见程序后的运行结果。1.菜单函数*欢 迎使用洛阳理工学 院开兀校区校园导游程序*景点名称星于京验验院院大图教主实实覆012345678星于京验验院院大图教主实实覆012345678请输入您要查找的景点编号：1您要查找景点信息如下：图书馆：环境优雅，充满书香气息，呈环形按任意键返回.!主实-1 “ J1. J 、/、 /、 / ilrz、 / 012345678S itg 息点戚点 占w常 占蔓Or的有有 景两两新已已 电询询 有杳查退12 3 4 5 6 0请输入您的选择:2.查询景点信息（按编号）查询景点信息（按名称）查询两景点之间的最短路径*欢迎使用洛阳理工学院开元校区校园导游程序*sw京验验居大图教主实实蕾012345679请输入您要查找的景点名称：大明桥您要查找景点信息如下：大明桥:落于小河上，风景优美课程设计任务书设计题目：校园导游程序设计内容与要求：问题描述用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景 点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路, 存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。 基本要求(1) 查询各景点的相关信息；(2) 查询图中任意两个景点间的最短路径。(3) 查询图中任意两个景点间的所有路径。(4) 增加、删除、更新有关景点和道路的信息。指导教师：2016年12月20日课程设计评语成绩:*欢 迎使用洛阳理工学院开兀校区校园导潇程 序*C/京51子柬验验院院 大图教壬头实实寰 XJ/X/)/J/7 XI/1/7 012345678旅醒超虑虑（08） ： 1请选岸终点熹点（08） : 7从图书馆到璞院餐厅的最短路径是（最短距离为380m）图书馆一 实验A棱一璞院餐厅请按任意键继续.查询两点之间的所有路径狄近1史用冶阳字阮汁兀我四我四导源程店*柬验着院 大图教主实实覆 012345678占g点 旦意 1 出目K441 先宠tt1 一 一S 厅- 磨大大图图 _ 亍 备厅厅蚯 美buFff剪章子子子* - -r 迷验验验验完实实实实实璞Sil 123456 有其舄第第尊添加新的景点及其路径添加过程 C:UsersG Y XDesktop快命名 1.exe*欢迎使用洛阳理工学院开元校区校园导游程序*蠢验验院院 大图教主实实董 X)/ XJZ )z X)/ 1/JZ 012345678蠢验验院院 大图教主实实董 X)/ XJZ )z X)/ 1/JZ 012345678请输入新景点的序号: 离输入新景点的名称: 或漪的露*欢迎使用洛阳理工学院开元校区校园导游程序*SW柬验验院院 大图教hH头实实鬟 J/)/JZ KI/X)/)/JZ 012345678隋输入此景点到第0个景点的距离（单位：m）（同一景点或不可到达用20000表示，极大值）:*欢迎使用洛阳理工学院开元校区校园导游程序*景点名称厅厅sw螯验验院 大图教玉头实实妻南 0123456789、曰或 自5可间占队占：占；：l翼 占篁尊的有有 景两两新已已 询询询加 查查查添譬退12 3 4 5 6 0请输入您的选择:添加后删除景点删除过程*欢迎使用洛阳理工学院开元校区校园导游程序*景点名称SW蕾验验院院 大图教玉头实实寨 J/J/XI/1/J/1/J/XI/1/ 012345678删除后请输入您要删除景点的编号：8删除成功！按任意键返回.*欢迎使用洛阳理工学兀开兀校区校园导潇程序*蚤验验院件 大图教壬头实实荔南 /XJZ 1/)z s)/SI/1/K)/ 0123456789蚤验验院件 大图教壬头实实荔南 /XJZ 1/)z s)/SI/1/K)/ 0123456789蚤验验院件 大图教壬头实实荔南 /XJZ 1/)z s)/SI/1/K)/ 0123456789请输入您的选择:2. 修改景点信息*欢迎使用洛阳理工学院开元校区校园导游程序*口口口口口口大图教玉头实实曹17 )z J-X17 )/)/J/JZJZ012345679或 110苫窒昼髯 占窒善的有有 景两两新已已 询询询加 查查查添12 3 4 5 6 0请输入您的选择:修改后*欢迎使用洛阳理工学院开元校区校园导游程序*景点名称需翳后的景点名称:大图教玉头实实薯 1/J J/JZ J J/1/J XJ/ 01234567912 0占g点请输入您的选择：1修改成功!*欢迎使用洛阳理工学院开元校区校园导游程序*景点名称WSI/ VI/ YJ- JZ J K)/ 7K1/JZ 012345679sn 或占食蓑的有有t两两新已己112 3 4 5 6 03. 文件内容文件(F)编辑(E)俺0(0)查看(V)蒂助(H)落于木孺，风景优美京境4融隽满书香气息,京境4融隽满书香气息,呈环形氟驾自习的地方，临近图书馆 巳餐养衿霰修过的餐厅，临近实验楼，是男女比例最适中的餐厅皿楼昂二避斑矗男生宿舍，食物种类比较多 旱三霸毛矗女生宿舍楼，比较便宜f| count -记事本文件(F)编辑(E)格式(0)查看(V)耕助(H)9-通过对这次对校园导游系统程序编写，我切实体会到了如何编写一个较大 的程序。这是我自己相对独立做的最大的一个程序，过程中遇到了各种各样的问 题。但同时巩固了课堂上所学的知识，也学到了很多新的东西，也收获了很多。拿到题目，第一步就是构思，分析，创建。题目要求用无向网完成，所以 我考虑的是用邻接矩阵存储这个无向网，参考了书上的无向网的邻接矩阵存储程 序写了 CrcatUDNo查询两个景点之间的最短路径刚开始我参考的是书上的迪杰斯特拉算法，后 来发现书上定义的顶点的结构体数组内容太简单，程序考虑的情况也很简单，无 法满足我题目的需求，于是我乂把辿杰斯特拉算法研读了一遍，自己做了改进。查找所有路径的Searchpath 1函数刚开始一直没有写出来，我和同学先在纸 上画出顶点，参考深度优先遍历把整个路径走了一遍，但是编程没有什么思路， 上网查找了关于这个算法的资料，看到有人说可以考虑用递归实现，就试着用递 归实现，同时参照迪杰斯特拉算法用一个数组收集访问过的顶点，还设置了一个 标志量标记顶点是否被访问。文件在上学期的课设中我写过，当时学习了一些关于文件的知识，所以运用 并没有遇到太多问题，利用文件保存数据，需要fopcn打开文件进行读写，还要 fclosc函数进行关闭操作，可能还会用到frcad读取文件。后来知道a+可以继续 录入，于是我通过加入一个a+形式的语句，实现了可不定时地增加景点数据的 功能所有框架写查找、删除、修改和添加函数本身并不太难，写好以后用main 函数调用可以了。写出框架后，刚开始运行也是没什么问题的，但是多做几步就遇到了问题。在添加的日寸候，刚开始没有考虑序号，程序自动生成的序号和我想。要的并不是 一种，于是我在添加景点里面让游客自己输入序号。后来又发现删除没有考虑找 不到需要删除的目标的可能性，用一个判断符a来判断是否删除成功。接下来整 个运行都没有错但是如果删除两个景点就会出现问题了 ,试了很久发现是循环条 件有问题，虽然固定了景点编号number,但是循环的num和number不能对应， 于是去询问老师，老师说可以把整个邻接矩阵重新修改或者设置特殊符号控制输 出，我选择了相对简便的修改方法。这个程序很长，编写花了很多时间，在程序编写过程中，我不断遇到困难， 调试时更是出现了很多问题，一个个的修改，有的花了很长的时间。但我的努力 和辛苦没有白费，在老师的指导，同学的帮助，和自己的努力下我终于完成了这 个程序。很感谢老师最后的点睛之笔，在我和同学冥思苦想很长时间都没有解决 方案的时候是老师帮助我们解决了问题。同时也反映出我思考问题的不全面和经 验的欠缺。在程序编写和解决问题时，每一个细节都很重要，既要避免功能的重复也 要避免功能疏漏的地方。理论和实践相结合是学好数据结构的关键，这次的课设 既培养了我们的自学能力，也提高了我们的学习兴趣。九、源程序/*相邻接的景点之间的路程*/*定义边的类型*/*图中的顶点，即为景点*/*图中的边，即为景点间的距离*/*顶点数，边数*/*定义图的类型*/*变量类型声明，声明fp是FILE型指针，用/*把图定义为全局变量*/*学校名称*/*用来存放图中的边*/*全局数组，用来存放路径上的各顶点*/*全局数组，用来记录各顶点被访问的情况*/*全局变鬲，用来记录每对顶点之间的所有路/*辅助变量存储最短路径长度*/include #include #includc /include #define Max 20000 typcdcf struct ArcCcll int adj;ArcCell;typcdef struct VertexType (int number; char sightfl00;char description1000; VertexType;typcdcf structVc rtcxTypc vex 20;ArcCell arcs20|20; int vex num,arcnum;JMGraph;FILE *fp,*count; 于指向file类型*/ MGraph G;char namcofschool100; intNUM=9;int P2020;int p20;int visited20;int a=0; 径的条数*/ long int D20|;void CreateUDN(int v,int a); void narrate。；void ShortcstPadi(int num);/*景点编号*/*景点名称*/*景点描述*/*定义顶点的类型*/*造图函数*/*说明函数*/*最短路径函数*/指导教师：年 月 日void output(int sight1,int sight2); int MenuQ;void search0；int ScarchMcnuO；void HaMiTonian(int);void Searchpath 1 (MGraph g);void disppath(MGraph g,int i,int j); void path(MGraph g,int i,int j,int k); void NcxtValuc(int);void displayO；int Addncwsight(int n);int DeletcsightO；void Changesight();int ChangemenuO；int SightmenuO；/*输出函数*/*主菜单*/*查询景点信息*/*查询子菜单*/*图的遍历*/*查询两个景点间的所有路径*/*确定路径上第k+1个顶点的序号*/*显示遍历结果*/*添加新的景点和路径*/*删除景点和路径*/*修改景点和路径*/*修改路径或顶点的选择菜单*/*选择需该景点的菜单*/void main。/*主函数*/int vO,vl;int ck;CreateUDN(NUM,ll);dock=McnuQ; switch (ck)case 1:sc arch 0；break;case 2:system fcls);narrateQ;printf(nnttt 请选择起点景点(0d) ：”,NUM-1); scanf(%d,&vO);printf(Httt 请选择终点景点(0d)： ”,NUM-1); scanf(,%d,&vl);ShortestPath(vO);/*计算两个景点之间的最短路径*/output(vO,vl)；/* 输出结果 */printfCnntttt 请按任意键继续getcharO；gctcharQ;break;case 3:system(cls);narrateQ;Searchpath 1 (G);printf(Hnntttt 请按任意键继续 getcharQ;getcharO；break;case 4：systcmCcls，narrate。；NUM二Addncwsight(NUM);systcm(cls*);narrate 0；break;case 5:NUM二Dclctcsight。；break;case 6:ChangesightQ; break;；while(ck!=O);int MenuQ/* 主菜单 */int c;int fla敏doflag=1;systcm(cls);narrate。；printt( nttt |n ),printffttt |1 3)；printfCttt |1、查询景点信息1 )；printf(Httt |2、查询两景点间最短路径1 仍；printfCttt |3、查询两景点间所有路线1 n“)；printffttt |4、添加新的景点和路径1 n”)；printffttt |5、删除已有景点和路径1 n”)；printf(ttt |6、修改已有景点或路径1 n”)；printff*ttt |0、退出1 W)；printffttt |1 3)；printf(ttt 13）；printfCtttt请输入您的选择：，scanf(%d,&c);if(c=1 | |c=2| |c=3| |c=4| |c=5| |c=6| |c=0) flag=O;Jwhile(flag);return c;int ScarchMenuOint ScarchMenuOint ScarchMenuOint c;int flag;do(flag= 1;system(cls);narrate。；printffnttt rprintf(ttt |1 3)；printffttt |1、按照景点编号查询1 n”)；printf(”ttt |2、按照景点名称查询1 n”)；printffttt |0、返回1 W)；printfCttt |1 5”)；printf(ttt 11 仍；i E;/*查询子菜单函数*/printfftttt请输入您的选择：)； scanf(%d,&c);if(c=l | |c=2| |c=0)flag=O; while (flag);return c;void search。return c;void search。void search。/*查询景点信息函数*/int num;int i;int c;/*读打开原文件book.txt*/ /*读写count文件*/char name20;fp二fbpen(”guide.txt”, ”r+， count=fopcn(count.txt,r+); do system(clsH); c=SearchMcnu(); switch (c)case 1:systemCcls，narratcQ;printf(nntt请输入您要查找的景点编号：”)； scanf(%cl,&num);for(i 二 O;ivNUM;i+)if(num=G.vcxi.number)printfCnnttt您要查找景点信息如下：，printf(nnttt%s: %-25snn,G.vexi.sight,G.vexi.description);printfCnttt 按任意键返回.”)；getcharO；getcharO；break;if(i=NUM)printf(nnttt 没有找到! *)；printfCnnttt 按任意键返回.”)；getcharQ;getcharO；break;case 2:systemfels*);narrate。；printf(nntt请输入您要查找的景点名称：，scan f(%sn,name);for(i=0;i;if(count=fopcn(count.txt,v+ ”)二二NULL) fprintf(count,0);fvrite(&G,sizeof(MGraph),l,fp)；/* 保存到文件中 */fclosc(fp);fprintf(count,%d”,NUM); fclosc(count);void CrcatcUDN(int v,int a)int i,j；if(fjp=fopen(,guide.txt；,a+)=NULL) ticket文件保存记录的详细信息printf(”文件未找到n;if(count=fopcn(count.txt,v+ ”)二二NULL) fprintf(count,0);fclosc(fp);fprintf(count,%d”,NUM); fclosc(count);void CrcatcUDN(int v,int a)int i,j；if(fjp=fopen(,guide.txt；,a+)=NULL) ticket文件保存记录的详细信息printf(”文件未找到n;if(count=fopcn(count.txt,v+ ”)二二NULL) fprintf(count,0);fclosc(fp);fprintf(count,%d”,NUM); fclosc(count);void CrcatcUDN(int v,int a)int i,j；if(fjp=fopen(,guide.txt；,a+)=NULL) ticket文件保存记录的详细信息printf(”文件未找到n;if(count=fopcn(count.txt,v+ ”)二二NULL) fprintf(count,0);/*创建初始图函数*/调用了 fopen,要用fclose关闭/count文件保存记录的条数elsefscan F(coun t,%d ，&N U M);strcpy(namcofschool,”洛阳理工学院开元校区，/*初始化结构中的景点数和边strcpy(namcofschool,”洛阳理工学院开元校区，/*初始化结构中的景点数和边/*初始化结构中的景点数和边/*初始化结构中的景点数和边/*初始化每-个景点的编号*/G.vexnum=v;数*/G.arcnum=a;for(i=0;i20;+i) G.vexi.number=i;/*初始化每一个景点名及其景点描述*/ strcpy（G.vcxO,sight,大明桥）； srrcpy（G.vex0.description,于小河上,风景优美）； strcpy（G. vex 1 .sigh t,图书馆）； strcpy（G.vex1.description,5境优雅,充满书香气息，呈环形， strcpy(G. vex 2 .sigh t, 学楼)；strcpy(G. vex 2.description,课和自习的地方，临近图书馆”)；strcpy(G.vex3.sight,子衿餐厅，strcpy(G.vex3.dcscription,”一餐厅,新装修过的餐厅，临近实验楼,是男女比例最适中的餐 厅，strcpy(G.vex4.sight,”实验 A 楼)strcpy(G. vex 4.description,老师办公室”)；strcpy(G.vex5.sight,实验 B 楼);strcpy(G .vex 5 .description,计算机机房，strcpy(G.vex 6.sight/ 实验 C 楼，strcpy(G. vex 6.description,H 电气实验楼”)；strcpy(G.vex 7 .sigh t,璞院餐厅);strcpy(G.vcx7.dcscription,”第二餐厅，临近男生宿舍,食物种类比较多”)；strcpy(G.vex8.sight,秀院餐厅”)；strcpy(G.vex8.description；H餐厅，临近女生宿舍楼，比较便宜，/*这里把所有的边假定为20000,含义是这两个景点之间是不可到达，极大值*/for(i=0;i20;+i)for(j=0;j20;+j)G.arcsij.adj=Max;/*下边是可直接到达的景点间的距离，由于两个景点间距离是互相的，所以要对图中对称的边同时赋值。*/G.arcs0l.adj=G.arcsl0.adj=50;G.arcsl3.adj=G.arcs3l.adj=70;G.arcs06.adj=G.arcs 60.adj=250;G.arcsfl4.adj=G.arcs4l.aclj=80;G.arcs24.adj=G.arcs42.adj=100;G.arcs35.adj=G.arcs53.adj=90;G.arcs 5 2. adj=G.arcs25.adj=100;G.arcs46.adj=G.arcs64.adj=75;G.arcs47.adj=G.arcsP4.adj=300;G. arcs 2 7. adj=G. arcs 7 2 .adj=400;G.arcs78|.adj二G.arcs87.adj=40;fvrite(&G,sizeof(MGraph),1,fp);保存到文件中fclosc(fp);关闭文件，但不是屏幕fj)rintf(count,”d”,NUM);fclosc(count);void narrateO /* 说明函数 */int i;printf(nt*欢迎使用，校园导游程序*n,namcofschool);printf(tn);printf(Htttt景点名称ttttttn);printf(ttrn);for(i=0;ivNUM;i+)if(G.vexi.numbcr!=-l)printf(tttt%c (%2d)%10s%cn,3,G.vcxi.numbcr,G.vcx国.sight,3);/* 输出景点列表*/printf(ttr仍；void ShortcstPath(int num)/*迪杰斯特拉算法最短路径函数num为入口点的编号*/(int v,w,i,t;/* i、w和v为计数辅助变量*/int final20;/* 辅助数组 */int min;fp=fopcnCguidc.txt,r4-u);读打开原文件 book.txtcount=fopcn(,count.txt,r+H)；/读写 count 文件for(v=0;vNUM;v+)finalMO;/*假设从顶点num到顶点v没有最短路径*/Dv=G.arcsnumv.adj;/*将与之相关的权值放入D中存放*/for(w=0;wNUM;w+) /* 设置为空路径 */Pvw=0;if(Dv20000) /* 存在路径 */Pvnum = l;/*存在标志置为1 */Pvv=l;/*自身到自身*/Dnum=0;finalnum = l;/*初始化num顶点属于S集合*/*开始主循环，每一次求得num到某个顶点的最短路径，并将其加入到S集合*/ for(i=0;ivNUM;+i) /* 其余 G.vcxnum-1 个顶点 */min=Max; /*当前所知离顶点num的最近距离*/for (v=0; w v N U M;+w)if(!finalw) /* w 顶点在 v-s 中 */if(Dwmin) /* w顶点离num顶点更近*/v=w;min=Dv;finalv=1; /*离num顶点更近的v加入到s集合*/for(w=0;wVNUM;+、v) /*更新当前最短路径极其距离*/ if(!finalw&(min+G.arcsvw.adj)Dv)/*不在s集合，并且比以前所我到的路径都 短就更新当前路径*/Dw =min+G.arcsv w.adj;fbr(t=0;tNUM;t+)Pwt=Pvt;Plww=l; fwrite(&G,sizeof(MGraph),l ,fp);保存到文件中fclosc(fp);fprintf(count,%d”,NUM)；fclose(count);void output(int sightl,int sight2) /* 输出函数 */(inc a,b,c,d,q=0;a=sight2; /*将景点二赋值给a */if(a!=sight1) /*如果景点二不和景点一输入重合，则进行.*/printf(Hnt 从$ 到$ 的最短路径是”,G.vexsight1.sight,G.vexsight2.sight);/* 输出 提示信息*/printft(最短距离为%dm.)nnt,Da); /*输出sight!到sigh(2的最短路径长 度，存放在D数组中*/printf(t%s,G.vexsightl.sight); /* 输出景点一的名称 */d=sight1;/*将景点一的编号赋值给d */fbr(c=0;cVNUM;+c)gate:; /*标号，可以作为got。语句跳转的位置*/Pasightl=O;for(b=0;bNUM;b+)if(G.arcsdb.adj%sM,G.vexb.sight); /* 输出此节点的名称 */ q=q+1；/*计数变量加一，满8控制输出时的换行*/Plab=O;d=b;/*将b作为出发点进行下一次循环输出，如此反复*/if(q%8=0) printf(”n”)；goto gate;/*从当前位置出发*/void Searchpathl(MGraph g)/*查询两个景点间的所有路径*/