大数据结构课程设计报告材料

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

2、 问题描述 12、 基本要求 13、 测试数据 2四、算法思想 35、 模块划分 45.1.1 应用函数 45.1.2 主函数 55.1.3 查询景点信息函数 65.1.4 查询两景点之间最短路径函数 65.1.5 查询两景点之间所有路径函数 75.2.6 删除已有的顶点和路径 85.2.7 修改已有的顶点和路径 96、 数据结构 107、 测试 118、 心得 199、 源程序 20问题描述用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。二、 基本要求（1）

3、 查询各景点的相关信息；（2） 查询图中任意两个景点间的最短路径。（3） 查询图中任意两个景点间的所有路径。（4） 增加、删除、更新有关景点和道路的信息。4三、 测试数据菜单函数：依次输入：1， 2， 3， 4， 5， 6， 0分别对应景点信息查询，最短路径查询，所有路径查询，添加景点及路径信息，删除景点及路径信息，修改景点及路径信息，退出。查询景点信息：输入：1， 2分别对应按编号查询，按景点名称查询按编号查询：输入编号：1按景点名称查询：输入名称：大明桥最短路径查询：输入起始景点和终点景点编号：1， 7所有路径查询：输入起始景点和终点景点编号：2， 8添加景点及路径信息：输入新景点序号：9

4、输入新景点名称：南门输入新景点相关信息：充满古韵的门，适合拍照输入到其余各景点的距离：50, 100, 20删除景点及路径信息：输入：1， 2分别对应按编号查询，按景点名称查询按编号查询：输入需要删除的景点编号：8修改景点及路径信息：输入：1， 2分别对应修改景点信息，修改道路信息修改景点信息：输入1， 2分别对应修改景点名称，修改景点描述修改景点信息：输入修改序号：1输入修改后的名称：图书馆123四、算法思想先禾J用CreateUDN创建初始无向网，通过 main主函数调用显示，操作功能 的选择通过Menu函数输出，根据游客需求选择景点信息查询、景点之间最短路 径查询、景点之间所有路径查询、

5、添加景点信息、删除景点信息或者修改信息。 如果是景点信息查询，在search中完成，再调用SearchMenu选择是按照景点编号或者景点名称查询，游客输入相应内容。如果是景点之间最短路径查询或是 景点之间所有路径查询则游 客输入起 始景点和结 束景点；最短路径 是用ShortestPath实现，其中运用了迪杰斯特拉算法；所有路径由Searchpathl调用disppath再调用path ,在path中通过递归算法实现寻找每一条路并输出。 如果是添加景点信息调用 Addnewsight函数，游客按照提示依次输入信息内容。 如果是删除景点信息，选择按照名称删除或是按照序号删除，再调用 Delete

6、sight 函数，游客输入相应内容进行删除。如果是修改信息，调用 Changesight , ChangemenuW个函数，游客按提示选择修改景点信息或者道路信 息，再按提示输入修改后得内容。输出使用调用的相应函数。信息保存于文件中。五、 模块划分5.1 应用函数void CreateUDN(int v,int a);/*void narrate();/*void ShortestPath(int num);/*void output(int sight1,int sight2);/*int Menu();/*void search();/*int SearchMenu();/*void Ha

7、MiTonian(int);/*void Searchpath1(MGraph g);/*void disppath(MGraph g,int i,int j);void path(MGraph g,int i,int j,int k);/* void NextValue(int);void display();/*int Addnewsight(int n);/*int Deletesight();/*void Changesight();/*int Changemenu();/*int Sightmenu();/*造图函数*/说明函数*/最短路径函数*/输出函数*/主菜单 */查询景点信息

8、*/查询子菜单*/图的遍历*/查询两个景点间的所有路径*/确定路径上第k+1 个顶点的序号*/显示遍历结果*/添加新的景点和路径*/删除景点和路径*/修改景点和路径*/修改路径或顶点的选择菜单*/选择需该景点的菜单*/5.2.1主函数1 .功能：初始图通过main主函数调用显示，操作功能的选择通过 Menu函数输出, 显示为菜单形式提醒用户进行操作，用户选择后在 main主函数中调用各个函数 实现各种功能。2 .流程图：开始1T景点信息和操作目录输入相应序号55.2.2查询景点信息函数1 .功能：在main主函数中调用search,打开存储了信息的文件，在显示界面显 示已有的景点名称和序号，游

