数据结构实习报告书new

1、北 京 林 业 大 学 12 学年 13 学年第1 学期 数据结构A 实习报告书专 业： 班 级： 姓 名： 学 号： 实习地点： 信息楼 A3机房 辅导教师： 李冬梅 实习题目： 基于无向图的北林校园导游与咨询系统 实习环境： Visual C+ 实习内容：实习内容排版格式要求： 五号字，中文用宋体，英文使用Times New Roman 单倍行距，图表中的字号均为小五。实习内容从以下三方面书写：（一）实现方法1. 所用数据结构的定义及其相关说明（相关结构体或类的定义及其含义）typedef structchar name15;/定义一个结构体/char infor70;/结构体中储存景点名

2、字和信息/Map;typedef struct/定义一个新的结构体/Map *vexs; /把vexs定义成Map类型/ArcType arcsMVNumMVNum;int vexnum,arcum;AMGraph;2. 自定义函数的名称及其功能说明，函数对应算法的时间复杂度1.CreateUDN(AMGraph &G)/创建一个邻接矩阵/ o(n2)2.Infor_Output(AMGraph &G) /查询景点的相关信息/ o(n)3.Output(AMGraph &G) /输出提供服务的所有景点的输出函数/ o(n)4.ShortestPath_DIJ(AMGraph &G,int v0

3、,int v2) /求两个景点的最短路径/ o(n2)6.Password(char pd100,char pass) /密码的输入/ o(1)7.Check_password() /比较输入的数与密码是否一致/ o(1)8.Change_point(AMGraph &G) /修改景点的信息/ o(n)9.Write_infile(AMGraph &G) /写入文件函数/ o(n2)10.Int_point(AMGraph &G) /增加景点及信息的函数/ o(1)11.Int_route(AMGraph &G) /增加路径的函数/ o(n)12.Delete_point(AMGraph &G

4、) /删除景点的函数/ o(n2)13Back_Operate() /后台操作的界面/ o(1)3. 系统的功能模块图北林校园导游与咨询系统前台服务子系统后台操作子系统增加一条路径服务删除一条路径服务删除一个景点服务密码服务最短路径的查询景点信息查询修改景点信息服务增加一个景点及信息删除路径函数删除景点函数写入文件函数增加路径函数增加景点函数修改函数判断是否正确输入密码4. 相应的算法流程图求最短路径的算法流程图：13开始 mG.vexnumm=0v0=mm+输出语句：请输入你所在的景点名称把输入的名称附给sta把输入的名称附给rou输出语句:输入目的地定义sta30,rou30为char类型

5、定义i,j,v,n,m,w为int 否起点名称与已有名字比较 是 是判断vnv加1Pathv=v0则Pathv=-1让Sv=falseDv=G.arcsv0v令n=G.vexnumv=0定义min为int 类型定义数组S100,D100,Path100为int类型终点与已有名称比较mG.vexnumv2=mm+ m=0 否 是 是 否 是判断DvMaxInt 是 否i加1Sv=true;w=0 Dw=Dv+G.arcsvw判断wnSw不存在且Dv+G.arcsvwDwPathw=vw上加1min=Dvv=wwnSw不存在且DwMinIntw=0min=MaxIntDv0=0i=1使Sv0=tr

6、ue 是 否 是w加1 否 是 否 是 否i=0w不等于v0i加1i=j-1j加1aj=Pathww=Pathwj=0w=v2输出语句：最短路径定义a100为int类型 否是输出G.的数据和符号“-” 是 否输出终点，输出Dw结束 （二）实验结果粘贴程序的实际运行测试结果并加以文字说明主界面和前台服务的界面但输入的数字不正确时会有提示错误，并可重新输入查询景点小南门的信息查询路线：从小南门学二食堂的路线选择0返回到主界面进入后台操作界面要输入密码输入的密码有误，请重新输入输入正确密码后进入后台操作把小南门的信息该为小吃聚集地文件中的信息也被修改增加一个景点：西配楼，外语学

7、院办公所在地。文件中更改为 增加路径时是一条已经存在的路径时会有提示例如增加：二教-一教 100米增加一条新的路径：二教综合楼文件中：删除一条路径删除：8号楼10号楼 50米文件中：删除景点：二教文件中：与二教有关的路径也删除了从后台返回主界面（三）结论分析1. 问题与解决方法 1） 一开始是最短路径这里老有问题，就是输出的路线是倒着输出的，无法按顺序输出路径中的各个景点，在老师的提示下，我先用一个数组来存储倒着的各个景点，再把这个数组中的数据倒着输出，这就得到顺序的最短路径。 2）在路径的增加函数上，一开始无法判断增加的路径是否存在，后来我想到去邻接矩阵中去找G.arcsij是否小于MaxI

8、nt就可以判断了，要是小于那就是已存在，不小于就不存在，并直接把G.arcsij改为路径长度就好了。 3）增加景点后我忘了把增加景点与其他景点的路径初始化为最大值，这个是在答辩时程序运行错误后老师发现的问题，在那会来后，我在那个增加景点函数的后面把路径修改的代码写进去的，之后我再运行程序，发现这样就好了。2. 收获和体会 1）在花了这一个星期做着大作业后，对“从大化小，有小组大”这八个有了更深刻的体会，当初在我们看来要完成这么大的一个校园导航咨询系统真的不容易，对我而言甚至可以说是很困难的，不过在这几天以后发现其实并没有我想象中的那么困难，只要我把每一个小的部分做好，在把小的部分一个一个的组合起来就可以把大的做好了。这一次在老师的提示的，我们从小的模块开始做，我想在以后我们在碰到大的问题就应该学着老师的做法，把问题分解成小块在去进行。 2）在做着个大作业的时候，我也深入的了解了图和邻接矩阵的一些知识，尤其是邻接矩阵，我觉得邻接矩阵在存储大量的信息的很好用，查找，删除，增加等等操作也相对比较的方便迅速。不过在删除某一行某一列时就不太方便，要用循环来依次覆盖。3. 尚存在的问题1）程序的健壮性依旧不是很好，例如当我要最短路径时我若输错了名字，我的程序目前还不会提醒我输入的名称是错误的。虽然在好几个地方我都努力在加强健壮性，像在增加路径时，若路径已存在就会出现提示并要求