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

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

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

3、ct 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(filename);if(!infile)ce

4、rr 无法打开文件！ 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;for (j = 1; j n)/该字符不存

5、在，添加该字符+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号单元未使用/初始化int i;for (i = 1;

6、 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, s2);huffTrees1.parent =

7、 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;/从叶子到根逆向求编码for (c = i, f = huf

8、fTreei.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; i code.size(); i += co

9、unt)/每个字符的编码结果最长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、根据字符出现的次数以他们为权值给出哈夫曼编码方式 * endl;

10、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;system(pause);cout endl;hu

11、ffman.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;huf

12、fman.ReadCodeFromFile(code.txt);cout 编码： endl;huffman.PrintCode();huffman.Decode();cout endl;cout 原文： endl;huffman.PrintText();huffman.SaveTextToFile(resulttext.txt);cout 1000#include /*数据结构*/哈弗曼树节点typedef struct unsigned int weight;unsigned int parent;unsigned int lchild;unsigned int rchild;HuffTre

13、eNode,*HuffTree;/字符-权值-编码映射typedef structchar c;unsigned int weight;char *code;CharMapNode,*CharMap;/*类定义*/class Huffman private:void select(int n, int &s1, int &s2);HuffTree huffTree;/哈弗曼树CharMap chars;/字符表int n;/字符数std:string text;/原文std:string code;/编码public:void InputCharsWeight();void CountChar

14、sWeight();void Decode();void ReadTextFromFile(char *filename);void ReadCodeFromFile(char *filename);void SaveTextToFile(char *filename);void SaveCodeToFile(char *filename);void PrintCode();void MakeCharMap();void PrintText();void PrintCharCode();void PrintCharWeight();void SetCharMap(CharMap m, int

15、number);void Encode();Huffman();virtual Huffman();2、 赫夫曼编码算法/ Huffman.cpp#include Huffman.h#include #include using namespace std;Huffman:Huffman()huffTree = NULL;chars = NULL;n = 0;Huffman:Huffman()void Huffman:Encode()code = ;for (string:size_type i = 0; i != text.size(); +i)for (int j = 1; j = n;

16、+j)if (charsj.c = texti)code += charsj.code;void Huffman:SetCharMap(CharMap m, int number)chars = m;n = number;void Huffman:select(int n, int &s1, int &s2)s1 = s2 = 0;for (int i = 1; i = n; +i)if (huffTreei.parent != 0)continue;if (s1 = 0)s1 = i;else if (s2 = 0)if (huffTreei.weight huffTrees1.weight

17、)s2 = s1;s1 = i;elses2 = i;elseif (huffTreei.weight huffTrees1.weight)s2 = s1;s1 = i;else if (huffTreei.weight huffTrees2.weight)s2 = i;void Huffman:PrintCharWeight()for (int i = 1; i = n; +i)switch (charsi.c)case t:cout t;break;case n:cout n;break;default:cout charsi.c;break;cout charsi.weight endl

18、;void Huffman:PrintCharCode()for (int i = 1; i = n; +i)switch (charsi.c)case t:cout t;break;case n:cout n;break;default:cout charsi.c;break;cout charsi.code endl;void Huffman:PrintText()cout text endl;void Huffman:PrintCode()cout code endl;void Huffman:MakeCharMap()if (n = 1)return;int m = 2 * n - 1

19、;huffTree = new HuffTreeNodem+1;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,s

20、2;select(i - 1, s1, s2);huffTrees1.parent = huffTrees2.parent = i;huffTreei.lchild = s1;huffTreei.rchild = s2;huffTreei.weight = huffTrees1.weight + huffTrees2.weight;char *cd = new charn;cdn-1 = 0;for(i = 1; i = n; +i)int start = n - 1;int c,f;for (c = i, f = huffTreei.parent; f != 0; c = f, f = hu

21、ffTreef.parent)if (huffTreef.lchild = c)cd-start = 0;elsecd-start = 1;charsi.code = new charn - start;strcpy(charsi.code,&cdstart);delete cd;void Huffman:ReadTextFromFile(char *filename)ifstream infile(filename);if(!infile)cerr 无法打开文件！ endl;return;char c;while(infile.get(c)text += c;void Huffman:Sav

22、eCodeToFile(char *filename)ofstream outfile(filename);if (!outfile)cerr 保存文件出错！ endl;return;outfile code;void Huffman:ReadCodeFromFile(char *filename)ifstream infile(filename);if (!infile)cerr 无法打开文件！ code;void Huffman:Decode()text = ;string:size_type i,count;for (i = 0; i code.size(); i += count)fo

23、r (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:;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

24、= 1; i != text.size(); +i)int j;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;void Huffman:SaveTextToFile(char *filename)ofstream outfile(filename);if (!outfile)cerr 保存文件出错！ endl;return;outfile text;3、 主函数/main.cpp#include #include Huffman.husing namespace std;int main()cout * endl;cout * * endl;cout * 哈夫曼编码译码器 * endl;cout * 1、打开一篇英文文章或输入一篇文章 * endl;cout * 2、根据字符出现的次数以他们为权值给出哈夫曼编码方式 * endl;cout * 3、对英文文章进行编码 * endl;cout * 4、对编码进行译码核对正确性 * e