9、客按需求进行序号查询或者名称查询，输入需要查 询的序号或者名称后会显示该景点的名称及简介，而后按任意键返回上级菜单选 择继续查询或者返回主界面，在查询景点信息函数中实现。2 .流程图：按编号查询按景点查询没有找到!5.2.3 查询两景点之间最短路径函数1 .功能：在main函数中调用narrate函数，打开存储了信息的文件，游客 输入起点编号或者终点编号，利用迪杰斯特拉算法由ShortestPath最短路径函 数选择一条两点之间的最短路径展示给游客，关闭文件。5.2.4 查询两景点之间所有路径函数1 .功能：当游客输入完毕后，根据之前构建的无向图，执行过程为进层和退 层两个阶段。首先开始递归进

10、层，考虑使用基于深度优先思想，在搜素过程中， 按照景点编号大小依次访问每一个节点，若访问到一个未被访问且有路径相通的 点则将其加入数组P,直到找到目的地，输出第一条路径，然后开始递归退层， 按照之前的方式递归访问它的所有未被访问的相邻节点。并通过相应的设置标志visited口 的方式使最终能不重复地走遍所有的简单路径。最后输出这些路径即 可。5.2.5 添加新的顶点和路径1 .功能：在Addnewsight添加新的景点和路径函数 中实现，打开存储了信 息的文件，输入需要新添加的景点名称，基本信息介绍并依次输入它到原有各景 点的距离，将新信息存储到文件中并保存。75.2.6删除已有的顶点和路径1

11、 .功能：删除不需要的景点信息，并保存删除后的文件，方便下一次浏览2 .流程图：9按 景 点 编 号按景点名称没有找到删除成功结束5.2.7修改已有的顶点和路径1 .功能：修改有误的景点信息，并保存修改后的文件，方便下一次浏览2 .流程图：11修改景点信息修改道路信息输入景点编号2 ZZ输入道路信息相邻接的景点之间的路程*/定义边的类型*/景点编号*/景点名称*/景点描述*/定义顶点的类型*/typedef structVertexType vex20;ArcCell arcs2020; /* int vexnum,arcnum;MGraph;六、 数据结构MGraph义图的类型，其中包含景点

12、，景点之间的距离，景点数和边数 VertexType 是景点的结构体，里面包含了景点编号，景点名称，景点描述。ArcCell 是边的结构体，其中包含了边的长度即景点之间的距离。typedef struct ArcCellint adj;/*ArcCell;/*typedef struct VertexTypeint number;/*char sight100;/*char description1000;/*VertexType;/*/*图中的顶点，即为景点*/图中的边，即为景点间的距离*/*顶点数，边数*/*定义图的类型*/41七、测试7.1. 测试数据输入：根据游客需求选择景点信息查询、

13、景点之间最短路径查询、景点之间 所有路径查询、添加景点信息、删除景点信息或者修改信息。如果是景点信息查 询，再选择是按照景点编号或者景点名称查询，游客输入相应内容；如果是景点之间最短路径查询或是景点之间所有路径查询则游客输入起始景点和结束景点； 如果是添加景点信息则按照提示依次输入信息内容；如果是删除景点信息，选择按照名称删除或是按照序号删除，再输入相应内容进行删除；如果是修改信息， 按提示选择修改景点信息或者道路信息，再按提示输入修改后得内容预期的输出结果：运行程序直接出现各景点及其编号，同时出现操作菜单， 其他结果依使用者需求而定，请参见程序后的运行结果。1 .菜单函数特*欢迎使用格口理工

