哈夫曼编码和译码的设计与实现

1、算法与数据结构课程设计哈夫曼编码和译码的设计与实现1 .问题描述利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输时间， 降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码， 在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息 的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站设计一个 哈夫曼码的编/译码系统。2 .基本要求a.编/译码系统应具有以下功能:(1) I :初始化(Initialization )。从终端读入字符集大小 n,以及n个 字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。(2) E：编码(Enco

2、ding)。利用已建好的哈夫曼树(如不在内存，则从文 件hfmTree中读入)，对文件ToBeTran中的正文进行编码，然后将 结果存入文件 CodeFile中。(3) D：译码(Decoding)。利用已建好的哈夫曼树将文件 CodeFile中的代 码进行译码，结果存入文件 TextFile中。(4) P：印代码文件(Print )。将文件CodeFile以紧凑格式显示在终端上， 每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。(5) T:印哈夫曼树(Tree printing )。将已在内存中的哈夫曼树以直观的 方式(树或凹入表形式或广义表)显示在终端上，同时将此字符

3、形 式的哈夫曼树写入文件TreePrint中。b.测试数据(1)利用下面这道题中的数据调试程序。某系统在通信联络中只可能出现八种字符，其概率分别为0.25,0.29,0.07 ,0.08, 0.14, 0.23, 0.03, 0.11 ,试设计哈夫曼编码。(2)用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：THIS PROGRAM IS MY FAVORlTE字符空格 ABCDEFGHI JKLM频度 18664 13 22 32 103 2115 47 57 1532 20字符 N 0P QRSTUVWXYZ频度 57 63 15 1 48 51 80 23

4、 8 18 1 16 13 .需求分析3.1 程序的基本功能本程序可以对任何大小的字符型文件进行 Huffman编码，生成一个编码文件。并可以在程序运行结束后的任意时间对它解码还原生成字符文件。即：先对一条 电文进行输入，并实现Huffman编码，然后对Huffman编码生成的代码用进行译 码，最后输出电文数字3.2 输入/输出形式当进行编码时输入为原字符文件文件名，当程序运行编码完成之后输入编码文件名(默认名为code.dll)。当进行译码时输入为编码文件名(默认名为 code.dll),从文件中读取 Huffman 编码树后输入字符文件的文件名。3.3 测试数据要求本程序中测试数据主要为字

5、符型文件。4 .概要设计1 .系统结构图(功能模块图)哈弗曼树编码译码器2 .功能模块说明(1) .编码：提示要编码的文件文件名一读取文件一以字母出现次数为权值 建立哈弗曼树一对文本进行哈弗曼编码并输出编码一提示将编码保存的文 件名一保存编码文件；(2) .译码：提示输入要译码的文件名一利用建立好的哈弗曼树进行译码一 将译码输出一提示保存译码文件的文件名一保存译码文件；(3) .退出：退出系统，程序运行结束。5 .详细设计创建哈弗曼树编码开始译码6 .调试分析1 .从叶子节点开始向上遍历二叉树，获得哈夫曼编码；2 .根据哈夫曼编码遍历哈夫曼树直到叶子节点，获得译码3 .算法的时间复杂度分析：程

6、序部分用双循环嵌套结构，时间复杂度为O(n2).4 .算法的空间复杂度分析：算法的空间复杂度为 O (n)5 .程序需要反复调试，并且调试过程比较慢，需要有一个比较正确的调试方法，更需要我们有耐心7.用户使用说明1.输入字符的个数n2输入n个字符和n个权值3选择（1-5）操作可对huffman树进行编码和译码以及 huffman树表的打印4退出系统8 .测试结果C:Win-TCprojects4.exeabc10110A .coding please inputBplease inputCB.codeprintingthe process ：the codingu|B.codeprint in

7、gthe process ：C.printC.printthethehutfnanhufF nanD.exitD.exitPC w abB.codeprintingthe process ：C.printthehuffnanD.exitri2336a44550 u000024 e0 0 013leftchild rightchild prentsB.codeprintingC.print thethe process ：hufF nanD.exit武 C;Iin-TCprojects4.exe EXplease input the word and theequal：M 1b 2 c 3 in

