数据结构哈夫曼报告

1、 数 据 结 构课程设计说明书题 目Huffman编码和译码学 号1367111126姓 名杨科指导教师孙涛日 期2015.1.6内蒙古科技大学课程设计任务书课程名称数据结构课程设计设计题目Huffman编码和译码指导教师孙涛时间2014年秋学期第15周至第19周一、教学要求1. 掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能3. 提高综合运用所学的理论知识和方法独立分析和解决问题的能力4. 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风二、设计资料及参数每个

2、学生在教师提供的课程设计题目中任意选择一题，独立完成，题目选定后不可更换。Huffman编码和译码根据给定的字符集和各字符的频率值，求出其中给定字符Huffman编码，并针对一段文本（定义在该字符集上）进行编码和译码，实现一个Huffman编码/译码系统。要求设计类（或类模板）来描述Huffman树及其操作，包含必要的构造函数和析构函数，以及其他能够完成如下功能的成员函数：v 求Huffman编码v 输入字符串，求出编码v 输入一段编码，实现译码 并设计主函数测试该类。三、设计要求及成果1. 分析课程设计题目的要求2. 写出详细设计说明3. 编写程序代码，调试程序使其能正确运行4. 设计完成的

3、软件要便于操作和使用5. 设计完成后提交课程设计报告四、进度安排资料查阅与讨论（1天）系统分析（2天）系统的开发与测试（5天）编写课程设计说明书和验收（2天）五、评分标准1. 根据平时上机考勤、表现和进度，教师将每天点名和检查2. 根据课程设计完成情况，必须有可运行的软件。3. 根据课程设计报告的质量，如有雷同，则所有雷同的所有人均判为不及格。4. 根据答辩的情况，应能够以清晰的思路和准确、简练的语言叙述自己的设计和回答教师的提问六、参考资料1数据结构 （C语言版）严蔚敏、吴伟民 主编 清华大学出版社 2004.112数据结构课程设计案例精编（用C/C+描述），李建学 等 编著，清华大学出版社

4、 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附录：程序代

5、码19参考文献2626 / 26文档可自由编辑打印第一章 需求分析1.1 引言目前，进行快速远距离通信的主要手段是电报，即将需传送的文字转化成由二级制的字符组成的字符串。利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个对应的字符的编码，这就是哈夫曼编码。通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总希望总长度尽可能最短，即采用最短码。因此，哈夫曼树在通信、编码和数

6、据压缩等技术领域有着广泛的应用。此设计说明书是对编码/译码系统开发的一个初步的分析说明性文档，旨在通过该文档清晰的阐述系统的实际功能，方便系统开发人员对系统的理解以及与用户的沟通。文档相关说明部分在目录部分已全部涵盖，阅读此文档的相关人员可以通过目录索引找到相应部分予以阅读。1.2 任务概述Huffman编码和译码根据给定的字符集和各字符的频率值，求出其中给定字符Huffman编码，并针对一段文本（定义在该字符集上）进行编码和译码，实现一个Huffman编码/译码系统。1.3 数据描述该哈夫曼编码/译码系统程序中的数据主要有：哈夫曼树、哈夫曼编码，哈夫曼译码等。1.4 功能需求（1）. 输入模

7、块：输入各个元素，建立哈夫曼树；（2）. 编码模块：将输入的各个元素建立哈夫曼树，进行编码；（3）. 译码模块：将电文以0或1输入后，根据之前的哈夫曼树进行译码；（4）. 输出模块：建立好的哈夫曼树、编码、译码进行输出。1.5 性能需求（1）. 要求该编码/译码系统具有一定的可扩展性以便适应发展，且便于维护；（2）. 要求该编码/译码系统便于使用，使用步骤简易明了。1.6 运行需求基于windows平台下的窗口图形界面软件，运行主界面为windows的经典运行界面，采用多文档界面，从而使程序更加美观，整齐有序，简易操作。软件运行基于windows平台上的xp,Vista,win7等第二章 概要