14、学院开兀校区校园导游程序*匚n匚房所聿. 息点In.点占；.寻詈京 占宜曾的有有 景两两酉已 询询询淼甯 普查查% ， 粕、 1234560请输入您的选择:2 .查询景点信息（按编号）* *水* *冰*欢迎使用洛阳理工学阮开兀校区校园导游程序*杭* * 千黎验验院院 大图教主实实裳 ,I，、>/ / !/ !/ !/ 11；. J. 012345678请输入您要查找的景点编号：1您要查找景点信息如下：图书馆：环境优雅，充满书香气息呈环形按任意键返回.3 .查询景点信息（按名称）*宓*京*配*欢迎 使用洛阳理工学 院开元校 区校园导游程 序*一一z7 012345679§i 请输

15、入您要查找的景点名称：大明桥您要查找景点信息如下：大明桥:落于小河上，风景优美4 .查询两景点之间的最短路径*欢迎使用洛阳理工学院开元校区校园导湍程序外*¥*景点名称主R圭DE012345678g1T,¥ss点点早量成点点起终¥x.J、：.-选选从图书馆到璞院餐厅的最短路径是（最短距离为330nc） 图书馆一 实验A楼一璞院督厅请按任意键继续一.5.查询两点之间的所有路径错髓盒I攵学楼到瓒院餐厅的所有游览品胭有：学亶雪院院 致子AH王签一17 XJr 012345678院明> > > > > 一 一一 亍 ttJT-JT-甲缸 香-&

16、#171;-.嘲答卷兀 璞子子 Ig-s-k*堂坊护Bf眇,眇Bf餐楼嘴楼喽楼褛 a孟SS孟孟子 ,TPIP 二工JP-M二£三 IFJSSB1234566.添加新的景点及其路径添加过程4 C:UsersG ¥ XDesktQpnpLexe*东*欢迎使用落阳理院开兀校区校园导三方程序*木*水水水IZH明小学靠验验院院大图教rH头实实最012345678ABC行褛褛褛一JTJf展输入新景点的序号'so1曾呼入新景点的名称 童年入新景点的木 龙曙古矗的门，:“请输入此景点到第。个景点的距离（单位=Q （同一景点或不可到达用2QQ00表示,极大值）, 50添加后*欢迎使用

17、洛B日理工学院开兀校区校园导游程序杼杼*景点名称口口口口 事于嘉验验院国 畜教PH头实实 0123456789 /k fk zk fk rv/k/k zk 8US短日或 息点点 每位篁量壹区 点豆量0?的有有 景BW新已已 询询询加 查查查添、工X% 、 1224560请输入您的选择:7 .删除景点 删除过程*冰*本欢迎使用1：3阳理工学院开元校区校园导游程序*林*欢迎使用洛阳理工学院开元校区校园导游程序* * *(mtABC嘘验偿 啬教主实实鬟Ylzulz-XJk)/ 012345678请输入您要删除景点的编号：8删除成功！按任意键返回.一删除后1路 日或 息点点点 141点星壹蒿 点豆量早

18、的春 景两两新已已 询询询加 查杳香_添® 、，、 12 3 4 5 6 0请输入您的选择:8 .修改景点信息*欢迎使用 洛 阳理工学院开兀校区校园导游程序*海强人修改后的景点名机 图书馆123验验悍 大图教子其实实璞南 0 12345679/fx fl-yx-(-/1请输入您的选择：1修改成功!修改后*/：.：.：.：*：*欢迎使用洛阳理工学院开元校区校园导游程序*：*籥脸验博 而图教主头实mSMSI/ XJr Y/ 012345679nnnn34-n-息用点点点 省堂置量早 占宜£早的WP =克两翳已已 询询询加 查查查12 3 4 5 6 0请输入您的选择:9 .文件

19、内容 n T . r 文件的编4(E)梢式(0)查看的帮助(H)落于小河上，风景优美 暴期鬻嘤行书香气息，呈环形课和自习的地方，临近图书馆 子衿餐五一餐厅，薪装修过的餐厅，临近实验楼，是男女比例最适中的餐厅 t实燧楼 老师办公室 实验B楼计算机机房矗矗楼聂二祟儒男生宿舍，食物种类比较多 另三第寓女生宿舍楼，比较便宜-I count -记事本文件旧编瑁(E) 格式Q)查看凹帮助(H)9八、 心得通过对这次对校园导游系统程序编写，我切实体会到了如何编写一个较大的程序。 这是我自己相对独立做的最大的一个程序，过程中遇到了各种各样的问题。但同时巩固了课堂上所学的知识，也学到了很多新的东西，也收获了很多

