哈夫曼树编码实验报告材料

1、精选优质文档-倾情为你奉上 、数据结构课程设计报告题 目： 哈夫曼编码/译码 学 院 数学与信息科学学院 学科门类 理科 专 业 数学类 学 号 姓 名 田娟 2014年 12 月30日 目 录一、需求分析1 程序的功能·······························

2、3;··················32输入输出的要求······························&

3、#183;···············33测试数据·································&

4、#183;··················3二、概要设计1本程序所用的抽象数据类型的定义···························&#

5、183;···32 主程序模块·············································

6、······33 主模块的流程及各子模块的主要功能·····························44 模块之间的层次关系··········

7、;·································4三、详细设计1采用c语言定义相关的数据类型·············&

8、#183;···················42. 伪码算法·····························

9、;························5四、调试分析1调试中遇到的问题及对问题的解决方法·····················

10、3;·····15五、使用说明及测试结果1.建立哈夫曼树，输入叶子结点个数，权值，字符集··················152.编码···················

11、83;······································153.译码··········

12、83;···············································164.显示码文·&

13、#183;·················································&

14、#183;··165.显示哈夫曼树·············································

15、83;····16六、源程序一、需求分析1程序的功能；哈夫曼编码是一种应用广泛而有效的数据压缩技术。利用哈夫曼编码进行通信可以大大提高信道利用率，加快信息传输速度，降低传输成本。数据压缩的过程称为编码，解压缩的过程称为译码。进行信息传递时，发送端通过一个编码系统对待传数据（明文）预先编码，而接收端将传来的数据（密文）进行译码。2输入输出的要求；：2.1构造哈夫曼树及哈夫曼编码：从终端读入字符集大小n、n个字符以及n个对应的权值，建立哈夫曼树；利用已经建好的哈夫曼树求每个叶结点的哈夫曼编码，并保存。2.2编码：利用已构造的哈夫曼编码对“明文”文件中的正文进

16、行编码，然后将结果存入“密文”文件中。2.3译码：将“密文”文件中的0、1代码序列进行译码。2.4打印“密文”文件：将文件以紧凑格式显示在终端上，每行30个代码；同时，将此字符形式的编码文件保存。2.5打印哈夫曼树及哈夫曼编码：将已在内存中的哈夫曼树以凹入表形式显示在终端上，同时将每个字符的哈夫曼编码显示出来；并保存到文件。3测试数据。3.1.令叶子结点个数N为4，权值集合为1,3,5,7，字符集合为A,B,C,D，且字符集与权值集合一一对应。3.2.请自行选定一段英文文本，统计给出的字符集，实际统计字符的频度，建立哈夫曼树，构造哈夫曼编码，并实现其编码和译码。二、概要设计1本程序所用的抽象数

17、据类型的定义；class HuffmanTree /哈夫曼树private: HuffmanNode *Node; /Node存放哈夫曼树 int LeafNum; /哈夫曼树的叶子个数，也是源码个数2.主程序模块main()2.2 建立哈夫曼树函数/ 函数功能：建立哈夫曼树void HuffmanTree:CreateHuffmanTree() 2.3 函数功能：为哈夫曼树编码void HuffmanTree:Encoder()2.4 函数功能：对哈夫曼树进行译码void HuffmanTree:Decoder()2.5输出码文函数/ 函数功能：从文件中输出哈夫曼树的码文void Huffm

18、anTree:PrintCodeFile()2.6 函数功能：用凹入法输出哈夫曼树void HuffmanTree:PrintHuffmanTree_aoru(int T,int layer)3主模块的流程及各子模块的主要功能；哈夫曼编码/译码系统 显示哈夫曼树建立哈夫曼树显示哈夫曼树编码 显示码文译码 基本功能分析4模块之间的层次关系。 初始化：从键盘接收字符集大小n，以及n个字符和n个权值。 建立哈夫曼树：构造哈夫曼树，即将HNode数组中的各个位置的各个域都添上相关的值，并将这个结构体数组存于文件HTree.txt中。 构造哈夫曼编码：为从文件HTree.txt中读入相关的字符信息进行哈

