数据结构课程设计----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.