哈夫曼编译码器设计任务书.doc

信息与计算科学本科专业数据结构课程设计任务书（10级）题目：哈夫曼编译码器设计学生姓名： 学号： 班级： 题目类型： 指导教师： 一 题目简介利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。通过该题目的设计过程，可以加深理解树及二叉树的逻辑结构、存储结构，掌握树及二叉树上基本运算的实现。进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养学生的动手能力。二 主要任务1、查阅文献资料，一般在3篇以上；2、设计哈夫曼码的编/译码系统，建立数据的逻辑结构和物理结构；3、完成相应算法的设计；4、完成测试工作；5、撰写设计说明书；6、做好答辩工作。三 主要内容、功能及技术指标（1）分别使用动态和静态存储结构，主要功能有：建立哈夫曼树、利用已建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件中的正文进行编码并输出编码、对文件中的代码进行译码、显示输出等功能；（2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”。字符 空格 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算法对于合法的输入数据都能产生满足规格说明要求的结果；（3）算法对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果；对算法实现过程中的异常情况能给出有效信息；（4）较高要求：实现图形化操作界面，以多种输出格式显示哈夫曼树。四 提交的成果1. 设计说明书一份，内容包括：1) 中文摘要100字；关键词3-5个；2) 序言；3）采用类c语言定义相关的数据类型4）各模块流程图及伪码算法5）函数的调用关系图6）调试分析a、调试中遇到的问题及对问题的解决方法；b、算法的时间复杂度和空间复杂度。7）测试结果8）源程序（带注释）9) 设计总结、参考文献、致谢等。2. 刻制光盘一张。五 主要参考文献1 严蔚敏，吴伟民.数据结构（C语言版）.清华大学出版社.2 严蔚敏，吴伟民.数据结构题集（C语言版）.清华大学出版社.3 DATA STRUCTURE WITH C+. William Ford,William Topp .清华大学出版社（影印版）. 4 谭浩强.c语言程序设计. 清华大学出版社. 5数据结构与算法分析（Java版） , A Practical Introduction to Data Structures and Algorithm Analysis Java Edition Clifford A. Shaffer , 张铭,刘晓丹译电子工业出版社 2001 年1月六 各阶段时间安排（共2周）周次日期内容地点完成情况教师签字第1周星期一教师讲解设计要求，准备参考资料教室星期二三分析设计要求，进行数据