19、夫曼编码，然后将结果存入HNode.txt中，同时将字符与0、1代码串的一一对应关系打印到屏幕上。 编码：利用已构造的哈夫曼编码（HNode.txt）对文件SourceFile.txt（明文）中的正文进行编码，然后将结果存入文件CodeFile.txt（密文）中。 译码：将文件CodeFile.txt（密文）中的代码按照中建立的编码规则将其翻译成字符集中字符所组成的字符串形式，进行译码，结果存入文件TextFile.txt（明文）中。（如果正确，TextFile.txt的内容与SourceFile.txt的内容一致） 显示哈夫曼树：从HNode数组中读入相关的结点信息，以凹入表方式将各个结点以

20、及叶子结点的权值和左分支上的0和右分支上的三、详细设计1采用c语言定义相关的数据类型；结点的类型定义描述如下：struct HuffmanNode /哈夫曼树的一个结点 int weight; int parent; int lchild,rchild; char sourcecode; std:string code; ;class HuffmanTree /哈夫曼树private: HuffmanNode *Node; /Node存放哈夫曼树 int LeafNum; 2. 伪码算法public: HuffmanTree(); HuffmanTree(); void CreateHuffm

21、anTree(); 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; / 函数功能：将哈夫曼的数组的空间释放/参数返

22、回值：无HuffmanTree:HuffmanTree() delete Node; / 建立哈夫曼树函数/ 函数功能：建立哈夫曼树void HuffmanTree:CreateHuffmanTree() char Choose; cout<<"从键盘输入哈夫曼树(按2)？" cin>>Choose; if(Choose='2') CreateHuffmanTreeFromKeyboard(); /choose='2' else /从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树 CreateHuffman

23、TreeFromFile(); / 函数功能：从键盘建立哈夫曼树void HuffmanTree:CreateHuffmanTreeFromKeyboard() int Num; cout<<"n请输入源码字符集个数：" cin>>Num; if (Num<=1) cout<<"无法建立少于2个叶子结点的哈夫曼树。nn" return; LeafNum=Num; Node=new HuffmanNode2*Num-1; for(int i=0;i<Num;i+) /读入哈夫曼树的叶子结点信息 cout<

24、;<"请输入第"<<i+1<<"个字符值" getchar(); Nodei.sourcecode=getchar(); /源文的字符存入字符数组Info getchar(); cout<<"请输入该字符的权值" cin>>Nodei.weight; /源文的字符权重存入Node.weight Nodei.parent=-1; Nodei.lchild=-1; Nodei.rchild=-1; Nodei.code="0" for(int j=Num;j<

25、2*Num-1;j+) /循环建立哈夫曼树内部结点 int pos1,pos2; int max1,max2; pos2=pos1=j; max2=max1=numeric_limits<int>:max( ); /在所有子树的根结点中，选权重最小的两个根结点，pos1最后应指向权重最小的根结点的下标for(int k=j-1;k>=0;k-) if (Nodek.parent=-1)/如果是某棵子树的根结点 if (Nodek.weight<max1) /发现比当前最大值还大的权重 max2=max1; max1=Nodek.weight; pos2=pos1; po

26、s1=k; else if(Nodek.weight<max2) /发现比当前次大值还大的次大权重 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 /产生

