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

（本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助）实验难度：A□B□C■序号学号姓名成绩12指导教师：（签名）学期：2012秋季学期任课教师:实验题目:图及其应用小组长:联系电话:电子邮件:完成提交时间：2012年12月20日云南大学软件学院2012学年秋季学期云南大学软件学院数据结构实验报告-1-《数据结构实验》成绩考核表学号：姓名：本人承担角色：小组长评分项目评分指标分值得分实验构思（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.有对基本数据结构的抽象数据类型定义5-2-2.实验方案设计完整，数据结构、算法选择合理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%)-3-本次实验使用C进行编写，自定义函数2个：voidinit_graph(graph*g)//图的初始化函数voidshortest_path(graph*g,ints,intt,intn)//求最短路径的算法主函数为功能选择界面三、【实现描述（Implement）】(30%)主函数显示开始界面，选择相应的功能求最短路径。-4-人性化设计：1.在输入出现错误时例如功能选择错误时，程序会给出友好的提示；-5-2.界面友好，容易上手。四、【代码】(10%)#includeiostream#includestdio.h#includestdlib.h#includewindows.h#defineINFINITY9999//最大距离#defineMAX_NODES30//最大结点数intdist[MAX_NODES][MAX_NODES];//dist[i][j]表示i、j连线的权重intpath[MAX_NODES];usingnamespacestd;typedefstructVertexType{char*sight;//景点名称//char*info;//景点描述}VertexType;//定义顶点的类型typedefstruct{intvexnum;VertexTypevex[MAX_NODES];}graph;voidinit_graph(graph*g){inta,x,y=0;g-vexnum=27;g-vex[0].sight=云大西二门;g-vex[1].sight=百家道;-6-g-vex[2].sight=文典广场;g-vex[3].sight=云大会堂;g-vex[4].sight=中山邦翰楼;g-vex[5].sight=仰止楼;g-vex[6].sight=桦苑;g-vex[7].sight=楠苑;g-vex[8].sight=格物楼;g-vex[9].sight=楠苑体育场;g-vex[10].sight=知味堂;g-vex[11].sight=楠苑超市;g-vex[12].sight=综合服务楼;g-vex[13].sight=楸苑;g-vex[14].sight=力行楼;g-vex[15].sight=软件楼;g-vex[16].sight=校医院;g-vex[17].sight=明远楼;g-vex[18].sight=至公大道;g-vex[19].sight=行政办公楼;g-vex[20].sight=云大北门;g-vex[21].sight=文汇楼;g-vex[22].sight=余味堂;g-vex[23].sight=梓苑超市;g-vex[24].sight=梓苑;g-vex[25].sight=钟楼;g-vex[26].sight=校车乘车点;for(x=0;xg-vexnum;x++)for(y=0;yg-vexnum;y++)dist[x][y]=INFINITY;//下边是可直接到达的景点间的距离，由于两个景点间距离是互相的，所以要对图中对称的边同时赋值dist[0][1]=dist[1][0]=10;dist[1][2]=dist[2][1]=20;dist[2][3]=dist[3][2]=20;dist[1][4]=dist[4][1]=50;dist[4][5]=dist[5][4]=200;dist[4][6]=dist[6][4]=130;dist[5][7]=dist[7][5]=600;dist[5][8]=dist[8][5]=800;dist[5][9]=dist[9][5]=600;dist[7][8]=dist[8][7]=100;dist[7][9]=dist[9][7]=600;dist[7][10]=dist[10][7]=150;dist[7][11]=dist[11][7]=110;dist[7][12]=dist[12][7]=100;dist[8][12]=dist[12][8]=80;dist[9][11]=dist[11][9]=700;dist[10][11]=dist[11][10]=5;dist[10][12]=dist[12][10]=50;dist[10][13]=dist[13][10]=150;dist[12][13]=dist[13][12]=100;dist[12][26]=dist[26][12]=20;dist[13][14]=dist[14][13]=200;dist[13][15]=dist[15][13]=250;dist[13][16]=dist[16][13]=700;dist[13][26]=dist[26][13]=100;dist[14][15]=dist[15][14]=20;dist[14][16]=dist[16][14]=500;dist[14][17]=dist[17][14]=1500;dist[16][17]=dist[17][16]=1300;dist[17][18]=dist[18][17]=50;dist[17][25]=dist[25][17]=300;dist[18][19]=dist[19][18]=30;dist[19][20]=dist[20][19]=100;-7-dist[20][21]=dist[21][20]=950;dist[20][22]=dist[22][20]=900;dist[21][22]=dist[22][21]=150;dist[21][24]=dist[24][21]=110;dist[21][25]=dist[25][21]=750;dist[22][23]=dist[23][22]=40;dist[22][24]=dist[24][22]=120;dist[23][24]=dist[24][23]=60;dist[24][1]=dist[1][24]=300;}voidshortest_path(graph*g,ints,intt,intn){structstate{intpredecessor;//前驱节点intlength;//到起始点的距离intlabel;}state[MAX_NODES];inti,k,min,mypath[MAX_NODES];structstate*p;for(p=&state[0];p&state[n];p++){p-predecessor=-1;p-length=INFINITY;p-label=0;}state[t].length=0;state[t].label=1;k=t;//当前工作结点do{for(i=0;in;i++){if(dist[k][i]!=0&&state[i].label==0){if(state[k].length+dist[k][i]state[i].length){state[i].length=state[k].length+dist[k][i];state[i].predecessor=k;}}}k=0;min=INFINITY;for(i=0;in;i++){if(state[i].label==0&&state[i].lengthmin){k=i;min=state[i].length;}}state[k].label=1;}while(k!=s);i=0;k=s;do{-8-path[i]=k;k=state[k].predecessor;mypath[i]=path[i];i++;}while(k=0);for(i--;i0;i--){printf(%s-,g-vex[mypath[i]].sight);}printf(%s\n,g-vex[mypath[i]].sight);printf(\n距离为%dm\n,min);}intmain(){intm,s,e,c;graphg;g.vexnum=27;init_graph(&g);printf(\n===========================================================\n);printf(\n呈贡云南大学校园导游\n);printf(\n\n);//打印景点列表for(m=0;mg.vexnum;m++){printf(\t%2d：%s\t\t,m,g.vex[m].sight);if(++m27&&m!=7)printf(\t%2d：%s\t\n,m,g.vex[m].sight);elseif(m==7)printf(\t%d：%s\t\n,m,g.vex[m].sight);elseprintf(\n);}printf(\n===========================================================\n);printf(\n\t■■■■■■■■■■■■■■■■■\n);printf(\t■■\n