《数据结构》课程设计
任务与指导书
绍兴文理学院元培学院信电系2015年9月
f《数据结构与算法》课程设计教学大纲
时间：2周（不停课）25学分
一、教学目的
《数据结构与算法》是一门实践性较强的课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。通过课程设计的锻炼使学生进一步加强对所学知识的理解和掌握，培养学生利用各种数据结构（如线性表、栈、队列、树和图）分析问题、解决问题的能力，使学生能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。具体目的：1、培养学生正确的设计思想，理论联系实际的工作作风，严肃认真、实事求是的科学态度和勇于探索的创新精神。2、培养学生综合运用所学知识与生产实践经验，分析和解决工程技术问题的能力。3、通过课程设计实践，训练并提高学生在理论计算、结构设计、查阅设计资料、运用标准与规范、编制软件和应用计算机等方面的能力。
二、教学要求
课程设计不同于一般上机实验，强调设计性和综合性，难度和分量较大。因此通过本次课程设计可以加强学生基本功的训练。要求学生在数据结构的逻辑特性和物理表示，数据结构的选择的应用、算法的设计及其实现等方面中加深对课程基本内容的理解，在程序设计方法以及上机操作等基本技能方面受到比较系统和严格的训练。
三、教学内容
参考课题：（可任选一题）
设计1、畅通工程之局部最小花费问题某地区经过对城镇交通状况的调查，得到现有城镇之间快速道路的统计数据，提出“畅通工程”的目标：使整个地区任何两个城镇之间都可以实现快速交通（不一定有直接的快速道路相连，只要互相间接通过快速路可达即可）。现得到城镇道路统计表，表中列出了任意两城镇间修建快速路的费用，以及该道路是否已经修建的状态。计算出全地区畅通需要的最低成本。输入说明：第1行给出村庄数目；随后是N（N1）2行对应村庄间道路的成本及修建状态：分别是两个村庄的编号、两村庄道路的修建成本以及修建的状态（1：已建，0：未建），用prim算法或kruskal算法求最小代价生成树，并计算得到的代价。样例输入4121013401410233024203450
f3121013212341样例输出50主要涉及的知识与技能有：查找图的连通集、图的最小生成树问题。设计2、模拟舞伴配对问题利用循环队列模拟舞伴配对问题：在舞会上，男、女各自按编号排成一队。舞会开始时。依次从男队和女队的队头各出一人r