数据结构课程设计报告-校园导游程序.doc
《数据结构课程设计报告-校园导游程序.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计报告-校园导游程序.doc（39页珍藏版）》请在冰点文库上搜索。
洛阳理工学院
课程设计说明书
课程名称数据结构课程设计
设计课题校园导游程序
专业计算机科学与技术
班级
学号
姓名
完成日期
课程设计任务书
设计题目：
校园导游程序
设计内容与要求：
[问题描述]
用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。
要求能够回答有关景点介绍、游览路径等问题。
[基本要求]
（1）查询各景点的相关信息；
（2）查询图中任意两个景点间的最短路径。
（3）查询图中任意两个景点间的所有路径。
（4）增加、删除、更新有关景点和道路的信息。
指导教师：
2016年12月20日
课程设计评语
成绩：
指导教师：
_______________
年月日
目录
一、 问题描述 1
二、基本要求 1
三、测试数据 2
四、算法思想 3
五、模块划分 4
5.1应用函数 4
5.2.1主函数 5
5.2.2查询景点信息函数 6
5.2.3查询两景点之间最短路径函数 6
5.2.4查询两景点之间所有路径函数 7
5.2.6删除已有的顶点和路径 8
5.2.7修改已有的顶点和路径 9
六、数据结构 10
七、测试 11
八、心得 19
九、源程序 20
一、问题描述
用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。
要求能够回答有关景点介绍、游览路径等问题。
二、基本要求
（1）查询各景点的相关信息；
（2）查询图中任意两个景点间的最短路径。
（3）查询图中任意两个景点间的所有路径。
（4）增加、删除、更新有关景点和道路的信息。
三、测试数据
菜单函数：
依次输入：
1，2，3，4，5，6，0
分别对应景点信息查询，最短路径查询，所有路径查询，添加景点及路径信息，删除景点及路径信息，修改景点及路径信息，退出。
查询景点信息：
输入：
1，2
分别对应按编号查询，按景点名称查询
按编号查询：
输入编号：
1
按景点名称查询：
输入名称：
大明桥
最短路径查询：
输入起始景点和终点景点编号：
1，7
所有路径查询：
输入起始景点和终点景点编号：
2，8
添加景点及路径信息：
输入新景点序号：
9
输入新景点名称：
南门
输入新景点相关信息：
充满古韵的门，适合拍照
输入到其余各景点的距离：
50，100，20…
删除景点及路径信息：
输入：
1，2
分别对应按编号查询，按景点名称查询
按编号查询：
输入需要删除的景点编号：
8
修改景点及路径信息：
输入：
1，2
分别对应修改景点信息，修改道路信息
修改景点信息：
输入1，2
分别对应修改景点名称，修改景点描述
修改景点信息：
输入修改序号：
1
输入修改后的名称：
图书馆123
2
四、算法思想
先利用CreateUDN创建初始无向网，通过main主函数调用显示，操作功能的选择通过Menu函数输出，根据游客需求选择景点信息查询、景点之间最短路径查询、景点之间所有路径查询、添加景点信息、删除景点信息或者修改信息。
如果是景点信息查询，在search中完成，再调用SearchMenu选择是按照景点编号或者景点名称查询，游客输入相应内容。
如果是景点之间最短路径查询或是景点之间所有路径查询则游客输入起始景点和结束景点；最短路径是用ShortestPath实现，其中运用了迪杰斯特拉算法；所有路径由Searchpath1调用disppath再调用path，在path中通过递归算法实现寻找每一条路并输出。
如果是添加景点信息调用Addnewsight函数，游客按照提示依次输入信息内容。
如果是删除景点信息，选择按照名称删除或是按照序号删除，再调用Deletesight函数，游客输入相应内容进行删除。
如果是修改信息，调用Changesight，Changemenu两个函数，游客按提示选择修改景点信息或者道路信息，再按提示输入修改后得内容。
输出使用调用的相应函数。
信息保存于文件中。
校园导游图
添加景点和路径
查询所有路径
查询最短路径
修改景点和路径
修改路径
修改景点
删除景点和路径
按编号
按名称
查询景点信息
按编号
按名称
修改名称
修改描述
五、模块划分
5.1应用函数
voidCreateUDN（intv,inta）;/*造图函数*/
voidnarrate（）;/*说明函数*/
voidShortestPath（intnum）;/*最短路径函数*/
voidoutput（intsight1,intsight2）;/*输出函数*/
intMenu（）;/*主菜单*/
voidsearch（）;/*查询景点信息*/
intSearchMenu（）;/*查询子菜单*/
voidHaMiTonian（int）;/*图的遍历*/
voidSearchpath1（MGraphg）;/*查询两个景点间的所有路径*/
voiddisppath（MGraphg,inti,intj）;
voidpath（MGraphg,inti,intj,intk）;/*确定路径上第k+1个顶点的序号*/
voidNextValue（int）;
voiddisplay（）;/*显示遍历结果*/
intAddnewsight（intn）;/*添加新的景点和路径*/
intDeletesight（）;/*删除景点和路径*/
voidChangesight（）;/*修改景点和路径*/
intChangemenu（）;/*修改路径或顶点的选择菜单*/
intSightmenu（）;/*选择需该景点的菜单*/
5.2.1主函数
1.功能：
初始图通过main主函数调用显示，操作功能的选择通过Menu函数输出，显示为菜单形式提醒用户进行操作，用户选择后在main主函数中调用各个函数实现各种功能。
2.流程图：
61
01
4
3
2
1
51
输入相应序号
结束
开始
查询信息
删除信息
所有路径
添加信息
最短路径
修改信息
退出
景点信息和操作目录
5.2.2查询景点信息函数
1.功能：
在main主函数中调用search,打开存储了信息的文件，在显示界面显示已有的景点名称和序号，游客按需求进行序号查询或者名称查询，输入需要查询的序号或者名称后会显示该景点的名称及简介，而后按任意键返回上级菜单选择继续查询或者返回主界面，在查询景点信息函数中实现。
2.流程图：
no
yes
2
1
开始
按编号查询
按景点查询
结束
输入相关信息
是否有此景点？
没有找到！
输出景点信息
5.2.3查询两景点之间最短路径函数
1.功能：
在main函数中调用narrate函数，打开存储了信息的文件，游客输入起点编号或者终点编号，利用迪杰斯特拉算法由ShortestPath最短路径函数选择一条两点之间的最短路径展示给游客，关闭文件。
5.2.4查询两景点之间所有路径函数
1.功能：
当游客输入完毕后，根据之前构建的无向图，执行过程为进层和退层两个阶段。
首先开始递归进层，考虑使用基于深度优先思想，在搜素过程中，按照景点编号大小依次访问每一个节点，若访问到一个未被访问且有路径相通的点则将其加入数组P，直到找到目的地，输出第一条路径，然后开始递归退层，按照之前的方式递归访问它的所有未被访问的相邻节点。
并通过相应的设置标志visited[]的方式使最终能不重复地走遍所有的简单路径。
最后输出这些路径即可。
5.2.5添加新的顶点和路径
1.功能：
在Addnewsight添加新的景点和路径函数中实现，打开存储了信息的文件，输入需要新添加的景点名称，基本信息介绍并依次输入它到原有各景点的距离，将新信息存储到文件中并保存。
5.2.6删除已有的顶点和路径
1.功能：
删除不需要的景点信息，并保存删除后的文件，方便下一次浏览。
2．流程图：
2
1
no
结束
是否有此景点？
输入需要删除的景点
删除成功
没有找到
yes
开始
按景点编号
按景点名称
5.2.7修改已有的顶点和路径
1.功能：
修改有误的景点信息，并保存修改后的文件，方便下一次浏览。
2．流程图：
2
2
1
22
1
开始
修改道路信息
结束
输入相关信息
修改景点信息
输入道路信息
输入景点编号
修改景点名称
修改景点描述
输入相关信息
六、数据结构
MGraph定义图的类型，其中包含景点，景点之间的距离，景点数和边数。
VertexType是景点的结构体，里面包含了景点编号，景点名称，景点描述。
ArcCell是边的结构体，其中包含了边的长度即景点之间的距离。
typedefstructArcCell
{
intadj;/*相邻接的景点之间的路程*/
}ArcCell;/*定义边的类型*/
typedefstructVertexType
{
intnumber;/*景点编号*/
charsight[100];/*景点名称*/
chardescription[1000];/*景点描述*/
}VertexType;/*定义顶点的类型*/
typedefstruct
{
VertexTypevex[20];/*图中的顶点，即为景点*/
ArcCellarcs[20][20];/*图中的边，即为景点间的距离*/
intvexnum,arcnum;/*顶点数，边数*/
}MGraph;/*定义图的类型*/
七、测试
7.1.测试数据
输入：
根据游客需求选择景点信息查询、景点之间最短路径查询、景点之间所有路径查询、添加景点信息、删除景点信息或者修改信息。
如果是景点信息查询，再选择是按照景点编号或者景点名称查询，游客输入相应内容；如果是景点之间最短路径查询或是景点之间所有路径查询则游客输入起始景点和结束景点；如果是添加景点信息则按照提示依次输入信息内容；如果是删除景点信息，选择按照名称删除或是按照序号删除，再输入相应内容进行删除；如果是修改信息，按提示选择修改景点信息或者道路信息，再按提示输入修改后得内容
预期的输出结果：
运行程序直接出现各景点及其编号，同时出现操作菜单，其他结果依使用者需求而定，请参见程序后的运行结果。
1.菜单函数
2.查询景点信息（按编号）
3.查询景点信息（按名称）
4.查询两景点之间的最短路径
5.查询两点之间的所有路径
6.添加新的景点及其路径
添加过程
添加后
7.删除景点
删除过程
删除后
8.修改景点信息
修改后
9.文件内容
八、心得
通过对这次对校园导游系统程序编写，我切实体会到了如何编写一个较大的程序。
这是我自己相对独立做的最大的一个程序，过程中遇到了各种各样的问题。
但同时巩固了课堂上所学的知识，也学到了很多新的东西，也收获了很多。
拿到题目，第一步就是构思，分析，创建。
题目要求用无向网完成，所以我考虑的是用邻接矩阵存储这个无向网，参考了书上的无向网的邻接矩阵存储程序写了CreatUDN。
查询两个景点之间的最短路径刚开始我参考的是书上的迪杰斯特拉算法，后来发现书上定义的顶点的结构体数组内容太简单，程序考虑的情况也很简单，无法满足我题目的需求，于是我又把迪杰斯特拉算法研读了一遍，自己做了改进。
查找所有路径的Searchpath1函数刚开始一直没有写出来，我和同学先在纸上画出顶点，参考深度优先遍历把整个路径走了一遍，但是编程没有什么思路，上网查找了关于这个算法的资料，看到有人说可以考虑用递归实现，就试着用递归实现，同时参照迪杰斯特拉算法用一个数组收集访问过的顶点，还设置了一个标志量标记顶点是否被访问。
文件在上学期的课设中我写过，当时学习了一些关于文件的知识，所以运用并没有遇到太多问题，利用文件保存数据，需要fopen打开文件进行读写，还要fclose函数进行关闭操作，可能还会用到fread读取文件。
后来知道a+可以继续录入，于是我通过加入一个a+形式的语句，实现了可不定时地增加景点数据的功能
所有框架写查找、删除、修改和添加函数本身并不太难，写好以后用main函数调用可以了。
写出框架后，刚开始运行也是没什么问题的，但是多做几步就遇到了问题。
在添加的时候，刚开始没有考虑序号，程序自动生成的序号和我想。
要的并不是一种，于是我在添加景点里面让游客自己输入序号。
后来又发现删除没有考虑找不到需要删除的目标的可能性，用一个判断符a来判断是否删除成功。
接下来整个运行都没有错但是如果删除两个景点就会出现问题了，试了很久发现是循环条件有问题，虽然固定了景点编号number，但是循环的num和number不能对应，于是去询问老师，老师说可以把整个邻接矩阵重新修改或者设置特殊符号控制输出，我选择了相对简便的修改方法。
这个程序很长，编写花了很多时间，在程序编写过程中，我不断遇到困难，调试时更是出现了很多问题，一个个的修改，有的花了很长的时间。
但我的努力和辛苦没有白费，在老师的指导，同学的帮助，和自己的努力下我终于完成了这个程序。
很感谢老师最后的点睛之笔，在我和同学冥思苦想很长时间都没有解决方案的时候是老师帮助我们解决了问题。
同时也反映出我思考问题的不全面和经验的欠缺。
在程序编写和解决问题时，每一个细节都很重要，既要避免功能的重复也要避免功能疏漏的地方。
理论和实践相结合是学好数据结构的关键，这次的课设既培养了我们的自学能力，也提高了我们的学习兴趣。
九、源程序
#include
#include
#include
#include
#defineMax20000
typedefstructArcCell
{
intadj;/*相邻接的景点之间的路程*/
}ArcCell;/*定义边的类型*/
typedefstructVertexType
{
intnumber;/*景点编号*/
charsight[100];/*景点名称*/
chardescription[1000];/*景点描述*/
}VertexType;/*定义顶点的类型*/
typedefstruct
{
VertexTypevex[20];/*图中的顶点，即为景点*/
ArcCellarcs[20][20];/*图中的边，即为景点间的距离*/
intvexnum,arcnum;/*顶点数，边数*/
}MGraph;/*定义图的类型*/
FILE*fp,*count;/*变量类型声明，声明fp是FILE型指针，用于指向file类型*/
MGraphG;/*把图定义为全局变量*/
charnameofschool[100];/*学校名称*/
intNUM=9;
intP[20][20];/*用来存放图中的边*/
intp[20];/*全局数组，用来存放路径上的各顶点*/
intvisited[20];/*全局数组，用来记录各顶点被访问的情况*/
inta=0;/*全局变量，用来记录每对顶点之间的所有路径的条数*/
longintD[20];/*辅助变量存储最短路径长度*/
voidCreateUDN（intv,inta）;/*造图函数*/
voidnarrate（）;/*说明函数*/
voidShortestPath（intnum）;/*最短路径函数*/
voidoutput（intsight1,intsight2）;/*输出函数*/
intMenu（）;/*主菜单*/
voidsearch（）;/*查询景点信息*/
intSearchMenu（）;/*查询子菜单*/
voidHaMiTonian（int）;/*图的遍历*/
voidSearchpath1（MGraphg）;/*查询两个景点间的所有路径*/
voiddisppath（MGraphg,inti,intj）;
voidpath（MGraphg,inti,intj,intk）;/*确定路径上第k+1个顶点的序号*/
voidNextValue（int）;
voiddisplay（）;/*显示遍历结果*/
intAddnewsight（intn）;/*添加新的景点和路径*/
intDeletesight（）;/*删除景点和路径*/
voidChangesight（）;/*修改景点和路径*/
intChangemenu（）;/*修改路径或顶点的选择菜单*/
intSightmenu（）;/*选择需该景点的菜单*/
voidmain（）/*主函数*/
{
intv0,v1;
intck;
CreateUDN（NUM,11）;
do
{
ck=Menu（）;
switch（ck）
{
case1:
search（）;
升级会员 