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

云南大学软件学院 数据结构实验报告 （本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助） 实验难度： A B C 序号学号姓名成绩12指导教师： （签名） 学期：2012秋季学期 任课教师: 实验题目: 图及其应用 小 组 长: 联系电话: 电子邮件: 完成提交时间：2012年12月 20日云南大学软件学院2012学年 秋季 学期数据结构实验成绩考核表学号： 姓名： 本人承担角色： 小组长 评分项目评分指标分值得分实验构思（10%）1. 实验目的明确52. 实验内容理解透彻、对实验所涉及到的知识点分析到位5实验设计（15%）1. 有对基本数据结构的抽象数据类型定义52. 实验方案设计完整，数据结构、算法选择合理 53.算法结构和程序功能模块之间逻辑清晰、有相应的流程图5实验实现（25%）1. 代码编写规范、风格统一、注释清楚易读 52. 程序运行正常，测试结果正确153. 界面友好、易于操作、有较强的容错性5实验报告撰写（10%）1. 内容详实无缺漏，文字流畅、图表清楚52. 实验结果分析客观、详细，实验体会真实可信，对原实验方案的改进和对实验内容的发散性思考5个人工作量（30%）1. 个人完成工作量152. 个人技术水平103. 团队合作精神5实验运作（10%）1. 有一定用户群52. 应用前景分析5综合得分： （满分100分）指导教师： 年 月 日学号： 姓名： 本人承担角色： 组员 评分项目评分指标分值得分实验构思（10%）1. 实验目的明确52. 实验内容理解透彻、对实验所涉及到的知识点分析到位5实验设计（15%）1. 有对基本数据结构的抽象数据类型定义52. 实验方案设计完整，数据结构、算法选择合理 53.算法结构和程序功能模块之间逻辑清晰、有相应的流程图5实验实现（25%）1. 代码编写规范、风格统一、注释清楚易读 52. 程序运行正常，测试结果正确153. 界面友好、易于操作、有较强的容错性5实验报告撰写（10%）1. 内容详实无缺漏，文字流畅、图表清楚52. 实验结果分析客观、详细，实验体会真实可信，对原实验方案的改进和对实验内容的发散性思考5个人工作量（30%）1. 个人完成工作量152. 个人技术水平103. 团队合作精神5实验运作（10%）1. 有一定用户群52. 应用前景分析5综合得分： （满分100分）指导教师： 年 月 日（注：此表在难度为C时使用，每个成员一份。）一、【实验构思（Conceive）】(10%)（本部分应包括：描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设计、算法等相关知识）本实验要求设计一个校园导游系统，要求通过图这一数据结构计算两点之间的最短距离，实现校园导航功能。首先要收集校园景点信息和景点之间的距离信息，然后利用图存储校园景点信息和景点之间的距离信息，最后使用Dijkstra算法计算最短路径。 离散数学相关知识：正确合理使用与或非之间的关系，进行程序分支判断，保证程序正常进行，以及图的使用。二、【实验设计(Design)】(20%)本次实验使用C进行编写，自定义函数2个：void init_graph(graph *g)/图的初始化函数void shortest_path(graph *g,int s, int t,int n)/求最短路径的算法主函数为功能选择界面三、【实现描述（Implement）】(30%)主函数显示开始界面，选择相应的功能求最短路径。人性化设计：1. 在输入出现错误时例如功能选择错误时，程序会给出友好的提示；2. 界面友好，容易上手。四、【代码】(10%) #include#include#include#include#define INFINITY 9999 /最大距离 #define MAX_NODES 30 /最大结点数 int distMAX_NODESMAX_NODES; /distij表示i、j连线的权重 int pathMAX_NODES;using namespace std;typedef struct VertexTypechar* sight; /景点名称 /char* info; /景点描述 VertexType; /定义顶点的类型 typedef structint vexnum;VertexType vexMAX_NODES;graph;void init_graph(graph *g)int a,x,y=0;g-vexnum = 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-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-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-vex26.sight=校车乘车点; for(x=0;xvexnum;x+)for(y=0;yvexnum;y+)distxy=INFINITY;/下边是可直接到达的景点间的距离，由于两个景点间距离是互相的，所以要对图中对称的边同时赋值 dist01=dist10=10; dist12=dist21=20; dist23=dist32=20; dist14=dist41=50; dist45=dist54=200; dist46=dist64=130; dist57=dist75=600; dist58=dist85=800; dist59=dist95=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=250; 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=dist2421=110; dist2125=dist2521=750; dist2223=dist2322=40; dist2224=dist2422=120; dist2324=dist2423=60; dist241=dist124=300; void shortest_path(graph *g,int s, int t,int n) struct state int predecessor; /前驱节点 int length; /到起始点的距离 int label; stateMAX_NODES; int i,k,min,mypathMAX_NODES; struct state * p; for(p=&state0; ppredecessor = -1; p-length = INFINITY; p-label = 0; statet.length = 0; statet.label = 1; k = t; /当前工作结点 do for(i=0; in; i+) if(distki!=0 & statei.label=0) if(statek.length+distkistatei.length) statei.length = statek.length+distki; statei.predecessor = k; k=0; min=INFINITY; for(i=0; in; i+) if(statei.label=0 & statei.length=0); for(i-;i0;i-) printf(%s-,g-vexmypathi.sight); printf(%sn,g-vexmypathi.sight); printf(n距离为%d mn,min); int main()int m,s,e,c;graph g;g.vexnum = 27;init_graph(&g);printf(n=n);printf(n 呈贡云南大学校园导游 n);printf(nn);/打印景点列表 for(m=0;mg.vexnum;m+)printf(t%2d：%stt,m,g.vexm.sight);if(+m27&m!=7) printf(t%2d：%stn,m,g.vexm.sight); else if(m=7) printf(t %d：%stn,m,g.vexm.sight); else printf(n);printf(n=n);printf(ntn); printf(t n); printf(t 1、查询景点路径 n);printf(t n); printf(t 0、退出 n); printf(t n); printf(tn);while(1) printf(n=n); printf(n请输入您的选择：); scanf(%d,&c); while(!(c=0|c=1) printf(n输入非法，请重新选择：n); scanf(%d,&c); switch(c) case 0: exit(0