20、。拿到题目，第一步就是构思，分析，创建。题目要求用无向网完成，所以我考虑的是用邻接矩阵存储这个无向网，参考了书上的无向网的邻接矩阵存储程序写了CreatUDN。查询两个景点之间的最短路径刚开始我参考的是书上的迪杰斯特拉算法，后来发现书上定义的顶点的结构体数组内容太简单，程序考虑的情况也很简单，无法满足我题目的需求，于是我又把迪杰斯特拉算法研读了一遍，自己做了改进。查找所有路径的Searchpath1 函数刚开始一直没有写出来，我和同学先在纸上画出顶点，参考深度优先遍历把整个路径走了一遍，但是编程没有什么思路，上网查找了关于这个算法的资料，看到有人说可以考虑用递归实现，就试着用递归实现， 同时参

21、照迪杰斯特拉算法用一个数组收集访问过的顶点，还设置了一个标志量标记顶点是否被访问。文件在上学期的课设中我写过，当时学习了一些关于文件的知识，所以运用并没有遇到太多问题，利用文件保存数据，需要 fopen 打开文件进行读写，还要fclose函数进行关闭操作，可能还会用到 fread读取文件。后来知道a+可以继 续录入，于是我通过加入一个 a+形式的语句，实现了可不定时地增加景点数据 的功能所有框架写查找、删除、修改和添加函数本身并不太难，写好以后用main函数调用可以了。写出框架后，刚开始运行也是没什么问题的，但是多做几步就遇到了问题。在添加的时候，刚开始没有考虑序号，程序自动生成的序号和我想。

22、要的并不是一种， 于是我在添加景点里面让游客自己输入序号。后来又发现删除没有考虑找不到需要删除的目标的可能性，用一个判断符a 来判断是否删除成功。接下来整个运行都没有错但是如果删除两个景点就会出现问题了，试了很久发现是循环条件有问题，虽然固定了景点编号 number,但是循环的numffi number不能对应，于是去询问老师，老师说可以把整个邻接矩阵重新修改或者设置特殊符号控制输出，我选择了相对简便的修改方法。这个程序很长，编写花了很多时间，在程序编写过程中，我不断遇到困难，调试时更是出现了很多问题，一个个的修改，有的花了很长的时间。但我的努力和辛苦没有白费，在老师的指导，同学的帮助，和自己

23、的努力下我终于完成了这个程序。 很感谢老师最后的点睛之笔，在我和同学冥思苦想很长时间都没有解决方案的时候是老师帮助我们解决了问题。同时也反映出我思考问题的不全面和经验的欠缺。在程序编写和解决问题时，每一个细节都很重要，既要避免功能的重复也要避免功能疏漏的地方。理论和实践相结合是学好数据结构的关键，这次的课设既培养了我们的自学能力，也提高了我们的学习兴趣。九、 源程序#include <string.h>#include <stdio.h>#include <malloc.h>#include <stdlib.h>#define Max 20000

24、typedef struct ArcCell相邻接的景点之间的路程*/定义边的类型*/int adj;/*ArcCell;/*typedef structVertexType vex20;/*ArcCell arcs2020;/*int vexnum,arcnum;/*MGraph;/*FILE *fp,*count ;/*用于指向file 类型 */MGraph G;/*char nameofschool100;/*int NUM=9;int P2020;/*int p20;/*int visited20;/*/int a=0;/*路径的条数*/long int D20;/*图中的顶点，即为

25、景点*/图中的边，即为景点间的距离*/顶点数，边数*/定义图的类型*/变量类型声明，声明fp 是 FILE 型指针，把图定义为全局变量*/学校名称*/用来存放图中的边*/全局数组，用来存放路径上的各顶点*/全局数组，用来记录各顶点被访问的情况全局变量，用来记录每对顶点之间的所有辅助变量存储最短路径长度*/void CreateUDN(int v,int a);/*void narrate();/*造图函数*/说明函数*/typedef struct VertexType int number;/*景点编号*/char sight100;/*景点名称*/char description1000;

