搜索
《数据结构》课程设计说明书题目Huffman编码和译码学号1367111126姓名杨科指导教师孙涛日期2015.1.6内蒙古科技大学课程设计说明书II内蒙古科技大学课程设计任务书课程名称数据结构课程设计设计题目Huffman编码和译码指导教师孙涛时间2014年秋学期第15周至第19周一、教学要求1.掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风二、设计资料及参数每个学生在教师提供的课程设计题目中任意选择一题，独立完成，题目选定后不可更换。Huffman编码和译码根据给定的字符集和各字符的频率值，求出其中给定字符Huffman编码，并针对一段文本（定义在该字符集上）进行编码和译码，实现一个Huffman编码/译码系统。要求设计类（或类模板）来描述Huffman树及其操作，包含必要的构造函数和析构函数，以及其他能够完成如下功能的成员函数：求Huffman编码输入字符串，求出编码输入一段编码，实现译码并设计主函数测试该类。三、设计要求及成果1.分析课程设计题目的要求2.写出详细设计说明3.编写程序代码，调试程序使其能正确运行4.设计完成的软件要便于操作和使用5.设计完成后提交课程设计报告四、进度安排资料查阅与讨论（1天）系统分析（2天）系统的开发与测试（5天）编写课程设计说明书和验收（2天）五、评分标准1.根据平时上机考勤、表现和进度，教师将每天点名和检查2.根据课程设计完成情况，必须有可运行的软件。3.根据课程设计报告的质量，如有雷同，则所有雷同的所有人均判为不及格。4.根据答辩的情况，应能够以清晰的思路和准确、简练的语言叙述自己的设计和回答教师的提问六、参考资料1．《数据结构（C语言版）》严蔚敏、吴伟民主编清华大学出版社2004.112．《数据结构课程设计案例精编（用C/C++描述）》，李建学等编著，清华大学出版社2007.23.《数据结构:用面向对象方法与C++语言描述》，殷人昆主编，清华大学出版社2007内蒙古科技大学课程设计说明书III目录目录···········································································································III第一章需求分析······························································································41.1引言································································································41.2任务概述·························································································41.3数据描述·························································································41.4功能需求·························································································51.5性能需求·························································································51.6运行需求·························································································5第二章概要设计·························································································62.1总体设计·························································································6（一）设计目的：················································································6（二）函数划分···················································································72.2数据类型设计（或数据结构设计）························································72.3接口设计·························································································72.4运行界面设计···················································································8第三章详细设计·························································································93.1输入、创建模块设计··········································································93.2编码模块设计··················································································103.3译码模块设计··················································································113.4主函数模块设计···············································································13第四章测试分析························································································154.1测试程序执行情况············································································154.2出现的问题和解决的方法···································································17第五章课程设计总结··················································································18附录：程序代码·······························································································19参考文献········································································································26内蒙古科技大学课程设计说明书4第一章需求分析1.1引言目前，进行快速远距离通信的主要手段是电报，即将需传送的文字转化成由二级制的字符组成的字符串。利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个对应的字符的编码，这就是哈夫曼编码。通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总希望总长度尽可能最短，即采用最短码。因此，哈夫曼树在通信、编码和数据压缩等技术领域有着广泛的应用。此设计说明书是对编码/译码系统开发的一个初步的分析说明性文档，旨在通过该文档清晰的阐述系统的实际功能，方便系统开发人员对系统的理解以及与用户的沟通。文档相关说明部分在目录部分已全部涵盖，阅读此文档的相关人员可以通过目录索引找到相应部分予以阅读。1.2任务概述Huffman编码和译码根据给定的字符集和各字符的频率值，求出其中给定字符Huffman编码，并针对一段文本（定义在该字符集上）进行编码和译码，实现一个Huffman编码/译码系统。1.3数据描述该哈夫曼编码/译码系统程序中的数据主要有：哈夫曼树、哈夫曼编码，哈夫曼译码等。内蒙古科技大学课程设计说明书51.4功能需求（1）.输入模块：输入各个元素，建立哈夫曼树；（2）.编码模块：将输入的各个元素建立哈夫曼树，进行编码；（3）.译码模块：将电文以0或1输入后，根据之前的哈夫曼树进行译码；（4）.输出模块：建立好的哈夫曼树、编码、译码进行输出。1.5性能需求（1）.要求该编码/译码系统具有一定的可扩展性以便适应发展，且便于维护；（2）.要求该编码/译码系统便于使用，使用步骤简易明了。1.6运行需求基于windows平台下的窗口图形界面软件，运行主界面为windows的经典运行界面，采用多文档界面，从而使程序更加美观，整齐有序，简易操作。软件运行基于windows平台上的xp,Vista,win7等内蒙古科技大学课程设计说明书6第二章概要设计2.1总体设计（一）设计目的：（1）掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；（2）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；（3）提高综合运用所学的理论知识和方法独立分析和解决问题的能力；（4）训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。图2.1：程序主体设计图主菜单根据哈夫曼树进行编码根据输入电文进行译码输入元素建立哈夫曼树内蒙古科技大学课程设计说明书7（二）函数划分该程序有一个主函数和多个子函数，主函数完成对子函数的调用，各子函数实现相应的功能。（1）结点的开辟。（2）实现对输入字符串中出现的不同字符及其出现字数的信息记录。（3）用叶子结点构造赫夫曼树。（4）获得构造的赫夫曼树中所有叶子结点的元素及其赫夫曼编码。（5）输出各叶子结点元素及其对应的赫夫曼编码。（6）输出输入的字符串的赫夫曼编码。（7）调用各子函数2.2数据类型设计（或数据结构设计）表2.1：数据类型设计数据数据类型权值整数数据双亲整数数据左孩子整数数据右孩子整数数据struct结构体类型2.3接口设计表2.1：函数列表函数名函数格式//即函数首部函数功能structtypedef树结点的结构定义树结点的存储定义HuffmanCreateint创建哈夫曼树Encodingvoid对创建好的哈夫曼树进行编码Decodingvoid根据创建好的哈夫曼树进行译码内蒙古科技大学课程设计说明书82.4运行界面设计图2.1：运行界面