云南大学软件学院大数据结构实验报告材料六

1、云南大学软件学院数据结构实验报告序号学号成绩12指导教师：（签名）（本实验项目方案受 教育部人才培养模式创新实验区（X3108005 ） ”项目资助） C 实验难度：AOB学 期：2012秋季学期任课教师：实验题目：图及其应用小组长:联系：电子:完成提交时间：2012年12月20日大学软件学院2012学年秋季学期数据结构实验成绩考核表学号：本人承担角色：小组长评分项目评分指标分值得分实验构思（10%）1.实验目的明确52.实验容理解透彻、对实验所涉及 到的知识点分析到位5实验设计（15%）1.有对基本数据结构的抽象数据 类型定义52.实验方案设计完整，数据结构、 算法选择合理53.算法结构和程

2、序功能模块之间逻 辑清晰、有相应的流程图5实验实现（25%）1.代码编写规、风格统一、注释清 楚易读52.程序运行正常，测试结果正确153.界面友好、易于操作、有较强的 容错性5实验报告撰写（10%）1.容详实无缺漏，文字流畅、图表 清楚52.实验结果分析客观、详细，实验 体会真实可信，对原实验方案的改 进和对实验容的发散性思考5个人工作量（30%）1.个人完成工作量152.个人技术水平103.团队合作精神5实验运作（10%）1.有一定用户群52.应用前景分析5综合得分：（满分100分）指导教师：年 月日学号： _: 本人承担角色： 组员评分项目评分指标分值得分实验构思（10%）1.实验目的明

3、确52.实验容理解透彻、对实验所涉及 到的知识点分析到位5实验设计（15%）1.有对基本数据结构的抽象数据 类型定义52.实验方案设计完整，数据结构、5算法选择合理3.算法结构和程序功能模块之间逻 辑清晰、有相应的流程图5实验实现(25%)1.代码编写规、风格统一、注释清 楚易读52.程序运行正常，测试结果正确153.界面友好、易于操作、有较强的 容错性5实验报告撰写(10%)1.容详实无缺漏，文字流畅、图表 清楚52.实验结果分析客观、详细，实验 体会真实可信，对原实验方案的改 进和对实验容的发散性思考5个人工作量(30%)1.个人完成工作量152.个人技术水平103.团队合作精神5实验运作

4、(10%)1.有一定用户群52.应用前景分析5综合得分：(满分100分)指导教师：(注：此表在难度为 C时使用，每个成员一份。)一、【实验构思(Conceive )】(10%)(本部分应包括：描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设计、算法等相 关知识)本实验要求设计一个校园导游系统，要求通过图这一数据结构计算两点之间的最短距离，实现校园 导航功能。首先要收集校园景点信息和景点之间的距离信息，然后利用图存储校园景点信息和景点之间的距离信息，最后使用Dijkstra 算法计算最短路径。离散数学相关知识：正确合理使用与或非之间的关系，进行程序分支判断，保证程序正常进行，以 及

5、图的使用。二、【实验设计(Design)】(20%)本次实验使用C进行编写，自定义函数2个:void ini t_graph(graph *g)图的初始化函数求最短路径的算法void shortest_path(graph *g,i nt s, int t,i nt n)主函数为功能选择界面、【实现描述(Implement )】(30%)主函数显示开始界面，选择相应的功能求最短路径。024 680246 80246 111112222西广邦醬服楼院大生乘楼 点 务 道门 车堂 肓市 公S4- 831 灵止苑苑苑苑件霞汇番 白云$聘寥器'C:Use rsA dminist rjtor D

6、es Icto 皂比 '呈贡云南大学校园导游工三三三三三三三竺三三三三 M 三三三三三三三 M三三三三三三竺三三三三三三M 三三三三三三竺三三三三三三三三竺M请输入您的选择I4 IiriI"C :U &e rs Ad miinistratorXDes Icto p卑瞌 2 启 xe'搂帀 公 "帀 超苑苑件恶汇矍 更仃文帝13579-1351111122 2楼 点 务 道门 车 堂服楼院大北堂乘 知综召至云余套 0 246 80246 1 11112222距离为1M0 n请输入您的选择: 扌I请输入您的选择21输入出发点与结束点：8 1?从"

7、;格物楼"到“行政办公楼"的最短路径为格物楼-综合服务楼-楸苑-> 力行機明远楼-至公大道行政办公楼人性化设计:1. 在输入出现错误时例如功能选择错误时，程序会给出友好的提示;i C:JsersAdmini5tr3tQrDesktoHi. 1=1 回 查询景点路胫 0S退岀请输入您的选择i i输入出发点与结束点：1 1输入非法.请重新选择：arn2. 界面友好，容易上手四、【代码】(10%)#in clude<iostream>#i nclude<stdio.h>#i nclude<stdlib.h>最大距离最大结点数表示i、j连线