8、it suuuvss?.codingB.codeprinting"lease input the process： 2 一 .R.codingB.codeprintingplease input the process：R .,please input the wordsu| abc 他 0 coding B.codeprinting please input the process： B please input the codingu|C.printC.printC.printthethethehuffmanhuffmanhuffmanD.exitD.exitD.exit9 .附

9、录#include "stdio.h"#include "stdlib.h"#include "string.h" #define MAX 100 struct HafNodeint weight;int parent;char ch; int lchild; int rchild;*myHaffTree;struct Coding char bitMAX; char ch; int weight;*myHaffCode;void Haffman(int n)/* 构造哈弗曼树 */ int i,j,x1,x2,s1,s2;for (

10、i=n+1;i<=2*n-1;i+) s1=s2=10000;x1=x2=0;for (j=1；j<=i-1；j+)if(myHaffTreeU.parent=0&&myHaffTreej.weight<s1)s2=s1;x2=x1;s1=myHaffTreej.weight;x1=j；else if(myHaffTreej.parent=0&&myHaffTreej.weight<s2)s2=myHaffTreej.weight;x2=j;myHaffTreex1.parent=i;myHaffTreex2.parent=i;myHaf

11、fTreei.weight=s1+s2;myHaffTreei.lchild=x1;myHaffTreei.rchild=x2;void HaffmanCode(int n)int start,c,f,i,j,k;char*cd;cd=(char *)malloc(n*sizeof(char);myHaffCode=(struct Coding *)malloc(n+1)*sizeof(struct Coding);cdn-1='0'for(i=1;i<=n;+i)start=n-1;for(c=i,f=myHaffTreei.parent;f!=0;c=f,f=myHa

12、ffTreef.parent)if(myHaffTreef.lchild=c) cd-start='0'else cd-start='1'for(j=start,k=0;j<n;j+)myHaffCodei.bitk=cdj;k+;myHaffCodei.ch=myHaffTreei.ch;myHaffCodei.weight=myHaffTreei.weight;free(cd);void print() printf("* *n，,)；printf("* *n");printf("* *n");prin

13、tf("* welcome to huffman coding and codeprinting *n");printf("* *n");printf("* *n");printf("*1.init2.coding3.codeprinting 4.print the huffman5.exitprintf(*n");*n，）；printf("* *n");”*Init()int i,n,m;printf("now initn");printf("please inp

14、ut the number of words:n");scanf("%d",&n);m=2*n-1;myHaffTree=(struct HafNode *)malloc(sizeof(struct HafNode)*(m+1); for(i=1;i<=n;i+)printf("please input the word and the equal:n");scanf("%s%d",&myHaffTreei.ch,&myHaffTreei.weight);myHaffTreei.parent=0

15、;myHaffTreei.lchild=0;myHaffTreei.rchild=0;for(i=n+1;i<=m;i+)myHaffTreei.ch ='#'myHaffTreei.lchild=0;myHaffTreei.parent=0;myHaffTreei.rchild=0;myHaffTreei.weight=0;Haffman(n);HaffmanCode(n);for(i=1;i<=n;i+)printf("%c %d”,myHaffCodei.ch,myHaffCodei.weight); printf("n");pr

16、intf("init success!n");return n;void Caozuo_C(int m)/* 对字符进彳T编码*/int n,i,j;char string50,*p;printf("please input the words： n");scanf("%s",string);n=strlen(string);for(i=1,p=string;i<=n;i+,p+)for(j=1;j<=m;j+)if(myHaffCodej.ch=*p)printf("%sn",myHaffCodej.

17、bit);void Caozuo_D(int n)int i,c;char code1000,*p;printf("please input the coding： n");scanf("%s",code);for(p=code,c=2*n-1;*p!='0'p+)if(*p='0')c=myHaffTreec.lchild;if(myHaffTreec.lchild=0)printf("%c",myHaffTreec.ch);c=2*n-1;continue;else if(*p='1'

18、;)c=myHaffTreec.rchild;if(myHaffTreec.lchild=0)printf("%c",myHaffTreec.ch);c=2*n-1;continue;printf("n");void Caozuo_T(int n)int i;printf("word equal leftchild rightchild prents'n");for(i=1;i<=2*n-1;i+)printf("%c %d %d %d %dn”,myHaffTreei.ch,myHaffTreei.weight,myHaffTreei.lchild,myHaf fTreei.rchild,myHaffTreei.parent);main()int n;char char1;print();n=Init();while(1)printf("A