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

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

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

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

4、1.个人完成工作量152.个人技术水平103.团队合作精神5实验运作 (10%)1.有f用户群52.应用前景分析5综合得分：(满分100分)指导教师：年 月 日(注：此表在难度为 C时使用，每个成员一份。)一、【实验构思(Conceive )1 (10%)(本部分应包括：描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设计、算法等相关知识)本实验要求设计一个校园导游系统，要求通过图这一数据结构计算两点之间的最短距离，实现校园 导航功能。首先要收集校园景点信息和景点之间的距离信息，然后利用图存储校园景点信息和景点之间的距离信息，最后使用Dijkstra 算法计算最短路径。离散数学相关

5、知识：正确合理使用与或非之间的关系，进行程序分支判断，保证程序正常进行，以 及图的使用。二、【实验设计(Design) (20%)本次实验使用C进行编写，自定义函数2个：void init_graph(graph *g)/图的初始化函数求最短路径的算法void shortest_path(graph *g,int s, int t,int n)主函数为功能选择界面、【实现描述(Implement )1 (30%)主函数显示开始界面，选择相应的功能求最短路径。'C:Use rsA dminist rjtor Des Jctc 导后 '呈贡云南大学校园导游类止苑苑苑苑件L汇4 百一

6、门楼 楼 点 -务 道门 车 西广邦亶服楼院大北堂乘 大典山苑物味宜仃医公大盘死车 云文中注知综主k余京 024 680246 802 46 111112222请输入您的选择.TI*C:U 耳2 rs Ad ministr3torD?s Icto p1 昼航 2 启陪苑苑件一册汇一塞 - S « «- 13579135 1111122 2-楼 点 务 道门 车 堂朋楂院大北堂乘 曼异孱大驻强车 知综襄至云M 5 1 1 - 1 91 ii II 1 0 246 80246 1 11112222请输入您的选择，1输入出发点与结束点：8 19从“格物楼"到"

7、行政办公楼”的最短路径为格物楼综合服务楼-楸苑-力行楼明远楼-至公大道行政办公楼距离为n 请输入您明选9包J rir_人性化设计:1 .在输入出现错误时例如功能选择错误时，程序会给出友好的提示;2 .界面友好，容易上手四、【代码】（10%）#include<iostream>#include<stdio.h>#include<stdlib.h>#include<windows.h>#define INFINITY 9999/最大距离#define MAX_NODES 30/最大结点数int distMAX_NODESMAX_NODES; /dis

8、tij表示 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=&

9、quot;百家道"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="知味

10、堂"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="行政

11、办公楼"g->vex20.sight="云大北门"g->vex21.sight="文汇楼"g->vex22.sight="余味堂"g->vex23.sight="梓苑超市"g->vex24.sight="梓苑"g->vex25.sight="钟楼"；g->vex26.sight="校车乘车点"for(x=0;x<g->vexnum;x+)for(y=0;y<g->vexnum;y+

12、)distxy=INFINITY;/下边是可直接到达的景点间的距离，由于两个景点间距离是互相的，所以要对图中对称的边同时赋值dist1=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;dist7

13、12=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=

14、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;dis

15、t241=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; p<&staten; p+)p->predecessor = -1;p->length = INFINITY;p->label = 0;statet

16、.length = 0;statet.label = 1;k = t; /当前工作结点dofor(i=0; i<n; i+)if(distki!=0 && statei.label=0)if(statek.length+distki<statei.length)statei.length = statek.length+distki; statei.predecessor = k;k=0;min=INFINITY;for(i=0; i<n; i+)if(statei.label=0 && statei.length<min)k=i;min

17、=statei.length;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-)printf("%s->",g->vexmypathi.sight);printf("%sn",g->vexmypathi.sight);printf("n 距离为 %d mn",min); int main()int m,s,e,c;graph g

18、;g.vexnum = 27; init_graph(&g);printf("n=n");printf("n呈贡云南大学校园导游n");printf("nn");/打印景点列表for(m=0;m<g.vexnum;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);elseprintf("n");printf("n=n");tt &