8、的权重#i nclude<wi ndows.h>#defi ne INFINITY 9999/#defi ne MAX_NODES 30/int distMAX_NODESMAX_NODES; distij in t pathMAX_NODES;using n amespace std;typedef struct VertexType char* sight; /景点名称/char* i nfo; /景点描述VertexType; /定义顶点的类型typedef structint vex num;VertexType vexMAX_NODES;graph;void ini t_

9、graph(graph *g)-int a,x,y=0; g->vex num = 27;g->vex0.sight="云大西二门”g->vex1.sight="百家道"g->vex2.sight="文典广场”；g->vex3.sight="云大会堂"g->vex4.sight="邦翰楼"g->vex5.sight="仰止楼"g->vex6.sight="桦苑"g->vex7.sight="楠苑"g-&

10、gt;vex8.sight="格物楼"g->vex9.sight="楠苑体育场"g->vex10.sight="知味堂"g->vex11.sight="楠苑超市"g->vex12.sight="综合服务楼"g->vex13.sight="楸苑"g->vex14.sight="力行楼"g->vex15.sight="软件楼"g->vex16.sight="校医院"g-&g

11、t;vex17.sight="明远楼"g->vex18.sight="至公大道"g->vex19.sight="行政办公楼"g->vex20.sight="云大北门"g->vex21.sight="文汇楼"g->vex22.sight="余味堂"g->vex23.sight="梓苑超市"g->vex24.sight="梓苑"g->vex25.sight="钟楼"g-&g

12、t;vex26.sight="校车乘车点"for(x=0;x<g->vex nu m;x+)for(y=0;y<g->vex num ;y+)dist x y=INFINITY;/下边是可直接到达的景点间的距离，由于两个景点间距离是互相的，所以要对图中对称的边同时赋值dist01=dist10=10;dist12=dist21=20;dist23=dist32=20;dist14=dist41=50;dist4 5=dist54=200;dist46=dist64=130;dist57=dist7 5=600;dist58=dist8 5=800;d

13、ist59=dist9 5=600;dist78=dist87=100;dist79=dist97=600;dist710=dist107=150;dist711=dist117=110;dist712=dist127=100;dist812=dist128=80;dist911=dist119=700;dist1011=dist1110=5;dist1012=dist1210=50;dist1013=dist1310=150;dist1213=dist1312=100;dist1226=dist2612=20;dist1314=dist1413=200;dist1315=dist1513=2

14、50;dist1316=dist1613=700;dist1326=dist2613=100;dist1415=dist1514=20;dist1416=dist1614=500;dist1417=dist1714=1500;dist1617=dist1716=1300;dist1718=dist1817=50;dist1725=dist2517=300;dist1819=dist1918=30;dist1920=dist2019=100;dist2021=dist2120=950;dist2022=dist2220=900;dist2122=dist2221=150;dist2124=dis

15、t2421=110;dist2125=dist2521=750; dist2223=dist2322=40;dist2224=dist2422=120;dist2324=dist2423=60;dist241=dist124=300;void shortest_path(graph *g,i nt s, int t,i nt n) -struct state 二int predecessor; /前驱节点in t le ngth;II到起始点的距离in t label;stateMAX_NODES;int i,k,min,mypathMAX_NODES;struct state * p;for

16、(p=&；state0; p<&staten; p+)p->predecessor = -1;p->le ngth = INFINITY;p->label = 0;statet.le ngth = 0;statet.label = 1;k = t; II当前工作结点dofor(i=0; i<n; i+)if(distki!=O && statei.label=0)if(statek.le ngth+distki<statei.le ngth)statei.le ngth = statek.le ngth+distki; sta

17、tei.predecessor = k;k=0;mi n=INFINITY;for(i=0; i<n; i+)if(statei.label=0 && statei.le ngth<mi n)k=i;min=statei.le ngth;statek.label = 1;while(k!=s);i=0;k=s;dopathi = k;k = statek.predecessor; mypathi=pathi;i+；while(k>=0);for(i-;i>0;i-)prin tf("%s->",g->vexmypathi.

18、sight); prin tf("%sn",g->vexmypathi.sight);printf("n距离为 %d mn”,min);int mai n()int m,s,e,c;graph g;g.vex num = 27;ini t_graph(&g);prin tf("n=n"); prin tf("n呈贡大学校园导游n");prin tf("nn");/打印景点列表for(m=0;m<g.vex num ;m+)printf("t%2d: %stt",m,g.vexm.sight);if(+m<27&&m!=7)printf("t%2d: %stn",m,g.vexm.sight);else if(m=7)printf("t %d: %stn",m,g.vexm.sight);elseprin tf("n ”);prin