《数据结构与算法》课程设计格式要求.pdf

《 数据结构与算法 》课程设计 （2010/2011 学年第二学期第 20 周） 指导教师： 孙麒 郭奕亿 班级： 09 计算机科学与技术 1 班 学号： 姓名：倪建鹤 《数据结构与算法》课程设计任务书 《数据结构与算法》 是计算机专业重要的核心课程之一， 在计算机专业的学习过程中占有非常重要 的地位。 《数据结构与算法课程设计》 就是要运用本课程以及到目前为止的有关课程中的知识和技术来 解决实际问题。 特别是面临非数值计算类型的应用问题时， 需要选择适当的数据结构， 设计出满足一定 时间和空间限制的有效算法。 本课程设计要求同学独立完成一个较为完整的应用需求分析。 并在设计和编写具有一定规模程序的 过程中，深化对《数据结构与算法》课程中基本概念、理论和方法的理解；训练综合运用所学知识处理 实际问题的能力，强化面向对象的程序设计理念；使自己的程序设计与调试水平有一个明显的提高。 赫夫曼编码 /译码器 1. 问题描述 利用赫夫曼编码进行通信可以大大提高信道利用率， 缩短信息传输时间， 降低传输成本。 这要求在 发送端通过一个编码系统对待传输数据预先编码， 在接收端将传来的数据进行译码 （复原）。对于双工 信道（即可以双向传输信息的信道），每端都需要一个完整的编 / 译码系统。试为这样的信息收发站编 写一个赫夫曼码的编 / 译码系统。 2. 基本要求 一个完整的系统应具有以下功能： (1) I ：初始化（ Initialization ）。从终端读入字符集大小 n ，以及 n 个字符和 n 个权值，建立赫夫曼树， 并将它存于文件 hfmTree 中。 (2) E ：编码（ Encoding ）。利用已建好的赫夫曼树（如不在内存，则从文件 hfmTree 中读入），对文件 ToBeTran 中的正文进行编码，然后将结果存入文件 CodeFile 中。 (3) D ：译码（ Decoding ）。利用已建好的赫夫曼树将文件 CodeFile 中的代码进行译码，结果存入文件 Textfile 中。 以下为选做： (4) P ：印代码文件（ Print ）。将文件 CodeFile 以紧凑格式显示在终端上，每行 50 个代码。同时将此字 符形式的编码文件写入文件 CodePrin 中。 (5) T ：印赫夫曼树（ Treeprinting ）。将已在内存中的赫夫曼树以直观的方式（比如树）显示在终端上， 同时将此字符形式的赫夫曼树写入文件 TreePrint 中。 3. 测试要求 (1) 已知某系统在通信联络中只可能出现八种字符， 其频率分别为 0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11 ， 试设计赫夫曼编码。 (2) 用下表给出的字符集和频度的实际统计数据建立赫夫曼树，并实现以下报文的编码和译码： “THIS PROGRAME IS MY FA VORITE ”。 字符 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 4