内蒙古科技大学课程设计说明书 数 据 结 构课程设计说明书题 目Huffman编码和译码学 号1367111126姓 名杨科指导教师孙涛日 期2015.1.6内蒙古科技大学课程设计任务书课程名称数据结构课程设计设计题目Huffman编码和译码指导教师孙涛时间2014年秋学期第15周至第19周一、教学要求1. 掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能3. 提高综合运用所学的理论知识和方法独立分析和解决问题的能力4. 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风二、设计资料及参数每个学生在教师提供的课程设计题目中任意选择一题，独立完成，题目选定后不可更换。Huffman编码和译码根据给定的字符集和各字符的频率值，求出其中给定字符Huffman编码，并针对一段文本（定义在该字符集上）进行编码和译码，实现一个Huffman编码/译码系统。要求设计类（或类模板）来描述Huffman树及其操作，包含必要的构造函数和析构函数，以及其他能够完成如下功能的成员函数：v 求Huffman编码v 输入字符串，求出编码v 输入一段编码，实现译码 并设计主函数测试该类。三、设计要求及成果1. 分析课程设计题目的要求2. 写出详细设计说明3. 编写程序代码，调试程序使其能正确运行4. 设计完成的软件要便于操作和使用5. 设计完成后提交课程设计报告四、进度安排资料查阅与讨论（1天）系统分析（2天）系统的开发与测试（5天）编写课程设计说明书和验收（2天）五、评分标准1. 根据平时上机考勤、表现和进度，教师将每天点名和检查2. 根据课程设计完成情况，必须有可运行的软件。3. 根据课程设计报告的质量，如有雷同，则所有雷同的所有人均判为不及格。4. 根据答辩的情况，应能够以清晰的思路和准确、简练的语言叙述自己的设计和回答教师的提问六、参考资料1数据结构 （C语言版）严蔚敏、吴伟民 主编 清华大学出版社 2004.112数据结构课程设计案例精编（用C/C+描述），李建学 等 编著，清华大学出版社 2007.23.数据结构:用面向对象方法与C+语言描述，殷人昆 主编，清华大学出版社 2007目 录目 录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参考文献2626第一章 需求分析1.1 引言目前，进行快速远距离通信的主要手段是电报，即将需传送的文字转化成由二级制的字符组成的字符串。利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个对应的字符的编码，这就是哈夫曼编码。通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总希望总长度尽可能最短，即采用最短码。因此，哈夫曼树在通信、编码和数据压缩等技术领域有着广泛的应用。此设计说明书是对编码/译码系统开发的一个初步的分析说明性文档，旨在通过该文档清晰的阐述系统的实际功能，方便系统开发人员对系统的理解以及与用户的沟通。文档相关说明部分在目录部分已全部涵盖，阅读此文档的相关人员可以通过目录索引找到相应部分予以阅读。1.2 任务概述Huffman编码和译码根据给定的字符集和各字符的频率值，求出其中给定字符Huffman编码，并针对一段文本（定义在该字符集上）进行编码和译码，实现一个Huffman编码/译码系统。1.3 数据描述该哈夫曼编码/译码系统程序中的数据主要有：哈夫曼树、哈夫曼编码，哈夫曼译码等。1.4 功能需求（1）. 输入模块：输入各个元素，建立哈夫曼树；（2）. 编码模块：将输入的各个元素建立哈夫曼树，进行编码；（3）. 译码模块：将电文以0或1输入后，根据之前的哈夫曼树进行译码；（4）. 输出模块：建立好的哈夫曼树、编码、译码进行输出。1.5 性能需求（1）. 要求该编码/译码系统具有一定的可扩展性以便适应发展，且便于维护；（2）. 要求该编码/译码系统便于使用，使用步骤简易明了。1.6 运行需求基于windows平台下的窗口图形界面软件，运行主界面为windows的经典运行界面，采用多文档界面，从而使程序更加美观，整齐有序，简易操作。软件运行基于windows平台上的xp,Vista,win7等第二章 概要设计2.1 总体设计（一） 设计目的：（1） 掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；（2） 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；（3） 提高综合运用所学的理论知识和方法独立分析和解决问题的能力；（4） 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。主菜单根据输入电文进行译码根据哈夫曼树进行编码输入元素建立哈夫曼树图2.1：程序主体设计图（二） 函数划分该程序有一个主函数和多个子函数，主函数完成对子函数的调用，各子函数实现相应的功能。（1） 结点的开辟。（2） 实现对输入字符串中出现的不同字符及其出现字数的信息记录。（3） 用叶子结点构造赫夫曼树。（4） 获得构造的赫夫曼树中所有叶子结点的元素及其赫夫曼编码。（5） 输出各叶子结点元素及其对应的赫夫曼编码。（6） 输出输入的字符串的赫夫曼编码。（7） 调用各子函数2.2 数据类型设计（或数据结构设计）表2.1：数据类型设计数据数据类型权值整数数据双亲整数数据左孩子整数数据右孩子整数数据struct结构体类型2.3 接口设计表2.1：函数列表函数名函数格式 /即函数首部函数功能structtypedef树结点的结构定义树结点的存储定义HuffmanCreateint创建哈夫曼树Encodingvoid对创建好的哈夫曼树进行编码Decodingvoid根据创建好的哈夫曼树进行译码2.4 运行界面设计图2.1：运行界面设计第三章 详细设计3.1 输入、创建模块设计输入、创建哈夫曼树：int HuffmanCreate(HuffNode*ht)int i,k,n,m1,m2,p1,p2;printf(请输入元素个数n);scanf(%d,&n);for(i=1;i=n;i+) /输入结点值和信息getchar();/接收回车printf(第%d个元素的:n结点值:,i);scanf(%c,&hti.data);printf(权值:);scanf(%d,&hti.weight);for(i=1;i=2*n-1;i+) /对数组初始化hti.parent=hti.left=hti.right=0;for(i=n+1;i=2*n-1;i+)m1=m2=32767; /初始化，令m1,m2为整数最大值p1=p2=1;for(k=1;k=i-1;k+) /从数组中找if(htk.parent=0) /parent为零切权值最小的两个结点if(htk.weightm1)m2=m1; /令m1为最小权值p2=p1; /p1 为最小权值的位置m1=htk.weight; /m1存放最小权值p1=k;else if(htk.weightm2)m2=htk.weight; /m2 为次小权值p2=k; /p2为次小权值所在位置htp1.parent=i; /i分别付给下标为p1，p2的数组中htp2.parent=i;hti.weight=m1+m2; /新节点权值为最小权值和次小权值之和hti.left=p1; /p1为新节点的左孩子hti.right=p2; /p2为新节点的右孩子printf(哈夫曼树已成功建立!n);return n; /返回结点数3.2 编码模块设计根据创建好的哈夫曼树，进行编码：void Encoding(HuffNode ht,HuffCode hcd,int n)HuffCode d;int i,k,f,c;for(i=1;i=n;i+)/对所有节点循环d.start=n+1; /起始地点c=i; /从叶结点开始向上f=hti.parent;while(f!=0) /到树根结束if(htf.left=c)d.cd-d.start=0; /规定左数代码为零elsed.cd-d.start=1; /规定右树代码为一c=f;/c为孩子位置f=htf.parent; /f指双亲位置