《数据结构课程设计哈夫曼编码译码器》由会员分享，可在线阅读，更多相关《数据结构课程设计哈夫曼编码译码器（15页珍藏版）》请在金锄头文库上搜索。
1、精品文档，仅供学习与交流，如有侵权请联系网站删除课 程 设 计课程名称_ _数据结构课程设计_ 题目名称_ 哈夫曼编码译码器_ 学生学院 专业班级 学 号 学生姓名 指导教师 2011 年 12月 23日摘要：在当今信息爆炸时代，如何采用有效的数据压缩技术来节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总希望总长度尽可能最短，即采用最短码。关键字：哈夫曼树 编码 解码 数据压缩技术目 录摘要：1关键字：1第一章 需求分析3第二章 数据结构定义及其操作实现3第三章 程序设计及其实现33.1 从文件读入原文33.2 统
2、计原文中各字符的权值43.3 编码53.4 解码63.5 主函数7第四章 运行结果及其分析8第五章 问题及其解决方法10第六章 心得体会（设计总结）10附录源程序111、 头文件112、 赫夫曼编码算法123、 主函数18参 考 文 献21第一章 需求分析1问题要求：打开一篇英文文章，统计出每个字符出现的次数，然后以他们为权值，对每个字符进行编码，编码完成后对其编码进行译码。2 程序运行环境：windows、visual c+或java等3 要求：a) 输入一篇英文文章，根据字符出现的次数给出哈夫曼编码方式。b) 对英文文章进行编码；c) 对编码进行译码核对正确性第二章 数据结构定义及其操作实
3、现2.1 哈弗曼树节点typedef struct unsigned int weight;unsigned int parent;unsigned int lchild;unsigned int rchild;HuffTreeNode,*HuffTree;2.2 字符-权值-编码映射typedef structchar c;unsigned int weight;char *code;CharMapNode,*CharMap;第三章 程序设计及其实现3.1 从文件读入原文void Huffman:ReadTextFromFile(char *filename)ifstream infile(
4、filename);if(!infile)cerr 无法打开文件！ endl;return;char c;while(infile.get(c)text += c;3.2 统计原文中各字符的权值void Huffman:CountCharsWeight()if (text.empty()return;if (chars != NULL)delete chars;int i = 0;n = 0;chars = new CharMapNode2;chars1.c = texti;chars1.weight = 1;+n;for (i = 1; i != text.size(); +i)int j;
5、for (j = 1; j n)/该字符不存在，添加该字符+n;CharMap newchars = new CharMapNoden + 1;memcpy(newchars, chars, n * sizeof(CharMapNode);delete chars;chars = newchars;charsn.c = texti;charsn.weight = 1;3.3 编码void Huffman:MakeCharMap()if (n = 1)return;int m = 2 * n - 1;/哈弗曼树所需节点数huffTree = new HuffTreeNodem+1;/0号单元未使
6、用/初始化int i;for (i = 1; i = n; +i)huffTreei.weight = charsi.weight;huffTreei.parent = 0;huffTreei.lchild = 0;huffTreei.rchild = 0;for (i = n + 1; i = m; +i)huffTreei.weight = 0;huffTreei.parent = 0;huffTreei.lchild = 0;huffTreei.rchild = 0;/建哈弗曼树for (i = n + 1; i = m; +i)int s1,s2;select(i - 1, s1, s
7、2);huffTrees1.parent = huffTrees2.parent = i;huffTreei.lchild = s1;huffTreei.rchild = s2;huffTreei.weight = huffTrees1.weight + huffTrees2.weight;/从叶子到根节点逆向求每个字符的哈弗曼编码char *cd = new charn;/分配求编码的工作空间（每个字符编码结果最长n-1再加上0）cdn-1 = 0;/编码结束符for(i = 1; i = n; +i)/逐个字符求哈弗曼编码int start = n - 1;int c,f;/从叶子到根逆向
8、求编码for (c = i, f = huffTreei.parent; f != 0; c = f, f = huffTreef.parent)if (huffTreef.lchild = c)/左孩子编码为0cd-start = 0;else/右孩子编码为1cd-start = 1;charsi.code = new charn - start;/为第i个字符编码分配空间strcpy(charsi.code,&cdstart);delete cd;3.4 解码void Huffman:Decode()text = ;string:size_type i,count;for (i = 0;
9、i code.size(); i += count)/每个字符的编码结果最长n-1，从1至n-1依次尝试for (count = 1; count n; +count)for (int j = 1; j = n; +j)if (code.substr(i, count) = charsj.code)text += charsj.c;goto next;next:3.5 主函数int main()cout * endl;cout * * endl;cout * 哈夫曼编码译码器 * endl;cout * 1、打开一篇英文文章或输入一篇文章 * endl;cout * 2、根据字符出现的次数以他
10、们为权值给出哈夫曼编码方式 * endl;cout * 3、对英文文章进行编码 * endl;cout * 4、对编码进行译码核对正确性 * endl;cout * * endl;cout * endlendl;system(pause);cout endl;Huffman huffman;huffman.ReadTextFromFile(text.txt);cout 程序自动统计字符和权值 endl;huffman.CountCharsWeight();cout endl;cout 字符及对应权值： endl;huffman.PrintCharWeight();cout endl;syste
11、m(pause);cout endl;huffman.MakeCharMap();cout 字符及对应编码： endl;huffman.PrintCharCode();cout endl;system(pause);cout endl;cout 对原文进行编码： endl;cout 原文： endl;huffman.PrintText();huffman.Encode();cout endl;cout 编码： endl;huffman.PrintCode();huffman.SaveCodeToFile(code.txt);cout endl;system(pause);cout endl;cout 对编码进行解码： endl;huffman.ReadCodeFromFile(code.txt);cout 编码： endl;huffman.PrintCode();