26、/*景点描述*/VertexType;/*定义顶点的类型*/void ShortestPath(int num);/*void output(int sight1,int sight2);/*int Menu();/*void search();/*int SearchMenu();/*void HaMiTonian(int);/*void Searchpath1(MGraph g);/*void disppath(MGraph g,int i,int j);void path(MGraph g,int i,int j,int k); /* void NextValue(int); void

27、display();int Addnewsight(int n); int Deletesight();void Changesight(); int Changemenu(); int Sightmenu();void main() int v0,v1; int ck;CreateUDN(NUM,11); do ck=Menu(); switch(ck) case 1: search(); break; case 2: system("cls"); narrate(); printf("nnttt scanf("%d",&v0); p

28、rintf("ttt scanf("%d",&v1); ShortestPath(v0); output(v0,v1); printf("nntttt getchar(); getchar();break;/*/*/*/*/*/*/*最短路径函数*/输出函数*/主菜单 */查询景点信息*/查询子菜单*/图的遍历*/查询两个景点间的所有路径*/确定路径上第k+1 个顶点的序号*/显示遍历结果*/添加新的景点和路径*/删除景点和路径*/修改景点和路径*/修改路径或顶点的选择菜单*/选择需该景点的菜单*/主函数 */请选择起点景点（。%。： "

29、;,NUM-1）;请选择终点景点（0%d）: ",NUM-1）;/*计算两个景点之间的最短路径*/*输出结果*/请按任意键继续.n"）;system("cls");narrate();Searchpath1(G);printf("nntttt请按任意键继续.n");getchar();getchar();break;case 3:system("cls");narrate();NUM=Addnewsight(NUM);system("cls");narrate();break;case 4:NU