27、所有叶子结点中字符的编码 for (int m=0;m<Num;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<<"哈夫曼树已成功构造完成

28、。n" char ch; cout<<"是否要替换原来的哈夫曼树文件(Y/N):" cin>>ch; if (ch!='y'&&ch!='Y') return; ofstream fop; fop.open("hfmTree.dat",ios:out|ios:binary|ios:trunc); /打开文件 if(fop.fail() cout<<"n哈夫曼树文件打开失败，无法将哈夫曼树写入hfmTree.dat文件。n" return; f

29、op.write(char*)&Num,sizeof(Num); /先写入哈夫曼树的叶子结点个数 for(int n=0;n<2*Num-1;n+) /最后写入哈夫曼树的各个结点（存储在Node中） fop.write(char*)&Noden,sizeof(Noden); flush(cout); fop.close(); /关闭文件 cout<<"n哈夫曼树已成功写入hfmTree.dat文件。n"/ 从文件建立哈夫曼树函数/ 函数功能：从文件建立哈夫曼树void HuffmanTree:CreateHuffmanTreeFromFil

30、e() 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<<"哈夫曼树文件中的数据有误，叶子结点个数少于2个，无法建立哈夫曼树。n" fip.close(); return; Node=n

31、ew HuffmanNode2*LeafNum-1; for(int i=0;i<2*LeafNum-1;i+) fip.read(char*)&Nodei,sizeof(Nodei); fip.close(); cout<<"哈夫曼树已从文件成功构造完成。n"/ 编码函数/ 函数功能：为哈夫曼树编码void HuffmanTree:Encoder() if(Node=NULL) /内存没有哈夫曼树，则从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树 CreateHuffmanTreeFromFile(); if (LeafNum<

32、;=1) cout<<"内存无哈夫曼树。操作撤销。nn" return; /if char *SourceText; /让用户选择源文是从键盘输入，还是从源文文件ToBeTran.txt中读入 char Choose; cout<<"从键盘输入源文(按2)？" cin>>Choose; if(Choose='1') ifstream fip1("ToBeTran.txt"); if(fip1.fail() cout<<"源文文件打开失败!无法继续执行。n&quo

33、t; return; char ch; int k=0; while(fip1.get(ch) k+; fip1.close(); SourceText=new chark+1; ifstream fip2("ToBeTran.txt"); k=0; while(fip2.get(ch) SourceTextk+=ch; fip2.close(); SourceTextk='0' else string SourceBuff; cin.ignore(); cout<<"请输入需要编码的源文(按回车键结束):n" getline

34、(cin,SourceBuff,'n'); int k=0; while(SourceBuffk!='0') k+; SourceText=new chark+1; k=0; while(SourceBuffk!='0') SourceTextk=SourceBuffk; k+; SourceTextk='0' cout<<"需编码的源文为：" cout<<SourceText<<endl; ofstream fop("CodeFile.dat",ios:

35、trunc); /打开码文存放文件 int k=0; while(SourceTextk!='0') /源文串中从第一个字符开始逐个编码 int i; for(i=0;i<LeafNum;i+) /找到当前要编码的源文的字符在哈夫曼树Node中的下标 if(Nodei.sourcecode=SourceTextk) /将对应编码写入码文文件 fop<<Nodei.code; break; ; if (i>=LeafNum) cout<<"源文中存在不可编码的字符。无法继续执行。n"<<endl; fop.clo

36、se(); return; k+; fop.close(); cout<<"已完成编码，码文已写入文件CodeFile.dat中。nn"/ 函数功能：对哈夫曼树进行译码void HuffmanTree:Decoder()/如果内存没有哈夫曼树，则从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树 if(Node=NULL) CreateHuffmanTreeFromFile(); if (LeafNum<=1) cout<<"内存无哈夫曼树。操作撤销。nn" return; ifstream fip1("

37、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<<&quo

38、t;经译码得到的源文为：" ofstream fop("TextFile.dat"); int j=LeafNum*2-1-1; int i=0; while(CodeStri!='0') /下行到哈夫曼树的叶子结点处，则译出叶子结点对应的源文字符 if(CodeStri='0') j=Nodej.lchild; else j=Nodej.rchild; if(Nodej.rchild=-1) /因为哈夫曼树没有度为1的结点，所以此条件等同于Nodej为叶结点 cout<<Nodej.sourcecode; fop<

39、;<Nodej.sourcecode; j=LeafNum*2-1-1; i+; fop.close(); cout<<"n译码成功且已存到文件TextFile.dat中。nn"/ 输出码文函数/ 函数功能：从文件中输出哈夫曼树的码文void HuffmanTree:PrintCodeFile() char ch; int i=1; ifstream fip("CodeFile.dat"); ofstream fop("CodePrin.dat"); if(fip.fail() cout<<"没

40、有码文文件，无法显示码文文件内容。n" return; while(fip.get(ch) cout<<ch; fop<<ch; if(i=50) cout<<endl; fop<<endl; i=0; i+; cout<<endl; fop<<endl; fip.close(); fop.close(); / 输出函数/ 函数功能：从内存或文件中直接输出哈夫曼树void HuffmanTree:PrintHuffmanTree() if(Node=NULL) CreateHuffmanTreeFromFile(

41、); 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);cout<<e