被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到，若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止； 3、 构造最小生成树的算法有：普里姆算法和克鲁卡尔算法；
4、 由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓朴排序，
拓朴排序的方法是：在有向图中选一个没有前驱的顶点且输出之，从图中删除该顶点和所有以它为尾的弧，重复上述步骤，直至全部顶点均被输出，或当前图中不存在无前驱的顶点为止。 5、 详细原理请参考教材。 【实验步骤】
一、用C语言编程实现图的遍历算法 1、采用邻接表存储结构创建一个图；
2、编程实现图的深度优先搜索（或广度优先搜索）遍历算法 3、输出遍历结果；
4、给定具体数据调试程序。 二、教学计划编制问题
软件专业的学生要学习一系列课程，其中有些课程必须在其先修课程完成后才能学习，具体关系见下表： 课程编号 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 课程名称 程序设计基础 离散数学 数据结构 汇编语言 语言的设计与分析 计算机原理 编译原理 操作系统 高等数学 线性代数 普通物理 数值分析 先决条件 无 C1 C1,C2 C1 C3,C4 C11 C3,C5 C3,C6 无 C9 C9 C1,C9,C10 假设每门课程的学习时间为一学期，试为该专业的学生设计教学计划，使他们能在最短的时间内修完这些课程。 1、 分析问题；
2、 根据此问题创建一个图表示课程与课程之间的关系； 3、 利用拓扑排序算法实现该教学计划； 4、输出课程开出的先后顺序 5、 调试程序。 【思考问题】
结合实验过程，回答下列问题：
1、 图有哪几种存储结构，哪种适合于存储无向图，哪种适合于存储有向图？； 2、 列举出几种需要应用关键路径或最短路径算法解决的实际问题。 【实验报告要求】
1、 根据对图的理解，如何创建一个图；
2、 实现图的遍历的程序设计思路； 3、 编制教学计划问题的设计思路； 4、本次实验的结论与体会。
实验六 查找
【实验目的】
1、 掌握静态查找表算法（重点掌握折半查找）； 2、 掌握动态查找表----二叉排序树查找算法； 3、 掌握哈希表查找算法 【实验学时】
4 学时 【实验类型】
设计型 【实验内容】
1、 编程实现有序表的折半查找算法； 2、 编程实现按二叉排序树算法进行查找。 3、 利用哈希表算法进行查找 【实验原理】
1、 有序表的折半查找过程是：先确定确定待查记录所在的范围（区间），然后逐步缩
小范围直到找到或找不到该记录为止；
2、 二叉排序树查找过程是：首先将给定值和根结点的关键字比较，若相等，则查找
成功，否则将依据给定值和根结点的关键字之间的大小关系，分别在左子树或右子树上继续进行查找；
3、 在查找问题中，理想的情况是希望不经过任何比较，一次存取便能得到所查记录，
那就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系，使每个关键字和结构中一个唯一的存储位置相对应。这需要构造一个哈希函数，常用的构造函数的方法有：直接定址法、数字分析法、平方取中法、折叠法、除留余数法和随机数法。构造的哈希表发生冲突是不可避免的，需要适当地处理冲突，处理冲突的方法有：开放定址法、再哈希法、链地址法和建立一个公共溢出区法。 4、 详细原理请参考教材。 【实验步骤】
一、用C语言编程实现有序表的折半查找算法 1、 创建一个递增的有序表；
2、 给定一个值，用折半查找算法在有序表中进行查找； 3、 输出查找结果；
4、 给定具体数据调试程序
二、用C语言编程实现在二叉排序树中进行查找
1、读入一串整数，采用二叉链存储结构创建一棵二叉排序树； 2、给定一个值，在二叉排序树中进行查找； 3、输出查找结果；
4、给定具体数据调试程序。 三、哈希表查找
针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查找程序。 1、 分析问题；
2、 创建此问题的哈希表；
3、 指定一个人名，在哈希表中进行查找，并输出查找结果； 4、调试程序。 【思考问题】
结合实验过程，回答下列问题：
何种情况适合采用折半查找、何种情况适合采用二叉排序树查找、何种情况适合采用哈希表查找？ 【实验报告要求】
1、根据对静态查找算法的理解，实现折半查找的程序设计思路；
2、根据对二叉排序树的理解，实现在二叉排序树中进行查找的程序设计思路； 3、如何构造哈希函数，如何解决地址冲突； 4、 实现在哈希表中进行查找的程序设计思路； 5、 本次实验的结论与体会。
实验七 内部排序
【实验目的】
1、 掌握常用的排序方法（如：希尔排序、快速排序、选择排序、归并排序），并掌握
用高级语言实现排序算法；
2、 深刻理解排序的定义和常用排序方法的特点，并能加以灵活应用； 3、 了解常用方法的排序过程及其依据的原理。 【实验学时】
2 学时 【实验类型】
设计型
【实验内容】(选择其中两个题做)
1、 编程实现插入排序算法； 2、 编程实现快速排序算法； 3、 编程实现选择排序算法； 4、 编程实现归并排序算法。 【实验原理】
1、 插入排序算法有：直接插入排序、2路插入排序和希尔排序； 2、 快速排序算法有：起泡排序、快速排序；
3、 选择排序算法有：简单选择排序、树形选择排序和堆排序； 4、 详细原理请参考教材。 【实验步骤】
一、用C语言编程实现插入排序算法
给出n个学生的考试成绩表，每条信息由姓名与分数组成，用一种插入排序算法编程实现：
① 按分数高低次序输出每个学生在考试中获得的名次，分数相同的为同一名次； ② 按名次列出每个学生的姓名与分数。 二、用C语言编程实现快速排序算法
给出n个学生的考试成绩表，每条信息由姓名与分数组成，用一种快速排序算法编程实现：
① 按分数高低次序输出每个学生在考试中获得的名次，分数相同的为同一名次； ② 按名次列出每个学生的姓名与分数。 三、用C语言编程实现选择排序算法
给出n个学生的考试成绩表，每条信息由姓名与分数组成，用一种选择排序算法编程实现：
① 按分数高低次序输出每个学生在考试中获得的名次，分数相同的为同一名次； ② 按名次列出每个学生的姓名与分数。 四、用C语言编程实现归并排序算法
给出n个学生的考试成绩表，每条信息由姓名与分数组成，用归并排序算法编程实现：
① 按分数高低次序输出每个学生在考试中获得的名次，分数相同的为同一名次； ② 按名次列出每个学生的姓名与分数。
【思考问题】
结合实验过程，回答下列问题：
何种情况适合采用插入排序算法处理排序问题、何种情况适合采用快速排序算法处理排序问题、何种情况适合采用选择排序算法处理排序问题、何种情况适合采用归并排序算法处理排序问题 【实验报告要求】
1、根据对插入排序算法的理解，实现插入排序的程序设计思路； 2、根据对快速排序算法的理解，实现快速排序的程序设计思路； 3、根据对选择排序算法的理解，实现选择排序的程序设计思路； 4、根据对归并排序算法的理解，实现归并排序的程序设计思路； 5、本次实验的结论与体会。