数据结构课程设计-哈夫曼编码的实现.doc

陕西理工学院数据结构程序设计数据结构课程设计设计说明书哈夫曼编码的实现学生姓名学号班级成绩指导教师计算机科学与技术系2009年 3 月 2 日数据结构课程设计评阅书题 目哈夫曼编码的实现学生姓名学号指导教师评语及成绩成绩： 教师签名： 年 月 日答辩教师评语及成绩成绩： 教师签名： 年 月 日教研室意见总成绩： 室主任签名： 年 月 日注：指导教师成绩60%，答辩成绩40%，总成绩合成后按五级制记入。 课程设计任务书2008 2009 学年第 一 学期专业： 信息管理与信息系统 学号： 姓名： 课程设计名称： 数据结构课程设计 设计题目： 哈夫曼编码的实现 完成期限：自 2009 年 2 月 23 日至 2009 年 3 月 6 日共 2 周设计依据、要求及主要内容（可另加附页）：利用哈夫曼编码进行信息通讯可以大大提高信道利用率，缩短信息传输时间，降低传输成本。基本要求：l 将权值数据存放在数据文件(文件名为data.txt，位于执行程序的当前目录中)；l 初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；l 编码：利用建好的哈夫曼树生成哈夫曼编码；l 输出编码；设字符集及频度如下表：字符 空格 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 可以根据题目要求把程序划成不同的模块，设计成菜单方式，每次执行一个模块后返回菜单。作出本算法的流程图和主要模块。 指导教师（签字）： 教研室主任（签字）： 批准日期： 年 月 日摘要 针对减少通信系统中字符编码所需要的二进制位长度，提出用于产生不定长的前缀编码算法，所谓前缀编码是指任一编码都不是其他编码的前缀。前缀编码算法的基本事项就是对于出现概率较大的字符采用短编码方式，而出现概率较小的字符采用长编码方式。在网络传输数据过程中个别数据出现的次数特别多，而有些则不怎么出现。如果对数据用同样的长度定义则会造成相当大的浪费，因而需要构建一种可根据数据出现频率生成长度不同但又不会在传输过程中出现混淆的编码。哈夫曼编码就是能完成这项工作的一种编码。而此次设计的哈夫曼树编码器，具有将输入的字符以及权值转换成对应哈夫曼编码的功能。本编码器采用C+作为软件开发环境，采用建立哈夫曼树来实现编码。提供了数据导入并完成编码、输出执行结果即哈夫曼编码这两个功能。关键词：函数；树；哈夫曼；编码；文件目 录1 课题描述12 问题分析和任务定义23 逻辑设计34 详细设计45 程序编码66 程序调试与测试107 结果分析128 总结14参考文献15151 课题描述哈夫曼树，又称最优树，是一类带权路径最短的树。哈夫曼算法能够使得其构造出的二叉树的WPL值最小，从而保证在通信过程中，传输二进制位总长度最短。该算法主要是根据给定的不同字符的出现频率（频次）建立一颗最优二叉树。 由哈夫曼树设计电文总长最短的二进制前缀编码并以n种字符出现的频率作权即为哈夫曼编码。 所设计的哈夫曼编码器，具有从外部文件中读入任意数量的字符和权值（字符和权值的数量要匹配）并能对每个字符输出相应的哈夫曼编码的功能，目的在于将通讯时需要传输的字符通过该编译器转换成相应的二进制代码。利用哈夫曼编码进行信息通讯可以大大提高信道利用率，缩短信息传输时间，降低传输成本。2 问题分析和任务定义 求解n个字符的哈夫曼编码其实就是构建一颗有n个叶子结点的哈夫曼树，首先要确定的是哈夫曼树的结点结构问题。自定义结点结构类型： typedef struct / 结点数据结构 char elem; / 结点信息 int m_weight; / 存放权值 int parent,lchild,rchild; / 双亲结点，左孩子，右孩子 ; 其次，根据哈夫曼树的特点可知，其中没有度为1的结点，所以当一颗哈夫曼树有n个结点时，推出总结点数为2*n-1个，可以用大小为2*n-1的一维数组来储存它。 程序主要算法：使用贪心算法构造最有前缀码的编码。 贪心算法采用的是逐步构造最优解的方法：在当前状态下一旦选定一个分量，就不再重试其他的可行性；它并不从整体最优上作出考虑，它的选择只是在贪心准则下的局部最优选择。3 逻辑设计图 3.1 哈夫曼编码流程图4 详细设计/哈夫曼编码伪代码typedef struct1.2. Elemtype weight; /结点的权值3. Elemtype parent,lchild,rchild; /结点的双亲指针以及左右孩子指针4.HTNode,*哈夫曼Tree; /动态分配数组存储哈夫曼树Typedef char * *哈夫曼Tree; /动态分配数组存储哈夫曼编码表哈夫曼Coding(哈夫曼Tree &HT,哈夫曼Code &HC,Elemtype *f,int n)1. if n=1 then return;2. m2*n-1; /这棵哈夫曼树共有n个结点，所有结点总数为2n-1个3. pHT(哈夫曼Tree)malloc(m+1)*sizeof(HTNode); /0号单元不用4. for i1 to n /初始化，使每一个结点作为一棵独立的二叉树5. do 6. *p*f,0,0,0;7. p+; w+;8. 9. for in+1 to m10. do11. *p0,0,0,0;12. p+;13. 14. for in+1 to m /构造哈夫曼树15. do16. select(HT,i-1,s1,s2); /从HT1,i-1中选择parent为0且权 /值最小的两个结点，其序号分别为s1和s2修改s1和s217. HTs1.parenti; HTs2.parent=i; /结点的双亲指针parent18. HTi.lchilds1; HTi.rchild=s2; /修改i结点的左右孩子的指针19. HTi.weightHTs1.weight+HTs2.weight; /修改结点i的权值20. 21. HC(哈夫曼Code)malloc(n+1)*sizeof(char); /分配n个字符型头指针向量22. cd(char *)malloc(n*sizeof(char); /分配求编码的工作空间23. cdn-1”0”; /编码结束符24. for i1 to n /逐个地求哈夫曼编码25. do26. startn-1; tHTi.parent; cI;27. while c!=0;28. do29. if HTt.lchildc;30. then31. cd-start0; /若是左孩子编为032. 33. else cd-start1; /若是右孩子编为134. ct;35. tHTt.parent;36. 37. HCi(char *)malloc(n-start)*sizeof(char); /为第i个字符分配空间38. strcpy(HCi,&cdstart); /将编码从cd 复制到HC中39. 40. free(cd); /释放空间5 程序编码#include#include#include#include using namespace std;typedef struct /定义结点类型； char elem; int m_weight; int parent,lchild,rchild; HTNode,*HuffmanTree; typedef char* HuffmanCode; typedef struct weight char elem; unsigned int m_weight; Weight;void Select(HuffmanTree HT,int n,int *s1,int *s2) /实现从HuffmanTree串中找出最小 /的两个权值；int i; (*s1)=(*s2)=0; for(i=1;i=n;i+) if(HTi.m_weightHT(*s2).m_weight&HTi.parent=0&(*s2)!=0) if(HTi.m_weightHT(*s1).m_weight) (*s2)=(*s1); (*s1)=i; else (*s2)=i; if(*s1)=0|(*s2)=0)&HTi.parent=0) if(*s1)=0) (*s1)=i; else if(*s2)=0) if(HTi.m_weight(*s2) i=(*s1); (*s1)=(*s2); (*s2)=i; return; void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,Weight *w,int n) /完成Huffman树的编码工作；int i,m,s1,s2,start,c,f; char *cd; if(n=1) return; m=2*n-1; (*HT)=(HuffmanTree)malloc(m+1)*sizeof(HTNode); for(i=1;i=n;+i) (*HT)i.elem=wi-1.elem; (*HT)i.m_weight=wi-1.m_weight; (*HT)i.parent=(*HT)i.lchild=(*HT)i.rchild=0; for(;i=m;+i) (*HT)i.elem=0; (*HT)i.m_weight=(*HT)i.parent=(*HT)i.lchild=(*HT)i.rchild=0; for(i=n+1;i=m;+i) Select(*HT,i-1,&s1,&s2); (*HT)s1.parent=i;(*HT)s2.parent=i; (*HT)i.lchild=s1;(*HT)i.rchild=s2; (*HT)i.m_weight=(*HT)s1.m_weight+(*HT)s2.m_weight; (*HC)=(HuffmanCode)malloc(n*sizeof(char*); cd=(char *)malloc(n*sizeof(char); cdn-1=0; for(i=1;i=n;+i) start=n-1; for(c=i,f=(*HT)i.parent;f!=0;c=f,f=(*HT)f.parent) if(*HT)f.lchild=c) cd-start=0; else cd-start=1; (*HC)i=(char *)malloc(n-start)*sizeof(char); strcpy(*HC)i,&cdstart); void OutputHuffmanCode(HuffmanTree HT,HuffmanCode HC,int n) int i; coutnnumber-element-weight-huffman coden; for(i=1;i=n;i+) couti HTi.elem HTi.m_weight HCi endl; void main() HuffmanTree HT; HuffmanCode HC; Weight *w; string d; int i=0,n=0,flag=0; int temp; char temp1; vector weight; vector elem; char way; ifstream in1(data.txt); ifstream in2(char.txt); coutwhat do you want?endl; while(1) /目录选项； flag=0; cout1.InputHuffmanCode.endl; cout2.OutputHuffmanCodeendl; cout3.Exittemp; weight.push_back(temp); /将读入数据压入权值向量中； while(getline(in2,d) i+; in2temp1; elem.push_back(temp1); if(i=n) w=(Weight *)malloc(n*sizeof(Weight); for(i=0;i=n;i+) wi.elem=elemi; wi.m_weight=weighti; HuffmanCoding(&HT,&HC,w,n);coutendlCompile over!endlendl; flag=1; else cout字符和权值数量不匹配endl; break;case2: /当编译正确是输出结果； if(flag) OutputHuffmanCode(HT,HC,n);break; elsecoutErrorendl;default:return;6 程序调试与测试 本程序采用自底向上实现方式，各个功能采用分块化思想，利用函数之间的参数地址传递达到各功能函数间的消息数据通信。 在调试过程中，同样采用分块化思想，对于每一个功能块临时添加输出语句，以作为中间结果输出，从而了解程序的具体执行过程，并方便发现错误。 程序的执行过程：文件数据读入编码（选择最小权值，生成编码）结果输出。 7 结果分析7.1使用说明 首先选择1 ：完成外部文件数据的读入和编译； 然后选择2 ：输出编译的结果。7.2登陆界面图 7.1 登陆界面7.2编译编码图7.2 编译编码7.3输出结果图 7.3 输出结果7.4错误处理图7.4错误处理7.5算法分析 时间复杂度：O(n); 空间开销 ：8 总结 通过一段时间的设计和实现，程序完成了从外部txt文件内对全部任意数量的字符和权值的读取，并能够将所有的字符和相应的权值求解出对应的哈夫曼编码且给予显示。程序中用到了向量存放字符和权值，实