普利姆算法求最小生成树,排序子系统.docxVIP

PAGE \* MERGEFORMAT22 成 绩 评 定 表 学生姓名班级学号专 业电子信息科学与技术课程设计题目普里姆算法求最小生成树；排序子系统(2)评 语 组长签字： 成绩 日期 20 年 月 日  课程设计任务书 学 院信息科学与工程学院专 业电子信息科学与技术学生姓名班级学号课程设计题目普里姆算法求最小生成树；排序子系统(2)实践教学要求与任务: 题目一：普里姆算法求最小生成树 1.对教材174页7.16的a图建立它的邻接表。 2.用普里姆算法求其最小生成树，依次输出顶点集合和边集合。 题目二：排序子系统(2) 1.设计一个选择式菜单。 排序子系统 ****************************************************** * 1 ……直接插入排序 * * 2 ……希尔排序 * * 0 ……返回 * ****************************************************** 请选择菜单号（0…2）： 2.编写直接插入排序程序。 3.编写希尔排序程序。 工作计划与进度安排: 第1天：1、指导教师布置课程设计题目及任务 2、查找相关资料 第2~4天：1、根据具体设计题目进行具体分析 2、对设计题目进行编码和调试 3、指导教师进行验收 第5天：1、指导教师针对课程设计进行答辩 2、完成课程设计报告指导教师： 201 年 月 日专业负责人： 201 年 月 日学院教学副院长： 201 年 月 日 目 录 一、课程设计目的4 二、课程设计内容和要求4 三、题目一设计过程5 四、题目二设计过程16 五、设计总结22 六、参考文献22 题目：普里姆算法求最小生成树；排序子系统（2） 课程设计的目的 本学期我们对《数据结构》这门课程进行了学习。这门课程是一门实践性非常强的课程，为了让大家更好地理解与运用所学知识，提高动手能力，我们进行了此次课程设计实习。这次课程设计不但要求学生掌握《数据结构》中的各方面知识，还要求学生具备一定的C语言基础和编程能力。 （1）题目一的目的： 1、掌握图的存储方法 2、掌握普里姆算法求解最小生成树 （2）题目二的目的： 1、掌握常用排序方法的基本思想 2、通过实验加深理解各种排序算法 3、了解各种排序方法的优缺点及适用范围 二、课程设计的内容和要求 （1）题目一的内容和要求： 1、对教材174页7.16的a图建立它的邻接表。 2、用普里姆算法求其最小生成树，依次输出顶点集合和边集合。 （2）题目二的内容和要求： 1、设计一个选择式菜单。 排序子系统 ****************************************************** * 1 ……直接插入排序 * * 2 ……希尔排序 * * 0 ……返回 * ****************************************************** 请选择菜单号（0…2）： 2、编写直接插入排序程序。 3、编写希尔排序程序。 三、题目一设计过程 1、题目分析 在本次试验中，定义了多种的 struct 结构，分别存储加权无向图的结点信息，及相连的结点位 置及结点信息加边上的权值。通过邻接矩阵的建立，可以将任意两点的权值存入其中，便于进行各 边的权值的比较修改，在 ALG（）函数中，无向图的邻接矩阵定义为二维数组的形式，通过函数的 转换，转换成邻接表并输出。在普利姆算法中，为实现这个算法需附设一个辅助数组 closedge，以 记录从 U 到 V-U 具有最小代价的边，对每个顶点 vi∈V-U,在辅助数组中存在一个相应分量 closedge[i-1] ， 他 包 括 两 个 域 ， 其 中 lowcost 存 储 该 边 上 的 权 值 。 显 然 ， closedge[i-1].lowcost=Min{cost(u,vi)| u∈U}从算法可以看出每加入一个顶点到