数据结构课程设计----Huffman树编码和译码.docx

高级语言课程设计题目： 数据结构课程设计 huffman树编码和译码班级学号姓名计092090698刘伟计092090703苏超计093090741纪乐昌 2011年 06 月 29 日北京目录一设计题目二 设计目的三 算法思想分析四 算法描述与实现1)结构定义2)程序算法描述：3)算法的实现方法4)结构框架5)源代码6)运行结果分析五结论一设计题目:题目2：哈夫曼编码和译码问题描述：利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼编/译码系统。基本要求：一个完整的系统应具有以下功能： （1）初始化（initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，(选做：并将它存于文件hfmtree中）。并显示出每个字符的编码。 （2）编码（encoding）。利用已建好的哈夫曼树（选做：如不在内存，则从文件htmtree中读入），对输入的字符串文本（选做：对文件tobetran中的正文）进行编码，（选做：然后将结果存入文件codefile中。）并显示在屏幕上。 （3）译码（decoding）。利用已建好的哈夫曼树将输入的代码进行译码（选做：将文件codefile中的代码进行译码，结果存入文件textfile中。），并显示在屏幕上。 （4）打印哈夫曼树（tree printing）。将已在内存中的哈夫曼树以直观的方式显示在屏幕上。二 设计目的:1了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学 的工作方法和作风。三 算法思想分析:通过c+算法建立一个类huffmnantree，在此类中定义并实现huffman树的建立（createhuffmantree()），编码（encoder()），译码（decoder()），输出等一系列方法。并通过主函数调用类中的各种方法来实现需求。四 算法描述与实现1算法描述： 1）结构定义：2） 程序算法描述：class huffmantree中的算法及类型定义private:huffmannode *node; 即node，用来存放哈夫曼树 int leafnum; 源码个数public: huffmantree(); 构造函数 huffmantree(); 析构函数void createhuffmantree(); 创建并初始化void createhuffmantreefromkeyboard(); 从键盘建立并初始化void createhuffmantreefromfile(); 从文件（hfmtree）中载入void encoder(); 编码（存入codefile.dat）void decoder(); 译码（存入textfile.dat）void printcodefile(); 屏幕显示编码结果void printhuffmantree(); 直观显示huffman树void printhuffmantree_aoru(int t,int layer=1); 凹入法实现直观显示huffman3）算法的实现方法void createhuffmantree()描述： void createhuffmantreefromkeyboard();用了几个for语句实现功能： for1 : 读入哈夫曼树的叶子结点信息. for2 : 循环建立哈夫曼树内部结点。 for:将结点排序 for3 : 产生所有叶子结点中字符的编码。将编码nodei.code 还实现将建立好的哈夫曼树写入文件hfmtree.dat。void huffmantree:createhuffmantreefromfile() 通过文件的读和写实现文件建立huffman树。void huffmantree:encoder()函数功能：为哈夫曼树编码函数。1） 判断是否存在huffman树2） 输入字符串。（从文件导入或键盘输入）3） 编码（通过nodei.code保存huffman编码）4） 将编码存入codefile.dat。void huffmantree:decoder()函数功能：对哈夫曼树进行译码1） 从文件中读入huffman树，建立编码译码转换工具（调用createhuffmantreefromfile()实现）2） 将码文从文件codefile.dat中读入codestr3） 将译码存到文件textfile.dat中void huffmantree:printcodefile()函数功能：从文件中输出哈夫曼树的码文 通过对文件的读取实现。void huffmantree:printhuffmantree()函数功能：从内存或文件中直接输出哈夫曼树调用printhuffmantree_aoru(int t,int layer)和文件的读取实现。void huffmantree:printhuffmantree_aoru(int t,int layer)函数功能：用凹入法输出哈夫曼树并存入treeprint.dat文件。通过判断t是否为空二叉树，用递归算法打印huffman树。4)结构框架： 4） 源代码： #include stdafx.h#include#include#include#include#include#includeusing namespace std;struct huffmannode /哈夫曼树的一个结点 int weight; int parent; int lchild,rchild; char sourcecode; /存放源文字符集里的一个字符，如a std:string code; /存放字符sourcecode对应的编码;class huffmantree /哈夫曼树private: huffmannode *node; /node存放哈夫曼树 int leafnum; /哈夫曼树的叶子个数，也是源码个数public: huffmantree(); huffmantree(); void createhuffmantree(); void createhuffmantreefromkeyboard(); void createhuffmantreefromfile(); void encoder(); void decoder(); void printcodefile(); void printhuffmantree(); void printhuffmantree_aoru(int t,int layer=1); ;/ 构造函数/ 函数功能：初始化哈夫曼树/函数参数：无/参数返回值：无huffmantree:huffmantree() node=null; leafnum=0; / 析构函数/ 函数功能：将哈夫曼的数组的空间释放/函数参数：无/参数返回值：无huffmantree:huffmantree() delete node; / 建立哈夫曼树函数/ 函数功能：建立哈夫曼树（调用键盘建立哈夫曼树或调用从文件建立哈夫曼树的函数）/ 函数参数：无/ 参数返回值：无void huffmantree:createhuffmantree() char choose; coutchoose; if(choose=2) /键盘输入建立哈夫曼树 createhuffmantreefromkeyboard(); /choose=2 else if (choose=1) /从哈夫曼树文件hfmtree.dat中读入信息并建立哈夫曼树 createhuffmantreefromfile(); else printf(您输入的不是或2 .请重新输入！);/ 从键盘建立哈夫曼树函数/ 函数功能：从键盘建立哈夫曼树/函数参数：无/参数返回值：无void huffmantree:createhuffmantreefromkeyboard() int num; coutnum; if (num=1) cout无法建立少于个叶子结点的哈夫曼树。nn; return; leafnum=num; node=new huffmannode2*num-1; /申请*num-1个空间存放结点 for(int i=0;inum;i+) /读入哈夫曼树的叶子结点信息 cout请输入第i+1个字符值; getchar(); nodei.sourcecode=getchar(); /源文的字符存入字符数组 getchar(); coutnodei.weight; /源文的字符权重存入node.weight nodei.parent=-1; /初定义父母及子女 nodei.lchild=-1; nodei.rchild=-1; nodei.code=0; for(int j=num;j2*num-1;j+) /循环建立哈夫曼树内部结点 int pos1,pos2; int max1,max2; pos2=pos1=j; max2=max1=numeric_limits:max( ); /在所有子树的根结点中，选权重最小的两个根结点，pos1最后应指向权重最小的根结点的下标 /pos2最后应指向权重第二小的根结点的下标 /max1存放当前找到的权重最小的根结点的权重 /max2存放当前找到的权重第二小的根结点的权重 for(int k=j-1;k=0;k-) if (nodek.parent=-1)/如果是某棵子树的根结点 if (nodek.weightmax1) /发现比当前最大值还大的权重 max2=max1; max1=nodek.weight; pos2=pos1; pos1=k; else if(nodek.weightmax2) /发现比当前次大值还大的次大权重 max2=nodek.weight; pos2=k; /if (nodej.parent=-1) /for /在下标i处新构造一个哈夫曼树的内部结点，其左、右孩子就是以上pos1、pos2所指向的结点 nodepos1.parent=j; nodepos2.parent=j; nodej.lchild=pos1; nodej.rchild=pos2; nodej.parent=-1; nodej.weight=nodepos1.weight+nodepos2.weight; /for /产生所有叶子结点中字符的编码 for (int m=0;mnum;m+) /产生nodei.sourcecode的编码，存入nodei.code中 int j=m; int j1; while(nodej.parent!=-1) /从叶结点开始往根结点走，每往上走一层，就产生一位编码存入code j1=nodej.parent; if(nodej1.lchild=j) nodem.code.insert(0,0); else nodem.code.insert(0,1); j=j1; cout哈夫曼树已成功构造完成。n; /把建立好的哈夫曼树写入文件hfmtree.dat char ch; coutch; if (ch!=y&ch!=y) return; ofstream fop; fop.open(hfmtree.dat,ios:out|ios:binary|ios:trunc); /打开文件 if(fop.fail() coutn哈夫曼树文件打开失败，无法将哈夫曼树写入hfmtree.dat文件。n; return; fop.write(char*)&num,sizeof(num); /先写入哈夫曼树的叶子结点个数 for(int n=0;n2*num-1;n+) /最后写入哈夫曼树的各个结点（存储在node中） fop.write(char*)&noden,sizeof(noden); flush(cout); fop.close(); /关闭文件 coutn哈夫曼树已成功写入hfmtree.dat文件。n;/ 从文件建立哈夫曼树函数/ 函数功能：从文件建立哈夫曼树/函数参数：无/参数返回值：无void huffmantree:createhuffmantreefromfile() ifstream fip; fip.open(hfmtree.dat,ios:binary|ios:in); if(fip.fail() cout哈夫曼树文件hfmtree.dat打开失败，无法建立哈夫曼树。n; return; fip.read(char*)&leafnum,sizeof(leafnum); if (leafnum=1) cout哈夫曼树文件中的数据有误，叶子结点个数少于个，无法建立哈夫曼树。n; fip.close(); return; node=new huffmannode2*leafnum-1; for(int i=0;i2*leafnum-1;i+) fip.read(char*)&nodei,sizeof(nodei); fip.close(); cout哈夫曼树已从文件成功构造完成。n;/ 编码函数/ 函数功能：为哈夫曼树编码/函数参数：无/参数返回值：无void huffmantree:encoder() if(node=null) /内存没有哈夫曼树，则从哈夫曼树文件hfmtree.dat中读入信息并建立哈夫曼树 createhuffmantreefromfile(); if (leafnum=1) cout内存无哈夫曼树。操作撤销。nn; return; /if char *sourcetext; /字符串数组，用于存放源文 /让用户选择源文是从键盘输入，还是从源文文件tobetran.txt中读入 char choose; coutchoose; if(choose=1) ifstream fip1(tobetran.txt); if(fip1.fail() cout源文文件打开失败!无法继续执行。n; return; char ch; int k=0; while(fip1.get(ch) k+; /第一次读文件只统计文件中有多少个字符，将字符数存入k fip1.close(); sourcetext=new chark+1; /申请存放源文的字符数组空间 ifstream fip2(tobetran.txt); /第二次读源文文件，把内容写入sourcetext k=0; while(fip2.get(ch) sourcetextk+=ch; fip2.close(); sourcetextk=0; else if(choose=2) /从键盘输入源文 string sourcebuff; cin.ignore(); cout请输入需要编码的源文(可输入任意长，按回车键结束):n; getline(cin,sourcebuff,n); int k=0; while(sourcebuffk!=0) k+; sourcetext=new chark+1; k=0; while(sourcebuffk!=0) sourcetextk=sourcebuffk; k+; sourcetextk=0; else printf(您输入的不是或2 .请重新输入！); cout需编码的源文为：; coutsourcetextendl; /开始译码 ofstream fop(codefile.dat,ios:trunc); /打开码文存放文件 int k=0; while(sourcetextk!=0) /源文串中从第一个字符开始逐个编码 int i; for(i=0;ileafnum;i+) /找到当前要编码的源文的字符在哈夫曼树node中的下标 if(nodei.sourcecode=sourcetextk) /将对应编码写入码文文件 fop=leafnum) cout源文中存在不可编码的字符。无法继续执行。nendl; fop.close(); return; k+; /源文串中的字符后移一个 fop.close(); cout已完成编码，码文已写入文件codefile.dat中。nn;/ 译码函数/ 函数功能：对哈夫曼树进行译码/函数参数：无/参数返回值：无void huffmantree:decoder() /如果内存没有哈夫曼树，则从哈夫曼树文件hfmtree.dat中读入信息并建立哈夫曼树 if(node=null) createhuffmantreefromfile(); if (leafnum=1) cout内存无哈夫曼树。操作撤销。nn; return; /将码文从文件codefile.dat中读入codestr ifstream fip1(codefile.dat); if(fip1.fail() cout没有码文，无法译码。n; return; char* codestr; int k=0; char ch; while(fip1.get(ch) k+; fip1.close(); codestr=new chark+1; ifstream fip2(codefile.dat); k=0; while(fip2.get(ch) codestrk+=ch; fip2.close(); codestrk=0; cout经译码得到的源文为：; ofstream fop(textfile.dat); int j=leafnum*2-1-1; /j指向哈夫曼树的根 int i=0; /码文从第一个符号开始，顺着哈夫曼树由根下行，按码文的当前符号决定下行到左孩子还是右孩子 while(codestri!=0) /下行到哈夫曼树的叶子结点处，则译出叶子结点对应的源文字符 if(codestri=0) j=nodej.lchild; else j=nodej.rchild; if(nodej.rchild=-1) /因为哈夫曼树没有度为的结点，所以此条件等同于nodej为叶结点 coutnodej.sourcecode; /屏幕输出译出的一个源文字符 fopnodej.sourcecode; j=leafnum*2-1-1; /j再指向哈夫曼树的根 i+; fop.close(); coutn译码成功且已存到文件textfile.dat中。nn;/ 输出码文函数/ 函数功能：从文件中输出哈夫曼树的码文/函数参数：无/参数返回值：无void huffmantree:printcodefile() char ch; int i=1; ifstream fip(codefile.dat); ofstream fop(codeprin.dat); if(fip.fail() cout没有码文文件，无法显示码文文件内容。n; return; while(fip.get(ch) coutch; fopch; if(i=50) coutendl; fopendl; i=0; i+; coutendl; fopendl; fip.close(); fop.close(); / 输出函数/ 函数功能：从内存或文件中直接输出哈夫曼树/函数参数：无/参数返回值：无void huffmantree:printhuffmantree() /如果内存没有哈夫曼树，则从哈夫曼树文件hfmtree.dat中读入信息并建立哈夫曼树 if(node=null) createhuffmantreefromfile(); if (leafnum=1) cout内存无哈夫曼树。操作撤销。nn; return; ofstream fop(treeprint.dat,ios_base:trunc); fop.close(); printhuffmantree_aoru(2*leafnum-1-1); return;/ 凹入法输出函数/ 函数功能：用凹入法输出哈夫曼树/函数参数：无/参数返回值：无void huffmantree:printhuffmantree_aoru(int t,int layer) /凹入表示法： / 左子树 / 根 / 右子树 if (t!=-1) /如果是非空二叉树 /递归输出左子树 printhuffmantree_aoru(nodet.lchild,layer+1); /输出根 ofstream fop(treeprint.dat,ios_base:app); coutendl; fopendl; for (int i=0;ilayer*5;i+) /按layer输出空格 cout ; fop ; if (nodet.lchild=-1) /叶结点 coutnodet.sourcecodenodet.weight(nodet.