8、设计2.1 总体设计（一） 设计目的：（1） 掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；（2） 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；（3） 提高综合运用所学的理论知识和方法独立分析和解决问题的能力；（4） 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。主菜单根据输入电文进行译码根据哈夫曼树进行编码输入元素建立哈夫曼树图2.1：程序主体设计图（二） 函数划分该程序有一个主函数和多个子函数，主函数完成对子函数的调用，各子函数实现相应的功能。（1） 结点的开辟。（2） 实现对输入字符串中出现的不同

9、字符及其出现字数的信息记录。（3） 用叶子结点构造赫夫曼树。（4） 获得构造的赫夫曼树中所有叶子结点的元素及其赫夫曼编码。（5） 输出各叶子结点元素及其对应的赫夫曼编码。（6） 输出输入的字符串的赫夫曼编码。（7） 调用各子函数2.2 数据类型设计（或数据结构设计）表2.1：数据类型设计数据数据类型权值整数数据双亲整数数据左孩子整数数据右孩子整数数据struct结构体类型2.3 接口设计表2.1：函数列表函数名函数格式 /即函数首部函数功能structtypedef树结点的结构定义树结点的存储定义HuffmanCreateint创建哈夫曼树Encodingvoid对创建好的哈夫曼树进行编码De

10、codingvoid根据创建好的哈夫曼树进行译码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

11、);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.weight<m1)m2=m1; /令m1为最小权值p2=p1; /p1

12、 为最小权值的位置m1=htk.weight; /m1存放最小权值p1=k;else if(htk.weight<m2)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 编码模块设计根据创建好

13、的哈夫曼树，进行编码：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指双亲位置hcdi=d;printf

