北 京 林 业 大 学

09学年—10学年第 2 学期 数据结构实验任务书

专业名称： 实验学时： 4 课程名称：数据结构 任课教师： 李冬梅 实验题目：图的最短路径算法的实现 实验环境： Visual C++ 实验目的：

1．掌握图的邻接矩阵的存储定义；

2．掌握图的最短路径（Dijsktra）算法的实现。 。

实验内容：

设计北京林业大学的校园平面图，所含景点不少于8个。以图中顶点表示学校内各景点，存放景点的名称、景点介绍信息等；以边表示路径，存放路径长度信息。要求将这些信息保存在文件graph.txt中，系统执行时所处理的数据要对此文件分别进行读写操作。

1．从文件graph.txt中读取相应数据, 创建一个图,使用邻接矩阵表示图（算法6.1）； 2．景点信息查询：为来访客人提供校园任意景点相关信息的介绍；

3．问路查询：为来访客人提供校园任意两个景点之间的一条最短路径（算法6.10）。

选做内容（对文件进行操作，相应信息变化后，再次进行景点信息查询和问路查询时应该有所体现）

1. 修改一个已有景点的相关信息； 2. 增加一个新景点及其相关信息； 3. 增加一条新的路径；

4. 删除一个景点及其相关信息； 5. 删除一条路径。

实现提示：

1. 校园道路是双向通行的，可设校园平面图是一个带权的无向图，用邻接矩阵表示此无向网。

typedef struct{ char name[100]; char info[10000];

}VertexType; //顶点结构 typedef struct{

VertexType vexs[10];

int arcs[100][100];//邻接矩阵

int vexnum,arcnum;//顶点个数，边的个数 }MGraph; //图结构

2. 将图的顶点信息和边的信息用数据文件graph.txt存储，数据文件格式可以设置如下形式：

图中顶点数 边的数目 景点名称 景点信息 始点 终点 路径长度

如可以在文件graph.txt中存储以下数据： 8 15

女生宿舍 有南北两栋，24层，是北林最漂亮的宿舍楼 小南门 经由北林主路通往学校北门，交通便利 ??

正门 主楼 80 正门 图书馆 400

??

程序运行的参考结果下图：

实验要求：

(1) 程序要具在一定的健壮性，即当输入数据非法时，程序也能适当地做出反应。 (2) 程序要添加适当的注释，程序的书写要采用缩进格式。

(3) 根据实验报告模板详细书写实验报告，在实验报告中给出校园平面图。

(4) 校园平面图中的校园景点信息保存在文件graph.txt中，源程序保存为“Graph_search.cpp”，实验报告命名为“实验报告3.doc”。将这三个文件压缩为一个文件，按以下方式命名：学号姓名.rar，上传到ftp的相应班级所在文件夹。

北 京 林 业 大 学

09学年—10学年第 2 学期 数据结构实验任务书

专业名称： 实验学时： 4 课程名称：数据结构 任课教师： 李冬梅

实验题目：学生管理系统的设计与实现 实验环境： Visual C++ 6.0 实验目的：

1．掌握重要的排序算法――直接插入排序和快速排序； 2．掌握折半查找算法。

3. 综合运用所学数据结构知识，提高解决实际问题的能力。

实验内容：

设计并实现一个学生管理系统，即定义一个包含学生信息（学号，姓名，成绩）的的顺序表，可以不考虑重名的情况，系统至少包含以下功能：

(1) 根据指定学生个数，逐个输入学生信息； (2) 逐个显示学生表中所有学生的相关信息； (3) 给定一个学生信息，插入到表中指定的位置； (4) 删除指定位置的学生记录； (5) 统计表中学生个数；

(6) 利用直接插入排序或者折半插入排序按照姓名进行排序； (7) 利用快速排序按照学号进行排序；

(8) 根据姓名进行折半查找，要求使用递归算法实现，成功返回此学生的学号和成绩； (9) 根据学号进行折半查找，要求使用非递归算法实现，成功返回此学生的姓名和成绩。

实验要求：

(1) 程序要添加适当的注释，程序的书写要采用缩进格式。

(2) 程序要具在一定的健壮性，即当输入数据非法时，程序也能适当地做出反应，如插入删除时指定的位置不对等等。

(3) 程序要做到界面友好，在程序运行时用户可以根据相应的提示信息进行操作。 (4) 根据实验报告模板详细书写实验报告。

(5) 上传源程序和实验报告到ftp的相应班级所在文件夹。源程序保存为Student.cpp，实验报告命名为：实验报告4.doc。源程序和实验报告压缩为一个文件（如果定义了头文件则一起压缩），按以下方式命名：学号姓名.rar，如070824101王拓.rar。