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

课程设计课程名称__数据结构课程设计_题目名称_哈夫曼编码译码器_学生学院专业班级学号学生姓名指导教师2011年12月23日1摘要：在当今信息爆炸时代，如何采用有效的数据压缩技术来节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总希望总长度尽可能最短，即采用最短码。关键字：哈夫曼树编码解码数据压缩技术2目录摘要：.........................................................................................................1关键字：.....................................................................................................1第一章需求分析......................................................................................3第二章数据结构定义及其操作实现......................................................3第三章程序设计及其实现......................................................................33.1从文件读入原文...........................................................................33.2统计原文中各字符的权值.........................................................43.3编码..............................................................................................53.4解码............................................................................................63.5主函数............................................................................................7第四章运行结果及其分析......................................................................8第五章问题及其解决方法....................................................................10第六章心得体会（设计总结）............................................................10附录——源程序......................................................................................111、头文件.........................................................................................112、赫夫曼编码算法........................................................................123、主函数.........................................................................................18参考文献......................................................................................213第一章需求分析1．问题要求：打开一篇英文文章，统计出每个字符出现的次数，然后以他们为权值，对每个字符进行编码，编码完成后对其编码进行译码。2．程序运行环境：windows、visualc++或java等3．要求：a)输入一篇英文文章，根据字符出现的次数给出哈夫曼编码方式。b)对英文文章进行编码；c)对编码进行译码核对正确性第二章数据结构定义及其操作实现2.1哈弗曼树节点typedefstruct{unsignedintweight;unsignedintparent;unsignedintlchild;unsignedintrchild;}HuffTreeNode,*HuffTree;2.2字符-权值-编码映射typedefstruct{charc;unsignedintweight;char*code;}CharMapNode,*CharMap;第三章程序设计及其实现3.1从文件读入原文voidHuffman::ReadTextFromFile(char*filename){4ifstreaminfile(filename);if(!infile){cerr无法打开文件！endl;return;}charc;while(infile.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].weight;5break;}}if(jn)//该字符不存在，添加该字符{++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号单元未使用//初始化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)6{ints1,s2;select(i-1,s1,s2);huffTree[s1].parent=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再加上'\0'）cd[n-1]='\0';//编码结束符for(i=1;i=n;++i)//逐个字符求哈弗曼编码{intstart=n-1;intc,f;//从叶子到根逆向求编码for(c=i,f=huffTree[i].parent;f!=0;c=f,f=huffTree[f].parent){if(huffTree[f].lchild==c)//左孩子编码为0cd[--start]='0';else//右孩子编码为1cd[--start]='1';}chars[i].code=newchar[n-start];//为第i个字符编码分配空间strcpy(chars[i].code,&cd[start]);}deletecd;}3.4解码voidHuffman::Decode(){text=;string::size_typei,count;for(i=0;icode.size();i+=count){//每个字符的编码结果最长n-1，从1至n-1依次尝试for(count=1;countn;++count){for(intj=1;j=n;++j)if(code.substr(i,count)==chars[j].code){7text+=chars[j].c;gotonext;}}next:;}}3.5主函数intmain(){cout************************************************************endl;cout**endl;cout*哈夫曼编码译码器*endl;cout*1、打开一篇英文文章或输入一篇文章*endl;cout*2、根据字符出现的次数以他们为权值给出哈夫曼编码方式*endl;cout*3、对英文文章进行编码*endl;cout*4、对编码进行译码核对正确性*endl;cout**endl;cout************************************************************endlendl;system(pause);coutendl;Huffmanhuffman;huffman.ReadTextFromFile(text.txt);cout程序自动统计字符和权值endl;huffman.CountCharsWeight();coutendl;cout字符及对应权值：endl;huffman.PrintCharWeight();coutendl;system(pause);8coutendl;huffman.MakeCharMap();cout字符及对应编码：endl;huffman.PrintCharCode();coutendl;system(pause);coutendl;cout对原文进行编码：endl;cout原文：endl;huffman.PrintText();huffman.Encode();coutendl;cout编码：endl;huffman.PrintCode();huffman.SaveCodeToFile(code.txt);coutendl;system(pause);coutendl;cout对编码进行解码：endl;huffman.ReadCodeFromFile(code.txt);cout编码：endl;huffman.PrintCode();huffman.Decode();coutendl;cout原文：endl;hu