数据结构课程设计指导书(第二版).doc

《数据结构与算法课程设计指导书》 第2版 计算机科学与信息工程学院 2011-05 总体说明 《数据结构与算法》课程设计为期两周，按2010版本科教学计划，安排在每学期的17、18周进行。课程设计进度安排如下： 1、第一周的第一天：小组布置设计题目；说明进度安排。 2、第一周的第二天：小组审题，查阅资料，进行设计前的必要资料准备。 3、第一周的第三天、第四天、第五天：程序编写、上机调试 4、第二周的第一天至第三天： 上机调试程序、结果分析。 5、第二周的第四天： 撰写设计报告。 6、第二周的第五天： 设计答辩及成绩评定。 课程设计中，每个学生必须选择参加一个题目组，共同完成课程设计任务书说明的任务，题目组人数不得超过课程设计任务书中的限定人数。每组自行推选一个小组长，负责整个题目组的协调和合作。课程设计中，每个学生必须负责完成题目的一个部分，并和其他组员讨论协作，共同完成任务书规定的任务的设计、实现和调试。每个学生必须独立完成自己的课程设计说明书，说明书中除把整个项目作为背景，描述整体设计思想外，要重点介绍自己负责设计实现的部分，介绍自己的设计思路、实现过程、问题处理和收获新得。 考核办法如下：考勤20% ；课程设计说明书50%；答辩30% 。课程设计结束后，每个学生必须提交书面的课程设计说明书和电子版。每个小组以小组为单位提交课程设计说明书（书面版和电子版）、最终的可执行程序的全部代码（包括测试数据）。 PAGE 1 《数据结构》课程设计任务书 设计题目 哈夫曼编\译码器 限定人数 6 问题描述 采用哈夫曼编码思想实现对字符串的编码，以及对编码的解码。字符串的长度不小于5000字节。 读取要编码的文本文件，将文件的内容进行编码，生成新的文件。对编码文件进行解码，获得文本文件。将译码的文本文件和原文件进行比较，恢复文件和原文件必须完全一致。 设字符集及频度如下表： 字符 空格 A B C D E F G H I J K L M 频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符 N O P Q R S T U V W X Y Z 频度 57 63 15 1 48 51 80 23 8 18 1 16 1 基本要求与说明 1、根据哈夫曼树编码原理，构造哈夫曼树，创建一套哈夫曼编码 2、读取文本文件，并对文件内容编码，生成编码文件 3、对编码文件进行译码，获得恢复文件 4、比较恢复文件和原文件是否相同。 计算机科学与信息工程学院制 《数据结构》课程设计任务书 设计题目 多种排序 限定人数 3 问题描述 利用随机函数产生N个随机整数（10000以上），对这些数进行多种方法进行排序。 基本要求与说明 采用如下六种方法实现上述问题求解：插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序。 统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。并将数据序列和不同的查找算法的性能结果记录入txt文件。 计算机科学与信息工程学院制  《数据结构》课程设计任务书 设计题目 表达式计算程序设计 限定人数 6 问题描述 设计一个能够计算表达式的程序，要求能够对包含加、减、乘、除、括号运算符的表达式进行计算。 基本要求与说明 计算表达式手工录入，计算结果必须正确 支持两位以上的整数和浮点数的运算 运算符优先级表可在程序中直接通过代码初始化 能够检查表达式是否合法，对于错误的表达式要能够给出错误原因。 计算机科学与信息工程学院制  《数据结构》课程设计任务书 设计题目 工程项目的关键路径的计算 限定人数 6 问题描述 随机生成一个有向无环图，作为一个有多个活动的工程项目的计划进度图，计算该工程的关键路径和工程完成时间。 基本要求与说明 描述工程项目进度的有向无环图能够根据给定顶点树和边数，随机生成，要求以源点开始的广度生成树的层数不能超过15层，工程的活动不能少于100个。 编写求关键路径算法，求生成的有向无环图的关键路径。 输出完成整项工程至少需要多少时间，以及每一个关键活动所依附的两个顶点、最早发生时间、最迟发生时间。 每次生成的图结构保存至文本文件，可以从文本文件读取已生成的有向无环图的结构。 计算机科学与信息工程学院制 《数据结构》课程设计任务书 设计题目 图的遍历和生成树求解 限定人数 6 问题描述 任意创建一个无环图，实现图的DFS,BFS 算