起止周：18～19周
周数：2周
实习地点：东区2教616室信息与计算科学实验室
一、课程设计的目的
数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。
通过该课程设计，了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练学生用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。
二、课程设计的基本要求
1、独立思考，独立完成：课程设计中各任务的设计和调试要求独立完成，遇到问题可以讨论，但不可以拷贝。
2、做好上机准备：每次上机前，要事先编制好准备调试的程序，认真想好调试步骤和有关环境的设置方法，准备好有关的文件。
3、按照课程设计的具体要求建立的功能模块，每个模块要求按照如下几个内容认真完成；
其中包括：
a）需求分析：
在该部分中叙述，每个模块的功能要求
b）概要设计
在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义。
c）详细设计
各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组源程序，每个功能模块采用不同的函数实现）
源程序要按照写程序的规则来编写。
要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。
d）调试分析
测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是哪些？问题如何解决？），算法的改进设想。
课程设计总结：课程设计过程的收获、遇到问题、遇到问题解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程设计过程中对《数据结构》课程的认识等内容；
4、每组实现的结果必须进行检查和演示；程序源代码和程序的说明文件必须上交，作为考核内容的一部分。
5、课程设计报告附原代码，可以对重点函数及结构进行说明。
报告格式见要求。
6、时间安排：
（1）*月*日：教师布置课程设计任务，学生选题。
（2）*月*日：收集资料，完成课程设计的总体设计。
（3）*月*日-*月*日：完成课程设计的各子部分（根据你的题目展开写）设计，运行调试。
三、课程设计内容：
1、内部排序演示
【问题描述】
设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受。
【基本要求】
(1) 对起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法进行比较；
(2) 待排序的元素的关键字为整数。
其中的数据要用伪随机产生程序产生(如10000个)，至少用5组不同的输入数据做比较，再使用各种算法对其进行排序，记录其排序时间，再汇总比较。
(3) 演示程序以人机对话的形式进行。
每次测试完毕显示各种比较指标值的列表，用饼图或条形图进行表示，以便比较各种排序的优劣。
(4) 界面友好，易与操作。
采用菜单方式进行选择。
【选做内容】
(1) 对不同表长进行比较；
(2) 验证各算法的稳定性；
(3) 输出界面的优化。
(4) 使用汉字显示。
2、哈夫曼编码/译码器
【问题描述】
设计一个哈夫曼编码/译码系统，对一个文本文件中的字符进行哈夫曼编码，生成编码文件（压缩文件，后缀名.cod）；反过来，可将一个压缩文件译码还原为一个文本文件(.txt)。
【基本要求】
(1) 输入一个待压缩的文本文件名，统计文本文件中各字符的个数作为权值，生成哈夫曼树；
(2) 将文本文件利用哈夫曼树进行编码，生成压缩文件（后缀名cod），
(3) 输入一个待解压的压缩文件名称,并利用相应的哈夫曼树将编码序列译码；
(4) 显示指定的压缩文件和文本文件；
(5) 界面友好，易与操作。
采用菜单方式进行选择。
【选做内容】
(1) 把哈夫曼编码用二进制位紧缩到一个变量中，利用位运算进行真正的数据压缩，并求压缩比。
(2) 显示哈夫曼树；
(3) 使用汉字显示。
3、运动会分数统计
【问题描述】
参加运动会有n个学校,学校编号为1……n.比赛分成m个男子项目,和w个女子项目.项目编号为男子1......m,女子m+1......m+w.不同的项目取前五名或前三名积分;取前五名的积分分别为:7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。
（m<=20,n<=20）
【功能要求】：
可以输入各个项目的前三名或前五名的成绩；
能统计各学校总分；
可以按学校编号、学校总分、男女团体总分排序输出；
可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。
【基本要求】
（1）输入数据形式和范围：20以内的整数（如果做得更好可以输入学校的名称，运动项目的名称）
（2）输出形式：有中文提示，各学校分数为整型
（3）界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。
4、文章编辑
【问题描述】
输入一页文字，程序可以统计出文字、数字、空格的个数。
【基本要求】
静态存储一页文章，每行最多不超过80个字符，共N行；要求
（1）分别统计出其中英文字母数和空格数及整篇文章总字数；
（2）统计某一字符串在文章中出现的次数，并输出该次数；
（3）删除某一子串，并将后面的字符前移。
存储结构使用线性表，分别用几个子函数实现相应的功能；
输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。
输出形式：
（1）分行输出用户输入的各行字符；
（2）分4行输出"全部字母数"、"数字个数"、"空格个数"、"文章总字数"
【选做内容】
输出删除某一字符串后的文章？
5、乡卫生所选址
【问题描述】
某乡有A，B，C，D，E 5个村庄，如下图所示，图中边上的权值表示两村之间的距离。
现要在5个村庄中选某个村庄建立卫生所。
其选址应使得距离卫生所最远的村庄到卫生所最近。
【基本要求】
（1）给出各村庄之间最短距离的矩阵A。
（2）卫生所应设在哪个村庄？
（3）输出各村庄到卫生所的路径和路径长度。
【选做内容】
如果增加或者减少一个村庄，整个问题数据结构会有哪些变化？
四、上交作业及成绩评定
1、上交要求
时间：第19周最后一次课检查，第19周星期四上午11点之前由学习委员收集上交，迟交无成绩。
形式：课程设计报告纸质和电子文档。
（电子版上交时每人交一份，文件夹的取名规则为：“学号姓名”，如“040111101 王**”。
该文件夹下至少包括：“源代码”、“课程设计报告”、“可执行文件”。
由学习委员按规定时间统一收齐上交）。
2、评分标准
根据完成任务的情况(必须进行系统演示)、课程设计报告书的质量和课程设计过程中的工作态度等按照30%、50%、20%加权综合打分。
成绩评定实行优秀、良好、中等、及格和不及格五个等级。
上机程序检查未通过者、无设计报告者以及严重抄袭他人设计者，成绩为不及格。
注：
每班分为4-5个小组，每组7-8人。
设计题目：（选题：学号%5，余数为1、2、3、4、0分别做第1、2、3、4、5题）
每小组各同学之间设计内容和报告文档不得雷同，否则成绩不及格。