数据结构实验六实验报告.doc

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

（本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助）

实验难度：A□B□C√

序号学号姓名成绩指导教师（签名）
学期：2012秋季学期
任课教师:
实验题目: 图及其应用(实验六)
小组长:
联系电话:
电子邮件:
完成提交时间：年月日

云南大学软件学院2010学年秋季学期
《数据结构实验》成绩考核表
学号：姓名：本人承担角色：
评分项目评分指标分值得分实验构思（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时使用，每个成员一份。）
（下面的内容由学生填写，格式统一为，字体:楷体,行距:固定行距18，字号:小四，个人报告按下面每一项的百分比打分。难度A满分70分，难度B满分90分）
一、【实验构思（Conceive）】(10%)
（本部分应包括：描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设计、算法等相关知识）
1.实验题目：图及其应用
2.实验开发环境:Microsoftvisualstudio2010;
3.基本思路:
先把我所需要的地图画出来，化成顶点状的，把路径长度都标出来，这样我就不会搞错。
定义两个结构体来表示顶点和弧结点的包含信息。顶点包含建筑编号，建筑名称以及建筑描述等，弧结点主要是包含他的权重，也就是路径长度。
定义一个造图函数，输入他的相关信息，建立他，并定义一个函数对其图结点进行说明，这个函数要初始化他的建筑编号，建筑名称以及建筑描述。
定义一个函数可以用来求两个建筑之间的最短路径。用Dijkstra算法求最短路径。
定义一个函数来实现输出路径，用来导航。
最后建立一个主函数，可以用来选择我们所要实现的操作，是查询建筑信息还是选择路径等。
4.相关地图和说明：
5
6
8
9
5
9
8
7
8
7
7
4
1
3
2
6
7
9
4
8
7
12
12

1:"格物楼:主要是楠苑教学楼";
2:"楠苑:楠苑学生的宿舍楼";
3:"力行楼:主要是楸苑教学楼";
4:"楸苑:楸苑学生的宿舍楼";
5:"仰止楼:图书馆";
6:"中山邦翰楼:主要是桦苑教学楼和事务大厅";
7:"桦苑:桦苑学生的宿舍楼";
8:"文汇楼:主要是梓苑教学楼";
9:"梓苑:梓苑学生的宿舍楼";
二、【实验设计(Design)】(20%)
（本部分应包括：抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明，主程序模块与各子程序模块间的调用关系）
1.抽象数据类型图的定义
ADTGraph{
数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。
数据关系R：
typedefstructArcCell
{intadj;/*相邻接的建筑之间的路程*/
}ArcCell;/*定义边的类型*/
typedefstructVertexType
{intnumber;/*建筑编号*/
char*sight;/*建筑名称*/
char*description;/*建筑描述*/
}VertexType;/*定义顶点的类型*/
typedefVertexTypeT;
typedefstruct
{VertexTypevex[NUM];/*图中的顶点，即为建筑*/
ArcCellarcs[NUM][NUM];/*图中的边，即为建筑间的距离*/
intvexnum,arcnum;/*顶点数，边数*/
}MGraph;/*定义图的类型*/
基本操作P：
voidCreateUDN()/*造图函数*/
//初始条件：V是图中的顶点集，VR是图中的弧的集合
//操作结果：按V和VR的定义构造图G
voidnarrate()/*说明函数*/
//初始条件：图已经存在
//操作结果：输入图顶点的相关信息
voidoutput(intv1,intv2,int*s,intu,intv0,int*path);/*输出函数*/
//初始条件：图已存在，v1和v2是两个顶点