14、("输出哈夫曼编码:n");for(i=1;i<=n;i+)printf("%c:",hti.data); /先输出结点for(k=hcdi.start;k<=n;k+) /在输出对应编码printf("%c",hcdi.cdk);printf("n");3.3 译码模块设计根据已有的哈夫曼树和提供的电文，进行译码：void Decoding(HuffNode ht,HuffCode hcd,int n)int f,m,k;DataType c,ch200; /c接收文件,ch存储printf(&quo

15、t;请输入电文(0 or 1),以#结束n");c=getchar();k=1;while(c!='#') /单字符循环输入，以#结束chk=c; /单字符一次存入ch字串中c=getchar();k=k+1; /ch 下地址后移m=k; /标记数组存储末位位置f=2*n-1;k=1;/k 记录电文字符个数printf("输出哈夫曼译码:n");while(k<m) /k循环到数组末尾结束while(htf.left!=0) /直到左孩子结点为零结束if(chk='0') /若接收字符为0，则存为左孩子f=htf.left;i

16、f(chk='1') /若接收字符为1，则存为右孩子f=htf.right;k+; /ch数组下标后移printf("%c",htf.data);f=2*n-1; /每次都从根节点开始查找printf("n");3.4 主函数模块设计主函数的设计：int main(int argc,char*argv)int n,select,flag=FALSE; /flag为零标记第一次选择功能HuffNode ht2*MAXNUM; /定义存放哈夫曼的数组HuffCode hcdMAXNUM; /定义存放编码的数组while(TRUE)printf

17、("n欢迎进入赫夫曼编码译码nn");printf("1.建立哈夫曼树 n");printf("2.编码 n");printf("3.译码 n");printf("4.退出程序 nn");printf("请选择您要实现的功能:(请输入1-4)n");scanf("%d",&select);if(select>=1&&select<=4)if(select!=1&&select!=4&&fl

18、ag=0)printf("请先建立哈夫曼树在选择其他功能!n");continue;flag=TRUE;switch(select) case 1:n=HuffmanCreate(ht);break;case 2:Encoding(ht,hcd,n);break;case 3:Decoding(ht,hcd,n);break;case 4:exit(0);elseprintf("请重新输入!n");return 0;第四章 测试分析4.1 测试程序执行情况图4.1：选择建立哈夫曼树图4.2：输入需建立哈夫曼树的元素个数图4.3：成功建立哈夫曼树图4.4：

19、根据建立好的哈夫曼树，进行编码图4.5：根据建立好的哈夫曼树以及输入的电文，进行译码4.2 出现的问题和解决的方法1. 程序的语句结束后，忘记打分号：程序运行出现错误后，加上分号；2. 输入电文时，误将0和1输成其他数据，结果程序出现将其他数据随机当做0或1。第五章 课程设计总结在课程设计过程中，我们每个人选择一个课题，认真研究，根据课堂教授内容，借助书本，自己动手实践。这样不但有助于我们消化课堂所讲解的内容，还可以增强我们的独立思考能力和动手能力；通过编写实验代码和调试运行，我们可以逐步积累调试C程序的经验并逐渐培养我们的编程能力、用计算机解决实际问题的能力。在课程设计过程中，我们不但有自己

20、的独立思考，还借助各种参考文献来帮助我们完成系统。更为重要的是，我们同学之间加强了交流，在对问题的认识方面可以交换不同的意见。在写代码前，首先，对问题进行了分析，明确了目标，列出了大的框架，然后逐渐细化，划分出不同的功能模块，由具体的子函数去实现，先在纸上编写代码，写好后进行了反复的逻辑推理，发现并解决逻辑问题，然后，上机调试，方法是：一个一个功能模块分开进行调试，主要看调试的模块能否达到预期的结果，这样可以缩小排错的范围，便以纠错和提高编程的效率，当每个功能模块都调试好后，就把各个部分组合起来，再进行调试，主要检查各函数接口是否正确，当达到预期的结果，调试结束，编程部分完成，然后按实验要求完

21、成实验报告。数据结构课程具有比较强的理论性，同时也具有较强的可应用性和实践性。课程设计是一个重要的教学环节。我们在一般情况下都能够重视实验环节，但是容易忽略实验的总结，忽略实验报告的撰写。通过这次实验让我们明白：作为一名大学生必须严格训练分析总结能力、书面表达能力。需要逐步培养书写科学实验报告以及科技论文的能力。只有这样，我们的综合素质才会有好的提高。附录：程序代码#include<stdio.h>#include<malloc.h>#include<limits.h>#include<string.h>#include<stdlib.h&

22、gt;#include<io.h>#include<math.h>#include<process.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR -1#define INFEASIBLE -1typedef char DataType;#define MAXNUM 50typedef struct /huffman 树结点的结构定义DataType data; /数据用字符表示int weight; /权值int parent; /双亲int left; /左孩子int right; /右孩

23、子HuffNode;typedef struct/huffman 树结点的存储定义DataType cdMAXNUM; /存放编码位串int start; /编码起始位置HuffCode;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&

24、quot;,&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.weight<m1)m2=m1;

25、/令m1为最小权值p2=p1; /p1 为最小权值的位置m1=htk.weight; /m1存放最小权值p1=k;else if(htk.weight<m2)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; /返回结

26、点数/编码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指双亲位置hcdi=d;printf(&qu

27、ot;输出哈夫曼编码:n");for(i=1;i<=n;i+)printf("%c:",hti.data); /先输出结点for(k=hcdi.start;k<=n;k+) /在输出对应编码printf("%c",hcdi.cdk);printf("n");/译码void Decoding(HuffNode ht,HuffCode hcd,int n)int f,m,k;DataType c,ch200; /c接收文件,ch存储printf("请输入电文(0 or 1),以#结束n");c=getchar();k=1;while(c!='#') /单字符循环输入，以#结束chk=c; /单字符一次存入ch字串中c=getchar();k=k+1; /ch下地址后移m=k; /标记数组存储末位位置f=2*n-1;k=1; /k记录电文字符个数printf("输出哈夫曼译码:n");while(k<m) /k循环到数组末尾结束while(htf.left!=0) /直到左孩子结点为零结束if(chk='0') /若接收字符为0，则存为左孩子f=htf.lef