数据结构课程设计-哈夫曼编码译码器

《数据结构课程设计-哈夫曼编码译码器》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课程设计课程名称__数据结构课程设计_题目名称_哈夫曼编码译码器_学生学院专业班级学号学生姓名指导教师2011年12月23日21摘要：在当今信息爆炸时代，如何采用有效的数据压缩技术来节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总希望总长度尽可能最短，即采用最短码。关键字：哈夫曼树编码解码数据压缩技术21目录摘要：1关键字：1第一章需求分析3第二章数据结构定义及其操作实现3第三章程序设计及其实现33.1从文件读入原文33.2统计原文中各字符的权值43.3编码53.4解码63.5主函数7第四章运行结果及其分析8第五章

2、问题及其解决方法10第六章心得体会（设计总结）10附录——源程序111、头文件112、赫夫曼编码算法123、主函数18参考文献2121第一章需求分析1．问题要求：打开一篇英文文章，统计出每个字符出现的次数，然后以他们为权值，对每个字符进行编码，编码完成后对其编码进行译码。2．程序运行环境：windows、visualc++或java等3．要求：a)输入一篇英文文章，根据字符出现的次数给出哈夫曼编码方式。b)对英文文章进行编码；c)对编码进行译码核对正确性第二章数据结构定义及其操作实现2.1哈弗曼树节点typedefstruct{unsignedintweight;unsignedintpare

3、nt;unsignedintlchild;unsignedintrchild;}HuffTreeNode,*HuffTree;2.2字符-权值-编码映射typedefstruct{charc;unsignedintweight;char*code;}CharMapNode,*CharMap;第三章程序设计及其实现3.1从文件读入原文voidHuffman::ReadTextFromFile(char*filename){21ifstreaminfile(filename);if(!infile){cerr<<"无法打开文件！"<

4、get(c)){text+=c;}}3.2统计原文中各字符的权值voidHuffman::CountCharsWeight(){if(text.empty())return;if(chars!=NULL)deletechars;inti=0;n=0;chars=newCharMapNode[2];chars[1].c=text[i];chars[1].weight=1;++n;for(i=1;i!=text.size();++i){intj;for(j=1;j<=n;++j)//遍历当前字符表，如果已存在该字符，权值+1{if(text[i]==chars[j].c){++chars[j].w

5、eight;21break;}}if(j>n)//该字符不存在，添加该字符{++n;CharMapnewchars=newCharMapNode[n+1];memcpy(newchars,chars,n*sizeof(CharMapNode));deletechars;chars=newchars;chars[n].c=text[i];chars[n].weight=1;}}}3.3编码voidHuffman::MakeCharMap(){if(n<=1)return;intm=2*n-1;//哈弗曼树所需节点数huffTree=newHuffTreeNode[m+1];//0号单元未使用//

6、初始化inti;for(i=1;i<=n;++i){huffTree[i].weight=chars[i].weight;huffTree[i].parent=0;huffTree[i].lchild=0;huffTree[i].rchild=0;}for(i=n+1;i<=m;++i){huffTree[i].weight=0;huffTree[i].parent=0;huffTree[i].lchild=0;huffTree[i].rchild=0;}//建哈弗曼树for(i=n+1;i<=m;++i)21{ints1,s2;select(i-1,s1,s2);huffTree[s1].p

7、arent=huffTree[s2].parent=i;huffTree[i].lchild=s1;huffTree[i].rchild=s2;huffTree[i].weight=huffTree[s1].weight+huffTree[s2].weight;}//从叶子到根节点逆向求每个字符的哈弗曼编码char*cd=newchar[n];//分配求编码的工作空间（每个字符编码结果最长n-1再