《数据结构》课程设计任务与指导书
绍兴文理学院元培学院信电系
2015年9月
《数据结构与算法》课程设计教学大纲
时间：2周（不停课） 2.5学分
一、教学目的
《数据结构与算法》是一门实践性较强的课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。通过课程设计的锻炼使学生进一步加强对所学知识的理解和掌握，培养学生利用各种数据结构（如线性表、栈、队列、树和图）分析问题、解决问题的能力，使学生能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。
具体目的：
1、培养学生正确的设计思想，理论联系实际的工作作风，严肃认真、实事求是的科学态度和勇于探索的创新精神。
2、培养学生综合运用所学知识与生产实践经验，分析和解决工程技术问题的能力。
3、通过课程设计实践，训练并提高学生在理论计算、结构设计、查阅设计资料、运用标准与规范、编制软件和应用计算机等方面的能力。
二、教学要求
课程设计不同于一般上机实验，强调设计性和综合性，难度和分量较大。因此通过本次课程设计可以加强学生基本功的训练。要求学生在数据结构的逻辑特性和物理表示，数据结构的选择的应用、算法的设计及其实现等方面中加深对课程基本内容的理解，在程序设计方法以及上机操作等基本技能方面受到比较系统和严格的训练。
三、教学内容
参考课题：（可任选一题）
设计1、畅通工程之局部最小花费问题
某地区经过对城镇交通状况的调查，得到现有城镇之间快速道路的统计数据，提出“畅通工程”的目标：使整个地区任何两个城镇之间都可以实现快速交通（不一定有直接的快速道路相连，只要互相间接通过快速路可达即可）。现得到城镇道路统计表，表中列出了任意两城镇间修建快速路的费用，以及该道路是否已经修建的状态。计算出全地区畅通需要的最低成本。
输入说明：第1行给出村庄数目；随后是N（N-1）/2行对应村庄间道路的成本及修建状态：分别是两个村庄的编号、两村庄道路的修建成本以及修建的状态（1：已建，0：未建），用prim算法或kruskal算法求最小代价生成树，并计算得到的代价。
样例输入
4
1 2 1 0
1 3 4 0
1 4 1 0
2 3 3 0
2 4 2 0
3 4 5 0
3
1 2 1 0
1 3
2 1
2 3 4 1
样例输出
5
主要涉及的知识与技能有：查找图的连通集、图的最小生成树问题。
设计2、模拟舞伴配对问题
利用循环队列模拟舞伴配对问题：在舞会上，男、女各自按编号排成一队。舞会开始时。依次从男队和女队的队头各出一人配成舞伴，输出配对的舞伴的编号和姓名。如果两队初始人数不等，则较长的那一队中未配对者等待下一轮舞曲。
主要涉及的知识与技能有：循环队列的应用。
设计3、骑士周游问题（马踏棋盘）
将马随机放在国际象棋的8×8棋盘Board[8][8]的某个方格中，马按走棋规则进行移动。要求每个方格只进一次，走遍棋盘上全部64个方格。编制程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8×8的方阵，输出。
主要涉及的知识与技能有：栈、回溯算法。
设计4、客户通讯录管理系统
假设客户数据包括：姓名，电话，地址，邮编及e-mail。主要功能：1、通讯录信息录入功能；
2、通讯录信息删除功能；
3、通讯录信息浏览功能；
4、通讯录信息查询功能；
5、按姓名排序功能；
6、保存数据到文件。
主要涉及的知识与技能有：线性表的应用，要求使用链表的有关操作（建立、插入、删除、查询、输出）来实现通讯录信息系统的动态管理。
设计5、一元多项式的乘法与加法运算以及求导。
设计三个函数分别求两个一元多项式的乘积、和、求导。输入格式:输入分两行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。输出格式:输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔。
主要涉及的知识与技能有：链表的基本操作以及在多项式运算上的应用。
设计6、迷宫问题
要求穷举出迷宫求解的所有路径并找出最短路径。入口、出口自定。
主要涉及的知识与技能有：堆栈、回溯、深度优先搜索技术及应用。
设计7、求二叉树上结点的路径
在采用链式存储结构的二叉树上，bt指向根结点，p指向任一给定结点，编程实现求出从根结点到给定结点之间的路径，要求实现二叉树的建立、遍历和求结点路径。
主要涉及的知识与技能有：二叉树的操作。
设计8、排序算法的比较与分析
主要涉及的知识与技能有：是一个算法性能评价程序，重点在于算法性能的评价上。对于直接插入排序、直接选择排序、冒泡排序、shell排序、快速排序和堆排序六种算法进行上机实验，数据长度分别取20、100、500三种，算法中增加比较次数和移动次数的统计功能，对结果做时空效率分析。
设计9、交通咨询系统设计
要求一个城市到所有城市的最短路径、任意的两个城市之间的最短路径。
主要涉及的知识与技能有：含权图（网）、最短路径、图的存储与邻接表、最优路线求解及应用。
采用如下测试数据。
设计10、学校超市选址问题
要求对于某一学校超市，其他各单位到其的距离不同，同时各单位人员去超市的频度也不同。请为超市选址，要求实现总体最优。
主要涉及的知识与技能有：带权有向图、最小生成树问题。
设计11、散列---整型关键字的散列映射
给定一系列不重复的整型关键字个数n和散列表长m，m若不为素数，重置为大于它的下一个素数，用除留余数法定义的散列函数H(Key)=Key % m将关键字映射到长度为m的散列表中，用线性探测法解决冲突。输入说明：输入第一行首先给出两个正整数n(<=1000)和m(>=n)，分别为待插入的关键字总数以及散列表的长度。第二行给出N个整型关键字。输出说明：给出成功查找的ASL。
样例输入
4 5
24 15 61 88
9 12
47 7 29 11 9 84 54 20 30
1000 1009
1000个不重复的随机数
样例输出