30、M=Deletesight();break;case 5:Changesight();break;while(ck!=0);int Menu()/*主菜单 */int c;int flag;doflag=1;system("cls");narrate();printf("nttt n")；printf("ttt11 n")；printf("tttI 1、查询景点信息1 n")；printf("tttI 2、查询两景点间最短路径1 n")；printf("tttI 3、查询两景点间所有路

31、线1 n")；printf("tttI 4、添加新的景点和路径1 n")；printf("tttI 5、删除已有景点和路径1 n")；printf("tttI 6、修改已有景点或路径1 n")；printf("tttI 0、退出1 n")；printf("ttt11 n")；printf("ttt11n");printf("tttt请输入您的选择：");scanf("%d",&c);if(c=1|c=2|c=3|c=4

32、|c=5|c=6|c=0)flag=0;while(flag);return c;int SearchMenu()/*int c;int flag;doflag=1;system("cls");查询子菜单函数*/printf("nttti n");printf("ttt11 n");printf("ttt11、按照景点编号查询I n");printf("ttt12、按照景点名称查询I n");printf("ttt0、返回n");printf("ttt11 n&qu

33、ot;);printf("ttt11n");narrate();printf("tttt请输入您的选择：");scanf("%d",&c);if(c=1|c=2|c=0)flag=0;while(flag);return c;void search()/*int num;int i; int c; char name20;fp=fopen("guide.txt","r+");/*count=fopen("count.txt","r+");/*do

34、system("cls"); c=SearchMenu();查询景点信息函数*/读打开原文件book.txt*/ 读写count文件*/switch (c)case 1:system("cls");narrate();printf("nntt请输入您要查找的景点编号：");scanf("%d",&num);for(i=0;i<NUM;i+)if(num=G.vexi.number)printf("nnttt您要查找景点信息如下:");printf("nnttt%s: %-

35、25snn",G.vexi.sight,G.vexi.description);printf("nttt按任意键返回.");getchar();getchar();break;if(i=NUM)printf("nnttt没有找到！");printf("nnttt按任意键返回.");getchar();getchar();break;case 2:system("cls");narrate();printf("nntt请输入您要查找的景点名称：");scanf("%s"

36、;,name);for(i=0;i<NUM;i+)if(!strcmp(name,G.vexi.sight)printf("nnttt您要查找景点信息如下:");printf("nnttt%s:%-25snn",G.vexi.sight,G.vexi.description);printf("nttt按任意键返回.");getchar();getchar();break;if(i=NUM)printf("nnttt没有找到！");printf("nnttt按任意键返回.");getchar

37、();getchar();break;while(c!=0);fwrite(&G,sizeof(MGraph),1,fp); /*保存到文件中*/fclose(fp);fprintf(count,"%d",NUM);fclose(count);void CreateUDN(int v,int a)/*int i,j;if(fp=fopen("guide.txt","a+")=NULL) /ticket 文件保存记录的详细信息printf(" 文件未找到n");if(count=fopen("cou

38、nt.txt","w+ ")=NULL) /countfprintf(count,"0");创建初始图函数*/调用了 fopen, 要用 fclose 关闭文件保存记录的条数elsefscanf(count,"%d",&NUM);strcpy(nameofschool," 洛阳理工学院开元校区");G.vexnum=v;/*数 */G.arcnum=a;for(i=0;i<20;+i) G.vexi.number=i; /*/初始化结构中的景点数和边初始化每一个景点的编号/* 初始化每一个景

39、点名及其景点描述*/strcpy（G.vex0.sight," 大明桥 "）;strcpy（G.vex0.description," 落于小河上，风景优美"）;strcpy(G.vex1.sight," strcpy(G.vex1.description," strcpy(G.vex2.sight," strcpy(G.vex2.description," strcpy(G.vex3.sight," strcpy(G.vex3.description," ");strcpy(G.vex

40、4.sight," strcpy(G.vex4.description," strcpy(G.vex5.sight," strcpy(G.vex5.description," strcpy(G.vex6.sight," strcpy(G.vex6.description," strcpy(G.vex7.sight," strcpy(G.vex7.description," strcpy(G.vex8.sight,"strcpy(G.vex8.description," /* 这里把所有的边假定为

41、图书馆");环境优雅，充满书香气息，呈环形");教学楼");上课和自习的地方, 临近图书馆");子衿餐厅");一餐厅，新装修过的餐厅，临近实验楼，实验A楼)老师办公室");实验 B 楼 ");计算机机房");实验C楼)电气实验楼");璞院餐厅");第二餐厅，临近男生宿舍，食物种类比较多琇院餐厅");20000，含义是这两个景点之间是不可到达是男女比例最适");第三餐厅，临近女生宿舍楼，比较便宜");, 极大值 */for(i=0;i<20;+i)for(j=0

42、;j<20;+j)G.arcsij.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.a

43、rcs64.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); /关闭文件, 但不是屏幕fprintf(count,"%d",NUM);fclose(count);void narrate() /* 说明函数*/ int i;printf("nt*欢 迎 使 用 %s 校 园 导 游 程 序*n",nameo

44、fschool);printf("tn"); printf("tttt景点名称ttttttn");printf("tttn");for(i=0;i<NUM;i+)if(G.vexi.number!=-1) printf("tttt%c(%2d)%-10s%cn",3,G.vexi.number,G.vexi.sight,3);/* 输出景点列表*/ printf("tttn");void ShortestPath(int num) /*点的编号*/int v,w,i,t;/* iint f

45、inal20;/*int min;fp=fopen("guide.txt","r+"); /count=fopen("count.txt","r+"); /迪杰斯特拉算法最短路径函数num 为入口、w和v为计数辅助变量*/辅助数组*/读打开原文件book.txt读写 count 文件for(v=0;v<NUM;v+)finalv=0; /*Dv=G.arcsnumv.adj;/*for(w=0;w<NUM;w+) /*假设从顶点num到顶点v没有最短路径*/将与之相关的权值放入D中存放*/设置为空路径*

46、/Pvw=0;if(Dv<20000) /* 存在路径*/Pvnum=1; /* 存在标志置为1 */Pvv=1; /* 自身到自身*/Dnum=0;finalnum=1; /*初始化num顶点属于S集合*/* 开始主循环，每一次求得num到某个顶点的最短路径，并将其加入到S集合*/for(i=0;i<NUM;+i) /*其余 G.vexnum-1 个顶点 */min=Max; /*当前所知离顶点 num的最近距离*/for(w=0;w<NUM;+w) if(!finalw) /* w if(Dw<min) /* w v=w;min=Dw;finalv=1; /*顶点在

47、 v-s 中 */顶点离num顶点更近*/离num顶点更近的v加入到s集合*/for(w=0;w<NUM;+w) /* 更新当前最短路径极其距离*/保存到文件中不在 s 集合， 并且比以前所找到if(!finalw&&(min+G.arcsvw.adj)<Dw)/*/Dw=min+G.arcsvw.adj;for(t=0;t<NUM;t+)Pwt=Pvt;Pww=1;fwrite(&G,sizeof(MGraph),1,fp); / fclose(fp);fprintf(count,"%d",NUM); fclose(count);

48、void output(int sight1,int sight2) /*输出函数*/int a,b,c,d,q=0;a=sight2; /* 将景点二赋值给a */if(a!=sight1) /*如果景点二不和景点一输入重合，则进行. */printf("nt从 %s 到 %s 的 最 短 路 径 是",G.vexsight1.sight,G.vexsight2.sight);/*输出提示信息*/printf("t(最短距离为%dm.)nnt",Da); /*输出 sight1 到 sight2 的最短路径长度，存放在D 数组中 */printf(&q

49、uot;t%s",G.vexsight1.sight); /*输出景点一的名称*/d=sight1; /*将景点一的编号赋值给d */for(c=0;c<NUM;+c) gate:; /*标号，可以作为goto 语句跳转的位置*/Pasight1=0;for(b=0;b<NUM;b+) if(G.arcsdb.adj<20000&&Pab) /*如果景点一和它的一个临界点之间存在路径且最短路径*/printf("->%s",G.vexb.sight); /*输出此节点的名称*/q=q+1;/*计数变量加一，满8 控制输出时的

50、换行*/Pab=0; d=b; /*将 b 作为出发点进行下一次循环输出，如此反复*/if(q%8=0) printf("n"); goto gate; /*从当前位置出发*/ void Searchpath1(MGraph g)/* 查询两个景点间的所有路径*/int l=0;int k=0;int i,j;fp=fopen("guide.txt","r+");/读打开原文件book.txtcount=fopen("count.txt","r+");/读写 count 文件printf(&qu

51、ot;选择出发景点：");scanf("%d",&i); printf("选择目地景点：");scanf("%d",&j); for(;k<g.vexnum;k+)/*g.vexnumber 表示网中的顶点个数*/if(i=g.vexk.number) i=k;/* 在网中找到其编号与输入的出发景点的编号相同的顶点*/for(;l<g.vexnum;l+) if(j=g.vexl.number) j=l;/* 在网中找到其编号与输入的目地景点的编号相同的顶点*/ printf("n 从

52、%s 到 %s 的 所 有 游 览 路 径 有 :nn",g.vexi.sight,g.vexj.sight);/*输出出发景点和目地景点的名称*/disppath(g,i,j);/* 调用 disppath 函数 , 用来输出两个景点间的所有路径*/fwrite(&G,sizeof(MGraph),1,fp); /保存到文件中fclose(fp); fprintf(count,"%d",NUM); fclose(count); void disppath(MGraph g,int i,int j)int k;p0=i;/ 把i赋2P0 , P是一条道路上

53、的所有景点的数组for(k=0;k<g.vexnum;k+)visitedi=0;/* 初始化各顶点的访问标志位，即都为未访问过的*/a=0;/* 初始化路径的条数*/path(g,i,j,0);/* 通过调用path 函数，找到从vi 到 vj 的所有路径并输出*/ void path(MGraph g,int i,int j,int k)/* 确定路径上第k+1 个顶点的序号*/int s;if(pk=j)/* 找到一条路径*/a+;/* 路径的条数值加1*/printf("第 条:t",a);for(s=0;s<=k-1;s+) /* 输出一条路径,s 是顶点